|
The Booch Components are a complex whole, and the purpose of this note is to provide an initial introduction to their use.
In the example, a Car has three attributes, the Plate (the Index Mark; my first car's was 8493KC), the Model name (it was a Vauxhall Cresta) and the date it was Registered (some time in the mists of antiquity).
with Ada.Calendar;
with Ada.Strings.Bounded;
package Cars is
package Plate_Strings
is new Ada.Strings.Bounded.Generic_Bounded_Length (10);
subtype Plate_String
is Plate_Strings.Bounded_String;
package Model_Strings
is new Ada.Strings.Bounded.Generic_Bounded_Length (32);
subtype Model_String
is Model_Strings.Bounded_String;
type Car is record
Plate : Plate_String;
Model : Model_String;
Registered : Ada.Calendar.Time;
end record;
end Cars;
A company's Fleet holds a number of Cars.
You're clearly going to need some sort of container to implement Fleet.
If you just want a standard container to support iteration, filtering and sorting, use Collections. The List components are much more complex than you'll need.
Later, we'll look at Maps.
The first thing to do is to instantiate the top-level abstract Containers for Car. Note, you have to supply an equality operator ("=") for Car; you could also just use Cars.
with BC.Containers; with Cars; package Abstract_Car_Containers is new BC.Containers (Cars.Car, "=" => Cars."=");
Next, using the new Abstract_Car_Containers, instantiate the abstract Collections. This is quite confusing the first few times you come across it!
When you instantiate a generic parent like BC.Containers, all the generic children of the generic parent become candidates for instantiation as actual children of the actual parent.
Although you have to with BC.Containers.Collections;, the thing you have to instantiate now is the newly magicked Abstract_Car_Containers.Collections:
with Abstract_Car_Containers; with BC.Containers.Collections; package Abstract_Car_Collections is new Abstract_Car_Containers.Collections;
Next, choose the representation to be used for concrete Collections. To start with, assume that you'll never have more than 30 Cars to deal with. This means that you can use the Bounded form. Again, what you instantiate is the child of the newly instantiated Abstract_Car_Collections.
with Abstract_Car_Collections; with BC.Containers.Collections.Bounded; package Fleets is new Abstract_Car_Collections.Bounded (Maximum_Size => 30);You now need to create your Fleet:
with Fleets;
package My_Fleet is
The_Fleet : Fleets.Collection;
end My_Fleet;
You might find it more convenient to do the instantiations in one place. Note the use type Cars.Car; to make Car equality visible:
with BC.Containers.Collections.Bounded;
with Cars;
package My_Fleet_Combined is
use type Cars.Car;
package Abstract_Car_Containers
is new BC.Containers (Cars.Car);
package Abstract_Car_Collections
is new Abstract_Car_Containers.Collections;
package Fleets
is new Abstract_Car_Collections.Bounded (Maximum_Size => 30);
The_Fleet : Fleets.Collection;
end My_Fleet_Combined;
or even to make the use of the Components private:
with BC.Containers.Collections.Bounded;
with Cars;
package My_Fleet_Hidden is
-- subprograms to add, find, and delete Cars
private
package Abstract_Car_Containers
is new BC.Containers (Cars.Car, "=" => Cars."=");
package Abstract_Car_Collections
is new Abstract_Car_Containers.Collections;
package Fleets
is new Abstract_Car_Collections.Bounded (Maximum_Size => 30);
The_Fleet : Fleets.Collection;
end My_Fleet_Hidden;
Aside from keeping things in Collections, there are other possibilities:
Iteration is the process of visiting each member of a collection and doing something with or to it.
Two forms of iteration are supported: open and closed. Both require the creation of Iterators.
With open iterators, you explicitly advance the iterator to the next element in the collection it references, until it's done; with closed iterators, you supply a procedure which gets called for each element in the collection.
Considering the packages declared in the discussion on separate instantiation above, the operations on iterators are all defined in Abstract_Car_Containers, while actual iterators can only be created by the concrete package:
declare
It : Abstract_Car_Containers.Iterator'Class
:= Fleets.New_Iterator (The_Fleet);
begin
while not Abstract_Car_Containers.Is_Done (It) loop
declare
C : Car := Abstract_Car_Containers.Current_Item (It);
begin
null; -- do something with C
end;
Abstract_Car_Containers.Next (It);
end loop;
end;
A closed-iterator version of the same would look like
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:
See BC.Containers for details.
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;
which you'd probably declare in the public part of My_Fleet_Combined. Its body might look like
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;
which is a bit of a mouthful.
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.
Suppose you want to keep your Fleet sorted (earliest first). You need
procedure Sort;
which, as before, gets declared in the public part of My_Fleet_Combined.
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 before, you with BC.Containers.Quicksort;, but when you do the instantiation it's of Abstract_Car_Containers.Quicksort.
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.
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."=");
(this time you can't get away with just use Cars).
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.
Most of the Containers come in four concrete forms, distinguished by the approach to storage management. The forms are
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.
This form was designed before storage pools were properly understood. You're probably best off not using it.
The unbounded form allocates space for each item held from a storage pool that you provide and returns it when the item is removed.
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.