declare

      procedure Process_Car (C : Car; OK : out Boolean);

      procedure Process_Fleet
        is new Abstract_Car_Containers.Visit (Process_Car);

      procedure Process_Car (C : Car; OK : out Boolean) is
      begin

         OK := True;  --  unless you want the iteration to stop early

         --  do something with C

      end Process_Car;

      It : Abstract_Car_Containers.Iterator'Class
        := Fleets.New_Iterator (The_Fleet);

   begin

      Process_Fleet (It);

   end;

This example uses the generic Visit, which takes the element to be processed as an in parameter. As well as this, there's the generic Modify, which takes the element as an in out parameter.

Both Visit and Modify come in three flavours:

• plain
• with an additional in parameter
• with an additional in out parameter.

See BC.Containers for details.

Selection

Suppose you want to find all the Cars in our Fleet that were registered before some date. You could imagine a function Registered_Before:

   function Registered_Before
     (Date : Ada.Calendar.Time) return Fleets.Collection;

   function Registered_Before
     (Date : Ada.Calendar.Time) return Fleets.Collection is

      function Wanted (C : Car) return Boolean;

      procedure Choose is new BC.Filter
        (Item => Car,
         Source => Abstract_Car_Containers,
         From => Fleets.Collection,
         Target => Abstract_Car_Containers,
         To => Fleets.Collection,
         Pass => Wanted,
         Clear => Fleets.Clear,
         Add => Fleets.Append);

      function Wanted (C : Car) return Boolean is
         use type Ada.Calendar.Time;
      begin
         return C.Registered < Date;
      end Wanted;

      Result : Fleets.Collection;

   begin
      Choose (The_Fleet, Result);
      return Result;
   end Registered_Before;

The tricky bit is the instantiation of BC.Filter (which, of course, you have to with):

Item

is the thing you're filtering (Car),

Source

is an instantion of BC.Containers with Items,

From

is the concrete Container type which contains the Items to be filtered; it has to have beeen derived from the abstract Container in Source,

Target

is a (possibly different) instantion of BC.Containers with Items,

To

is the concrete Container type which is to receive the Items when they have been filtered; it has to have been derived from the abstract Container in Target, and may or may not be the same as From,

Pass

is a function which takes an Item and returns True if it's to be kept. In this case, this is Wanted,

Clear

is a procedure which empties a To Container,

Add

is a procedure which adds an Item to a To Container.

Sorting

Suppose you want to keep your Fleet sorted (earliest first). You need

  procedure Sort;

   procedure Sort is

      function Earlier (L, R : Car) return Boolean;

      procedure Sort is new Abstract_Car_Containers.Quicksort
        ("<" => Earlier,
         Container => Fleets.Collection,
         Length => Fleets.Length);

      function Earlier (L, R : Car) return Boolean is
         use type Ada.Calendar.Time;
      begin
         return L.Registered < R.Registered;
      end Earlier;

   begin
      Sort (The_Fleet);
   end Sort;

As an alternative to Quicksort you can use BC.Containers.Shellsort; the quicksort is (usually) quicker but uses recursion, so may take more stack space.

What other Components might be useful?

Maps

If you had a lot of Cars to deal with, you might want a quick-access Container to implement Fleet rather than the general-purpose Collection.

Quick-access? since all Plates are unique (at any one instant, anyway. Let's not worry about transferring Plates between Cars!) you can treat Plate as a unique Key to allow you to find the Car given the Plate. The Booch Container that does this is the Map; other container libraries may use other names (dictionary, associative array are two).

Continuing in the style described in the discussion on separate instantiation above, you start by creating an Abstract_Car_Maps package:

   with Abstract_Car_Containers;
   with BC.Containers.Maps;
   with Cars;
   package Abstract_Car_Maps
   is new Abstract_Car_Containers.Maps (Key => Cars.Plate_String,
					"=" => Cars.Plate_Strings."=");

The Map is implemented using a hash table. You say how many hash buckets you want, and you supply a hash function which, given a Key, indicates which bucket is to be used. The buckets correspond to individual Collection-like containers.

   with Cars;
   function Plate_Hash (P : Cars.Plate_String) return Natural;

   with Abstract_Car_Maps;
   with BC.Containers.Maps.Bounded;
   with Plate_Hash;
   package Mapped_Fleets is new Abstract_Car_Maps.Bounded
     (Hash => Plate_Hash,
      Buckets => 5,
      Maximum_Size => 30);

Why does this speed things up? The reason is that, to search a Collection for a particular element, you need to look at half the elements on average. If you have a Map with 1000 Cars split among 10 hash buckets, a search will only have to examine 50 Cars on average rather than the 500 you'd need to look at if you used a plain Collection.

For this to work properly you do need a good hash function, of course (Plate_Hash). It would be quite legal, but not at all efficient, for the hash function always to return 0. A set of string hash functions (part of the author's ColdFrame package, a code framework generator backend for UML CASE tools) is available in tar and zip forms.

In many applications, you'll probably find the fact that a Map implements associative lookup as useful as, if not more so than, the performance aspects.

More to come here on Sets and Queues.

What are these "Forms"?

Most of the Containers come in four concrete forms, distinguished by the approach to storage management. The forms are

• Bounded,
• Dynamic (deprecated),
• Unbounded, and
• Unmanaged.

Bounded

We've already come across the Bounded form; you can use it if you know the maximum number of items you'll need to store.

Note on unconstrainedness.

The bounded form doesn't allocate memory of itself (of course, you can use it to hold items that are allocated), so it may be appropriate for systems where allocation is frowned upon. However, it can be slower, especially for insertion or deletion "in the middle".

There is an issue with deletion of items that need finalizing: the finalization will only occur when the item's storage slot is overwritten or when the container itself is finalized. Also, if the item is an access type, you have to manage deallocation.

Dynamic

This form was designed before storage pools were properly understood. You're probably best off not using it.

Unbounded

Unmanaged

The unmanaged form allocates space for each item held from the system memory pool and returns it when the item is removed. It's by far the simplest form to use.

The Mapped_Fleets example above would become

   with Abstract_Car_Maps;
   with BC.Containers.Maps.Unmanaged;
   with Plate_Hash;
   package Mapped_Fleets is new Abstract_Car_Maps.Unmanaged
     (Hash => Plate_Hash,
      Buckets => 5);

I guess this should cover Storage Management as well.

[index]