!topic AI-302
!from Matthew Heaney 2003-09-25
!discussion

This document was formatted using hard line-breaks, with a maximum of 72
columns.  If you print it I suggest using 10 pt. font.

The container library API described here comprises the following
library-level units:

Ada.Containers
Ada.Containers.Vectors
Ada.Containers.Vectors.Unbounded
Ada.Containers.Vectors.Bounded
Ada.Containers.Deques
Ada.Containers.Deques.Unbounded
Ada.Containers.Lists
Ada.Containers.Lists.Double
Ada.Containers.Lists.Double.Unbounded
Ada.Containers.Lists.Double.Bounded
Ada.Containers.Lists.Single
Ada.Containers.Lists.Single.Unbounded
Ada.Containers.Lists.Single.Bounded
Ada.Containers.Maps
Ada.Containers.Maps.Hashed
Ada.Containers.Maps.Hashed.Unbounded
Ada.Containers.Maps.Hashed.Unbounded.Unchecked_Modification
Ada.Containers.Maps.Hashed.Strings
Ada.Containers.Maps.Hashed.Strings.Unbounded
Ada.Containers.Maps.Hashed.Wide_Strings
Ada.Containers.Maps.Hashed.Wide_Strings.Unbounded
Ada.Containers.Maps.Sorted
Ada.Containers.Maps.Sorted.Unbounded
Ada.Containers.Maps.Sorted.Unbounded.Unchecked_Modification
Ada.Containers.Maps.Sorted.Strings
Ada.Containers.Maps.Sorted.Strings.Unbounded
Ada.Containers.Maps.Sorted.Wide_Strings
Ada.Containers.Maps.Sorted.Wide_Strings.Unbounded
Ada.Containers.Multimaps
Ada.Containers.Multimaps.Hashed
Ada.Containers.Multimaps.Hashed.Unbounded
Ada.Containers.Multimaps.Hashed.Unbounded.Unchecked_Modification
Ada.Containers.Multimaps.Hashed.Strings
Ada.Containers.Multimaps.Hashed.Strings.Unbounded
Ada.Containers.Multimaps.Hashed.Wide_Strings
Ada.Containers.Multimaps.Hashed.Wide_Strings.Unbounded
Ada.Containers.Multimaps.Sorted
Ada.Containers.Multimaps.Sorted.Unbounded
Ada.Containers.Multimaps.Sorted.Unbounded.Unchecked_Modification
Ada.Containers.Multimaps.Sorted.Strings
Ada.Containers.Multimaps.Sorted.Strings.Unbounded
Ada.Containers.Multimaps.Sorted.Wide_Strings
Ada.Containers.Multimaps.Sorted.Wide_Strings.Unbounded
Ada.Containers.Sets
Ada.Containers.Sets.Hashed
Ada.Containers.Sets.Hashed.Unbounded
Ada.Containers.Sets.Hashed.Unbounded.Unchecked_Modification
Ada.Containers.Sets.Sorted
Ada.Containers.Sets.Sorted.Unbounded
Ada.Containers.Sets.Sorted.Unbounded.Unchecked_Modification
Ada.Containers.Multisets
Ada.Containers.Multisets.Hashed
Ada.Containers.Multisets.Hashed.Unbounded
Ada.Containers.Multisets.Hashed.Unbounded.Unchecked_Modification
Ada.Containers.Multisets.Sorted
Ada.Containers.Multisets.Sorted.Unbounded
Ada.Containers.Multisets.Sorted.Unbounded.Unchecked_Modification
Ada.Containers.Hash_String
Ada.Containers.Hash_String_Case_Insensitive
Ada.Containers.Equal_String_Case_Insensitive
Ada.Containers.Less_String_Case_Insensitive
Ada.Containers.Hash_Wide_String
Ada.Containers.Hash_Wide_String_Case_Insensitive
Ada.Containers.Equal_Wide_String_Case_Insensitive
Ada.Containers.Less_Wide_String_Case_Insensitive
Ada.Containers.Hash_Integer
Ada.Containers.Hash_Long_Integer
Ada.Containers.Hash_<etc>


Note that only the terminal units are interesting.  The other units are
merely placeholders.

The API has been annotated with lots of examples to illustrate the kinds
of problems the library solves, and the most effective way to use the
library to solve them.  So what you have here is a tutorial, too.  Note
that the actual container specifications are relatively simple, and none
of them are any more complicated than, say, Ada.Text_IO or
Ada.Strings.Unbounded.  (In fact all the containers use type, operation,
and parameter names that were inspired by those packages.)

This library API is modeled on the STL.  It has the same containers as
the STL does, using the same container names and semantics.  If you know
the STL already then you will instantly understand how this library
works.  It does not have any of the STL algorithms, but that's only
because I wanted to keep the API small (and not because it's not
possible to support STL-style algorithms -- it is).  The API described
here has exactly the minimum set of containers I believe all Ada
developers need, in exactly the form they need it.  (To be honest: I'd
wish it had container forms to store limited elements, too, but what's
here is the minimal set.)

We can broadly characterize containers as being either "sequence
containers" or "associative containers."  All sequence containers allow
insertion and deletion at any position in the container, but each one
optimizes differently for insertions at certain positions.  Associative
containers associate elements with a key, which defines how elements are
ordered in the container.

A vector is a sequence container optimized for insertion at the back
end.  It of course allows insertion at any position, but as you move
toward the front the cost of vector insertion approaches O(n).

A deque is a sequence container optimized for insertion at either the
front or the back end.  Like all sequence containers it allows items to
be inserted at any position, but as you move towards the middle
positions the cost of deque insertion approaches O(n).

Both vectors and deques support constant-time random access of elements.
Except for a couple of operations, the interfaces are identical.

A linked-list container provides constant-time (meaning O(1) time
complexity) insertion and deletion at any position, but of course does
not provide random access.  A doubly-linked list has nodes with both
next and prev pointers, and a singly-linked list has nodes with only a
next pointer.

A doubly-linked list supports both forward and reverse iteration; the
singly-linked list supports only forward iteration.  A doubly-linked
list container is thus more general than a singly-linked list container,
but a singly-linked list consumes less storage and forward iteration is
often all you need anyway.

Vectors and deques specify positions via a discrete index subtype.
Linked-lists (and all the associative containers) specify positions
using an iterator, which is just a fancy name for an access type that
designates an internal node of storage.  Note that unlike a discrete
index, an iterator always designates the node that contains an element;
it never designates an element directly.  (There's a special selector
operation for that.)

The vector and linked-list containers have both unbounded and bounded
forms.  The latter form allows the maximum number of elements to be
specified as a discriminant, so that storage for the container can be
implemented as a stack-allocated array.  This allows those container
packages to be instantiated at any nesting level.

The associative containers order their elements by key.  A map has an
explicit key type, but with a set the key is implicit in the element
itself.  Multimaps and multisets allow multiple keys and elements,
respectively, to have non-unique values.

The associative containers have both sorted and hashed versions.  For
insertions, deletions, and searches, a sorted associative container
guarantees O(log N) time complexity even in the worst case; under some
circumstances insertion is amortized O(1).  Hashed containers provide
O(1) average time complexity, but of course cannot make any worst-case
guarantees.

For the maps and multimaps, there are forms that use types String and
Wide_String specifically as the key.  Using a string as the key of a map
container is so common in nearly every application that the library
provides this directly.  This is an example of my philosophy that a
library should be designed around the common case.  If you need to do it
often, then the library should make it easy to do it.

There are also library-level subprograms for performing case-insensitive
string comparisons, and for returning the hash value of a both
case-sensitive and case-insensitive strings.

This API is based on an existing container library called Charles.  Some
of you were at my paper presentation in Toulouse, and so may already be
familiar with that library.  The source code itself and a couple of
papers about the design of Charles are at my home page:

<http://home.earthlink.net/~matthewjheaney/charles/index.html>

The PowerPoint slides ("foils") from my paper presentation at AE-2003
are also there.  It's in various formats including HTML, so you can get
some background info by viewing that, too.

My immediate plan is to synchronize the Charles library to the spec I've
submitted today, which should only take a few days.  Thanks to important
contributions from Mario Alves and especially Chris Grein, the packages
described here are much simpler than the corresponding specs in Charles.
However, even in its current state the version at my website is close
enough to what I've shown here that if desired you could use it as-is to
bootstrap your own implementation.

The Charles release also has an examples subdirectory containing a few
programs you can run.

If the ARG chooses this API as the basis for standardization, then I and
the other members of the ASCLWG will work on building a test suite for
testing implementors' conformance to the API.  Let us know what you'd
like done, and we'll take care of it.

Here are a few issues:

The set container packages have a generic nested package called
Generic_Keys.  I didn't know whether to nest it in the parent package,
or to declare it as a generic child package.  If anyone has a preference
please let me know.

For a few containers I have described them indirectly, in terms of how
they differ from another container.  If this is not your preferred API
format then I'll change it to however you like.

The containers specified here can only be instantiated with elements
that are non-limited and definite.  If there is interest in containers
for limited element types, or for indefinite element types, then let me
know and I will amend this specification.

I didn't know what to do about the stream attributes.  Should containers
be streamable?  It's simple enough for a user to just iterate through
the elements in the container and write them out himself, so I wasn't
sure whether the containers needed to provide stream support directly.

Charles has a container for strings, which is similar to a vector except
that the internal array designates type String.  It's not unlike type
Unbounded_String, but it's a proper container and thus fits within the
container framework.  If there is interest in a container optimized for
storing an unbounded String (or Wide_String) let me know.

Charles also has a Pointer_Type abstraction, which is sort of a
"container" for storing a single access object.  It is similar to the
auto_ptr in C++.  The access object can be transferred from Poiner_Type
object to Pointer_Type object, thus transferred ownership of the access
object.  If a Pointer_Type object still owns an access object during its
Finalize, then it automatically Free's the access object, thus providing
a cheap form of garbage collection.  If there is interest in
standardizing such an abstraction then let me know.

There are no bounded forms for the associative containers.  The package
names have been chosen to allow for the possibility, but this API only
specifies unbounded forms.  I'm pretty sure the sorted associative
containers can implemented in the normal way (i.e. as an array), and I
think I know how to implement a hash table on the stack, so if there is
interest then let me know.

The sorted associative containers are implemented using a tree.  Each
node consumes 3 pointers worth of storage in addition to the element
(and key, for maps).  It is possible to implement a sorted associative
container using a sorted vector, which might be useful as a
storage-optimized form.  Again, if there is interest let me know.

A votre service,
Matt


--STX

The root of the containers subsystem is as follows:

package Ada.Containers is
   pragma Pure;
end Ada.Containers;


The specification of the root of the vector containers subsystem is as
follows:

package Ada.Containers.Vectors is
   pragma Pure;
end Ada.Containers.Vectors;

The specification of the unbounded vector container package is as
follows:

generic

   type Index_Type is (<>);
   
   type Element_Type is private;
   
   with function "=" 
     (Left, Right : Element_Type) return Boolean is <>;
   
package Ada.Containers.Vectors.Unbounded is

   pragma Preelaborate;
   
   subtype Index_Subtype is Index_Type;
   
   type Container_Type is private;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;
   
   function Length (Container : Container_Type) return Natural;
   
   function Is_Empty (Container : Container_Type) return Boolean;
   
   procedure Clear (Container : in out Container_Type);
   
   procedure Swap (Left, Right : in out Container_Type);
      
   procedure Append
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);
      
   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Index_Type'Base;
      New_Item  : in     Element_Type);
     
   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Index_Type'Base);

   procedure Insert_N
     (Container : in out Container_Type;
      Before    : in     Index_Type'Base;
      Count     : in     Natural;
      New_Item  : in     Element_Type);

   procedure Insert_N
     (Container : in out Container_Type;
      Before    : in     Index_Type'Base;
      Count     : in     Natural);

   procedure Delete
     (Container : in out Container_Type;
      Index     : in     Index_Type'Base);
            
   procedure Delete_Last
     (Container : in out Container_Type);
   
   procedure Delete_N
     (Container : in out Container_Type;
      First     : in     Index_Type'Base;
      Count     : in     Natural);

   function Size
     (Container : Container_Type) return Natural;
   
   procedure Resize
     (Container : in out Container_Type;
      Size      : in     Natural);
      
   function Front 
     (Container : Container_Type) return Index_Type'Base;

   function First 
     (Container : Container_Type) return Index_Type;

   function First_Element
     (Container : Container_Type) return Element_Type;

   function Last
     (Container : Container_Type) return Index_Type'Base;

   function Last_Element
     (Container : Container_Type) return Element_Type;

   function Back 
     (Container : Container_Type) return Index_Type'Base;
   
   function Element 
     (Container : Container_Type;
      Index     : Index_Type'Base) return Element_Type;
   
   generic
      type Element_Access is access all Element_Type;
   function Generic_Element
     (Container : Container_Type;
      Index     : Index_Type'Base) return Element_Access;
         
   procedure Replace_Element
     (Container : in Container_Type;
      Index     : in Index_Type'Base;
      By        : in Element_Type);
      
   generic
      with procedure Process 
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Element
     (Container : in Container_Type;
      Index     : in Index_Type'Base);
     
   generic
      with procedure Process 
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

   generic
      with procedure Process 
        (Element : in out Element_Type) is <>;
   procedure Generic_Reverse_Process_Elements
     (Container : in Container_Type);

private

   --not specified by this standard

end Ada.Containers.Vectors.Unbounded;


!discussion

A vector container manages an internal array whose component subtype is
Element_Type.  The element components are aliased.  (Indeed, elements
are aliased in every container.)  The "size" of a vector corresponds to
the length of the internal array (and hence to the number of "physical"
elements), and the "length" of the vector corresponds to the number of
"logical" or "active" elements in the internal array.  The elements of
the array between the vector length and the vector size are "inactive."

As elements are inserted into the container (thus increasing the length
of the vector), the internal array automatically expands as necessary
(thus increasing the size of the vector).  The new size of the vector
following expansion is always a factor of its current size, although the
exact algorithm is not specified by this standard.  (A typical value for
the new size is two times the current size.)  Insertions at the back end
of a vector container therefore have amortized constant time complexity.

!end discussion

Container_Type is a pass-by-reference type.  The size of a
default-initialized vector is 0.

Implementation Requirements:
The internal array has C convention.

!discussion

The lingua franca for APIs is C.  We need to be able to pass the
internal array (really, a pointer to its first element) to a C function
with a T* argument.  Therefore the elements must have the same alignment
as they have in C.

For example, what I often do in C++ on Windows is this:

   typedef std::vector<HANDLE> handles_t;
   
   handles_t handles = /* ... */ ;
   
   WaitForMultipleObjects(handles.size(),
                          &handles[0],   
                          FALSE,
                          INFINITE);
                          
The Ada analog looks like this:

   type Handle_Access is access all Win32.HANDLE;
   for Handle_Access'Storage_Size use 0;
   pragma Convention (C, Handle_Access);

   function To_Access is
      new Handle_Vectors.Generic_Element (Handle_Access);

   Handles : Handle_Vectors.Container_Type;
   ...
   WaitForMultipleObjects
     (Length (Handles),
      To_Access (Handles, Index => First (Handles)),
      False,
      INFINITE);
         
This is actually quite close to the C++ example above.

!end discussion


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

If Source is an alias of Target, the operation has no effect.  If the
length of Source is less than or equal to the size of Target, then the
active elements in Source are assigned to the elements in Target.  Any
exceptions raised during assignment are propagated.  Otherwise if the
length of Source is greater than the size of Target, a new internal
array is allocated with elements that are initialized from the active
elements in Source.  Any exceptions raised during allocation are
propagated, and Target is not modified.  Otherwise, the existing array
is replaced by the new array, and then the old array is deallocated.
Any exceptions raised during deallocation are propagated.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for vectors.  If Left and Right refer to the same
container, then the function returns immediately with the value True.
If Left and Right have different lengths, then the function returns
immediately with the value False.  Otherwise, elements are compared
sequentially using the equality operator supplied as the generic actual.
Any exception raised during evaluation of element equality is
propagated, immediately terminating the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of active elements in the vector.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Sets the length of the container to 0.  The size of the container does not
change.

!discussion

You can think of Clear as "removing" the elements in the container, but
of course it does not really remove them.  The elements that were
formerly active simply now become inactive.

In particular, the internal array is not altered, and no finalization of
the active elements occurs.  If this is required, then then user must
effect this himself prior to clearing the vector.  There are many ways
to do that; here is one way:

   procedure My_Clear (V : in out Vector_Subtype) is
   
      procedure Finalize
        (E : in out Element_Subtype) is ...;
      
      procedure Finalize_Elements is
         new Generic_Process_Elements (Process => Finalize);      
   begin      
      Finalize_Elements (V);   
      Clear (V);
   end;

The internal array never shrinks, and it only expands under specific
conditions.  If you want to clear the vector and also deallocate the
internal array, you can use the swap trick:

   procedure Clear_And_Deallocate (V : in out Vector_Subtype) is
     
      V2 : Vector_Subtype; -- internal array is null 
   begin
      Swap (V, V2);
   end;   

The internal array that belonged to V is swapped into V2, and the null
array of V2 is swapped into V.  When V2 is finalized, its internal array
is deallocated.  This also invokes Finalize for controlled elements.

!end discussion


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal array and element count of the Left vector with
that of the Right vector.  Elements that were in the Left vector are now
in the Right vector, and vice versa.  The time complexity of Swap is
O(1).

!discussion

The internal array of a vector container only grows.  The Resize
operation can only be used to grow the internal array, not to shrink it.
If for whatever reason you want more efficient use of storage, you can
use the swap trick to allocate an array having the minimum size
necessary to store the active elements:

   procedure Reclaim_Storage (V : in out Vector_Subtype) is
      Temp : Vector_Subtype := V;
   begin
      Swap (V, Temp);
   end;

This copies all active elements in V to the temporary vector object
Temp, which is allocated using a smaller internal array (presumably the
smallest size necessary to store the elements, according to whatever
algorithm the implementor has chosen).  The new array is swapped with
the original array, which is then deallocated when Temp is finalized.

!end discussion


procedure Append
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);
   
Equivalent to Insert (Container, Back (Container), New_Item).  This
operation has (amortized) O(1) time complexity.

!example

Append is the canonical method for inserting items into a vector
container:

   procedure Copy (A : Array_Subtype) is
      V : Vector_Subtype;
   begin
      Resize (V, Size => A'Length);
      
      for I in A'Range loop
         Append (V, New_Item => A (I));
      end loop;
      ...
   end Copy;      

The Resize operation tells the vector object to preallocate an internal
array having at least the size specified.  If you need to perform many
repeated insertions, then if you know the ultimiate length apriori you
should always call Resize beforehand.  This is more efficient because it
allocates the internal array once, and therefore avoids the repeated
reallocation, copying, and deallocation cycles that would be necessary
otherwise as the array is expanded.

!end example

!example

You can use a vector to implement a stack in the traditional way:

  package Stacks is new Ada.Containers.Vectors.Unbounded (ET);
  use Stacks;

  Stack : Stacks.Container_Type;

  procedure Push (E : in ET) is
  begin
     Append (Stack, New_Item => E);
  end;

  function Top return ET is
  begin
     return Last_Element (Stack);
  end;

  procedure Pop is
  begin
     Delete_Last (Stack);
  end;

Note that we can't use the front end as the top of the stack, because
there's no Delete_First.  Compare this to the single list example.

!end example


procedure Insert
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base;
   New_Item  : in     Element_Type);

Equivalent to Insert_N (Container, Before, 1, New_Item).
  

procedure Insert
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base);

Equivalent to Insert_N (Container, Before, 1).


procedure Insert_N
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base;
   Count     : in     Natural;
   New_Item  : in     Element_Type);

If Count has the value 0, then Insert_N does nothing.  Otherwise the new
length is calculated from the sum of the current length and the value of
Count; if the new value of Last would be greater than Index_Type'Last
the operation fails and Constraint_Error is raised.  If the value of
Before is not in the range First (Container) .. Back (Container), the
operation fails and Constraint_Error is raised.

If the current vector size is greater than or equal to the new length,
the elements in the range Before .. Last (Container) slide up by Count
positions, and the elements in the Count positions starting at Before
are assigned to the value New_Item.  Any exceptions raised during the
assignment are propagated.

Otherwise if the current vector size is less than the new length, a new
internal array is allocated and initialized from New_Item and the active
elements in Container.  Any exceptions are propagated and Container is
not modified.  The existing array is replaced by the new array, and then
the old array is deallocated.  Any exceptions raised during the
deallocation are propagated.


procedure Insert_N
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base;
   Count     : in     Natural);

Equivalent to Insert_N (Container, Before, Count, New_Item), with the
difference that the elements in the Count positions starting at Before
are not assigned.

!example

This operation essentially opens up a "hole" in the middle of the
internal array.  It's more efficient to do it this way than inserting
one-item-at-a-time, because the sliding is done only once.  For example,
we can copy an array (or any other container) into a vector at some
arbitary position like this:

   procedure Copy
     (A : in     Array_Subtype;
      V : in out Vector_Subtype;
      I : in     Index_Type'Base) is
      
      J : Index_Type'Base := I;
   begin
      Insert_N (V, Before => I, Count => A'Length); -- dig the hole

      for Index in A'Range loop
         Replace_Element (V, J, By => A (Index));  -- fill the hole
         J := J + 1;
      end loop;
      ...
   end Copy;

!end example
   

procedure Delete
  (Container : in out Container_Type;
   Index     : in     Index_Type'Base);

If Index is outside the range First (Container) .. Last (Container), the
operation does nothing.  Otherwise the elements in the range
Index_Type'Succ (Index) .. Last (Container) slide down by one position.
Any exceptions raised during element assignment are propagated.

!example

There's no Delete_First operation, as a not-so-subtle reminder to
developers that that's a potentially expensive operation.  However, you
can achieve the same effect by simply specifying the first index:

   procedure Op (V : in out Vector_Subtype) is
   begin
      Delete (V, Index => First (V));  -- pop front element
      ...
   end;

!end example   


procedure Delete_Last (Container : in out Container_Type);

Equivalent to Delete (Container, Last (Container)).  This operation has
O(1) time complexity.

!example

If some sort of finalization of the last element is necessary prior to
its removal, the programmer is responsible for effecting this action
prior to calling Delete_Last.  As an example, suppose we have a vector
whose elements are access objects, and we need to deallocate the element
when it is "popped" from the vector:

   procedure Pop (V : in out Container_Type) is
   
      procedure Process is
         new Ada.Unchecked_Deallocation (T, T_Access);
         
      procedure Free is
         new Generic_Process_Element; -- use "Process" default
   begin
      Free (V, Index => Last (V));
      Delete_Last (V);
   end;

!end example   
   

procedure Delete_N
  (Container : in out Container_Type;
   First     : in     Index_Type'Base;
   Count     : in     Natural);      
   
If Count is 0, the operation does nothing.  If First does not specify a
value in the range First (Container) .. Last (Container), the operation
fails and Constraint_Error is raised.  The back of the half-open range
to be deleted is then calculated as the minimum of First plus Count, and
Back (Container).  The active elements of the internal array starting at
the back of the calculated range slide down to the corresponding index
positions starting at First.  Any exceptions raised during the
assignment are propagated.


function Size (Container : Container_Type) return Natural;

Returns the length of the internal array.


procedure Resize
  (Container : in out Container_Type;
   Size      : in     Natural);
   
If Size (Container) is greater than or equal to Size, the operation does
nothing.  Otherwise a new internal array is allocated having at least
the length specified and initialized from the active elements in
Container.  Any exceptions raised during the allocation are propagated,
and Container is not modified.  Otherwise the existing array is replaced
by the new array, and then the old array is deallocated.  Any exceptions
raised during deallocation are propagated.


function Front 
  (Container : Container_Type) return Index_Type'Base;

Returns the value Index_Type'Pred (Index_Type'First).

!example

The Front selector exists so that during reverse iteration over a
vector, the index can "fall off the end" of the range onto the sentinel:

   procedure Op (V : in Vector_Subtype) is
      I : Index_Subtype := Last (V);
      J : constant Index_Subtype := Front (V);
   begin
      while I /= J loop
         Process (E => Element (V, I));
         I := Index_Type'Pred (I);
      end loop;
   end Op;

!end example   


function First 
  (Container : Container_Type) return Index_Type;

Returns the value Index_Type'First.


function First_Element
  (Container : Container_Type) return Element_Type;

Equivalent to Element (Container, First (Container)).
  

function Last
  (Container : Container_Type) return Index_Type'Base;

Returns the index value corresponding to the length (meaning number of
active elements) of the vector.


function Last_Element
  (Container : Container_Type) return Element_Type;

Equivalent to Element (Container, Last (Container)).  


function Back 
  (Container : Container_Type) return Index_Type'Base;

Equivalent to Index_Type'Succ (Last (Container)).


function Element 
  (Container : Container_Type;
   Index     : Index_Type'Base) return Element_Type;

If Index is not in the range First (Container) .. Last (Container), the
operation fails and Constraint_Error is raised.  Otherwise it returns
the element of the internal array at the specified Index.


!example

The First and Last selectors allow iteration over a vector analogous to
iteration over an array, using the loop machinary provided by the
language:

   procedure Op (V : in Vector_Subtype) is
      procedure Process (E : in Element_Subtype) is ...;
   begin
      for I in First (V) .. Last (V) loop
         Process (E => Element (V, I));
      end loop;
   end Op;

Here we've used the element selector function.  Another possibility is
pass the element as the parameter of a generic subprogram:

   procedure Op (V : in Vector_Subtype) is

      procedure Process (E : in out Element_Subtype) is ...;

      procedure Process is
         new Generic_Process_Element; -- accept "Process" default
   begin
      for I in First (V) .. Last (V) loop
         Process (V, I);
      end loop;
   end Op;

But if we're going to iterate over the entire range of active elements,
then it's probably simpler to just use a passive iterator:

   procedure Op (V : in Vector_Subtype) is

      procedure Process (E : in out Element_Subtype) is ...;

      procedure Process is
         new Generic_Process_Elements; -- accept "Process" default
   begin
      Process (V);
   end Op;

In fact here we make yet another simplification:

   procedure Process (E : in out Element_Subtype) is ...;

   procedure Op is
      new Generic_Process_Elements; -- accept "Process" default

!end example   


generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Container : Container_Type;
   Index     : Index_Type'Base) return Element_Access;
      
If Index is not in the range First (Container) .. Last (Container), the
operation fails and Constraint_Error is raised.  Otherwise it returns an
access value that designates a variable view of the element of the
internal array at Index.

!example

This function is very important, as it allows in-place modification of
elements.  For example, suppose we have a vector whose elements are
lists, and we want to append an item to the list at a specified vector
position.  We can do that as follows:

   procedure Append 
     (V : List_Vectors.Container_Type;
      I : Index_Type'Base;
      E : Element_Subtype) is
  
      type List_Access is access all List_Subtype;
      function To_Access is new Generic_Element (List_Access);

      List : List_Subtype renames To_Access (V, I).all;
   begin
      Append (List, New_Item => E);
   end;

It's often the case that during an insertion you don't have an item
value to assign to the new element, and instead you want simply to
reserve space for an element and then modify it directly.  For example:

   procedure Op (V : in out Vector_Subtype) is
   begin
      Insert (V, Before => Back (V));  -- no item

      declare
         E : Element_Subtype renames To_Access (V, Last (V)).all;
      begin
         -- now modify E
      end;
   end Op;

!end example   


procedure Replace_Element
  (Container : in Container_Type;
   Index     : in Index_Type'Base;
   By        : in Element_Type);
   
If Index does not specify a value in the range First (Container) .. Last
(Container), the operation fails and Constraint_Error is raised.
Otherwise the element at position Index is assigned the value By.  Any
exceptions raised during the assignment are propagated.

!example

This allows array-like modification of vector elements:

   procedure Op (V : in out Vector_Subtype) is
      I : Index_Subtype := ...;
      E : Element_Subtype := ...;
   begin
      Insert (V, Before => I, New_Item => E);
      ... -- modify E some more
      Replace_Element (V, Index => I, By => E); -- aka V(I) := E;
   end;

!end example      


generic
   with procedure Process 
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Container : in Container_Type;
   Index     : in Index_Type'Base);

If Index does not specify a value in the range First (Container) .. Last
(Container), the operation fails and Constraint_Error is raised.
Otherwise, the actual subprogram bound to Process is called with the
element at position Index.

!example

You can use this operation to modify an element in-place.  For example,
given our vector-of-lists from the earlier example, we could swap a list
object with one of the list elements already in vector, like this:

   procedure Swap
     (V : in     List_Vectors.Container_Type;
      I : in     Index_Type'Base;
      L : in out List_Subtype) is

      procedure Process (VE : in out List_Subtype) is
      begin
         Swap (L, VE);
      end;
         
      procedure Swap_Element is
        new Generic_Process_Element; -- accept "Process" default
   begin
      Swap_Element (V, Index => I);
   end;

This would allow us to populate a list object, separate from a vector,
and then add it to the vector without having to actually copy it:

   procedure Op (V : in List_Vectors.Container_Type) is
      L : List_Subtype;
   begin
      Append (L, New_Item => E);
      ... -- populate list some more
      Insert (V, Before => Back (V)); -- create a new element in V
      Swap (V, Last (V), L);          -- swap new element in V with L
   end;
      
The new list element that is appended to V during Insert is immediately
swapped with the list object L.  This effectively "moves" L onto V,
without any copying.  The element that was in V is moved into L, which
is then finalized.

Note that if you wanted to swap two vector elements, you could use
Generic_Process_Element but it would be awkward.  It would probably be
easier to use an instantiation of Generic_Element to get a variable view
of the elements and then use them directly.  For example, given our
instantiation To_Access from the earlier example, we would implement the
operation this way:

  procedure Swap
    (V    : in out List_Vectors.Container_Type;
     I, J : in     Index_Type'Base) is

     IE : List_Subtype renames To_Access (V, I).all;
     JE : List_Subtype renames To_Access (V, J).all;
  begin
     Swap (IE, JE);
  end;

!end example

  
generic
   with procedure Process 
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Calls the actual subprogram bound to Process for each active element in
Container.  Any exception raised during Process is propagated,
immediately terminating the iteration.


generic
   with procedure Process 
     (Element : in out Element_Type) is <>;
procedure Generic_Reverse_Process_Elements
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process as per
Generic_Process_Elements, except that the elements are traversed in
reverse order.


This standard specifies a bounded vector container.  It differs from the
unbounded vector container as follows:

(0) The name of the bounded vector container package is
    Ada.Containers.Vectors.Bounded.

(1) The package has Pure categorization, not Preelaborate.

(2) The container type is limited, and has a discrimiant, as follows:

        type Container_Type (Size : Natural) is limited private;

    Container_Type is a pass-by-reference type.  The Size discriminant
    specifies the maximum length (number of elements) for the container
    object.
    
    The container type is not controlled, and therefore the package may
    be instantiated at any nesting level.

(3) The Swap and Resize operations are omitted.

(4) The implementation requirements are as follows.  The internal array
    has C convention.  The Container_Type should be implemented as a
    stack-allocated array with exactly Size components.

(5) The semantics of Insert_N differ as follows:

procedure Insert_N
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base;
   Count     : in     Natural;
   New_Item  : in     Element_Type);

If Count has the value 0, the operation does nothing.  If the current
length of Container plus Count is greater than Container.Size, or if the
new value of Last would be greater than Index_Type'Last, the operation
fails and Constraint_Error is propagated.  If the value of Before is
outside the range First (Container) .. Back (Container), the operation
fails and Constraint_Error is propagated.

Otherwise the elements in the range Before .. Last (Container) slide up
by Count positions and the elements in the Count positions starting at
Before are assigned the value New_Item.  Any exceptions raised during
the assignment are propagated.

!example

The Win32 API limits the number of kernel synchronization objects for
which it will wait to a maximum of 64.  The bounded form of the vector
container allows you to express this restriction directly in code:

   Handles : Handle_Vectors.Container_Type (64);  -- max 
   ...
   WaitForMultipleObjects
     (Length (Handles),
      To_Access (Handles, Index => First (Handles)),
      False,
      INFINITE);

This way if you violate the limit, you'll know about it sooner (at the
time of insertion of the 65th element), instead of later when you call
the API function.

!end example         


The root of the deque containers subsystem is as follows:

package Ada.Containers.Deques is
   pragma Pure;
end Ada.Containers.Deques;


This standard specifies an unbounded deque container.  It differs from
the unbounded vector container as follows:

(1) The name of the package is Ada.Containers.Deques.Unbounded.

(2) The final declaration in the generic formal region is a generic
    formal constant:

    Elements_Per_Node : in Positive := 8;

!comment

I have passed the number of elements per node as a generic formal
constant, but I again I don't know whether this is exposing too many
implementation details, or whether this will constrain implementor
freedom.  If there is little enthusiasm among implementors for allowing
a user to specify the number of elements per node, then we can get rid
of it.

(3) The following insertion operation is defined:

procedure Prepend
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);
   
Equivalent to Insert (Container, First (Container), New_Item).  This
operation has O(1) time complexity.


(4) The following deletion operation is defined:

procedure Delete_First (Container : in out Container_Type);

Equivalent to Delete (Container, First (Container)).  The time
complexity of this operation is O(1).


(5) The semantics of Clear differ as follows.  Sets the length of
    Container to 0.  Any exceptions raised during deallocation of
    internal storage are propagated.


(6) The semantics of Swap differ as follows.  Exchanges the internal
    nodes of Left and Right.  Elements that were in the Left deque are
    now in the Right deque, and vice versa.  The time complexity of Swap
    is O(1).

(7) The semantics of Insert_N differ as follows:

procedure Insert_N
  (Container : in out Container_Type;
   Before    : in     Index_Type'Base;
   Count     : in     Natural;
   New_Item  : in     Element_Type);

If Count has the value 0, the operation does nothing.  Otherwise the new
length is calculated from the sum of the current length and the value of
Count; if the new value of Last would be greater than Index_Type'Last
the operation fails and Constraint_Error is raised.  If Before is
outside the range First (Container) .. Back (Container), the operation
fails and Constraint_Error is raised.

Otherwise, active elements are created in the Count positions starting
at Before, by sliding existing elements either towards the front of the
container or towards the back, whichever is the smaller distance, and
then assigned the value New_Item.  Any exceptions raised during element
assignment or allocation of internal storage are propagated.


(8) The semantics of Delete differ as follows:

procedure Delete
  (Container : in out Container_Type;
   Index     : in     Index_Type'Base);

If Index is outside the range First (Container) .. Last (Container), the
operation does nothing.  Otherwise either the front elements slide up,
or the back elements slide down, whichever is the smaller range.  Any
exceptions raised during element assignment or storage deallocation are
propagated.


(9) The semantics of Delete_N differ as follows:

procedure Delete_N
  (Container : in out Container_Type;
   First     : in     Index_Type'Base;
   Count     : in     Natural);      
   
If Count is 0, the operation does nothing.  Otherwise if First is
outside the range First (Container) .. Last (Container), the operation
fails and Constaint_Error is raised.  The back of the range to be
deleted is calculated as the minimum of the sum of First and Count and
Back (Container).  Either the elements in the range starting at the back
of the calculated range slide down to the corresponding index positions
starting at First, or the elements that precede First slide up,
whichever is the fewer number of elements.  Any exceptions raised during
element assignment or storage deallocation are propagated.


(10) The Size and Resize operations are omitted.


!discussion

The name "deque" is pronounced the same as "deck," as in "deck of
cards."

A deque is implemented as a set of nodes, each containing a fixed number
of elements (Elements_Per_Node).  Like a vector, a deque supports random
access, but unlike a vector insertion and deletion at the front end is a
constant-time operation.

The nodes are addressed internally via a secondary index, comprising an
array of pointers to nodes.  As elements are inserted and the number of
nodes increases, the array grows as necessary to address each node.  The
storage overhead for a deque container is therefore about 1 pointer per
node.

Do not confuse this container with data structures variously called
"stacks" or "queues" or "double-ended queues" etc, that restrict the
positions at which insertion or deletion may occur.  A deque is a
sequence container, and like all sequence containers it allows insertion
and deletion at any position.

It is interesting to compare a deque to a vector.  A vector makes room
for a new item inserted in the middle by sliding existing elements up
towards the back, and during deletion in the middle the existing
elements slide down towards the front.

Insertion in the middle of the deque works by determining which is the
closer end, and then sliding existing elements out towards that end.
Deletion in the middle works analogously, by sliding existing elements
in from the closer end.

!end discussion

!example

What is often under-appreciated about a deque is that it will perform
better than a vector if you must append many elements to the container,
and you don't know the total number of elements apriori.  In the case of
a vector, you wouldn't be able to use Resize, which means there would be
repeated allocation and deallocation as the internal array grows.  A
deque, however, can simply allocate a new internal node, which doesn't
affect existing nodes.  For example:

   procedure Copy (A : Really_Long_Array_Subtype) is
      D : Deque_Subtype;
   begin
      for I in A'Range loop
         Append (D, New_Item => A (I));  -- always cheap
      end loop;
      ...
   end Copy;

A deque also has the benefit that it doesn't need large contiguous
regions of memory, which is different from a vector.

!end example   

!example

A deque object has an offset to keep track of which element on the front
node is the first active element.  Given an index value, the offset is
added to the index, and that sum is divided by the number of elements
per node.  This is how the deque figures out where the element
associated with that index is, and why the deque is able to provide
random-access to its elements.

Therefore it's possible to iterate through the elements using a regular
for loop, analogous to array iteration:

   procedure Op (D : in Deque_Types.Container_Type) is
   begin
      for I in Index_Subtype range First (D) .. Last (D) loop
         Do_Something (Element (D, I));
      end loop;
   end;

However, although element selection is a constant-time operation,
there's still a calculation to be made as each element is selected out
of the deque.  In this case, a passive iterator is likely to beat a for
loop, because the iterator maintains context during iteration:

   procedure Op (D : in Deque_Types.Container_Type) is

      procedure Iterate is
         new Deque_Types.Generic_Process_Element (Do_Something);
   begin
      Iterate (D);
   end;

In general, using a passive iterator is preferred to using an active
iterator, among other reasons because it's likely to be more efficient.
If the container knows that it's visiting elements in sequence (as is
the case in a passive iterator), then it can visit the elements in a way
that takes advantage of that container's representation.  For example
the sorted associative containers use a recursive algorithm to perform
an in-order tree traversal.

!end example

!example

You can use a deque to implement a stack in the traditional way, but
using the front end, too:

  package Stacks is new Ada.Containers.Deques.Unbounded (ET);
  use Stacks;

  Stack : Stacks.Container_Type;

  procedure Push (E : in ET) is
  begin
     Prepend (Stack, New_Item => E);
  end;

  function Top return ET is
  begin
     return First_Element (Stack);
  end;

  procedure Pop is
  begin
     Delete_First (Stack);
  end;

Compare this to the vector example, which can only use the back end.
Here it doesn't make any difference which end, because the time
complexity (O(1)) is the same.

We can also use a deque to implement a queue, in which items are
inserted at one end and deleted from the other end.  This might be
better than, say, using a singly-linked list container (see the example
in that section), because a deque has a smaller storage cost than a
linked-list.

!end example


!example

An AVI file is a popular format for storing digital media comprising
more than one stream, such as separate tracks for video and audio.
Video and audio frames are typically "interleaved" within the file,
meaning that the audio frame that "goes with" a frame of video is
physically close to it on disk, allowing them to be read together in a
single read operation.

To know where each frame of media is on the disk, an AVI file has an
"index chunk" comprising "index entries," each of which describes the
kind of frame (video vs. audio), its file offset, and its size.

Within the index chunk, entries for video and audio are interspersed,
because this is an interleaved file.  I need to have an index comprising
just one kind of frame or the other, because I need random access to the
index entries.  (A client can specify a time in his play request, so I
need to be able to find the video frame that corresponds to that time.)

My first attempt at solving the problem used a vector, like this:

   package Index_Types is
      new Ada.Containers.Vectors.Unbounded (Index_Entry_Type);

   Video_Index : Index_Types.Container_Type;
   Audio_Index : Index_Types.Container_Type;

   procedure Load_Index (File : AVI_File_Type) is
      IE : Index_Entry_Type;
   begin
      Seek_Index (File);

      while Offset (File) /= End_Of_Index (File) loop
          Read (File, IE);
 
          if Is_Video (IE) then
             Append (Video_Index, New_Item => IE);
          elsif Is_Audio (IE) then
             Append (Audio_Index, New_Item => IE);
          end if;
      end loop;
   end Load_Index;

When I ran this on some typical files, my performance was horrible.
Why?  Feature-length movies can have over two hours worth of data, which
means hundreds of thousands of frames.  The frame index is therefore
very large.

Insertion into a vector works by using up the available space in the
internal array (the "inactive" elements).  When the space runs out, the
container allocates a new internal array (probably twice the size of the
old one), copies the contents of the old array onto the new array, and
then deallocates the old array.  You begin to see the problem: for a
large AVI file index, this cycle of reallocation, copying, and
deallocation repeats over and over again until the resulting internal
array is large enough to contain all the items.

I said earlier that if you know the ultimate length of a vector
container apriori then should always call Resize first, before you make
any insertions.  However, that option isn't available to us here,
because an AVI file doesn't tell us how many video entries (say) there
are in the index -- all we know is the total index size, which has
multiple kinds of entries.

To solve the problem I made a one-line change:

   package Index_Types is
      new Ada.Containers.Deques.Unbounded (Index_Entry_Type);

This solved the problem because inserting at the end of a deque when
there are no more inactive elements on the last internal page simply
appends a new page onto the internal index of pages.  The elements
already in the deque aren't affected, because they live on different
pages.

I didn't make this example up.  It really happened.  Real programmers
really do have real performance issues, that can make the difference
between success and failure in an application.  It's simply not an
option for me to have my server top-out the CPU every time it loads a
file, or to put potentially thousands of clients on hold, because some
guy in Idaho decided he wanted to watch the two-hour version of The
Matrix instead of the two-minute trailer.  Performance matters.

!end example

The root of the linked-list containers subsystem is as follows:

package Ada.Containers.Lists is
   pragma Pure;
end Ada.Containers.Lists;

The root of the doubly-linked list containers subsystem is as follows:

package Ada.Containers.Lists.Double is
   pragma Pure;
end Ada.Containers.Lists.Double;


The specification of the unbounded doubly-linked list container package
is as follows:

generic

   type Element_Type is private;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Lists.Double.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Prepend
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Append
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type);

   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      New_Item  : in     Element_Type);

   procedure Insert
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Iterator  :    out Iterator_Type);

   procedure Delete
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   procedure Delete_First
     (Container : in out Container_Type);

   procedure Delete_Last
     (Container : in out Container_Type);

   procedure Reverse_Container
     (Container : in Container_Type);

   generic
      with function "<"
        (Left, Right : Element_Type) return Boolean is <>;
   procedure Generic_Sort
     (Container : in Container_Type);

   generic
      with function "<"
        (Left, Right : Element_Type) return Boolean is <>;
   procedure Generic_Merge
     (Container : in out Container_Type;
      Source    : in out Container_Type);

   procedure Splice
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Source    : in out Container_Type);

   procedure Splice
     (Container : in out Container_Type;
      Before    : in     Iterator_Type;
      Source    : in out Container_Type;
      Iterator  : in     Iterator_Type);

   function First
     (Container : Container_Type) return Iterator_Type;

   function First_Element
     (Container : Container_Type) return Element_Type;

   function Last
     (Container : Container_Type) return Iterator_Type;

   function Last_Element
     (Container : Container_Type) return Element_Type;

   function Back
     (Container : Container_Type) return Iterator_Type;

   function Element
     (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access all Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   procedure Replace_Element
     (Iterator : Iterator_Type;
      By       : Element_Type);

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   function Succ
     (Iterator : Iterator_Type) return Iterator_Type;

   function Pred
     (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment (Iterator : in out Iterator_Type);

   procedure Decrement (Iterator : in out Iterator_Type);

   generic
      with procedure Process
        (Iterator  : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Iterator  : in Iterator_Type) is <>;
   procedure Generic_Reverse_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Reverse_Process_Elements
     (Container : in Container_Type);

private

   -- not specified by this standard

end Ada.Containers.Lists.Double.Unbounded;


!discussion

A doubly-linked list container manages a linked list of internal storage
nodes, each of which contains an element and pointers to the next
(successor) and previous (predecessor) internal nodes.

An iterator is similar to an access type (indeed, that is how it's
implemented), that designates a node of internal storage.

Unlike a vector (which is optimized for insertion at the back) or a
deque (optimized for insertion at the front or back), insertion into a
doubly-linked list container at any position is a constant-time
operation.

When a doubly-linked list container object elaborates, a sentinel node
belonging to the container is allocated automatically.  Its element is
uninitialized, except for any controlled initialization or
default-initialized components.  It is not included in the count of
elements in the container, and it cannot be deleted.

The function Back returns an iterator that designates the sentinel node.
The First and Last functions return iterators designating the front-most
and back-most (non-sentinel) nodes, respectively.  Back is the successor
of Last, and Last is the predecessor of Back.  A doubly-linked list also
has wrap-around semantics, meaning that the successor of Back is First,
the predecessor of First is Back.

Insertion and deletion of an element executes in constant time.  During
insertion, iterators that designate nodes already in the doubly-linked
list are not affected, and therefore an iterator that designates an
element continues to designate that same element.  (Really, an iterator
designates a node, but we sometimes say "designates an element" if the
context is clear.  Iterators never designate elements directly.)

Deletion of an element (really, deletion of the node containing an
element) only affects the iterators that designate that node, which
become invalid.  Iterators that designate other elements of the
doubly-linked list container are not affected.

Nodes can migrate from one doubly-linked list container to another
during Swap, Merge, and Splice.  Iterators designating nodes that move
of course remain valid, and continue to designate the same node, in its
new home.

!end discussion


Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, objects of type
Iterator_Type are default-initialized to the value Null_Iterator.


Implementation Requirements

Do we need to require that instances of type Iterator_Type be passed by
copy?  For example, this locution is allowed:

   procedure Insert_N
     (C : in out Container_Type;
      I : in out Iterator_Type;
      E : in     Element_Subtype;
      N : in     Natural) is
   begin
      for Index in 1 .. N loop
         -- I is in-param for Before, and out-param Iterator
         Insert (C, Before => I, New_Item => E, Iterator => I);  
      end loop;
   end;
   
This isn't any real burden, since (in the unbounded case, anyway) the
full view of Iterator_Type is implemented as an access type.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

If Source is an alias of Target, the operation does nothing.  Otherwise,
assigns to Target a copy of the elements from Source.  Any exceptions
raised during internal allocation are propagated, and Target is not
modified.

!comment
The sentinel doesn't count as an element, so it is never copied.  The
sentinel is not affected by Assign, and so following Assign the Target
has the same sentinel as it did prior to Assign.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for double-linked list containers.  If Left and
Right refer to the same container, then the function returns immediately
with the value True.  If Left and Right have different lengths, then the
function returns immediately with the value False.  Otherwise, elements
are compared sequentially using the equality operator supplied as the
generic actual.  Any exception raised during evaluation of element
equality is propagated, immediately terminating the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of elements in Container.  The time complexity of
this operation is O(1).

!comment
The time complexity of Length differs from the corresponding size()
operation in C++, which allows size() for a list to have O(n) time
complexity.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Deletes all the nodes that belong to Container, and sets the length of
to 0.  Any exceptions raised during deallocation are propagated.

!comment

Here and elsewhere, when an operation propagates an exception, the
container is never left in an inconsistent state.  This standard might
not specify what state the container is left in, but it does require
that whatever that state is, that it is consistent, and the container is
of course still usable.

In the case of Clear (for example), we don't specify how many nodes
remain in the container if the deallocation raises an exception.  But we
do require that if, say, 10 nodes were removed and then deallocation of
the 10th node failed, that the new length has a value 10 less than the
old length.

For example, an implementation has permission to implement Clear by
unlinking the nodes from Container, setting the length to 0, and then
walking the list to deallocate each node.  If there's an exception, then
the un-deallocated nodes would be lost, but Length (Container) would
accurately reflect the fact that the container is empty.

Another implementation may choose to implement Clear by as a loop,
unlinking a node, decrementing the container length by 1, and then
deallocating the node.  If the deallocation fails then in that case
Length (Container) would return a non-zero value, but it would
accurately reflect the fact that there are that many nodes remaining in
the container.

!end comment


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes of Left and Right.  Elements that were in
the Left container are now in the Right container, and vice versa.  The
time complexity of Swap is O(1).

!comment
The Back sentinel node follows the rest of the nodes to their new home
in the other container.


procedure Prepend
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, First (Container), New_Item).  The time
complexity of this operation is O(1).


procedure Append
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Back (Container), New_Item).  The time
complexity of this operation is O(1).
   

procedure Insert
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);
   
If Before equals Null_Iterator, the operation fails and Constraint_Error
is propagated.  If Before does not designate a node that belongs to
Container, program execution is erroneous.  Otherwise it allocates a new
node whose element is initialized to the value New_Item, and inserts it
prior to the node designated by Before.  Iterator designates the
newly-allocated node.  Any exceptions raised during allocation of
internal storage are propagated, and Container is not modified.  The
time complexity of this operation is O(1).


procedure Insert
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Before, New_Item, Iterator), with the
difference that the iterator parameter is omitted.  The time complexity
of this operation is O(1).


procedure Insert
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert (Container, Before, New_Item, Iterator), with the
difference that the element on the newly-allocated node is unitialized,
except for any controlled initialization or default-initialized
components.  The time complexity of this operation is O(1).


procedure Delete
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

If Iterator equals Null_Iterator or Back (Container), the operation does
nothing.  If Iterator does not designate a node that belongs Container,
program execution is erroneous.  Otherwise it removes the node
designated by Iterator from the Container.  The Iterator value returned
designates the successor of the node deleted.  Any exceptions raised
during deallocation are propagated.  The time complexity of this
operation is O(1).
   

procedure Delete_First
  (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise it deletes
the front-most node, as per Delete (Container, First (Container)).  The
time complexity of this operation is O(1).


procedure Delete_Last
  (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise it deletes
the back-most (non-sentinel) node, as per Delete (Container, Last
(Container)).  The time complexity of this operation is O(1).

  
procedure Reverse_Container (Container : in Container_Type);

The nodes in Container are put in reverse order.


generic
   with function "<"
     (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Sort
  (Container : in Container_Type);

The nodes in Container are sorted according to the order specified as
the generic formal less-than operator.  The sort is stable.  Any
exceptions raised during evalution of the less-than operator are
propagated, immediately terminating the iteration.

Here and elsewhere the actual bound to the less-than operator must
behave as a "strict" relation, in the sense that Left must really be
less than Right.  If Left is equal to Right then "<" must return False.


generic
   with function "<"
     (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Merge
  (Container : in out Container_Type;
   Source    : in out Container_Type);

If Source is an alias of Container, the operation has no effect.
Otherwise the elements of Source are spliced into Container.  Both
Container and Source are assumed to be sorted in the order specified as
the generic formal.  Elements in Source that are less than elements in
Container are spliced in before the elements already in Container.
Elements in Source that are equal to or greater than elements in
Container are spliced in after the elements already in Container.  Any
exceptions raised during evaluation of less-than are propagated,
immediately terminating the iteration.


procedure Splice
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   Source    : in out Container_Type);

If Source is an alias of Container, the operation has no effect.  If
Before equals Null_Iterator, the operation fails and Constraint_Error is
propagated.  If Before does not designate a node that belongs to
Container, then program execution is erroneous.  Otherwise, all the
nodes in Source (except for its Back sentinel) are moved onto Container,
just prior to Before.  The length of Container is incremented by the
number of nodes in Source, and the length of Source is set to 0.


procedure Splice
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   Source    : in out Container_Type;
   Iterator  : in     Iterator_Type);

Relinks the node designated by Iterator so that it immediately precedes
Before.

If Source is an alias of Container, then if Iterator equals Back
(Container) or Null_Iterator, or if Iterator equals Before, the
operation has no effect.  If Before equals Null_Iterator, the operation
fails and Constraint_Error is propagated.  If Iterator or Before does
not designate a node in Container, then program execution is erroneous.
Otherwise the node designated by Iterator is moved so that it becomes
the predecessor of Before.

Otherwise if Source is not an alias of Container, then if Iterator
equals Back (Source) or Null_Iterator, the operation has no effect.  If
Before equals Null_Iterator, the operation fails and Constraint_Error is
propagated.  If Iterator does not designate a node in Source, or Before
does not designate a node in Container, then program execution is
erroneous.  Otherwise the node designated by Iterator is moved from the
Source linked-list onto Container, immediately prior to Before.  The
length of Container is incremented, and the length of Source is
decremented.
   

function First
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the front-most node.  If Container
is empty, First returns the value of Back (Container).


function First_Element
  (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, it returns the element on the node designated by
First (Container).


function Last
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the back-most (non-sentinel) node.
If Container is empty, Last returns the value of Back (Container).


function Last_Element
  (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, it returns the element on the node designated by
Last (Container).


function Back
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the sentinel node.


function Element
  (Iterator : Iterator_Type) return Element_Type;

Returns the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

Returns an access value that designates a variable view of the element
stored on the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is propagated.


procedure Replace_Element
  (Iterator : Iterator_Type;
   By       : Element_Type);

Assigns the value By to the element stored on the node designated by
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.


generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to Process with the element on the
node designated by Iterator.  If Iterator equals Null_Iterator, the
operation fails and Constraint_Error is propagated.


function Succ
  (Iterator : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately following
(towards the back) the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is raised.

!comment
The successor of Last is Back, and the successor of Back is First.  If
the list is empty, First, Last, and Back all designate the same node.


function Pred
  (Iterator : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately prior to
(towards the front) the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is raised.

!comment
The predecessor of Back is Last, and the predecessor of First is Back.


procedure Increment (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).


procedure Decrement (Iterator : in out Iterator_Type);

Equivalent to Iterator := Pred (Iterator).


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process with an iterator that
designates each node in Container.  Any exceptions raised during Process
are propagated, immediately terminating the iteration.
   

generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Reverse_Iteration
  (Container : in Container_Type);

Iterates over the nodes in Container as per Generic_Iteration, except
that elements are traversed in reverse order.


generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process for each element in
Container.  Any exception raised during Process is propagated,
immediately terminating the iteration.

!example

There's no need to pass an extra parameter to indicate that iteration
should stop, since that functionality can be built using active
iterators:

   procedure Op (C : in Container_Type) is
      I : Iterator_Type := First (C);
      J : constant Iterator_Type := Back (C);
   begin
      while I /= J loop
         exit when Predicate (Element (I));
         Process (Element (I));
         Increment (I);
      end loop;
   end Op;

!end example
   

generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Reverse_Process_Elements
  (Container : in Container_Type);

Iterates over elements on Container as per Generic_Process_Elements,
with the difference that the elements are traversed in reverse order.

!example

There are a couple of ways to actively iterate (here, in reverse) over a
double list.  One way is to start at the back sentinel and then stop at
first:

   procedure Op (C : in Container_Type) is
      I : Iterator_Type := Back (C);
      J : constant Iterator_Type := First (C);
   begin
      while I /= J loop
         Decrement (I);      
         Process (Element (I));
      end loop;
   end Op;

The other way is to start at last and then "fall off the end" from first
onto the back sentinel.  This works because a list has wrap-around
semantics:

   procedure Op (C : in Container_Type) is
      I : Iterator_Type := Last (C);
      J : constant Iterator_Type := Back (C);
   begin
      while I /= J loop
         Process (Element (I));
         Decrement (I);      
      end loop;
   end Op;

This even works in the other direction: for forward iteration you could
start at back and navigate to last:

   procedure Op (C : in Container_Type) is
      I : Iterator_Type := Back (C);
      J : constant Iterator_Type := Last (C);
   begin
      while I /= J loop
         Increment (I);      
         Process (Element (I));
      end loop;
   end Op;

!end example


This standard specifies a bounded doubly-linked list container.  It
differs from the unbounded doubly-linked list container as follows:

(1) The name of the bounded doubly-linked list container package is
    Ada.Containers.Lists.Double.Bounded.

(2) The package has Pure categorization, not Preelaborate.

(3) The container type is limited, and has a discrimiant, as follows:

        type Container_Type (Size : Natural) is limited private;

    Container_Type is a pass-by-reference type.  The Size discriminant
    specifies the maximum length (number of elements) for the container
    object.

    The container type is not controlled, and therefore the package may
    be instantiated at any nesting level.

(4) The Implementation Requirements are as follows.  Container_Type
    should be implemented as a stack-allocated array, comprising
    exacitly Size node components.  No heap should be used for container
    storage.

(5) There is no sentinel node.

(6) The semantics of Assign differ as follows.  If Source is an alias of
    Target, the operation does nothing.  If the length of Source is
    greater than Target.Size, the operation fails and Constraint_Error
    is propagated.  Otherwise, copies the active elements of Source to
    Target.  Any exceptions raised during element assignment are
    propagated.

(7) The semantics of Clear differ as follows.  Sets the length of the
    container to 0.  The time complexity of this operation is O(1).

!discussion

A bounded linked-list (both doubly-linked and singly-linked) is
implemented as an array, with a storage node as the array component.
Similar to a vector, a bounded linked-list has nodes that are "active"
and nodes that are "inactive."  The active nodes are the ones that we
include in the value returned by Length.  The amount of "free storage"
available to a bounded linked list container object is just Size -
Length number of nodes.

During insertion, a node in the "free list" or "free store" becomes
"active," meaning that it is unlinked from the free list and (re)linked
onto the active list.  There is never any copying of nodes, and the only
element that is ever copied is the one inserted (this is true for all
linked lists).

During deletion, the opposite sequence occurs, and an active node is
simply linked onto the free store of the container, and thus becomes
"inactive."

A bounded linked-list container keeps track of which node is the front
end of the active list and which node is the back end of the active
list.  Therefore Clear for a bounded linked-list container can be
implemented by simply splicing the entire active list onto the free
store.

If a user needs to "finalize" the elements somehow prior to their
"removal" from the bounded linked-list container, then he can use a
passive iterator to first modify each element as appropriate, and then
call Clear.

!end discussion

(8) The operation Swap is omitted.

(9) The semantics of Insert differ as follows:

procedure Insert
  (Container : in out Container_Type;
   Before    : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

If Container.Size equals the length of Container, the operation fails
and Constraint_Error is propagated.  Otherwise, one node of Container's
free storage is reserved and its element is assigned the value New_Item.
If element assignment fails, the exception is propagated and except for
free-store manipulation Container is not modified.  Otherwise the node
is linked onto the active list just prior to Before, and the container
length is incremented by 1.  If Before equals Back (Container) (this is
the same value as Null_Iterator), the node is linked onto the back end
of the active list.  Iterator designates the newly-inserted node.  The
time complexity of this operation is O(1).

(10) The signature and semantics of Splice differ as follows.

procedure Splice
  (Container : in Container_Type;
   Before    : in Iterator_Type;
   Iterator  : in Iterator_Type);

The node designated by Iterator is relinked so that it becomes the
predecessor of Before.  If Iterator equals Back (Container) (which is
the same as Null_Iterator), or if Iterator equals Before, the operation
has no effect.  If Before equals Back (Iterator) (again, this is the
same value as Null_Iterator), the node is relinked at the back end of
the active list.

Note that in a bounded linked-list container, nodes cannot be spliced
across containers.  Hence there is only a single Splice operation, sans
Source parameter.


(11) The semantics of Back differ as follows:

function Back (Container : Container_Type) return Iterator_Type;

Returns the value Null_Iterator.


(12) The signature of Element differs as follows:

function Element
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Element_Type;

Returns the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


(13) The signature of Generic_Element differs as follows:

generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Element_Access;

Returns an access value that designates a variable view of the element
stored on the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is propagated.


(14) The signature of Replace_Element differs as follows:

procedure Replace_Element
  (Container : in Container_Type;
   Iterator  : in Iterator_Type;
   By        : in Element_Type);

Assigns the value By to the element stored on the node designated by
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Any exceptions raised during the
assignment are propagated.


(15) The signature of Generic_Process_Element differs as follows:

generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Container : in Container_Type;
   Iterator  : in Iterator_Type);

Invokes the actual subprogram bound to Process with the element on the
node designated by Iterator.  If Iterator equals Null_Iterator, the
operation fails and Constraint_Error is propagated.


(16) The signature of Succ differs as follows:

function Succ
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately following
(towards the back) the node designated by Iterator.  If Iterator equals
Back (Container), the value First (Container) is returned.  If Iterator
equals Last (Container), the value Back (Container) is returned.


(17) The signature of Pred differs as follows:

function Pred
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately prior to
(towards the front) the node designated by Iterator.  If Iterator equals
Back (Container), the value Last (Container) is returned.  If Iterator
equals First (Container), the value Back (Container) is returned.


(18) The signature of Increment differs as follows:

procedure Increment
  (Container : in     Container_Type;
   Iterator  : in out Iterator_Type);

Equivalent to Iterator := Succ (Container, Iterator).


(19) The signature of Decrement differs as follows:

procedure Decrement
  (Container : in     Container_Type;
   Iterator  : in out Iterator_Type);

Equivalent to Iterator := Pred (Container, Iterator).


!example

Bounded linked-list containers turn out to be extremely useful
especially when used with other containers.  For example, suppose we
have a histogram that counts the frequency of each word in a text file.
We would use the string-key map, that has type String as the key and
Natural as its Element_Type.

After we've exhausted the input, we want to display the words in
frequency order.  However, we can't iterate over the map directly, since
it is ordered by key -- we need to order by element (here, a count).

We can do that very easily by creating a linked-list of map iterators,
and then sorting the linked-list according to the element count.  We
know exactly how big the linked-list needs to be -- it's just the number
of elements in the map.  For example:

   procedure Post_Process
     (Histogram : in String_Integer_Maps.Container_Type) is

      package List_Types is  -- nested instantiation is allowed
        new Ada.Containers.Lists.Double.Bounded
          (Element_Type => String_Integer_Maps.Iterator_Type);

      List : List_Types.Container_Type (Size => Length (Histogram));

      procedure Process (I : in String_Integer_Maps.Iterator_Type) is
      begin
         Append (List, New_Item => I);
      end;

      procedure Populate_List is
        new String_Integer_Maps.Generic_Iteration; -- use default name

   begin -- Post_Process
   
      Populate_List (Histogram);

      ... -- see below

   end Post_Process;   

Here we use the passive iterator for maps to populate the linked-list
container object.

Now that we have the linked-list, we need to sort it, so we need an
order relation.  We want to sort the elements in reverse order, so that
largest count is listed first in the output.  We can define the order
relation like this:

   declare
      function "<" (L, R : String_Integer_Maps.Iterator_Type)
        return Boolean is
      begin
         return Element (L) > Element (R); -- yes
      end;

      procedure Sort is
        new List_Types.Generic_Sort;  -- use "<" default
   begin
      Sort (List);
   end;

We can do better though: suppose that for counts that are equal, we want
to list the items in alphabetic order of the words.  We only have fix
our order relation to compare keys, too:

   declare
      function "<" (L, R : String_Integer_Maps.Iterator_Type)
        return Boolean is
      begin
         if Element (L) = Element (R) then
            return Key (L) < Key (R);  -- compare String
         else
            return Element (L) > Element (R);  -- compare Integer
         end if;
      end;

      procedure Sort is
        new List_Types.Generic_Sort;  -- use "<" default
   begin
      Sort (List);
   end;

To display the results, all we have to do is iterate through the sorted
list:

   declare
      procedure Process  -- prints "n:word" to stdout
        (I : in out String_Integer_Maps.Iterator_Type) is
      begin
         Put (Element (I), Width => 0);   -- the count
         Put (':');
         Put (Key (I));                   -- the word 
         New_Line;
      end;

      procedure Print_Results is
        new List_Types.Generic_Process_Elements;  -- use default name
   begin
      Print_Results (List);
   end;

Et voila!  If we only want to display the top 10 words, then we can use
an active iterator, like this:

   declare
      I : List_Types.Iterator_Type := First (List);
      J : constant List_Types.Iterator_Type := Back (List);
   begin
      Print_Results:
      for Index in 1 .. 10 loop
         exit when I = J;
         
         declare
            K : constant String_Integer_Maps.Iterator_Type :=
              Element (List, I);
         begin
            Put (Element (K), Width => 0);
            Put (':');
            Put (Key (K));
            New_Line;
         end;

         Increment (List, I);
      end loop Print_Results;
   end;

In the example immediately above, we use the Element selector function
to extract the linked-list element.  Here that's just a map iterator, so
in this particular case there is no cost for making a copy of the
element.  However, in general this is not the case (consider our vector
of lists example), and so we need a way to inspect the element in place.
To do that we can use Generic_Process_Element to do the output, which
also allows us to remove the inner declare block:

   declare
      procedure Process
        (I : in out String_Integer_Maps.Iterator_Type) is
      begin
         Put (Element (I), Width => 0);   -- the count
         Put (':');
         Put (Key (I));                   -- the word 
         New_Line;
      end;

      procedure Print_Element is
        new List_Types.Generic_Process_Element; -- use default

      I : List_Types.Iterator_Type := First (List);
      J : constant List_Types.Iterator_Type := Back (List);
   begin
      Print_Results:
      for Index in 1 .. 10 loop
         exit when I = J;
         Print_Element (List, I);         
         Increment (List, I);
      end loop Print_Results;
   end;

In this example, we only required forward iteration, so we could have
used the single-linked bounded list container, which consumes less
storage.

!end example

!discussion

A bounded linked-list container is just implemented using an array in
the normal way:

   type Container_Type (Size : Natural) is limited record
      Nodes : Node_Array (1 .. Size);
      ...
   end record;

An iterator is just an array index, but that self-initializes:

   type Iterator_Type is record
      Index : Natural := 0;
   end record;

   Null_Iterator : constant Iterator_Type := (Index => 0);

I think we need to say somewhere that if the Index component of an
Iterator_Type value lies outside the range of array, then
Constraint_Error is propagated.  For example:

   declare
     L1 : List_Types.Container_Type (1);
     L2 : List_Types.Container_Type (2);

     I : List_Types.Iterator_Type;
   begin
     Append (L2, X);
     Append (L2, Y);
     I := Last (L2);       -- I.Index = 2
     Z := Element (L1, I); -- raise CE
   end;

The other issue is what happens if an iterator "points" to a node in the
free-store part of the nodes array, e.g.

   declare
     L : List_Types.Container_Type (2);
     I : List_Types.Iterator_Type;
   begin
     Append (L, X);   -- L.Nodes (1) = X
     Append (L, Y);   -- L.Nodes (2) = Y
     I := Last (L);   -- I.Index = 2
     Delete_Last (L);
     Z := Element (L, I);  -- L.Nodes (2) is in L's "free store"
   end;

I don't know if this is an "error" or a "feature."  Perhaps it's a
"bounded error"?

!end discussion


The specification of the root of the singly-linked list containers
subsystem is as follows:

package Ada.Containers.Lists.Single is
   pragma Pure;
end Ada.Containers.Lists.Single;

The specification of the unbounded singly-linked list container package
is as follows:

generic

   type Element_Type is private;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Lists.Single.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Prepend
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Append
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Insert_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type);

   procedure Insert_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      New_Item  : in     Element_Type);

   procedure Insert_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      Iterator  :    out Iterator_Type);

   procedure Delete_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type);

   procedure Delete_First
     (Container : in out Container_Type);

   procedure Reverse_Container
     (Container : in out Container_Type);

   generic
      with function "<"
        (Left, Right : Element_Type) return Boolean is <>;
   procedure Generic_Sort (Container : in out Container_Type);

   generic
      with function "<"
        (Left, Right : Element_Type) return Boolean is <>;
   procedure Generic_Merge
     (Container : in out Container_Type;
      Source    : in out Container_Type);

   procedure Splice_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      Source    : in out Container_Type);

   procedure Splice_After
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      Source    : in out Container_Type;
      Pred      : in     Iterator_Type);

   function First
     (Container : Container_Type) return Iterator_Type;

   function First_Element
     (Container : Container_Type) return Element_Type;

   function Last
     (Container : Container_Type) return Iterator_Type;

   function Last_Element
     (Container : Container_Type) return Element_Type;

   function Back
     (Container : Container_Type) return Iterator_Type;

   function Element
     (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access all Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   procedure Replace_Element
     (Iterator : in Iterator_Type;
      By       : in Element_Type);

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   function Succ
     (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment
     (Iterator : in out Iterator_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

private

   --not specified by this standard
   
end Ada.Containers.Lists.Single.Unbounded;


!discussion

The singly-linked list container is implemented as a linked-list of
storage nodes, each of which contains an element and a pointer to the
next (successor) node.  A singly-linked list therefore consumes less
storage than a doubly-linked list, but since a single-link node does not
have a pointer that designates its predecessor, a singly-linked list
container does not support reverse iteration.

An iterator is implemented as an access type that designates a node.
Iterators always designate internal nodes of storage, never elements
directly.  During Swap, Merge, and Splice, nodes can migrate across
containers and so an iterator that designated the node in its old
linked-list container continues to designate that same node in its new
container.

The same as for the doubly-linked list container, insertions and
deletions have constant time complexity.  Note that elements live on
nodes and so when an element is inserted into the linked-list container
really it's a node (having an element component) that is being inserted.
Deletion of an element means that the node containing that element is
first removed from the container by unlinking it from other nodes in the
same linked-list, the container length is decremented, and then the node
that was removed is deallocated.

Iterators that designate nodes in the linked-list container are not
affected by insertion, and the iterators continue to designate the same
nodes, with the same elements.  During deletion the only iterators
affected are iterators that designate the node deleted.

Unlike a doubly-linked list container, a singly-linked list container
does not allocate a sentinel node.  The reason is that a sentinel is
only necessary to support reverse iteration, so that when you fall off
the end of the linked-list onto Back, you're able to backup onto Last.
However, since a singly-linked list doesn't support backing up, no
sentinel is necessary.

!end discussion


Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, an instance of type
Iterator_Type is initialized to the value Null_Iterator.

Implementation Requirements:

The implementation must cache an iterator that designates the node
containing the last element, in order to conform to the requirement that
the functions Last and Append execute in constant time.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

If Source is an alias of Target, the operation does nothing.  Otherwise,
assigns to Target a copy of the elements from Source.  Any exceptions
raised during internal allocation are propagated, and Target is not
modified.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for singly-linked list containers.  If Left and
Right refer to the same container, then the function returns immediately
with the value True.  If Left and Right have different lengths, then the
function returns immediately with the value False.  Otherwise, elements
are compared sequentially using the actual subprogram bound to the
generic formal equality operator.  Any exception raised during
evaluation of the equality operator is propagated, immediately
terminating the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of elements in Container.  The time complexity of
this operation is O(1).


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Sets the length of Container to 0.  Any exceptions raised during
deallocation of internal storage are propagated.


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes of Left and Right.  Elements that were in
the Left vector are now in the Right vector, and vice versa.  The time
complexity of Swap is O(1).


procedure Prepend
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_After (Container, Back (Container), New_Item).  The
time complexity of this operation is O(1).

!example

You can use a single list to implement a stack:

  package Stacks is new Lists.Single.Unbounded (ET);
  use Stacks;

  Stack : Stacks.Container_Type;

  procedure Push (E : in ET) is
  begin
     Prepend (Stack, New_Item => E);
  end;

  function Top return ET is
  begin
     return First_Element (Stack);
  end;

  procedure Pop is
  begin
     Delete_First (Stack);
  end;

Note that we can't use the back end as the top of the stack, because
there's no Delete_Last.  Compare this to the vector example.

!end example


procedure Append
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_After (Container, Last (Container), New_Item).  The
time complexity of Append is O(1).

!example

The fact that Append and Last have unit time complexity means you can
use a single list to implement a queue:

  package Queues is new Lists.Single.Unbounded (ET);
  use Queues;

  Queue : Queues.Container_Type;

  procedure Push (E : in ET) is
  begin
     Append (Queue, New_Item => E);  -- make new foot
  end;

  function Head return ET is
  begin
     return First_Element (Queue);
  end;

  function Foot return ET is
  begin
     return Last_Element (Queue);
  end;

  procedure Pop is
  begin
     Delete_First (Queue); -- make new head
  end;

!end example


procedure Insert_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Allocates a new node whose element is initialized to the value New_Item,
and inserts it immediately following Position.  The Iterator returned
designates the newly-allocated node.  If Position equals Back
(Container) (which is the same as Null_Iterator), the element is
inserted at the front.  Any exceptions raised during allocation are
propagated, and Container is not modified.  If Position does not
designate a node that belongs to Container, program execution is
erroneous.  The time complexity of this operation is O(1).


procedure Insert_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_After (Container, Position, New_Item, Iterator),
with the difference that the iterator parameter is omitted.


procedure Insert_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert_After (Container, Position, New_Item, Iterator),
with the difference that the element of the node is unitialized, except
for any controlled initialization or default-initialized components.


procedure Delete_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type);

Removes the successor of the node designated by Position from Container.
If Position equals Last (Container), the operation has no effect.  If
Position equals Back (Container) (which is the same as Null_Iterator),
the front-most node is deleted.  Any errors raised during deallocation
of internal storage are propagated.  The time complexity of this
operation is O(1).  If Position does not designate a node that belongs
to Container, program execution is erroneous.


procedure Delete_First
  (Container : in out Container_Type);

Equivalent to Delete_After (Container, Back (Container)).  The time
complexity of this operation is O(1).
  

procedure Reverse_Container
  (Container : in out Container_Type);

Reverses the order of nodes in Container.
  

generic
   with function "<"
     (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Sort (Container : in out Container_Type);

Orders the nodes in container according to the relation specified as the
generic formal less-than operator.  The sort is stable.  Any exceptions
raised during evaluation of less-than are propagated, immediately
terminating the iteration.


generic
   with function "<"
     (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Merge
  (Container : in out Container_Type;
   Source    : in out Container_Type);

If Source is an alias of Container, the operation has no effect.
Otherwise the elements of Source are spliced into Container.  Both
Container and Source are assumed to be sorted in the order specified as
the generic formal.  Elements in Source that are less than elements in
Container are spliced in before the elements already in Container.
Elements in Source that are equal to or greater than elements in
Container are spliced in after the elements already in Container.  Any
exceptions raised during evaluation of less-than are propagated,
immediately terminating the iteration.


procedure Splice_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Source    : in out Container_Type);

Moves all the nodes in Source to Container, immediately following
Position.  If Source is an alias of Container, the operation has no
effect.  If Position equals Back (Container) (the same value as
Null_Iterator), the nodes are moved to the front of the list.  The
length of Container is incremented by the number of nodes in Source, and
the length of Source is set to 0.  If Position does not designate a node
that belongs to Container, program execution is erroneous.


procedure Splice_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Source    : in out Container_Type;
   Pred      : in     Iterator_Type);

Relinks the successor of Pred so that it immediately follows Position.

If Source is an alias of Container, then if Pred equals Position, or if
Pred equals Last (Container), the operation has no effect.  If Position
equals Back (Container) (which is the same as Null_Iterator), the
successor of Pred is moved to the front of the list.  If Pred equals
Back (Container), the front-most node is moved.  If Position or Pred
does not designate a node in Container, program execution is erroneous.
   
Otherwise if Source is not an alias of Container, then if Pred equals
Last (Source), the operation does nothing.  If Pred equals Back
(Source), the front-most node of Source is moved to Container.  If
Position equals Back (Container), the node is moved to the front of
Container.  The length of Container is incremented, and the length of
Source is decremented.  If Position does not designate a node in
Container, or Pred does not designate a node in Source, program
execution is erroneous.


function First
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the front-most node.  If Container
is empty, returns Back (Container).


function First_Element
  (Container : Container_Type) return Element_Type;

Equivalent to Element (First (Container)).


function Last
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the back-most node.  If Container is
empty, Last returns Back (Container).  The time complexity of Last is
O(1).


function Last_Element
  (Container : Container_Type) return Element_Type;

Equivalent to Element (Last (Container)).  


function Back
  (Container : Container_Type) return Iterator_Type;

Returns the value Null_Iterator.


function Element
  (Iterator : Iterator_Type) return Element_Type;

Returns the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

Returns an access value that designates a variable view of the element
stored on the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is propagated.


procedure Replace_Element
  (Iterator : in Iterator_Type;
   By       : in Element_Type);

Assigns By to the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to the generic formal Process, with
the element on the node designated by Iterator as the parameter.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.  Any exceptions raised by Process are propagated.


function Succ (Iterator : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately following
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.


procedure Increment (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).

!example

A single list doesn't have an operation to return the predecessor of a
node (such an operation would have O(n) time complexity), but you can
implement that yourself easily enough:

   function Pred
     (Container : Container_Type;
      Iterator  : Iterator_Type) return Iterator_Type is

      Result : Iterator_Type;
   begin
      if Iterator = Back (Container) then

         Result := Last (Container);

      elsif Iterator = First (Container) then

         Result := Back (Container);

      else

         Result := First (Container);

         while Succ (Result) /= Iterator loop
            Increment (Result);
         end loop;

      end if;

      return Result;
   end Pred;

!end example         


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process with an iterator that
designates each element in Container.  Any exceptions raised by Process
are propagated, immediately terminating the iteration.


generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process for each element in
Container.  Any exceptions raised by Process are propagated, immediately
terminating the iteration.


This standard specifies a bounded singly-linked list container.  It
differs from the unbounded singly-linked list container as follows:

(1) The name of the bounded singly-linked list container package is
    Ada.Containers.Lists.Single.Bounded.

(2) The package has Pure categorization, not Preelaborate.

(3) The container type is limited, and has a discrimiant, as follows:

        type Container_Type (Size : Natural) is limited private;

    Container_Type is a pass-by-reference type.  The Size discriminant
    specifies the maximum length (number of elements) for the container
    object.

    The container type is not controlled, and therefore the package may
    be instantiated at any nesting level.

(4) The Implementation Requirements are as follows.  Container_Type
    should be implemented as a stack-allocated array, comprising
    exacitly Size node components.  No heap should be used for container
    storage.

(5) The semantics of Assign differ as follows.  If Source is an alias of
    Target, the operation does nothing.  If the length of Source is
    greater than Target.Size, the operation fails and Constraint_Error
    is propagated.  Otherwise, copies the active elements of Source to
    Target.  Any exceptions raised during element assignment are
    propagated.

(6) The semantics of Clear differ as follows.  Sets the length of the
    container to 0.  The time complexity of this operation is O(1).

(7) The operation Swap is omitted.

(8) The semantics of Insert_After differ as follows:

procedure Insert_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

If Container.Size equals Length (Container), the operation fails and
Constraint_Error is propagated.  Otherwise one node of free storage is
reserved, its element is assigned the value New_Item, and then it is
relinked into the active list immediately following Position.  If
Position equals Back (Container), the element is inserted at the front.
Any exceptions raised during element assignment are propagated, and
except for free-storage manipulation Container is not modified.  The
time complexity of this operation is O(1).


(9) The semantics of Delete_After differ as follows.

procedure Delete_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type);

Relinks the node designated by Position from the active list of
Container to its free store, and decrements the container length.  If
Position equals Last (Container), the operation has no effect.  If
Position equals Back (Container), the front-most node is deleted.  The
time complexity of this operation is O(1).


(10) The signature and semantics of Splice_After differ as follows:

procedure Splice_After
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Pred      : in     Iterator_Type);

Relinks the successor of Pred so that it immediately follows Position.
If Pred equals Position, or if Pred equals Last (Container), the
operation has no effect.  If Position equals Back (Container), the
successor of Pred is moved to the front of the list.  If Pred equals
Back (Container), the front-most node is moved.  The time complexity of
this operation is O(1).


(11) The signature of Element differs as follows:

function Element
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Element_Type;

Returns the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


(12) The signature of Generic_Element differs as follows:

generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Element_Access;

Returns an access value that designates a variable view of the element
stored on the node designated by Iterator.  If Iterator equals
Null_Iterator, the operation fails and Constraint_Error is propagated.


(13) The signature of Replace_Element differs as follows:

procedure Replace_Element
  (Container : in Container_Type;
   Iterator  : in Iterator_Type;
   By        : in Element_Type);

Assigns By to the element stored on the node designated by Iterator.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.


(14) The signature of Generic_Process_Element differs as follows:

generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Container : in Container_Type;
   Iterator  : in Iterator_Type);

Invokes the actual subprogram bound to the generic formal Process, with
the element on the node designated by Iterator as the parameter.  If
Iterator equals Null_Iterator, the operation fails and Constraint_Error
is propagated.  Any exceptions raised by Process are propagated.


(15) The signature of Succ differs as follows:

function Succ
  (Container : Container_Type;
   Iterator  : Iterator_Type) return Iterator_Type;

Returns an iterator that designates the node immediately following
Iterator.  Succ (Container, Back (Container) equals First (Container),
and Succ (Container, Last (Container)) equals Back (Container).


(16) The signature of Increment differs as follows:

procedure Increment
  (Container : in     Container_Type;
   Iterator  : in out Iterator_Type);

Equivalent to Iterator := Succ (Container, Iterator).


The specification of the root of the map containers subsystem is as
follows:

package Ada.Containers.Maps is
   pragma Pure;
end Ada.Containers.Maps;


The specification of the root of the hashed map containers subsystem is
as follows:

package Ada.Containers.Maps.Hashed is
   pragma Pure;
end Ada.Containers.Maps.Hashed;


The specification of the hashed map container is as follows:

generic

   type Key_Type is private;

   type Element_Type is private;

   with function Hash
     (Key : Key_Type) return Integer'Base is <>;

   with function Is_Equal_Key
     (Left, Right : Key_Type) return Boolean is "=";

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Maps.Hashed.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Replace
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert_Sans_Resize
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert_Sans_Resize
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Replace_Sans_Resize
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Insert_Sans_Resize
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Delete
     (Container : in out Container_Type;
      Key       : in     Key_Type);

   procedure Delete
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   function Is_In
     (Key       : Key_Type;
      Container : Container_Type) return Boolean;

   function Find
     (Container : Container_Type;
      Key       : Key_Type) return Iterator_Type;

   function Element
     (Container : Container_Type;
      Key       : Key_Type) return Element_Type;

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Equal_Range
     (Container : in Container_Type;
      Key       : in Key_Type);

   function Size (Container : Container_Type) return Natural;

   procedure Resize
     (Container : in out Container_Type;
      Size      : in     Natural);

   function First
     (Container : Container_Type;
      Index     : Positive) return Iterator_Type;

   function Back (Container : Container_Type) return Iterator_Type;

   function Index
     (Container : Container_Type;
      Key       : Key_Type) return Positive;

   function Succ (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment
     (Iterator : in out Iterator_Type);

   function Key (Iterator : Iterator_Type) return Key_Type;

   generic
      type Key_Access is access constant Key_Type;
   function Generic_Key 
     (Iterator : Iterator_Type) return Key_Access;

   function Is_Equal_Key
     (Left, Right : Iterator_Type) return Boolean;

   function Is_Equal_Key
     (Left  : Iterator_Type;
      Right : Key_Type) return Boolean;

   function Is_Equal_Key
     (Left  : Key_Type;
      Right : Iterator_Type) return Boolean;

   function Element (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access all Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   procedure Replace_Element
     (Iterator : in Iterator_Type;
      By       : in Element_Type);

   generic
      with procedure Process
        (Key     : in     Key_Type;
         Element : in out Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Key     : in     Key_Type;
         Element : in out Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

private

   -- not specified by this standard

end Ada.Containers.Maps.Hashed.Unbounded;

In addition, the hashed map container package has one generic child
procedure:

generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Maps.Hashed.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

pragma Preelaborate  --TODO: verify this with ARG
  (Ada.Containers.Maps.Hashed.Unbounded.Unchecked_Modification);
  

Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, objects of type
Iterator_Type are default-initialized to the value Null_Iterator.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

Assigns the key/elements pairs in Source to Target.  If Source is an
alias of Target, the operation does nothing.  Any exceptions raised
during internal allocation or deallocation are propagated.

!comment

Here and elsewhere we might decide to impose the req'mt that if there's
an exception during Assign, then Target is not modified.  We can make
that guarantee for a list, but it's not clear whether we can or even
should make it for hashed containers, too.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for hashed maps.  If Left and Right refer to the
same container, then the function returns immediately with the value
True.  If Left and Right have different lengths, then the function
returns immediately with the value False.  Otherwise, elements (and
*only* elements -- keys do not participate in the computation of
container equality) are compared in canonical order using the equality
operator supplied as the generic actual.  Any exception raised during
evaluation of element equality is propagated, immediately terminating
the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of key/element pairs in the container.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Sets the length of the container to 0.  The size of the container is not
affected.  Any exceptions raised during deallocation are propagated.

!comment
This doesn't delete the buckets array -- it just deletes the nodes
hanging off the buckets array.  If you want to delete the buckets array
too (thus setting the map's size to 0), then you can Swap with a
temporary map object.  (Map objects are default-initialized with a
zero-length buckets array.)


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes and buckets array of Left and Right.
Key/element pairs that were in the Left vector are now in the Right
vector, and vice versa.  The time complexity of Swap is O(1).


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

If Length (Container) equals Size (Container), then Container is resized
to some larger value as per Resize.  The position of the new node in the
buckets array is computed from the hash value of Key and Size
(Container).  The actual subprogram bound to Is_Equal_Key is used to
compare Key to the key of each node in the list at that index of the
buckets array.  If a key matches, Success returns False and Iterator
designates the (first) node with the matching key.  Otherwise, a new
node is allocated whose key and element are initialized to Key and
New_Item, respectively, and inserted at the head of the list.  Success
returns True and Iterator designates the newly-inserted node.  Any
exceptions raised during allocation are propagated, and Container is not
modified.  The time complexity of this operation is O(1) average case.


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item, Iterator, Success), with
the difference that the iterator and success parameters are omitted.


procedure Replace
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item), with the difference
that if Key is already in the map, then New_Item is assigned to the
element associated with that key.  Any exceptions raised during the
assignment are propagated.


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts the Key into Container as per Insert (Container, Key, New_Item,
Iterator, Success), with the difference that a newly-inserted element is
uninitialized, except for any controlled initialization or
default-initialized components.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts the Key/New_Item pair into Container as per Insert (Container,
Key, New_Item, Iterator, Success), with the difference that there is no
resize prior to the insertion proper.  If the container size is 0 the
operation fails and Constraint_Error is propagated.

!comment

This allows a developer to resize the container at the time most
suitable for his application, independently of the time of insertion.
It also allows the developer explicit control of the load factor.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_Sans_Resize (Container, Key, New_Item, Iterator,
Success), with the difference that the Iterator and Success parameters
are omitted.

!example

It's often the case that you know apriori the total number of elements
you intend to insert into the map.  Under these circumstances you should
always Resize the map first, and then perform the insertions.  This
avoids any automatic rehashing that occurs during normal insertion to
preserve the load factor.  For example:

   procedure Op (N : Natural) is
      Map : Map_Types.Container_Type;  -- Size = 0
   begin
      Resize (Map, Size => N);  -- Size >= N

      for I in 1 .. N loop
         Insert_Sans_Resize  -- no resizing necessary
           (Container => Map,
            Key       => Get_Key (I),
            New_Item  => Get_Element (I));
      end loop;

      ...
   end;

!end example   
         

procedure Replace_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_Sans_Resize (Container, Key, New_Item), with the
difference that if the Key is already in the map, then New_Item is
assigned to the element associated with that key.  Any exceptions raised
during the assignment are propagated.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Equivalent to Insert_Sans_Resize (Container, Key, New_Item, Iterator,
Success), with the difference that a newly-inserted element is
uninitialized.


procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes the node that matches Key.  If Length (Container) equals 0, then
Delete does nothing.  Otherwise the index is computed from the hash
value of Key and Size (Container).  Any exception raised during
invokation of Hash is propagated.  The nodes in the list at that index
of the buckets array are compared to Key using Is_Equal_Key.  The node
that matches Key is removed from the list and then deallocated.  Any
exceptions raised by Is_Equal_Key or during the deallocation are
propagated.

!comment

Here and elsewhere, even if deallocation fails, Container must remain
consistent.  Here its state must reflect the fact that the node was
removed from the map, even if it wasn't successfully deallocated.


procedure Delete
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

If Iterator equals Null_Iterator, the operation has no effect.  If
Iterator does not designate a node that belongs to Container, program
execution is erroneous.  Otherwise the buckets index is computed from
the hash value of the key on the node designated by Iterator and Size
(Container).  Any exception raised during invokation of Hash is
propagated.  The node is removed from the map and then deallocated.  Any
exceptions raised by during the deallocation are propagated.  The
Iterator returned designates the node that followed Iterator prior to
the deletion; if this is the end of the list then Null_Iterator is
returned.


function Is_In
  (Key       : Key_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Key) /= Null_Iterator.


function Find
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

If Length (Container) equals 0, then the function returns immediately
with the value Null_Iterator.  Otherwise the buckets index is computed
from the hash value of Key and the size of Container.  If the list at
that index is empty, then Null_Iterator is returned.  Otherwise the list
is traversed and the key of each node on the list is compared to Key
using Is_Equal_Key.  If Is_Equal_Key returns True, an iterator
designating the first node (really, the only node) with the matching key
is returned.  Otherwise, if no node in the list matches Key, it returns
Null_Iterator.
   

function Element
  (Container : Container_Type;
   Key       : Key_Type) return Element_Type;

Equivalent to Element (Find (Container, Key)).
   

generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Key       : in Key_Type);

Attempts to find a matching key as per Find (Container, Key).  If a
matching key is found, it invokes the generic actual bound to Process
with the element associated with the key as the parameter.

!example

You could do this with Find:

   procedure Op (M : in Map_Subtype; K : in Key_Subtype) is
      I : Iterator_Type := Find (M, K);
   begin
      if I /= Null_Iterator then
         Do_Something (Element (I));
      end if;
   end;

but this locution happens often enough that it might as well be a single
operation:

   procedure Op is
      new Generic_Equal_Range (Do_Something);

Its presence here also provides compatability with the same operation in
the multimap, where it allows you to not have to walk the sublist of
equal keys manually.

!end example


function Size (Container : Container_Type) return Natural;

Returns the length of the internal buckets array.  The size of a
default-initialized map container is 0.


procedure Resize
  (Container : in out Container_Type;
   Size      : in     Natural);

If Size (Container) is greater than or equal to Size, the operation has
no effect.  Otherwise, a new buckets array is allocated whose length is
a least the value specified.  If the allocation fails, the exception is
propagated, and Container is not modified.  Nodes in the container are
then rehashed from the old buckets array onto the new one.  If Hash
fails, the exception is propagated, and the nodes that were moved onto
the new buckets array are lost.


function First
  (Container : Container_Type;
   Index     : Positive) return Iterator_Type;

If Index is outside the range 1 .. Size (Container), then
Constraint_Error is propagated.  Otherwise, an iterator that designates
the node at the list at Index is returned.  If there is no list at that
Index, then Null_Iterator is returned.


function Back (Container : Container_Type) return Iterator_Type;

Returns the value Null_Iterator.


function Index
  (Container : Container_Type;
   Key       : Key_Type) return Positive;

If Size (Container) equals 0, the operation fails and Constraint_Error
is propagated.  Otherwise, returns the value of the expression Hash
(Key) mod Size (Container).

!comment
We could relax the precondition, and simply return 1 if size is 0.


function Succ (Iterator : Iterator_Type) return Iterator_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an iterator that
designates the successor node in the same list.  If Iterator designates
the last node of the list, it returns the value Null_Iterator.


procedure Increment (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).


function Key (Iterator : Iterator_Type) return Key_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns the key component
of the designated node.


generic
   type Key_Access is access constant Key_Type;
function Generic_Key
  (Iterator : Iterator_Type) return Key_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a constant view of the key component of the node
designated by Iterator.


function Is_Equal_Key
  (Left, Right : Iterator_Type) return Boolean;

Equivalent to Is_Equal_Key (Key (Left), Key (Right)).
  

function Is_Equal_Key
  (Left  : Iterator_Type;
   Right : Key_Type) return Boolean;

Equivalent to Is_Equal_Key (Key (Left), Right).   


function Is_Equal_Key
  (Left  : Key_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Is_Equal_Key (Left, Key (Right)).


function Element (Iterator : Iterator_Type) return Element_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns the element
component of the designated node.


generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the element component of the node
designated by Iterator.


procedure Replace_Element
  (Iterator : in Iterator_Type;
   By       : in Element_Type);

Assigns the value By to the element stored on the node designated by
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propated.  Any exceptions raised during assignment
are propagated.


generic
   with procedure Process
     (Key     : in     Key_Type;
      Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to Process with the key and element
of the node designated by Iterator.  If Iterator equals Null_Iterator,
the operation fails and Constraint_Error is propagated.  Any exceptions
raised by Process are propagated.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Generic_Iteration calls the actual subprogram bound to Process once for
each node in the Container.  Any exceptions raised during Process are
propagated, immediately terminating the iteration.


generic
   with procedure Process
     (Key     : in     Key_Type;
      Element : in out Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Calls the actual subprogram bound to Process once for each key/element
pair in Container.  Any exception raised during Process is propagated,
immediately terminating the iteration.


generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Maps.Hashed.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the key component on the node
designated by Iterator.

!comment

It would be easy to break a map abstraction if keys were modified,
especially if it were easy to do so, when the modification might be
accidental.  However, under some circumstances it may make sense to
modify a key object in a benign way, such that it doesn't change the
value returned by Is_Equal_Key.

!example

The simplest and fastest way to iterate over all the elements in the map
is to use one of the passive iterators:

   procedure Op (Map : in Map_Types.Container_Type) is

      procedure Process (I : in Map_Types.Iterator_Type) is ...;

      procedure Iterate is
         new Generic_Iteration; -- accept default
   begin
      Iterate (Map);
   end;

You could implement this function yourself, by iterating over the list
in each bucket of the hash table:

   procedure Op (Map : in Map_Types.Container_Type) is

      procedure Process (I : in Map_Types.Iterator_Type) is ...;

      I : Map_Types.Iterator_Type;

   begin

      Iterate:
      for Index in 1 .. Size (Map) loop 

         I := First (Map, Index);  -- head of list at buckets[index]

         while I /= Null_Iterator loop
            Process (I);
            Increment (I);
         end loop;

      end loop Iterate;

   end Op;

If you want to walk the entire map in the more traditional way, then you
can do it like this:

   procedure Op (Map : in Map_Types.Container_Type) is

      Index : Positive := 1;
      Iter  : Iterator_Type;

      I : Positive := 1;

   begin

      if Length (Map) = 0 then
         return;
      end if;

      Find_First_Iter:
      loop
         Iter := First (Map, Index);
         exit when Iter /= Null_Iterator;
         Index := Index + 1;
      end loop Find_First_Iter;

      Iterate:
      loop

         Process (Iter);  -- process I'th 

         I := I + 1;

         exit when I > Length (Map);

         Increment (Iter);

         while Iter = Null_Iterator loop
            Index := Index + 1;
            Iter := First (Map, Index);
         end loop;

      end loop Iterate;

   end Op;

This latter locution allows you to walk a hashed container while you're
simultaneously walking another container.

Generic algorithms are typically written to work with iterators this way:

   generic
      type IT is private;
      with function Succ (I : IT) return IT is <>;
      with procedure Process (I : IT) is <>;
      with function "=" (L, R : IT) return Boolean is <>;
   procedure Generic_Algorithm (First, Back : in IT);

The implementation would look something like this:   

   procedure Generic_Algorithm (First, Back : in IT) is
      I : IT := First;
   begin
      while I /= Back loop
         ...
         Process (I);
         ...
         I := Succ (I);
      end loop;
   end Generic_Algorithm;
         
The benefit is that this algorithm will work with any "sequence of
items," which just means any container with an iterator having the
requisite properties, as specified in the generic formal region.  The
virtue of this approach is that it abstracts-away the container.  The
generic algorithm above (and others like it) works with all the
containers in the library -- it even works for built-in array types.

To make this work with a map, we need only to override the default
successor operation for map iterators and keep around some context:

   procedure Op (Map : in Map_Types.Container_Type) is

      Index : Positive := 1;
      I     : Positive := 1;

      function Succ (Iter : Iterator_Type) return Iterator_Type is
         Result : Iterator_Type := Map_Types.Succ (Iter);
      begin
         I := I + 1;

         if I > Length (Map) then
            return Result;
         end if;

         while Result = Null_Iterator loop
            Index := Index + 1;
            Result := First (Map, Index);
         end loop;

         return Result;
      end Succ;

      procedure Process (Iter : Iterator_Type) is ...;

      procedure Algorithm is
         new Generic_Algorithm (Iterator_Type); -- accept defaults

      First_Iter : Iterator_Type;      

   begin -- Op

      if Length (Map) = 0 then
         return;
      end if;

      Find_First_Iter:
      loop
         First_Iter := First (Map, Index);
         exit when First_Iter /= Null_Iterator;
         Index := Index + 1;
      end loop Find_First_Iter;

      Algorithm (First => First_Iter, Back => Null_Iterator);

   end Op;


!end example


The specification of the root of the string-key hashed map containers
subsystem is as follows:

package Ada.Containers.Maps.Hashed.Strings is
   pragma Pure;
end Ada.Containers.Maps.Hashed.Strings;

The specification of the unbounded string-key hashed map container
differs from the unbounded hashed map container in the following manner:

(1) There is no formal Key_Type, as the key type is String.  The generic
    formal region and package name are as follows:

generic

   type Element_Type is private;

   with function Hash
     (Key : String) return Integer'Base is <>;

   with function Is_Equal_Key
     (Left, Right : String) return Boolean is "=";

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Maps.Hashed.Strings.Unbounded is ...;


(2) Everywhere where the formal type Key_Type is specified, it is
    systematically replaced by type String.

(3) The Generic_Key function is omitted.

(4) The following function is defined:

function Key_Length (Iterator : Iterator_Type) return Natural;

Equivalent to Key (Iterator)'Length.

(5) The generic child procedure Unchecked_Modification is omitted.


The specification of the root of the wide_string-key hashed map containers
subsystem is as follows:

package Ada.Containers.Maps.Hashed.Wide_Strings is
   pragma Pure;
end Ada.Containers.Maps.Hashed.Wide_Strings;

The specification of the unbounded wide_string-key hashed map container
differs from the unbounded string-key hashed map container in the
following manner:

(1) The name of the package is
    Ada.Containers.Maps.Hashed.Wide_Strings.Unbounded;

(2) Everywhere where the formal type String is specified, it is
    systematically replaced by type Wide_String.

!example

Hashed maps with type String as the key are nearly ubiquitous.  The
canonical example is of course the word-frequency problem, in which
"words" (using some suitable definition of delimiter) are counted as
they are scanned in the input stream.

We can solve this problem easily using a map with string as the key and
subtype Natural as the element:

   with Ada.Containers.Hash_String;

   package Wordcount_Maps is
      new Ada.Containers.Maps.Hashed.Strings.Unbounded
        (Element_Type => Natural, 
         Hash         => Ada.Containers.Hash_String); -- case-sensitive

   Map : Wordcount_Maps.Container_Type;

Here we've specified the hash function for strings provided by the
library.  The scanning phase looks like this:
   
   Open (File, In_File, Name);

   Scan_Lines:
   while not End_Of_File (File) loop

      Get_Line (File, Line, Line_Last);

      Line_First := Line'First;

      Scan_Line:
      loop

         Find_Token (Line (Line_First .. Line_Last), ...);

         exit when Word_Last = 0;

         --THIS IS THE OP WE CARE ABOUT:
         Insert (Word => Line (Word_First .. Word_Last));

         Line_First := Word_Last + 1;

      end loop Scan_Line;

   end loop Scan_Lines;

Now all we have to do is implement Insert.  That function looks like
this:

   procedure Insert (Word : String) is

      Iter    : Wordcount_Maps.Iterator_Type;
      Success : Boolean;

      type Count_Access is access all Natural;

      function To_Access is
        new Wordcount_Maps.Generic_Element (Count_Access);

   begin -- Insert

      Insert
        (Container => Map,
         Key       => To_Lower (Word),
         New_Item  => 0,  -- yes
         Iterator  => Iter,
         Success   => Success);

      declare
         N : Natural renames To_Access (Iter).all;  -- the element
      begin
         N := N + 1;
      end;

   end Insert;

Map (and set) insertion works conditionally.  It searches the container
(here, in the list of the buckets array at the index computed from the
hash-value of the key), to determine whether there is an equal key
already in the map.

Note that in the example above, the New_Item parameter has the value 0.
This is deliberate.  What happens is that if the word is already in the
map, then the insertion "fails" in the sense that no new node is
allocated.  Rather, Insert reports the fact that the key was already in
the map (by returning the value False for Success), and an iterator that
designates the node with the matching key.

But not inserting a new node is exactly the behavior we want.  In the
case of a word already in the map, the iterator returned designates an
existing word/count pair, whose count is non-zero.  When we alias the
count object, we simply increment its value.

However, the word might not be in the map, in which case the insertion
"succeeds," which means a new node is inserted whose element is
initialized to the value of New_Item, which here is 0.  Iterator
designates the newly-inserted element (really, it designates the node
containing that key/element pair).  When we alias the element, the count
has the value 0, and so by incrementing it the count gets set to the
value 1.

Conditional insertion is a necessary feature of any efficient map
abstraction.  It makes no sense to search for the element (via Find,
say) to determine whether it's in the map, and if it's not in the map
call a separate operation to insert it.  This would be horribly
inefficient because the lookup done by insert would only duplicate the
lookup just done by the search.

To dump the contents of the map, you can just use one of the passive
iterators:

   declare
      procedure Process
        (Word  : in     String;
         Count : in out Natural) is
      begin
         Put (Word); Put (':'); Put (Count); New_Line;
      end;

      procedure Dump is
        new Wordcount_Maps.Generic_Process_Elements; -- "Process"
  begin
     Dump (Map);
  end;

This would display the words in their order in the hashed map.  That's
probably not what you want (especially for a well-performing hash table,
which would scatter keys everywhere), which is to display them in order
by frequency.  I showed how to do that in the doubly-linked bounded list
example.  What we did was to populate the list with iterators that
designate the map entries, and then sort the list:

   declare
      List : List_Subtype;

      procedure Process (I : Wordcount_Maps.Iterator_Type) is
      begin
         Append (List, New_Item => I);
      end;

      procedure Populate_List is
         new Wordcount_Maps.Generic_Iteration;  -- "Process"
   begin
      Populate_List (Map);
      ... -- see doubly-linked bounded list
   end;

As with all containers, it's usually simpler and more efficient to use
the passive iterators if you're going to traverse all the elements in
the container.  The library is often used by making a lot of little
on-the-fly instantiations, as in the examples above.
         
!end example


!example

When a client connects to a streaming media server to play a video, the
server opens the file and then transmits frames to the client.
Ultra-efficient file I/O is usually done by memory-mapping the sections
on disk.  Typically, a server maintains its own file cache, so that many
clients streaming the same file can share the memory-mapped sections.

When the client request comes in, the server must look up the file by
name in order to see if it's in cache.  If it's in cache, then we can
increment a reference count.  If it's not, we create some context for
the file and create a new entry for it in the cache.

Suppose the context type looks like this:

  type Context_Type is limited record
     File      : File_Type;
     Ref_Count : Natural;
     ...;
  end record;

  type Context_Access is access Context_Type;
     
Our cache is just a map, indexed by file name:

   package File_Cache_Types is
      new Ada.Containers.Maps.Hashed.Strings.Unbounded
        (Element_Type => Context_Access,
         Hash         => Ada.Containers.Hash_String_Case_Insensitive,
         Is_Equal_Key => Ada.Containers.Equal_String_Case_Insensitive);

   File_Cache : File_Cache_Types.Container_Type;

The naive way to implement the lookup is:

   procedure Setup (Name : in String) is

      Iter : File_Cache_Types.Iterator_Type :=
         File (File_Cache, Key => Name);

      Context : Context_Access;

   begin -- Setup

      if Iter = Null_Iterator then

         Context := new Context_Type;
         Context.Ref_Count := 0;
         ... -- init Context

         Insert (File_Cache, Key => Name, New_Item => Context);

      else

         Context := Element (Iter);

      end if;

      Context.Ref_Count := Context.Ref_Count + 1;
      ... -- use Context

   end Setup;

The problem is that we're duplicating work: we first searched for the
file context in the cache, and if it wasn't found we insert a new entry,
which just searches again.  The correct way to do this is as follows:

   procedure Setup (Name : in String) is

      Iter         : File_Cache_Types.Iterator_Type;
      Not_In_Cache : Boolean;
      Context      : Context_Access;

   begin

      Insert
        (Container => File_Cache,
         Key       => Name,
         New_Item  => null,  -- yes
         Iterator  => Iter,
         Success   => Not_In_Cache);

      if Not_In_Cache then

         pragma Assert (Element (Iter) = null);

         Context := new Context_Type;
         Context.Ref_Count := 0;
         ... -- init context

         Replace_Element (Iter, By => Context);

      else

         Context := Element (Iter);

      end if;

      Context.Ref_Count := Context.Ref_Count + 1;
      ... -- use context

   end Setup;

Here we make an insertion attempt, by trying to insert a null context
into the map.  If it's already in the map, then the insertion fails, but
that's just what we want to happen, because we wish to share the file
already in cache.  If it's not in the map, the insertion succeeds, by
creating a slot for this file (the context is null), which we just fill
in with a newly-allocated context object.

!end example   


The specification of the root of the sorted map containers subsystem is
as follows:

package Ada.Containers.Maps.Sorted is
   pragma Pure;
end Ada.Containers.Maps.Sorted;


The specification of the sorted map container is as follows:

generic

   type Key_Type is private;

   type Element_Type is private;

   with function "<"
     (Left, Right : Key_Type) return Boolean is <>;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Maps.Sorted.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Replace
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type);

   procedure Insert
     (Container : in out Container_Type;
      Key       : in     Key_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      Key       : in     Key_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      Key       : in     Key_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Delete
     (Container : in out Container_Type;
      Key       : in     Key_Type);

   procedure Delete
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   procedure Delete_Sans_Increment
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   procedure Delete_First (Container : in out Container_Type);

   procedure Delete_Last (Container : in out Container_Type);

   function Is_In
     (Key       : Key_Type;
      Container : Container_Type) return Boolean;

   function Find
     (Container : Container_Type;
      Key       : Key_Type) return Iterator_Type;

   function Element
     (Container : Container_Type;
      Key       : Key_Type) return Element_Type;

   function Lower_Bound
     (Container : Container_Type;
      Key       : Key_Type) return Iterator_Type;

   function Upper_Bound
     (Container : Container_Type;
      Key       : Key_Type) return Iterator_Type;

   generic
      with procedure Process
        (Element : in out Element_Type) is <>;
   procedure Generic_Equal_Range
     (Container : in Container_Type;
      Key       : in Key_Type);

   function First (Container : Container_Type) return Iterator_Type;

   function First_Key (Container : Container_Type) return Key_Type;

   function First_Element (Container : Container_Type) return Element_Type;

   function Last (Container : Container_Type) return Iterator_Type;

   function Last_Key (Container : Container_Type) return Key_Type;

   function Last_Element (Container : Container_Type) return Element_Type;

   function Back (Container : Container_Type) return Iterator_Type;

   function Succ
     (Iterator : Iterator_Type) return Iterator_Type;

   function Pred
     (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment (Iterator : in out Iterator_Type);

   procedure Decrement (Iterator : in out Iterator_Type);

   function Key (Iterator : Iterator_Type) return Key_Type;

   generic
      type Key_Access is access constant Key_Type;
   function Generic_Key
     (Iterator : Iterator_Type) return Key_Access;

   function "<"
     (Left, Right : Iterator_Type) return Iterator;

   function "<"
     (Left  : Iterator_Type;
      Right : Key_Type) return Boolean;

   function "<"
     (Left  : Key_Type;
      Right : Iterator_Type) return Boolean;

   function Element (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access all Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   procedure Replace_Element
     (Iterator : Iterator_Type;
      By       : Element_Type);

   generic
      with procedure Process
        (Key     : in     Key_Type;
         Element : in out Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Reverse_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Key     : in     Key_Type;
         Element : in out Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

   generic
      with procedure Process
        (Key     : in     Key_Type;
         Element : in out Element_Type) is <>;
   procedure Generic_Reverse_Process_Elements
     (Container : in Container_Type);

private

   -- not specified by this standard

end Ada.Containers.Maps.Sorted.Unbounded;


The following generic child subprogram is defined:

generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Maps.Sorted.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

pragma Preelaborate -- TODO: check this
  (Ada.Containers.Maps.Sorted.Unbounded.Unchecked_Modification);


!discussion

A sorted map orders keys in the order implied by the relational operator
passed as the generic actual.  It is implemented as a balanced tree.
The time complexity of insertion, deletion, and find is O(log N) in the
worst case.

When a sorted map container object elaborates, a sentinel node belonging
to the container is allocated automatically.  Its key and element are
uninitialized, except for any controlled initialization or
default-initialized components.  It is not included in the count of
elements in the container, and it cannot be deleted.

!end discussion


Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, objects of type
Iterator_Type are default-initialized to the value Null_Iterator.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

Assigns the key/element pairs in Source to Target.  If Source is an
alias of Target, the operation does nothing.  Any exceptions raised
during internal allocation or deallocation are propagated.

Note that the sentinel doesn't count as an element, so it is never
copied.  The sentinel is not affected by Assign, and so following Assign
the Target has the same sentinel as it did prior to Assign.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for sorted maps.  If Left and Right refer to the
same container, then the function returns immediately with the value
True.  If Left and Right have different lengths, then the function
returns immediately with the value False.  Otherwise, elements (and
*only* elements -- keys do not participate in the computation of
container equality) are compared sequentially using the equality
operator supplied as the generic actual.  Any exception raised during
evaluation of element equality is propagated, immediately terminating
the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of key/element pairs in the container.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Sets the length of the container to 0.  Any exceptions raised during
deallocation are propagated.


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes Left and Right.  Key/element pairs that
were in the Left map are now in the Right map, and vice versa.  The time
complexity of Swap is O(1).

    
procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts the pair Key/New_Item in Container.  The Key is compared to
other keys already in the map using the subprogram bound to the generic
formal "<" operator.  If the key is already in the map, Success is False
and Iterator designates the node containing the equivalent key.
Otherwise, a new node is allocated and initialized to the values Key and
New_Item, Success returns True and Iterator designates the
newly-allocated node.  Any exceptions raised during evaluation of the
relational operator or during allocation are propagated, and Container
is not modified.  The time complexity of insertion is O(log N) worst
case.

The equality operator "=" for Key_Type is never used.  Instead, a pair
of keys K1 and K2 match if they are "equivalent," which is defined as
"not (K1 < K2) and not (K2 < K1)".


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item, Iterator, Success), with
the difference that the iterator and success parameters are omitted.


procedure Replace
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item), with the difference
that if the Key is already in the map, then New_Item is assigned to the
element associated with that key.  Any exceptions raised during the
assignment are propagated.
   

procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts a new key/item pair as per Insert (Container, Key, New_Item,
Iterator, Success), with the difference that the element of the
newly-inserted node is uninitialized, except for any controlled
initialization or default-initialized components.


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Equivalent to Insert (Container, Key, New_Item, Iterator, Success), with
the addition of a Position parameter, which specifies a hint about where
to insert the new key.  If Position equals Null_Iterator, this operation
is equivalent to the Position-less version of Insert.  If Position does
not designate an iterator that belongs to Container, program execution
is erroneous.  If the hint is useful, the time complexity of this
operation is amortized O(1).


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Equivalent to Insert (Container, Position, Key, New_Item, Iterator,
Success), with the difference that the element of the new node is
uninitialized.


procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes the node that matches Key.  Any exceptions raised by "<" are
propagated, and Container is not modified.  Any exception raised during
deallocation is propagated.  The time complexity of this operation is
O(log N), worst case.


procedure Delete
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

If Iterator equals Null_Iterator or Back (Container), the operation does
nothing.  If Iterator does not designate a node that belongs to
Container, program execution is erroneous.  Otherwise, the node
designated by Iterator is removed from the tree.  Any exception raised
during deallocation is propagated.  The iterator value returned
designates the successor of the node deleted.


procedure Delete_Sans_Increment
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

Equivalent to Delete (Container, Iterator), with the difference that the
iterator value returned equals Null_Iterator.
   

procedure Delete_First (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise the node
designated by First (Container) is deleted.


procedure Delete_Last (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise the node
designated by Last (Container) is deleted.


function Is_In
  (Key       : Key_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Key) /= Null_Iterator.
   

function Find
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Finds the node whose key is equivalent to Key, and returns an iterator
that designates that node.  If there are no equivalent keys, the
iterator value Null_Iterator is returned.  Any exceptions raised during
evaluation of "<" are propagated.  The time complexity of this operation
is O(log N) in the worst case.


function Element
  (Container : Container_Type;
   Key       : Key_Type) return Element_Type;

Equivalent to Element (Find (Container, Key)).
   

function Lower_Bound
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest key
not less than Key.  If there is no key already in the map that is
equivalent to or greater than to Key, then it returns Back (Container).
   

function Upper_Bound
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest key
greater than Key.  If there is no key already in the map that is greater
than Key, then it returns Back (Container).


generic
   with procedure Process
     (Element : in out Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Key       : in Key_Type);

Attempts to find a matching key as per Find (Container, Key).  If a
matching key is found, it invokes the generic actual bound to Process
with the element associated with the key as the parameter.


function First (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
key.  If Container is empty, it returns the iterator value Back
(Container).  This operation has O(1) time complexity.


function First_Key (Container : Container_Type) return Key_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, returns the key on the node designated by First
(Container).


function First_Element (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, returns the element on the node designated by First
(Container).


function Last (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the node containing the greatest
key.  If Container is empty, it returns the iterator value Back
(Container).  This operation has O(1) time complexity.


function Last_Key (Container : Container_Type) return Key_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, returns the key on the node designated by Last
(Container).


function Last_Element (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
raised.  Otherwise, returns the element on the node designated by Last
(Container).


function Back (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the sentinel node.  This operation
has O(1) time complexity.


function Succ (Iterator : Iterator_Type) return Iterator_Type;

Returns the successor of the node designated by Iterator.  If Iterator
equals Null_Iterator, the operation fails and Constraint_Error is
propagated.

!comment

A sorted map has wrap-around semantics similar to an unbounded
doubly-linked list.  Therefore the successor of Last is Back, and the
successor of Back is First.  If Container is empty, then the iterator
values returned by First, Last, Back all designate the sentinel.


function Pred (Iterator : Iterator_Type) return Iterator_Type;

Returns the predecessor of the node designated by Iterator.  If Iterator
equals Null_Iterator, the operation fails and Constraint_Error is
propagated.

!comment

Pred is symmetric to Succ.  Therefore the predecessor of Back is Last,
and the predecessor of First is Back.


procedure Increment (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).


procedure Decrement (Iterator : in out Iterator_Type);

Equivalent to Iterator := Pred (Iterator).


function Key (Iterator : Iterator_Type) return Key_Type;

Returns the value of the key component of the node designated by
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.


generic
   type Key_Access is access constant Key_Type;
function Generic_Key
  (Iterator : Iterator_Type) return Key_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a constant view of the the key component of the node
designated by Iterator.


function "<"
  (Left, Right : Iterator_Type) return Iterator;

Equivalent to Key (Left) < Key (Right).


function "<"
  (Left  : Iterator_Type;
   Right : Key_Type) return Boolean;

Equivalent to Key (Left) < Right.


function "<"
  (Left  : Key_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Key < Key (Right).   


function Element (Iterator : Iterator_Type) return Element_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns the element
component of the designated node.


generic
   type Element_Access is access all Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the the element component of the node
designated by Iterator.


procedure Replace_Element
  (Iterator : Iterator_Type;
   By       : Element_Type);

Assigns the value By to the element stored on the node designated by
Iterator.  If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propated.


generic
   with procedure Process
     (Key     : in     Key_Type;
      Element : in out Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to Process with the key and element
of the node designated by Iterator.  If Iterator equals Null_Iterator,
the operation fails and Constraint_Error is propagated.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Generic_Iteration calls the actual subprogram bound to Process once for
each node in the Container (exluding the sentinel, of course).  Any
exceptions raised during Process are propagated, immediately terminating
the iteration.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Reverse_Iteration
  (Container : in Container_Type);

Iterates through the nodes in Container as per Generic_Iteration, with
the difference that the nodes are traversed in reverse order.


generic
   with procedure Process
     (Key     : in     Key_Type;
      Element : in out Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Calls the actual subprogram bound to Process once for each key/element
pair in Container (excluding the sentinel, of course).  Any exception
raised during Process is propagated, immediately terminating the
iteration.


generic
   with procedure Process
     (Key     : in     Key_Type;
      Element : in out Element_Type) is <>;
procedure Generic_Reverse_Process_Elements
  (Container : in Container_Type);

Iterates through the nodes in Container as per Generic_Process_Elements,
with the difference that the elements are traversed in reverse order.


generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Maps.Sorted.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the key component of the node
designated by Iterator.


!example

In a POSIX OS that supports real-time signals, the OS will deliver a
payload-carrying signal to the app.  In the case of a socket, when I/O
completes asynchronously, the OS delivers an RT signal that specifies
the file descriptor of the socket whose I/O completed.

The problem is that I typically declare the socket as part the
representation of some abstraction that gets allocated dynamically, and
therefore I have no idea which object the socket belonged to, so I have
no idea how to act on the information the OS is providing me.

The abstraction I have in mind looks like this:

   package Sessions is

      type Session_Type (<>) is limited private;

      function Session_Access is access all Session_Type;

      function Setup_Session return Session_Type;

      procedure Play
        (Session : access Session_Type;
         Stream  : in     String);
      ...
      procedure IO_Completion (Session : access Session_Type);

   private

      type Session_Type is limited record
         Socket : Socket_Type;
         ...;
      end Session_Type;

   end Sessions;


What I need to do is correlate the file descriptor reported in the RT
signal to a session object.  With a map it's almost trivial.  In the
body I can instantiate the map like this:

   function "<" (L, R : Session_Access) return Boolean is
   begin
      return L.all'Address < R.all'Address;
   end;

   package FD_Map_Types is
      new Ada.Containers.Maps.Sorted.Unbounded
        (Key_Type     => C.int,
         Element_Type => Session_Access); -- accept "<" default

Now I can declare a map object in the body:

   package Sessions is
      ...
      FD_Map : FD_Map_Types.Container_Type;
      
When I allocate a new session object, this opens the socket.  A socket
object has a selector function to return its file descriptor.  I use
this as the key to insert the session object into the map:

   function Setup_Session return Session_Access is
     Session : constant Session_Access := new Session_Type;
   begin
      Open (Session.Socket, ...);

      Insert
        (Container => FD_Map,
         Key       => FD (Session.Socket),
         New_Item  => Session);
      ...
      return Session;
   end;

Now that the session object has inserted itself into the map, I can use
map lookup to find that session when I receive a signal.  Something
like:

   procedure Handle_Signal (Siginfo : in Siginfo_Type)
      FD   : constant C.int := Siginfo.FD;
      Iter : constant Iterator_Type := Find (FD_Map, Key => FD);
   begin
      if Iter /= Null_Iterator then
         IO_Completion (Element (Iter));
      end if;
   end Handle_Signal;

and then the session object reacts to the I/O completion accordingly.

Signals come in fast and furious, and I need to handle them quickly.
Searching a sorted map has O(log N) time complexity, which is ideal
because I might have hundreds or even thousands of session objects in
existence.  (As you can probably I guess, I'm a server writer.)

!end example


!example

As usual if you need to iterate over all the items in a sorted map, you
should use a passive iterator.  It's faster and less error-prone.
However, let's assume you need to perform active iteration.  It's much
simpler to (actively) iterate over all the elements in a sorted map than
in a hashed map, because in a sorted container every node is reachable
from any other node.  For example:

   procedure Op (Map : in Map_Types.Container_Type) is
      I : Iterator_Type := First (Map);
      J : constant Iterator_Type := Back (Map);
   begin
      while I /= J loop
         Process (I);
         Increment (I);
      end loop;
   end loop;

To use our little generic algorithm from the earlier example, there's
nothing special we need to do to instantiate it:

   procedure Op (Map : in Map_Subtype) is

      procedure Process (I : in Iterator_Type) is ...;

      procedure Algorithm is
         new Generic_Algorithm (Iterator_Type); -- accept defaults
   begin
      Algorithm (First (Map), Back (Map));
   end;
         
!end example


The specification of the root of the string-key sorted map containers
subsystem is as follows:

package Ada.Containers.Maps.Sorted.Strings is
   pragma Pure;
end Ada.Containers.Maps.Sorted.Strings;

The specification of the unbounded string-key sorted map container
differs from the unbounded sorted map container in the following manner:

(1) There is no formal Key_Type, as the key type is String.  The generic
    formal region and package name are as follows:

generic

   type Element_Type is private;

   with function "<"
     (Left, Right : String) return Boolean is <>;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Maps.Sorted.Strings.Unbounded is ...;


(2) Everywhere where the formal type Key_Type is specified, it is
    systematically replaced by type String.

(3) The Generic_Key function is omitted.

(4) The following function is defined:

function Key_Length (Iterator : Iterator_Type) return Natural;

Equivalent to Key (Iterator)'Length.

(5) The generic child procedure Unchecked_Modification is omitted.


The specification of the root of the wide_string-key sorted map containers
subsystem is as follows:

package Ada.Containers.Maps.Sorted.Wide_Strings is
   pragma Pure;
end Ada.Containers.Maps.Sorted.Wide_Strings;

The specification of the unbounded wide_string-key sorted map container
differs from the unbounded string-key sorted map container in the
following manner:

(1) The name of the package is
    Ada.Containers.Maps.Sorted.Wide_Strings.Unbounded.

(2) Everywhere where the formal type String is specified, it is
    systematically replaced by type Wide_String.


!example

In the RTSP protocol, requests are sent to a server in (clear) text.  To
create a session, a client connects to the server and sends it a SETUP
request, e.g.

SETUP rtsp://mheaney/thematrix.avi RTSP/1.0
Transport: ...

Each RTSP session has a "session id," which is a random string of
characters at least 8 characters long.  When a SETUP request doesn't
specify a session id, this is interpreted to mean that the client wishes
to create a new session.

On the server side, it allocates a session object (described above), and
generates a session id for it.  The representation of the session object
looks like this:

   type Session_Type is limited record
      Id : String (1 .. 8);
      ...;
   end record;

And the session constructor looks like:   

   function Setup_Session return Session_Access is
      Session : constant Session_Access := new Session_Type;
   begin
      Generate_Id (Session.Id);
      ... -- see below
   end;

The server responds by including the session id in the response:

RTSP/1.0 200 OK
Session: HAiye8-r

And thereafter, a client sends requests to a session by specifying a
session id header:

PLAY rtsp://mheaney/thematrix.avi RTSP/1.0
Range: npt=101.42-
Session: HAiye8-r

The server-side problem is this.  When the server receives the request
from the client, it parses the request and looks for a session id.  The
problem then becomes finding the session object that is associated with
that unique id.  There might very well be hundreds of session objects,
so whatever method we use has to run fast.  (The is a real-time
streaming server, and RTSP request/response overhead must be kept to a
minimum.)

What we do is declare a string-key map object that uses the session id
as the key, and a Session_Access as the element, like this:

   package Id_Maps is
      new Ada.Containers.Maps.Sorted.Strings.Unbounded
        (Element_Type => Session_Access);
        -- accept "<" default for type String

   Id_Map : Id_Maps.Container_Type;
   use Id_Maps;

When the session is allocated, we insert the id/session pair into the
map like this:

   function Setup_Session return Session_Access is
      Session : constant Session_Access := new Session_Type;
   begin
      Generate_Id (Session.Id);

      Insert
        (Container => Id_Map,
         Key       => Session.Id,
         New_Item  => Session);
      ...
      return Session;         
   end;


When a client issues a request, we parse out the session id, and then
forward the command to the session object associated with that session
id key:

   procedure Play
     (Session_Id  : in     String;
      NPT_Range   : in     NPT_Range_Type;
      RTSP_Status :    out RTSP_Status_Type) is

      Iter : constant Iterator_Type :=
        Find (Id_Map, Key => Session_Id);

      Session : Session_Access;
   begin
      if Iter = Null_Iterator then
         RTSP_Status := RTSP.Session_Not_Found;
         return;
      end if;

      Session := Element (Iter);

      Play (Session, NPT_Range, RTSP_Status);
   end;

Both insertion and find execute fast: O(log N) in the worst case.
Having these kinds of performance guarantees is important in real-time
programs.

Actually, this example could have been written just as easily using the
string-key hashed map.  The only difference would be the instantiation
of the map container package, but otherwise the rest of the code would
be identical.

!end example


!example

The Id map we instantiated in the previous example takes type
Session_Access as the element type.  The constructor (repeated here)
looks like this:

   function Setup_Session return Session_Access is
      Session : constant Session_Access := new Session_Type;
   begin
      Generate_Id (Session.Id);

      Insert
        (Container => Id_Map,
         Key       => Session.Id,
         New_Item  => Session);
      ...
      return Session;         
   end;

Here we first allocate a session object, and then separately (in Insert)
allocate a node (in the container) whose element is the pointer to the
session object.  If you think about it, this means there are actually
two separate allocations: one for the element (here, a session object),
and another for the node.

If a container were to support element types that were limited, then we
could rewrite the example like this:

   package Id_Maps is
      new Ada.Containers.Maps.Sorted.Strings.Unbounded_Limited
        (Element_Type => Session_Type);   -- not an access type

   Id_Map : Id_Maps.Container_Type;

That would allow use to allocate just a node, and then implement the
constructor to return a pointer that designates the session object
element on the node itself:
   
   function To_Access is
      new Id_Maps.Generic_Element (Session_Access);

   function Setup_Session return Session_Access is

      I : Id_Maps.Iterator_Type;
      B : Boolean;

      Id : Id_Subtype;
      Session : Session_Access;  -- no allocation here

   begin

      Generate_Id (Id);

      Insert
        (Container => Id_Map,
         Key       => Id,  -- specify key only; no element
         Iterator  => I,
         Success   => B;

      Session := To_Access (I);  -- point to node's element
      ...
      return Session;         

   end Session_Setup;

It doesn't make any difference to the caller of Setup_Session how the
session object it returns is allocated.  Indeed the whole point of that
function is to hide that very detail.

In the interest of keeping things small, this API does not specify any
containers that support limited elements.  But here you get a taste of
how containers that do support limited elements would work.  It's nice
because we can push the responsibility for "deallocating" the element
onto the container (when the node is deleted, it contains the element,
so the element goes away too).  Compare this to our other examples,
which require explicit action by the client to deallocate the object
(because the container element is just an access object that designates
the "real" object).

!end example   


!example

We have been silent about the operation of Generate_Id, which makes a
session id for us comprising a sequence of 8 random characters.  One of
our requirements for a session id is that it must be unique among all
the sessions currently being streamed by this server.

Even if we use a random number generator to synthesize characters, we
still must check to ensure that this session id is unique.  The obvious
way is to use Find to see if it's in the already:

   procedure Generate_Id (Id : out Id_Subtype) is
      Iter : Id_Maps.Iterator_Type;
   begin
      loop
         Synthesize_Random_String (Id);
         Iter := Find (Id_Map, Key => Id);
         exit when Iter = Null_Iterator;  -- good: not found
      end loop;
   end Generate_Id;

The constructor for session objects generates a unique session id, and
then uses the id as the key when inserting the new session object:

   function Setup_Session return Session_Access is

      I : Id_Maps.Iterator_Type;
      B : Boolean;

      Id : Id_Subtype;
   begin
      Generate_Id (Id);

      Insert
        (Container => Id_Map,
         Key       => Id,
         Iterator  => I,
         Success   => B;
      ...
   end Setup_Session;
         
This works, but we can do better.  The problem is that Insert duplicates
the work done just earlier by Find, when checking the newly-synthesized
id for uniqueness.

Find is a bit of a sledgehammer: it tells us that the key isn't already
in the map, but it doesn't tell us anything else.  What would like to
ask the container is, if the key isn't in the map, can you tell me who
its neighbor would be?

The function we're interested in is called Lower_Bound, which searches
the container for the smallest key in the map not less than some key.
It satisfies the invariant that

   Key <= Lower_Bound (Container, Key)

The result of Lower_Bound is an iterator that designates the node that
matches Key, if indeed Key is already in the map, or an iterator that
designates its successor, if Key is not in the map.  To disambiguate
which case we have we only need to make a simple test:

   Iter := Lower_Bound (Container, Key);

   if Key < Iter then
      ... -- no match: Key is not in the map
   else
      ... -- match: Key is equivalent to Key (Iter)
   end if;

Let's rewrite our Generate_Id procedure so that it returns this extra
information:

   procedure Generate_Id
     (Id   : out Id_Subtype;
      Hint : out Id_Maps.Iterator_Type) is
   begin
      loop
         Synthesize_Random_String (Id);
         Iter := Lower_Bound (Id_Map, Key => Id);
         exit when Hint = Back (Id_Map);  -- no match
         exit when Id < Hint;             -- no match
      end loop;
   end Generate_Id;

Now we can rewrite our constructor to use this new information during
insertion:

   function Setup_Session return Session_Access is

      I : Id_Maps.Iterator_Type;
      B : Boolean;

      Id   : Id_Subtype;
      Hint : Id_Maps.Iterator_Type;
   begin
      Generate_Id (Id, Hint);

      Insert
        (Container => Id_Map,
         Position  => Hint,
         Key       => Id,
         Iterator  => I,
         Success   => B;

      pragma Assert (B);
      pragma Assert (Succ (I) = Hint);
      ...
   end Setup_Session;

Here we use the insert-with-hint procedure, which specifies where to
being searching for a matching Id.  Since Hint is the result of
Lower_Bound, we know the hint is useful and therefore the insertion has
amortized constant time.  It's hard to beat that!

This is a great because we can test whether insert will succeed, and
then reuse the results our test so that the insertion itself has
essentially no cost.  Thus we have a way to first search for a key and
then insert it later, without incuring any penalty.

!end example


!example

When a client issues a play request, he can specify the time from which
play begins.  This lets him jump to any position in the file and play
from that point.  Let's assume a video frame index is implemented as a
sorted set, with elements that look like this:

   0   9  34  42  50 78  85 ...

where the numbers above represent the time of the leading edge of each
video frame in the file.

If the play request specifies a time, have to find the frame that "goes
with" that time, which means the frame whose leading edge comes at or
before the time specified.

This is kind of like a floor function.  You might think you could use
Lower_Bound to do it, like this:

   function Floor (Time : Time_Type) return Iterator_Type is
   begin
      return Lower_Bound (Video_Index, Key => Time);
   end;

This would work if the key matched a value already in the index, for
example:

   Floor (42) = Lower_Bound (VI, 42) = 42

The problem is if the key isn't in the index.  Lower_Bound returns the
smallest key in the container equal to or greater than a key, e.g.

   Floor (45) = Lower_Bound (VI, 45) = 50

But this isn't what we want.  The "floor" of 45 is 42, not 50.

The solution is to use Upper_Bound, which returns the smallest key in the
container greater than a key, and then back up one position:

   function Floor (Time : Time_Type) return Iterator_Type is
   begin
      return Pred (Upper_Bound (VI, Key => Time));
   end;

This works for all key values:

   Floor (42) = Pred (UB (VI, 42)) = Pred (50) = 42
   Floor (45) = Pred (UB (VI, 45)) = Pred (50) = 42

And now all is well.  Note that it doesn't matter if you specify some
large key value that is greater than every key in the set.  In that case
Upper_Bound returns Back, and the Pred of Back is Last, which is just
what we want.

!end example


!example

When we create a session object, we insert a pointer to the session
object in the Id_Map.  The complementary problem is how to handle
deletion of the session object.  Suppose we have a function like this:

   procedure Free (X : in out Session_Access);

What's the best way to remove the object from the map?  Since the
session knows its own Id, it can use the key-form of Delete:

   procedure Free (X : in out Session_Access) is
   begin
      if X /= null then
         Delete (Id_Map, Key => X.Id);
         Deallocate (X);
      end if;
   end;

This takes care of removing the session from the map.  But consider
this: to delete a node, you must find the node, and here that means
traversing the internal tree from its root downward to find the node
whose key is equivalent to Key (here, the session id).

Another option for us is to use the iterator-form of Delete.  This is
going to more efficient, because no tree traversal is necessary to find
the node.  You already have the node -- it's what is designated by the
iterator.

What we can do is cache the iterator returned by Insert as part of the
state of the session object:

   function Setup_Session return Session_Access is
      Session : constant Session_Access := new Session_Type;
      Success : Boolean;
   begin
      Generate_Id (Session.Id);

      Insert
        (Container => Id_Map,
         Key       => Session.Id,
         New_Item  => Session,
         Iterator  => Session.Id_Map_Iter,
         Success   => Success);

      pragma Assert (Success);
      pragma Assert (Key (Session.Id_Map_Iter) = Session.Id);
      pragma Assert (Element (Session.Id_Map_Iter) = Session);
      ...

      return Session;         
   end Setup_Session;

Now we can implement Free this way:

   procedure Free (X : in out Session_Access) is
   begin
      if X /= null then
         Delete (Id_Map, Iterator => X.Id_Map_Iter);  -- faster
         Deallocate (X);
      end if;
   end;

This turns out to be a very common idiom.  In the body of a package that
declares a type, you declare a set or map container to keep track of
instances of the type.  As part of its representation, the type includes
an iterator that designates the node that contains this instance.  When
the object is finalized, it deletes itself from the container.

!end example

!example

When the server shuts down, it tears down all the session objects.  But
where are the session objects?  They're all in the Id_Map, of course!
Given the Free operation defined above, we can implement a session
shutdown operation like this:

   Id_Map : Id_Map_Types.Container_Type;
   ...

   procedure Shutdown_Sessions is
      Session : Session_Access;
   begin
      while not Is_Empty (Id_Map) loop
         Session := First_Element (Id_Map);
         Free (Session);  -- removes this session from id_map
      end loop;
   end Shutdown_Sessions;

Since a session object removes itself from the map during Free, this
decrements the length of the map, which means that the loop iteration
will eventually terminate.

In the examples we've seen, the session object inserts itself into the
map during the constructor function Setup_Session, and deletes itself
during the destructor operation Free.  If the type is controlled,
another possibility is to do the insertion during Initialize, and the
deletion during Finalize.  This technique would work even for
stack-allocated objects.

!end example

!example

Let's pretend Free doesn't remove the designated session object from the
map, but rather has its traditional semantics of merely deallocating the
object.  To shutdown all the sessions, we could do this instead:

   Id_Map : Id_Map_Types.Container_Type;
   ...

   procedure Shutdown_Sessions is

      procedure Process
        (Id      : in     String;
         Session : in out Session_Access) is
      begin
         Free (Session);
      end;

      procedure Free_Sessions is
         new Id_Map_Types.Generic_Process_Elements; -- accept default

   begin -- Shutdown_Sessions
   
      Free_Sessions (Id_Map);

      Clear (Id_Map);
      
   end Shutdown_Sessions;

The passive iterator visits all the sessions in the map and Free's them.
That leaves us with a map with all of its elements set to null.  We then
Clear the map, which sets its length to 0.

Clear is probably going to be faster than deletion one-element-at-a-time
as in our previous example.  The reason is that a sorted map is
implemented as a balanced tree, and when you delete a single item, the
tree must be fixed-up to keep it balanced.

With Clear, however, it can simply deallocate all the nodes in one fell
swoop.  It doesn't need to rebalance the tree because the tree itself
is being deleted.

!end example

!example

Suppose we have a key declared this way:

   type Key_Type is record
      X : Integer;
      Y : Integer;
   end record;

It's going to be used to instantiate a map container.  The sorted key
relation is defined as follows:

   function "<" (L, R : Key_Type) return Boolean is
   begin
      return L.X < R.X;
   end;

Note that the key relation only depends on the value of the X component.
We instantiate the map in the normal way:

   package Map_Types is
      new Ada.Containers.Maps.Sorted.Unbounded
        (Key_Type,
         Element_Type);
         -- assume "<" is directly visible

   Map : Map_Types.Container_Type;

Now let's insert a key into the map:

   procedure Insert_42_1776 (I : out Iterator_Type) is
      K : Key_Type := (X => 42, Y => 1776);
      B : Boolean;
   begin
      Insert (Map, K, I, B);
   end;

Now let's suppose we need to change the Y component of our key.  One way
to do that would be to delete it from the map, change the value, and
then (re)insert it, like this:

   procedure Insert_42_2001 (I : in out Iterator_Type) is
      K : constant Key_Type := Key (I);
      E : constant Element_Type := Element (I);
      B : Boolean;
   begin
      Delete_Sans_Increment (Map, I);  
      K.Y := 2001;      -- modify key
      Insert (Map, K, E, I, B);
   end;

Here we used the Delete_Sans_Increment op, which is more efficient than
Delete because it doesn't perform a tree traversal to find the
successor of the node deleted.

However, we can do better.  The issue in the fragment above it that to
insert a new key/element pair, you must traverse the tree starting from
its root, in order to find the correct insertion position.  Let's use
the normal form of delete, and then use hint-form of insert:

   procedure Insert_42_2001_v2 (I : in out Iterator_Type) is
      K : constant Key_Type := Key (I);
      E : constant Element_Type := Element (I);
      B : Boolean;
   begin
      Delete (Map, I);  -- I now designates successor
      K.Y := 2001;      -- modify key
      Insert (Map, I, K, E, I, B);  -- supply hint
   end;

The Delete operation returns the successor of the node deleted.  We can
use this information when we re-insert the key into the map.  Since the
iterator I really does designate the successor of key K, the cost of
insertion is less, because we don't have to perform a tree traversal.

However, we can do better still.  What we did was make a copy of the
key/element in the map, then delete the node containing the original
key/element pair, then turn around an immediately insert the key/element
back into the map.  This is silly.  What we really wanted to do was
modify the key object in place.

The library provides such a parachute function.  It's the generic child
procedure Unchecked_Modification.  It returns an access value that
designates a variable view of the key:

   with Ada.Containers.Maps.Sorted.Unbounded.Unchecked_Modification;

   type Key_Access is access all Key_Type;
   for Key_Access'Storage_Size use 0;

   package Map_Types is ...;

   function Modify_Key is
      new Map_Types.Unchecked_Modification (Key_Type);

Now that we have this modifier, we can rewrite our little op to be much
more efficient:

   procedure Insert_42_2001_v3 (I : in out Iterator_Type) is
      K : Key_Type renames Modify_Key (I).all;
   begin
      K.Y := 2001; -- that's all!
   end;

Clearly, modifying keys indiscriminantly could break the map.  However,
sometimes we have the need to modify a key, and here it's perfectly
safe, because we only change Y, not X.  So this is a benign change as
far as the map is concerned.

!end example


The specification of the root of the multimaps subsystem is as follows:

package Ada.Containers.Multimaps is
   pragma Pure;
end Ada.Containers.Multimaps;


The specification of the root of the hashed multimap containers
subsystem is as follows:

package Ada.Containers.Multimaps.Hashed is
   pragma Pure;
end Ada.Containers.Multimaps.Hashed;


The specification of the unbounded hashed multimap container differs
from the unbounded hashed (unique-key) map container as follows:

(1) The name of the package is
    Ada.Containers.Multimaps.Hashed.Unbounded.

(2) The signature and semantics of the operations named Insert change as
    follows:

procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

If Length (Container) equals Size (Container), then the size is
increased as per Resize.  The position of the new node in the buckets
array is computed from the hash value of Key and Size (Container).  The
actual subprogram bound to Is_Equal_Key is used to compare Key to the
key of each node in the list at that index of the buckets array.  If the
predicate returns True, then a new node is allocated with the first
matching node as its successor; otherwise, a new node is allocated at
the head of the list.  Iterator designates the newly-inserted node.  Any
exceptions raised during allocation are propagated, and Container is not
modified (except for any possible resizing).


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item, Iterator), with the
difference that the iterator parameter is omitted.


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Inserts the Key into Container as per Insert (Container, Key, New_Item,
Iterator), with the difference that the element is uninitialized, except
for any controlled initialization or default-initialized components.

(3) The signature and semantics of the operations named
    Insert_Sans_Resize change as follows:

procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Inserts the Key/New_Item pair into Container as per Insert (Container,
Key, New_Item, Iterator), with the difference that there is no resize
prior to the insertion proper.  If Size (Container) equals 0, the
operation fails and Constraint_Error is propagated.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_Sans_Resize (Container, Key, New_Item, Iterator),
with the difference that the iterator parameter is omitted.
   

procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert_Sans_Resize (Container, Key, New_Item, Iterator),
with the difference that the element is uninitialized.

    
(4) The operations Replace and Replace_Sans_Resize are omitted.

(5) The semantics of Delete (Container, Key) change as follows:

procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes all the nodes that match Key.  If Length (Container) equals 0,
then Delete does nothing.  Otherwise the buckets array index is computed
from the hash value of Key and Size (Container).  Any exception raised
during invokation of Hash is propagated.  The nodes in the list at that
index are compared to Key using Is_Equal_Key.  Any exceptions raised by
Is_Equal_Key or during the deallocation are propagated, immediately
terminating the iteration.

(6) The generic child procedure is defined as follows:

generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Multimaps.Hashed.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

pragma Preelaborate  --OK?
  (Ada.Containers.Multimaps.Hashed.Unbounded.Unchecked_Modification);

This operation has the same semantics as the corresponding hashed map
procedure.

!example  

Find returns an iterator that designates the first node in the subrange
of matching keys.  We can then walk the sublist to find all the matching
keys:

   procedure Do_Something
     (M : Map_Subtype;
      K : Key_Subtype) is

      I : Iterator := Find (M, K);
   begin
      if I = Null_Iterator then  -- no matching keys
         return;
      end if;
      
      loop
         Process (Element (I));
         Increment (I);
         exit when I = Null_Iterator;
         exit when not Is_Equal_Key (I, Key);
      end loop;
   end;

Of course, a simpler way to do this is to use Generic_Equal_Range:

   procedure Do_Something is
      new Multimap_Types.Generic_Equal_Range (Process);

This avoids having to walk the sublist manually.

!end example

!example

There's no predefined operation for counting the number of matching
keys, but we can implement such a function easily enough:

   function Count
     (Map : in Multimap_Types.Container_Type;
      Key : in Key_Subtype) return Natural is

      Result : Integer'Base := 0;
      
      I : Iterator_Type := Find (Map, Key);

   begin -- Count

      if I /= Null_Iterator then 
      
         loop
            Result := Result + 1;
            Increment (I);
            exit when I = Null_Iterator;
            exit when not Is_Equal_Key (I, Key);
         end loop;

      end if;

      return Result;
      
   end Count;

Compare this to the sorted multimap example.   

!end example

   
The specification of the root of the string-key hashed multimap containers
subsystem is as follows:

package Ada.Containers.Multimaps.Hashed.Strings is
   pragma Pure;
end Ada.Containers.Multimaps.Hashed.Strings;

The specification of the unbounded string-key hashed multimap container
differs from the unbounded hashed multimap container in the following
manner:

(1) There is no formal Key_Type, as the key type is String.  The generic
    formal region and package name are as follows:

generic

   type Element_Type is private;

   with function Hash
     (Key : String) return Integer'Base is <>;

   with function Is_Equal_Key
     (Left, Right : String) return Boolean is "=";

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Multimaps.Hashed.Strings.Unbounded is ...;


(2) Everywhere where the formal type Key_Type is specified, it is
    systematically replaced by type String.

(3) The Generic_Key function is omitted.

(4) The following function is defined:

function Key_Length (Iterator : Iterator_Type) return Natural;

Equivalent to Key (Iterator)'Length.

(5) The generic child procedure Unchecked_Modification is omitted.


The specification of the root of the wide_string-key hashed multimap
containers subsystem is as follows:

package Ada.Containers.Multimaps.Hashed.Wide_Strings is
   pragma Pure;
end Ada.Containers.Multimaps.Hashed.Wide_Strings;

The specification of the unbounded wide_string-key hashed multimap
container differs from the unbounded string-key hashed multimap
container in the following manner:

(1) The name of the package is
    Ada.Containers.Multimaps.Hashed.Wide_Strings.Unbounded;

(2) Everywhere where the formal type String is specified, it is
    systematically replaced by type Wide_String.

    
The specification of the root of the sorted multimap containers
subsystem is as follows:

package Ada.Containers.Multimaps.Sorted is
   pragma Pure;
end Ada.Containers.Multimaps.Sorted;


The specification of the unbounded sorted multimap container differs
from the unbounded sorted (unique-key) map as follows:

(1) The name of the package is
    Ada.Containers.Multimaps.Sorted.Unbounded.

(2) The signature and semantics of the Insert operations differ as
    follows:

procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Inserts the pair Key/New_Item in Container.  The Key is compared to
other keys already in the container using the subprogram bound to the
generic formal "<" operator.  The Key/New_Item pair is inserted after
equivalent keys already in the container.  Any exceptions raised during
evaluation of the relational operator or during allocation are
propagated, and Container is not modified.

The equality operator "=" for Key_Type is never used.  Instead, a pair
of keys K1 and K2 match if they are "equivalent," which is defined as
"not (K1 < K2) and not (K2 < K1)".


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, Key, New_Item, Iterator), with the
difference that the iterator parameter is omitted.


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Inserts a new key/item pair as per Insert (Container, Key, New_Item,
Iterator), with the difference that the element of the newly-inserted
node is uninitialized (except for any controlled initialization or
default-initialized components).


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert (Container, Key, New_Item, Iterator), with the
addition of a Position parameter, which specifies a hint about where to
begin searching for equivalent keys.  If Position equals Null_Iterator,
this operation is equivalent to the Position-less version of Insert.  If
Position does not designate a node that belongs to Container, program
execution is erroneous.

Insert first assumes Position is a potential successor.  If Position
equals Back (Container) or Key is less than or equal to the key
designated by Position, and Position equals First (Container) or the
predecessor of Position is less than or equivalent to Key, then the
Key/New_Item pair is inserted immediately prior to Position.

If Position is not a successor, then Insert assumes Position is a
potential predecessor.  If Position is less than or equivalent to Key,
and Key is less than or equivalent to the successor of Position, then
the Key/New_Item pair is inserted immediately following Position.

Otherwise, the Key/New_Item pair is inserted as per the Position-less
version of Insert.


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert (Container, Position, Key, New_Item, Iterator),
with the difference that the element of the new node is uninitialized
(except for any controlled initialization or default-initialized
components).


(3) The semantics of Delete (Container, Key) differs as follows:

procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes all the nodes whose keys are equivalent to Key.  Any exceptions
raised by "<" or during deallocation are propagated.


(4) The semantics of Find change as follows.

Finds the front-most node whose key is equivalent to Key, and returns an
iterator that designates that node.  If there are no equivalent keys,
the iterator value Null_Iterator is returned.  Any exceptions raised
during evaluation of "<" are propagated.  The time complexity of this
operation is O(log N) worst case.


(5) The generic child procedure is defined as follows:

generic
   type Key_Access is access all Key_Type;
function Ada.Containers.Multimaps.Sorted.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Key_Access;

pragma Preelaborate  --TODO: verify this with ARG
  (Ada.Containers.Multimaps.Sorted.Unbounded.Unchecked_Modification);

This operation has the same semantics as the corresponding hashed
multimap procedure.


!example

Here's how to count the equivalent keys in a sorted multimap:

   function Count
     (Map : in Multimap_Types.Container_Type;
      Key : in Key_Subtype) return Natural is

      Result : Integer'Base := 0;
      
      I : Iterator_Type := Lower_Bound (M, K);
      J : constant Iterator_Type := Upper_Bound (M, K);

   begin -- Count

      while I /= J loop
         Result := Result + 1;
         Increment (I);
      end loop;

      return Result;
      
   end Count;

Compare this to the hashed multimap example.   

!end example


The specification of the root of the string-key sorted multimap containers
subsystem is as follows:

package Ada.Containers.Multimaps.Sorted.Strings is
   pragma Pure;
end Ada.Containers.Multimaps.Sorted.Strings;

The specification of the unbounded string-key sorted multimap container
differs from the unbounded sorted multimap container in the following
manner:

(1) There is no formal Key_Type, as the key type is String.  The generic
    formal region and package name are as follows:

generic

   type Element_Type is private;

   with function "<"
     (Left, Right : String) return Boolean is <>;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Multimaps.Sorted.Strings.Unbounded is ...;


(2) Everywhere where the formal type Key_Type is specified, it is
    systematically replaced by type String.

(3) The key of the sentinel node has a length of 0.

(3) The Generic_Key function is omitted.

(4) The following function is defined:

function Key_Length (Iterator : Iterator_Type) return Natural;

Equivalent to Key (Iterator)'Length.

(5) The generic child procedure Unchecked_Modification is omitted.


The specification of the root of the wide_string-key sorted multimap
containers subsystem is as follows:

package Ada.Containers.Multimaps.Sorted.Wide_Strings is
   pragma Pure;
end Ada.Containers.Multimaps.Sorted.Wide_Strings;

The specification of the unbounded wide_string-key sorted multimap
container differs from the unbounded string-key sorted multimap
container in the following manner:

(1) The name of the package is
    Ada.Containers.Multimaps.Sorted.Wide_Strings.Unbounded;

(2) Everywhere where the formal type String is specified, it is
    systematically replaced by type Wide_String.

The following library-level subprograms are defined:

function Ada.Containers.Hash_String
   (Key : String) return Integer'Base;
pragma Pure (Ada.Containers.Hash_String);

function Ada.Containers.Hash_String_Case_Insensitive
   (Key : String) return Integer'Base;
pragma Pure (Ada.Containers.Hash_String_Case_Insensitive);

function Ada.Containers.Equal_String_Case_Insensitive
   (Left, Right : String) return Boolean;
pragma Pure (Ada.Containers.Equal_String_Case_Insensitive);

function Ada.Containers.Less_String_Case_Insensitive
   (Left, Right : String) return Boolean;
pragma Pure (Ada.Containers.Less_String_Case_Insensitive);

function Ada.Containers.Hash_Wide_String
   (Key : Wide_String) return Integer'Base;
pragma Pure (Ada.Containers.Hash_Wide_String);

function Ada.Containers.Hash_Wide_String_Case_Insensitive
   (Key : Wide_String) return Integer'Base;
pragma Pure (Ada.Containers.Hash_Wide_String_Case_Insensitive);

function Ada.Containers.Equal_Wide_String_Case_Insensitive
   (Left, Right : Wide_String) return Boolean;
pragma Pure (Ada.Containers.Equal_Wide_String_Case_Insensitive);

function Ada.Containers.Less_Wide_String_Case_Insensitive
   (Left, Right : Wide_String) return Boolean;
pragma Pure (Ada.Containers.Less_Wide_String_Case_Insensitive);

!comment

I think we should have hash functions for all predefined types, such
Integer, Long_Integer, etc.

It might even be nice to have a predefined attribute for built-in types
to return a hash value, e.g.

   package File_Cache_Types is
      new Ada.Containers.Maps.Hashed.Strings.Unbounded
        (Element_Type => Context_Access,
         Hash         => String'Hash_Case_Insensitive,
         Is_Equal_Key => String'Equal_Case_Insensitive);

or something like that.  Or to have an extensible mechanism a la T'Read
and T'Write.


The specification of the root of the set containers subsystem is as
follows:

package Ada.Containers.Sets is
   pragma Pure;
end Ada.Containers.Sets;


The specification of the root of the hashed set containers subsystem is
as follows:

package Ada.Containers.Sets.Hashed is
   pragma Pure;
end Ada.Containers.Sets.Hashed;


The specification of the unbounded hashed set container is as follows:

generic

   type Element_Type is private;

   with function Hash
     (Item : Element_Type) return Integer'Base is <>;

   with function Is_Equal_Key
     (Left, Right : Element_Type) return Boolean is "=";

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Sets.Hashed.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Insert
     (Container : in out Container_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Insert_Sans_Resize
     (Container : in out Container_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert_Sans_Resize
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Delete
     (Container : in out Container_Type;
      Item      : in     Element_Type);

   procedure Delete
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   function Is_In
     (Item      : Element_Type;
      Container : Container_Type) return Boolean;

   function Find
     (Container : Container_Type;
      Item      : Element_Type) return Iterator_Type;

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Equal_Range
     (Container : in Container_Type;
      Item      : in Element_Type);

   function Size (Container : Container_Type) return Natural;

   procedure Resize
     (Container : in out Container_Type;
      Size      : in     Natural);

   function First
     (Container : Container_Type;
      Index     : Positive) return Iterator_Type;

   function Index
     (Container : Container_Type;
      Item      : Element_Type) return Positive;

   function Back (Container : Container_Type) return Iterator_Type;

   function Succ (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment (Iterator : in out Iterator_Type);

   function Is_Equal_Key
     (Left, Right : Iterator_Type) return Boolean;
     
   function Is_Equal_Key
     (Left  : Iterator_Type;
      Right : Element_Type) return Boolean;

   function Is_Equal_Key
     (Left  : Element_Type;
      Right : Iterator_Type) return Boolean;

   function Element (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access constant Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);


   generic

      type Key_Type (<>) is limited private;

      with function Hash (Key : Key_Type) return Integer'Base is <>;

      with function Is_Equal_Key
        (Element : Element_Type;
         Key     : Key_Type) return Boolean is <>;

   package Generic_Keys is

      function Is_In
        (Key       : Key_Type;
         Container : Container_Type) return Boolean;

      function Find
        (Container : Container_Type;
         Key       : Key_Type) return Iterator_Type;

      function Element
        (Container : Container_Type;
         Key       : Key_Type) return Element_Type;

      generic
         with procedure Process
           (Element : in Element_Type) is <>;
      procedure Generic_Equal_Range
        (Container : in Container_Type;
         Key       : in Key_Type);

      function Index
        (Container : Container_Type;
         Key       : Key_Type) return Positive;

      procedure Delete
        (Container : in out Container_Type;
         Key       : in     Key_Type);

      function Is_Equal_Key
        (Left  : Iterator_Type;
         Right : Key_Type) return Boolean;

      function Is_Equal_Key
        (Left  : Key_Type;
         Right : Iterator_Type) return Boolean;

      generic

         with procedure Set_Key
           (Element : in out Element_Type;
            Key     : in     Key_Type) is <>;

      package Generic_Insertion is

         procedure Insert
           (Container : in out Container_Type;
            Key       : in     Key_Type;
            Iterator  :    out Iterator_Type;
            Success   :    out Boolean);

         procedure Insert_Sans_Resize
           (Container : in out Container_Type;
            Key       : in     Key_Type;
            Iterator  :    out Iterator_Type;
            Success   :    out Boolean);

      end Generic_Insertion;

   end Generic_Keys;

private

   -- not specified by this standard

end Ada.Containers.Sets.Hashed.Unbounded;


In addition, the hashed set container package has one generic child
procedure:

generic
   type Element_Access is access all Element_Type;
function Ada.Containers.Sets.Hashed.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Element_Access;

pragma Preelaborate
  (Ada.Containers.Sets.Hashed.Unbounded.Unchecked_Modification);


Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, objects of type
Iterator_Type are default-initialized to the value Null_Iterator.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

Assigns the elements in Source to Target.  If Source is an alias of
Target, the operation does nothing.  Any exceptions raised during
internal allocation or deallocation are propagated.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for hashed sets.  If Left and Right refer to the
same container, then the function returns immediately with the value
True.  If Left and Right have different lengths, then the function
returns immediately with the value False.  Otherwise, elements are
compared in canonical order using the equality operator supplied as the
generic actual.  Any exception raised during evaluation of element
equality is propagated, immediately terminating the iteration.


function Length (Container : Container_Type) return Natural;

Returns the number of elements in the container.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Deletes all the elements in Container.  The size of the container is not
affected.  Any exceptions raised during deallocation are propagated.


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes and buckets array of Left and Right.  The
elements that were in the Left set are now in the Right set, and vice
versa.  The time complexity of Swap is O(1).


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

If Length (Container) equals Size (Container), then Container is resized
to some larger size as per Resize.  The index in the buckets array is
then computed from the hash value of New_Item and the size of Container.
The actual subprogram bound to Is_Equal_Key is then used to compare
New_Item to each node in the list of the buckets array at that index.
If the predicate returns True, then Success returns False and Iterator
designates the (first and only) matching node.  Otherwise, a new node is
allocated whose element is initialized to New_Item and inserted at the
head of the list.  Success returns True and Iterator designates the
newly-inserted node.  Any exceptions raised during allocation are
propagated, and Container is not modified (except for any possible
resizing).  The time complexity of this operation is O(1) average case.


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, New_Item, Iterator, Success), with the
difference that the iterator and success parameters are omitted.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts the New_Item into Container as per Insert (Container, New_Item,
Iterator, Success), with the difference that there is no resize prior to
the insertion proper.  If Size (Container) equals 0, the operation fails
and Constraint_Error is propagated.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_Sans_Resize (Container, New_Item, Iterator,
Success), with the difference that the iterator and success parameters
are omitted.


procedure Delete
  (Container : in out Container_Type;
   Item      : in     Element_Type);

Deletes the node whose element matches Item.  If Length (Container)
equals 0, then Delete does nothing.  Otherwise the buckets array index
is computed from the hash value of Item and the size of Container.  Any
exception raised during invokation of Hash is propagated.  The nodes of
the list at that index in the buckets array are compared to Item using
Is_Equal_Key.  The node that matches Item is removed from the set and
then deallocated.  Any exceptions raised by Is_Equal_Key or during the
deallocation are propagated.


procedure Delete
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

If Iterator equals Null_Iterator, the operation has no effect.  If
Iterator does not designate a node in Container, program execution is
erroneous.  Otherwise the buckets index is computed from the hash value
of the element on the node designated by Iterator and the size of
Container.  Any exception raised during invokation of Hash is
propagated.  The node is removed from the set and then deallocated.  Any
exceptions raised by during the deallocation are propagated.  The
Iterator returned designates the node that followed Iterator prior to
the deletion; if this is the end of the list then Null_Iterator is
returned.


function Is_In
  (Item      : Element_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Item) /= Null_Iterator.


function Find
  (Container : Container_Type;
   Item      : Element_Type) return Iterator_Type;

If Length (Container) equals 0, then the function returns immediately
with the value Null_Iterator.  Otherwise the buckets index is computed
from the hash value of Item and the size of Container.  If the list at
that index is empty, then Null_Iterator is returned.  Otherwise the list
is traversed and the element of each node on the list is compared to
Item using Is_Equal_Key.  If Is_Equal_Key returns True, it returns an
iterator designating the (first) node with the matching key.  Otherwise
if no node in the list matches Key, it returns the value Null_Iterator.


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Item      : in Element_Type);

Attempts to find a matching element as per Find (Container, Item).  If a
matching element is found, it invokes the generic actual bound to
Process with the matching element as the parameter.


function Size (Container : Container_Type) return Natural;

Returns the length of the internal buckets array.


procedure Resize
  (Container : in out Container_Type;
   Size      : in     Natural);

If Size (Container) is greater than or equal to Length, the operation
has no effect.  Otherwise, a new buckets array is allocated whose length
is at least the value specified.  If allocation of the new buckets array
fails, the exception is propagated and Container is not modified.  Nodes
already in the set are then rehashed onto the new buckets array.  If
Hash fails, the exception is propagated, and the nodes that were moved
onto the new buckets array are lost.


function First
  (Container : Container_Type;
   Index     : Positive) return Iterator_Type;

If Index is outside the range 1 .. Size (Container), then
Constraint_Error is propagated.  Otherwise, it returns an iterator that
designates the head of the list of the buckets array at Index.  If there
is no list at that Index, then it returns Null_Iterator.


function Index
  (Container : Container_Type;
   Item      : Element_Type) return Positive;

If Size (Container) equals 0, the operation fails and Constraint_Error
is propagated.  Otherwise, returns the value of the expression Hash
(Item) mod Size (Container).


function Back (Container : Container_Type) return Iterator_Type;

Returns the value Null_Iterator.


function Succ (Iterator : Iterator_Type) return Iterator_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an iterator that
designates the successor node in the same list.  If Iterator designates
the last node of the list, then it returns Null_Iterator.


procedure Increment (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).


function Is_Equal_Key
  (Left, Right : Iterator_Type) return Boolean;

Equivalent to Is_Equal_Key (Element (Left), Element (Right)).
  

function Is_Equal_Key
  (Left  : Iterator_Type;
   Right : Element_Type) return Boolean;

Equivalent to Is_Equal_Key (Element (Left), Right).
   

function Is_Equal_Key
  (Left  : Element_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Is_Equal_Key (Right, Left).


function Element (Iterator : Iterator_Type) return Element_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns the element
component of the designated node.


generic
   type Element_Access is access constant Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a constant view of the element component of the node
designated by Iterator.


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to Process with the element of the
node designated by Iterator.  If Iterator equals Null_Iterator, the
operation fails and Constraint_Error is propagated.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Generic_Iteration calls the actual subprogram bound to Process once for
each node in the Container.  Any exceptions raised during Process are
propagated, immediately terminating the iteration.


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Calls the actual subprogram bound to Process once for each element in
Container.  Any exception raised during Process is propagated,
immediately terminating the iteration.


function Is_In
  (Key       : Key_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Key) /= Null_Iterator.
   

function Find
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

If Length (Container) equals 0, then the function returns immediately
with the value Null_Iterator.  Otherwise the buckets index is computed
from the hash value of Key and the size of Container.  If the list at
that index is empty, then it returns Null_Iterator.  Otherwise the list
is traversed and the element of each node on the list is compared to Key
using Generic_Keys.Is_Equal_Key.  If Is_Equal_Key returns True, it
returns an iterator designating the (first) node with the matching
element.  Otherwise if no node in the list matches Key, it returns the
value Null_Iterator.


function Element
  (Container : Container_Type;
   Key       : Key_Type) return Element_Type;

Equivalent to Element (Find (Container, Key)).


generic
   with procedure Process
     (Element : Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Key       : in Key_Type);

Attempts to find a matching element as per Find (Container, Key).  If a
matching element is found, it invokes the generic actual bound to
Process with the matching element as the parameter.


function Index
  (Container : Container_Type;
   Key       : Key_Type) return Positive;

If Size (Container) equals 0, the operation fails and Constraint_Error
is propagated.  Otherwise, returns the value of the expression Hash
(Key) mod Size (Container).


procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes the node that matches Key.  If Length (Container) equals 0, then
Delete does nothing.  Otherwise it computes the index of the buckets
array from the hash value of Key and the size of Container.  Any
exception raised during invokation of Hash is propagated.  The nodes of
the list at that index in the buckets array are compared to Key using
Generic_Keys.Is_Equal_Key.  The node that matches Key is removed from
the set and then deallocated.  Any exceptions raised by Is_Equal_Key or
during the deallocation are propagated.


function Is_Equal_Key
  (Left  : Iterator_Type;
   Right : Key_Type) return Boolean;

Equivalent to Is_Equal_Key (Element (Left), Right).
   

function Is_Equal_Key
  (Left  : Key_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Is_Equal_Key (Right, Left).


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

If Length (Container) equals Size (Container), then Container is resized
to some greater size as per Resize.  The index in the buckets array is
then computed from the hash value of Key and the size of Container.  The
actual subprogram bound to Generic_Keys.Is_Equal_Key is used to compare
Key to the element of each node in the list at that index of the buckets
array.  If an element compares True, then Success returns False and
Iterator designates the (first) matching node.  Otherwise a new node is
allocated and then Generic_Insertion.Set_Key is immediately invoked with
the (uninitialized) element of the new node and Key as the parameters.
Any exception raised during the allocation is propagated and Container
is not modified.  If allocation succeeds but initialization fails, then
the node is deallocated and the exception is propagated, and Container
is not modified.  Otherwise, the new node is inserted at the head of the
list, Success returns True, and Iterator designates the newly-inserted
node.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts a new node per Insert (Container, Key, Iterator, Success), with
the difference that Container is not resized.  If Size (Container)
equals 0, the operation fails and Constraint_Error is propagated.


generic
   type Element_Access is access all Element_Type;
function Ada.Containers.Sets.Hashed.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the element on the node designated by
Iterator.


The specification of the root of the sorted set containers subsystem is
as follows:

package Ada.Containers.Sets.Sorted is
   pragma Pure;
end Ada.Containers.Sets.Sorted;

The specification of the unbounded sorted set container is as follows:

generic

   type Element_Type is private;

   with function "<"
     (Left, Right : Element_Type) return Boolean is <>;

   with function "="
     (Left, Right : Element_Type) return Boolean is <>;

package Ada.Containers.Sets.Sorted.Unbounded is

   pragma Preelaborate;

   type Container_Type is private;

   type Iterator_Type is private;

   Null_Iterator : constant Iterator_Type;

   procedure Assign
     (Target : in out Container_Type;
      Source : in     Container_Type);

   function "=" (Left, Right : Container_Type) return Boolean;

   function "<" (Left, Right : Container_Type) return Boolean;

   function "<=" (Left, Right : Container_Type) return Boolean;

   function ">" (Left, Right : Container_Type) return Boolean;

   function ">=" (Left, Right : Container_Type) return Boolean;

   function Length (Container : Container_Type) return Natural;

   function Is_Empty (Container : Container_Type) return Boolean;

   procedure Clear (Container : in out Container_Type);

   procedure Swap (Left, Right : in out Container_Type);

   procedure Insert
     (Container : in out Container_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Insert
     (Container : in out Container_Type;
      New_Item  : in     Element_Type);

   procedure Insert
     (Container : in out Container_Type;
      Position  : in     Iterator_Type;
      New_Item  : in     Element_Type;
      Iterator  :    out Iterator_Type;
      Success   :    out Boolean);

   procedure Delete
     (Container : in out Container_Type;
      Item      : in     Element_Type);

   procedure Delete
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   procedure Delete_Sans_Increment
     (Container : in out Container_Type;
      Iterator  : in out Iterator_Type);

   procedure Delete_First (Container : in out Container_Type);

   procedure Delete_Last (Container : in out Container_Type);

   function Is_In
     (Item      : Element_Type;
      Container : Container_Type) return Boolean;

   function Find
     (Container : Container_Type;
      Item      : Element_Type) return Iterator_Type;

   function Lower_Bound
     (Container : Container_Type;
      Item      : Element_Type) return Iterator_Type;

   function Upper_Bound
     (Container : Container_Type;
      Item      : Element_Type) return Iterator_Type;

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Equal_Range
     (Container : in Container_Type;
      Item      : in Element_Type);

   function First
     (Container : Container_Type) return Iterator_Type;

   function First_Element
     (Container : Container_Type) return Element_Type;

   function Last
     (Container : Container_Type) return Iterator_Type;

   function Last_Element
     (Container : Container_Type) return Element_Type;

   function Back
     (Container : Container_Type) return Iterator_Type;

   function Succ
     (Iterator : Iterator_Type) return Iterator_Type;

   function Pred
     (Iterator : Iterator_Type) return Iterator_Type;

   procedure Increment
     (Iterator : in out Iterator_Type);

   procedure Decrement
     (Iterator : in out Iterator_Type);

   function "<" (Left, Right : Iterator_Type) return Boolean;

   function "<"
     (Left  : Iterator_Type;
      Right : Element_Type) return Boolean;

   function "<"
     (Left  : Element_Type;
      Right : Iterator_Type) return Boolean;

   function Element (Iterator : Iterator_Type) return Element_Type;

   generic
      type Element_Access is access constant Element_Type;
   function Generic_Element
     (Iterator : Iterator_Type) return Element_Access;

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Process_Element
     (Iterator : in Iterator_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Iterator : in Iterator_Type) is <>;
   procedure Generic_Reverse_Iteration
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Process_Elements
     (Container : in Container_Type);

   generic
      with procedure Process
        (Element : in Element_Type) is <>;
   procedure Generic_Reverse_Process_Elements
     (Container : in Container_Type);

   generic

      type Key_Type (<>) is limited private;

      with function "<"
        (Left  : Element_Type;
         Right : Key_Type) return Boolean is <>;

      with function "<"
        (Left  : Key_Type;
         Right : Element_Type) return Boolean is <>;

   package Generic_Keys is

      function Is_In
        (Key       : Key_Type;
         Container : Container_Type) return Boolean;

      function Find
        (Container : Container_Type;
         Key       : Key_Type) return Iterator_Type;

      function Element
        (Container : Container_Type;
         Key       : Key_Type) return Element_Type;

      function Lower_Bound
        (Container : Container_Type;
         Key       : Key_Type) return Iterator_Type;

      function Upper_Bound
        (Container : Container_Type;
         Key       : Key_Type) return Iterator_Type;

      generic
         with procedure Process
           (Element : in Element_Type) is <>;
      procedure Generic_Equal_Range
        (Container : in Container_Type;
         Key       : in Key_Type);

      procedure Delete
        (Container : in out Container_Type;
         Key       : in     Key_Type);

      function "<"
        (Left  : Iterator_Type;
         Right : Key_Type) return Boolean;

      function "<"
        (Left  : Key_Type;
         Right : Iterator_Type) return Boolean;               

      generic

         with procedure Set_Key
           (Element : in out Element_Type;
            Key     : in     Key_Type) is <>;

      package Generic_Insertion is

         procedure Insert
           (Container : in out Container_Type;
            Key       : in     Key_Type;
            Iterator  :    out Iterator_Type;
            Success   :    out Boolean);

         procedure Insert
           (Container : in out Container_Type;
            Position  : in     Iterator_Type;
            Key       : in     Key_Type;
            Iterator  :    out Iterator_Type;
            Success   :    out Boolean);

      end Generic_Insertion;


   end Generic_Keys;


private

   -- not specified by this standard
   
end Ada.Containers.Sets.Sorted.Unbounded;


In addition, the sorted set container package has one generic child
procedure:

generic
   type Element_Access is access all Element_Type;
function Ada.Containers.Sets.Sorted.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Element_Access;

pragma Preelaborate
  (Ada.Containers.Sets.Sorted.Unbounded.Unchecked_Modification);


Container_Type is a pass-by-reference type.

In the absence of any explicit initialization, objects of type
Iterator_Type are default-initialized to the value Null_Iterator.

!comment

When a sorted set container object elaborates, a sentinel node belonging
to the container is allocated automatically.  Its element is
uninitialized, except for any controlled initialization or
default-initialized components.  It is not included in the count of
elements in the container, and it cannot be deleted.


procedure Assign
  (Target : in out Container_Type;
   Source : in     Container_Type);

Assigns the elements in Source to Target.  If Source is an alias of
Target, the operation does nothing.  Any exceptions raised during
internal allocation or deallocation are propagated.

!comment

The sentinel is not affected by Assign, and its element is never copied.
The sentinel Target had before the Assign is the same sentinel has after
the Assign.


function "=" (Left, Right : Container_Type) return Boolean;

The equality operator for sorted sets.  If Left and Right refer to the
same container, then the function returns immediately with the value
True.  If Left and Right have different lengths, then the function
returns immediately with the value False.  Otherwise, elements are
compared sequentially using the equality operator supplied as the
generic actual.  Any exception raised during evaluation of element
equality is propagated, immediately terminating the iteration.


function "<" (Left, Right : Container_Type) return Boolean;

Performs a lexicographical comparison of the elements in Left and Right.
If Left is an alias of Right, then the operation returns immediately
with the value False.  Otherwise, elements are compared sequentially
using the generic formal less-than operator for elements.  Any exception
raised during evaluation of less-than is propagated, immediately
terminating the iteration.


function "<=" (Left, Right : Container_Type) return Boolean;

Equivalent to not (Left > Right).


function ">" (Left, Right : Container_Type) return Boolean;

Equivalent to Right < Left.


function ">=" (Left, Right : Container_Type) return Boolean;

Equivalent to not (Left < Right).


function Length (Container : Container_Type) return Natural;

Returns the number of elements in the container.


function Is_Empty (Container : Container_Type) return Boolean;

Equivalent to Length (Container) = 0.


procedure Clear (Container : in out Container_Type);

Deletes all the elements in Container.  Any exceptions raised during
deallocation are propagated.


procedure Swap (Left, Right : in out Container_Type);

Exchanges the internal nodes of Left and Right.  Elements that were in
the Left set are now in the Right set, and vice versa.  The time
complexity of Swap is O(1).


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Inserts the New_Item into Container.  The New_Item is compared to
elements already in the set using the subprogram bound to the generic
formal "<" operator.  If the element is already in the set, Success is
False and Iterator designates the node containing the "equivalent"
element.  Otherwise, a new node is allocated and initialized to the
value of New_Item, Success returns True and Iterator designates the
newly-allocated node.  Any exceptions raised during evaluation of the
relational operator or during allocation are propagated, and Container
is not modified.

The equality operator "=" for Element_Type is only used to compute the
value of container equality; it is not used to compute the result of any
other operation.  During insertion elements are compared not for
equality but rather for "equivalence," which for elements E1 and E2 is
defined as "not (E1 < E2) and not (E2 < E1)".


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, New_Item, Iterator, Success), with the
difference that the iterator and success parameters are omitted.


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Equivalent to Insert (Container, New_Item, Iterator, Success), with the
addition of a Position parameter, which specifies a hint about where to
insert the new element.  If Position equals Null_Iterator, the operation
is equivalent to the Position-less version of Insert.  If Position does
not designate a node that belongs to Container, program execution is
erroneous.  For a hint to be useful, it should designate a node
containing an element that would be adjacent to New_Item, were it in the
container.


procedure Delete
  (Container : in out Container_Type;
   Item      : in     Element_Type);

Deletes the node that matches Item.  Any exceptions raised by "<" or
during deallocation are propagated.


procedure Delete
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

If Iterator equals Null_Iterator or Back (Container), the operation does
nothing.  If Iterator does not designate a node that belongs to
Container, program execution is erroneous.  Otherwise, the node
designated by Iterator is removed from the tree.  Any exception raised
during deallocation is propagated.  The iterator value returned
designates the successor of the node deleted.


procedure Delete_Sans_Increment
  (Container : in out Container_Type;
   Iterator  : in out Iterator_Type);

Equivalent to Delete (Container, Iterator), with the difference that the
iterator value returned equals Null_Iterator.


procedure Delete_First (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise the node
designated by First (Container) is deleted.


procedure Delete_Last (Container : in out Container_Type);

If Container is empty, the operation does nothing.  Otherwise the node
designated by Last (Container) is deleted.


function Is_In
  (Item      : Element_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Item) /= Null_Iterator.


function Find
  (Container : Container_Type;
   Item      : Element_Type) return Iterator_Type;

Finds the node whose element is equivalent to Item, and returns an
iterator that designates that node.  If there is no equivalent element,
the iterator value Null_Iterator is returned.  Any exceptions raised
during evaluation of "<" are propagated.


function Lower_Bound
  (Container : Container_Type;
   Item      : Element_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
element not less than Item.  If there is no element already in the set
that is equivalent to or greater than to Item, then it returns Back
(Container).


function Upper_Bound
  (Container : Container_Type;
   Item      : Element_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
element greater than Item.  If there is no element already in the set
that is greater than Item, then it returns Back (Container).


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Item      : in Element_Type);

Searches for the node containing the element that is equivalent to Item
as per Find.  If the search is successful, it invokes the actual
subprogram bound to Process with the equivalent element as the
parameter.


function First
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
element.  If Container is empty, the iterator value Back (Container) is
returned.  The time complexity of this operation is O(1).


function First_Element
  (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
propagated.  Otherwise, it returns the element on the node designated by
First (Container).


function Last
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the node containing the greatest
element.  If Container is empty, the iterator value Back (Container) is
returned.  The time complexity of this operation is O(1).


function Last_Element
  (Container : Container_Type) return Element_Type;

If Container is empty, the operation fails and Constraint_Error is
propagated.  Otherwise, it returns the element on the node designated by
Last (Container).


function Back
  (Container : Container_Type) return Iterator_Type;

Returns an iterator that designates the sentinel node.


function Succ
  (Iterator : Iterator_Type) return Iterator_Type;

Returns the successor of the node designated by Iterator.  If Iterator
equals Null_Iterator, the operation fails and Constraint_Error is
propagated.


function Pred
  (Iterator : Iterator_Type) return Iterator_Type;

Returns the predecessor of the node designated by Iterator.  If Iterator
equals Null_Iterator, the operation fails and Constraint_Error is
propagated.


procedure Increment
  (Iterator : in out Iterator_Type);

Equivalent to Iterator := Succ (Iterator).


procedure Decrement
  (Iterator : in out Iterator_Type);

Equivalent to Iterator := Pred (Iterator).


function "<" (Left, Right : Iterator_Type) return Boolean;

Equivalent to Element (Left) < Element (Right).


function "<"
  (Left  : Iterator_Type;
   Right : Element_Type) return Boolean;

Equivalent to Element (Left) < Right.
   

function "<"
  (Left  : Element_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Left < Element (Right).   


function Element
  (Iterator : Iterator_Type) return Element_Type;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns the element
component of the designated node.


generic
   type Element_Access is
      access constant Element_Type;
function Generic_Element
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a constant view of the the element on the node
designated by Iterator.


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Process_Element
  (Iterator : in Iterator_Type);

Invokes the actual subprogram bound to Process with the element of the
node designated by Iterator.  If Iterator equals Null_Iterator, the
operation fails and Constraint_Error is propagated.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Iteration
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process with an iterator that
designates each node in Container.


generic
   with procedure Process
     (Iterator : in Iterator_Type) is <>;
procedure Generic_Reverse_Iteration
  (Container : in Container_Type);

Iterates over the nodes in Container as per Generic_Iteration, with the
difference that the nodes are traversed in reverse order.
  

generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Process_Elements
  (Container : in Container_Type);

Invokes the actual subprogram bound to Process for each element in
Container.


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Reverse_Process_Elements
  (Container : in Container_Type);

Iterates over the elements in Container as per Generic_Process_Elements,
with the difference that the elements are traversed in reverse order.


function Is_In
  (Key       : Key_Type;
   Container : Container_Type) return Boolean;

Equivalent to Find (Container, Key) /= Null_Iterator.


function Find
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Finds the node whose element is equivalent to Key, and returns an
iterator that designates that node.  If there is no equivalent element,
it returns value Null_Iterator.  Any exceptions raised during evaluation
of "<" are propagated.


function Element
  (Container : Container_Type;
   Key       : Key_Type) return Element_Type;

Equivalent to Element (Find (Container, Key)).


function Lower_Bound
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
element not less than Key.  If there is no element already in the set
that is equivalent to or greater than Key, it returns Back (Container).


function Upper_Bound
  (Container : Container_Type;
   Key       : Key_Type) return Iterator_Type;

Returns an iterator that designates the node containing the smallest
element greater than Key.  If there is no element already in the set
that is greater than Key, it returns Back (Container).


generic
   with procedure Process
     (Element : in Element_Type) is <>;
procedure Generic_Equal_Range
  (Container : in Container_Type;
   Key       : in Key_Type);

Searches for the node containing the element that is equivalent to Key
as per Find.  If the search is successful, it invokes the actual
subprogram bound to Process with the equivalent element as the
parameter.


procedure Delete
  (Container : in out Container_Type;
   Key       : in     Key_Type);

Deletes the node containing the element equivalent to Key.  Any
exceptions raised by "<" or during deallocation are propagated.


function "<"
  (Left  : Iterator_Type;
   Right : Key_Type) return Boolean;

Equivalent to Element (Left) < Right.
   

function "<"
  (Left  : Key_Type;
   Right : Iterator_Type) return Boolean;

Equivalent to Left < Element (Right).   


procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Key is compared to elements already in the set using the subprogram
bound to the Generic_Insertion generic formal "<" operators.  If an
element that is equivalent to Key is already in the set, Success is
False and Iterator designates the node containing the equivalent
element.  Otherwise, a new node is allocated with an uninitialized
element, and then Generic_Insertion.Set_Key is immediately invoked with
the element and Key as the parameters.  If Set_Key raises an exception,
the node is deallocated and the exception is propagated without
modifying Container.  Otherwise, the node is inserted into the tree,
Success returns True and Iterator designates the newly-allocated,
key-initialized node.  Any exceptions raised during evaluation of the
relational operator or during allocation are propagated, and Container
is not modified.


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type;
   Success   :    out Boolean);

Equivalent to Insert (Container, Key, Iterator, Success), with the
addition of a Position parameter, which specifies a hint about where to
begin searching for Key.  If Position equals Null_Iterator then this
operation is equivalent to the Position-less version of Insert.  If
Position does not designate a node that belongs to Container then
program execution is erroneous.


generic
   type Element_Access is access all Element_Type;
function Ada.Containers.Sets.Sorted.Unbounded.Unchecked_Modification
  (Iterator : Iterator_Type) return Element_Access;

If Iterator equals Null_Iterator, the operation fails and
Constraint_Error is propagated.  Otherwise, it returns an access value
that designates a variable view of the element on the node designated by
Iterator.
  
!example

Mario Alves suggested this example to me.  Suppose we have a set and
want to copy the elements from the set into an array.  Here's one way to
do it:

   procedure Op (S : in Integer_Sets.Container_Type) is

      A : Integer_Array (1 .. Length (S));
      I : Integer_Sets.Iterator_Type := First (S);
      J : Positive := A'First;
   begin
      while I /= Back (S) loop
         A (J) := Element (I);
         Increment (I);
         J := J + 1;
      end loop;
      ...
   end Op;

Here we're incrementing both the array index and the set iterator
manually.  However, when you're iterating over two containers
simultaneously, you can often let one or the other drive the iteration,
so that only one position needs to be incremented manually.

We can change the example use a built-in for loop:

   procedure Op (S : in Integer_Sets.Container_Type) is

      A : Integer_Array (1 .. Length (S));
      I : Integer_Sets.Iterator_Type := First (S);
   begin
      for J in A'Range loop
         A (J) := Element (I);
         Increment (I);
      end loop;
      ...
   end Op;

This lets the array drive the iteration.  I have said elsewhere that you
should use a passive iterator in preference to an explicit loop.  The
algorithm above might run faster if we do this:

   procedure Op (S : in Integer_Sets.Container_Type) is

      A : Integer_Array (1 .. Length (S));
      J : Positive := A'First;

      procedure Process (E : in Integer) is
      begin
         A (J) := E;
         J := J + 1;
      end;

      procedure Fill_Array_A is
         new Integer_Sets.Generic_Process_Elements;  -- accept default
   begin
      Fill_Array_A (S);
      ...
   end Op;

This lets the set drive the iteration.   

!end example


!example

Let's continue the streaming server examples from earlier.  In TCP, a
client "connects" to a server, who is "listening" on a port known to the
client.  When the server "accepts" the connection, this establishes a
dedicated connection with that client.  We can reify this in code as follows:

   package Connections is

      type Connection_Type (<>) is limited private;

      type Connection_Access is access Connection_Type;

      function Accept_Connection (Socket : Socket_Type)
         return Connection_Access;  -- the ctor for connection objects
      ...
   end Connections;

We have a need to keep track of all of our current connections.  So when
we create a new connection object, what we do is insert it in a set:

   package body Connections is

      function "<" (L, R : Connection_Access) return Boolean is
      begin
         return L.all'Address < R.all'Address;
      end;

      package Connection_Sets is
         new Ada.Containers.Sets.Sorted.Unbounded (Connection_Access);

      Connection_Set : Connection_Sets.Container_Type;

      function Accept_Connection (Socket : Socket_Type)
         return Connection_Access is

         Connection : constant Connection_Access :=
            new Connect_Type;
      begin
         Insert (Connection_Set, New_Item => Connection);
         ...
         return Connection;
      end;
      ...
   end Connections;

When a new connection object is allocated, it is inserted into the
Connection_Set.  Insertions should always succeed because each allocated
object has a unique access value, so here we don't bother checking.

Now let's suppose we want to shutdown a specific connection.  We can do
it like this:

   procedure Shutdown (X : in out Connection_Access) is
   begin
      if X /= null then
         Delete (Connection_Set, Item => X);
         Free (X);
      end if;
   end Shutdown;

Here we use the item-form of Delete to simply remove the item from the
set, and then deallocate it.

Now let's suppose we want to shutdown the entire system, and so we need
to clear out all of the connection objects.  We could do it like this:

   procedure Shutdown_Connections is
      X : Connection_Access;
   begin
      while not Is_Empty (Connection_Set) loop
         X := First_Element (Connection_Set);
         Shutdown (X);
      end loop;
   end Shutdown_Connections;

Another technique would be to use an active iterator, like this:

   procedure Shutdown_Connections is
      I : Iterator_Type := First (Connection_Set);
      J : constant Iterator_Type := Back (Connection_Set);

      X : Connection_Access;
   begin
      while I /= J loop
         X := Element (I);
         Delete (Connection_Set, Iterator => I);
         Free (X);
      end loop;
   end Shutdown_Connections;
   
Here we use the iterator-form of Delete.  Delete returns the successor
of the iterator deleted, so eventually the loop terminates.

!end example

!example

One of the canonical container examples is the set-of-employees.
Suppose we have an employee type defined this way:

   type Employee_Type is record
      SSN          : SSN_Type;   -- social security no.
      Name         : Name_Type;
      Home_Address : Home_Address_Type;
      ...;
   end record;

To make a set, we need to establish an order relationship for its
elements.  Since each social security number is presumably unique
(unless your identity has been stolen), we can use that to define an
order for Employee_Type:

   function "<" (L, R : Employee_Type) return Boolean is
   begin
      return L.SSN < R.SSN;
   end;

This allows us to instantiate the set in the normal way:

   package Employee_Sets is
      new Ada.Containers.Sets.Sorted.Unbounded (Employee_Type);

   Employees : Employee_Sets.Container_Type;

When someone gets a job at our firm, we add them to our little database
as follows:

   procedure Hire (Name : Name_Type; SSN : SSN_Type; ...) is

      Employee : Employee_Type;
   begin
      Employee.SSN := SSN;
      Employee.Name := Name;
      ...
      Insert (Employees, New_Item => Employee);
   end;

Now let's suppose that we need to modify some information for an
employee.  Like a map, a set orders its elements in key order, except
that for a set the element is its own key.  In the example here, the key
is really the SSN part of the employee object.

Suppose we only know the employee's social security number.  How do we
find that employee?  Remember that the "key" of a set is just the
element itself.  One way is to synthesize a dummy employee object, and
then look it up by element type:

   procedure Change_Address
     (SSN      : SSN_Type;
      New_Home : Home_Address_Type) is

      Iter : Iterator_Type;
   begin
      declare
         Dummy : Employee_Type;
      begin
         Dummy.SSN := SSN;
         Iter := Find (Employees, Item => Dummy);
      end;

      if Iter /= Null_Iter then ...;
   end;

But this is kind of a hack.  I don't really want to make a dummy element
just to look up the real element.  For many types synthesizing a dummy
object this way might not even be possible.

A much more elegant technique is to use the nested generic package
Generic_Keys, which allows you to explicitly name the key-part of the
element.  We can instantiate that package like this:

   function "<"
     (Employee : Employee_Type;
      SSN      : SSN_Type) return Boolean is
   begin
      return Employee.SSN < SSN;
   end;

   function "<"
     (SSN      : SSN_Type;
      Employee : Employee_Type) return Boolean is
   begin
      return SSN < Employee.SSN;
   end;

   package SSN_Keys is
      new Employee_Sets.Generic_Keys (SSN_Type);

With this new package we can now look up the employee by his SSN
directly:

   procedure Change_Address
     (SSN      : SSN_Type;
      New_Home : Home_Address_Type) is

      Iter : Iterator_Type := Find (Employees, Key => SSN);
   begin
      if Iter /= Null_Iter then ...;
   end;

OK.  That problem was solved.  Here's our next problem.  We want to
modify the employee object this way:

   declare
      E : Employee_Type renames To_Access (Iter).all;
   begin
      E.Home_Address := New_Home;
   end;

This is exactly how we'd do it if we were using a map instead of a set.
The To_Access function is an instantiation of the Generic_Element
selector function:

   type Employee_Access is access all Employee_Type

   function To_Access is
     new Employee_Sets.Generic_Element (Employee_Access);

However, this code fragment won't compile, because Generic_Element only
accepts an access constant type, like this:

   type Employee_Constant_Access is access constant Employee_Type

   function To_Constant_Access is
     new Employee_Sets.Generic_Element (Employee_Constant_Access);

This now compiles, but it's not what we want either, because we need a
variable view of the employee object in order to modify it.  After all,
we're trying to change his address.

The reason the set abstraction doesn't let you modify elements (very
easily, anyway -- keep reading) is that elements have a strict order,
and if you were to change an element's value such that it was no longer
in order then you'd break the set.

However, here we have a legitimate reason to modify an element in place.
We're not trying to change his social security number (which is what
defines the "order" for employees in this set), just his address, so we
should be allowed to make this modification.

To accomodate this need each of the associative containers has a generic
child subprogram to permit the key to be modified.  It's up the the
developer to ensure that his modifications are benign.  The new
instantion looks like this:

   with Ada.Containers.Sets.Sorted.Unbounded.Unchecked_Modification;

   package Employee_Sets is ...;

   type Employee_Access is access all Employee_Type

   function To_Access is
     new Employee_Sets.Unchecked_Modification (Employee_Access);

This is a sharp knife, but if we promise to be careful then we're
allowed to say:

   declare
      E : Employee_Type renames To_Access (Iter).all;
   begin
      E.Home_Address := New_Home;  -- OK
   end;

And now all is well.  

Now let's say that the employee's wallet was stolen, which contained his
social security card.  In order to prevent identity theft, he needs to
apply for a new social security number, and then change his entry in the
database.

Clearly we can't use the technique we just showed, because changing his
SSN would break the database.  In this case we need to copy him out of
the set, change the value of the SSN field, and then (re)insert him:

   procedure Change_SSN
     (Old_SSN : SSN_Type;
      New_SSN : SSN_Type) is

      Iter : Iterator_Type := Find (Employees, Key => Old_SSN);
   begin
      if Iter /= Null_Iterator then
         declare
            Employee : Employee_Type := Element (Iter);
         begin
            Employee.SSN := New_SSN;
            Insert (Employees, New_Item => Employee);
         end;
      end if;
   end Change_SSN;

Suppose now we want a list all the employees in the firm.  One way to do
it is like this:

   procedure Display is

      procedure Process (Employee : in Employee_Type) is
      begin
         Put ("Name: ");  Put (Employee.Name);
         Put ("SSN: "); Put (Employee.SSN);
         ...;
      end;

      procedure Print is
         new Employee_Sets.Generic_Process_Elements; -- "Process"
   begin
      Print (Employees);
   end;

However, this will list employees in order of their social security
number.  This is probably not what we want, which is to print employees
in order of name.

One way would be to copy the elements into some other container, which
is sorted according to the criterion we desire.  However, if elements
are large or otherwise not easily copied, then this is not not really an
option.

A much better way is not to copy elements directly but rather to copy
iterators that designate those elements.  Here we use a singly-linked
bounded list, which comes with its own sort operation:

   procedure Display is

      package List_Types is  -- nested instantiation
         new Ada.Containers.Lists.Single.Bounded
           (Element_Type => Employee_Sets.Iterator_Type);

      List : List_Types.Container_Type (Size => Length (Employees));

   begin -- Display

      declare
         procedure Process (I : Employee_Sets.Iterator_Type) is
         begin
            Append (List, New_Item => I);
         end;

         procedure Populate_List is
            new Employee_Sets.Generic_Iteration; -- "Process"
      begin
         Populate_List (Employees);
      end;

      declare               
         function "<" (L, R : Employee_Sets.Iterator_Type)
           return Boolean is

           EL : Employee_Type renames To_Constant_Access (L).all;
           ER : Employee_Type renames To_Constant_Access (R).all;
         begin
           return EL.Name < ER.Name;
         end;

         procedure Sort is
            new List_Types.Generic_Sort;  -- "<"
      begin
         Sort (List);
      end;
         
      declare
         procedure Process (I : Employee_Sets.Iterator_Type) is
            E : Employee_Type renames To_Constant_Access (I).all;
         begin
            Put ("Name: ");  Put (E.Name);
            Put ("SSN: "); Put (E.SSN);
            ...;
         end;

         procedure Print_Employees is
            new List_Types.Generic_Process_Elements; -- "Process"
      begin
         Print_Employees (List);
      end;

   end Display;

First we use the passive iterator for sets to insert an iterator
designating every employee into the bounded linked-list.  We used a
bounded linked-list because we know the maximum number of elements,
which is just the number of elements in the set.

Next we define an order for relation for list elements, which here are
just set iterators.  We wish to print employees in order of name, so the
order relation for iterators is defined in terms of the names of the
employees designated by the iterators.

Note carefully that we didn't use the element selector for iterators:

   EL : Employee_Type := Element (L); -- wrong!

This would make a copy of the employee designated by the iterator, which
is not what we want at all.  That would undermine our reason for sorting
set iterators instead of set elements.  So we used our element access
selector, which returns an access object.  Here we just use the plain
selector, that returns an access object with a constant view, since we
don't need to modify the employee -- only read it.

Now that the employees (really, iterators that designate the employees)
have been sorted, we use the passive iterator for lists to traverse all
the set iterators, and print each employee (in name order) in turn.

!end example


!example

In you were paying very careful attention to the Id_Map example earlier,
you might have realized that since the session object (which was the
element of the map) had an Id field, we were in fact duplicating the Id
object, since it's also stored as the key-part of the map entry.

In turns out we didn't really need to use a map.  We could have used a
set, and instantiated the Generic_Keys nested package using type String
as the formal Key_Type.

   function "<" (L, R : Session_Access) return Boolean is
   begin
      return L.Id < R.Id;
   end;

   package Session_Set_Types is
      new Ada.Containers.Sets.Sorted.Unbounded (Session_Access);

   -- instead of Id_Map, use a set to store sessions:
   Session_Set : Session_Set_Types.Container_Type;

   function "<"
     (Session : Session_Access;
      Id      : String) return Boolean is
   begin
      return Session.Id < Id;
   end;

   function "<"
     (Id      : String;
      Session : Session_Access) return Boolean is
   begin
      return Id < Session.Id;
   end;

   package Id_Keys is
      new Session_Set_Types.Generic_Keys (String);

This lets us perform session lookups based on the session identifier:
      
   procedure Play
     (Session_Id  : in     String;
      NPT_Range   : in     NPT_Range_Type;
      RTSP_Status :    out RTSP_Status_Type) is

      Iter : constant Session_Set_Types.Iterator_Type :=
        Find (Session_Set, Key => Session_Id);

      Session : Session_Access;
   begin
      if Iter = Null_Iterator then
         RTSP_Status := RTSP.Session_Not_Found;
         return;
      end if;

      Session := Element (Iter);

      Play (Session, NPT_Range, RTSP_Status);
   end;

We can insert a session object into the set in the normal way:

   function Setup_Session return Session_Access is
      Session : constant Session_Access := new Session_Type;
   begin
      Generate_Id (Session.Id);
      Insert (Sessions_Set, New_Item => Session);
      ...
      return Session;         
   end;

An alternate way to do this is to use the key-form of insertion:

   procedure Set_Key
     (Session : in out Session_Access;
      Id      : in     String) is
   begin
      Session := new Session_Type;
      Session.Id = Id;
   end;

   procedure Insertion is
      new Id_Types.Generic_Insertion;  -- accept default

   function Setup_Session return Session_Access is
      Id      : Id_Subtype;
      Iter    : Session_Set_Types.Iterator_Type;
      Success : Boolean;
      Session : Session_Access;
   begin
      Generate_Id (Id);
      Insert (Sessions_Set, Id, Iter, Success);
      Session := Element (Iter);
      ...
      return Session;         
   end;
      
This example also illustrates that sets and maps are essentially the
same.  The only difference is where the key lives.

!end example


The specification of the root of the multisets subsystem is as follows:

package Ada.Containers.Multisets is
   pragma Pure;
end Ada.Containers.Multisets;

The specification of the root of the hashed multiset containers
subsystem is as follows:

package Ada.Containers.Multisets.Hashed is
   pragma Pure;
end Ada.Containers.Multisets.Hashed;


The specification of the hashed multiset container differs from the
hashed (unique-element) set container as follows:

(1) The package is named Ada.Containers.Multisets.Hashed.Unbounded.

(2) The signature and semantics of the operations named Insert differ as
    follows:

procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

If Length (Container) equals Size (Container), then Container is resized
to some larger size as per Resize.  The index in the buckets array is
then computed from the hash value of New_Item and the size of Container.
The actual subprogram bound to Is_Equal_Key is then used to compare
New_Item to each node in the list of the buckets array at that index.
If the predicate returns True, then a new node is allocated with the
first matching node as its successor; otherwise, if there are no
elements that match key, a new node is allocated at the head of the
list.  Iterator designates the newly-inserted node.  Any exceptions
raised during allocation are propagated, and Container is not modified.


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, New_Item, Iterator), with the
difference that the iterator parameter is omitted.

    
(3) The signature and semantics of the operations named
    Insert_Sans_Resize differ as follows:

procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Inserts the New_Item into Container as per Insert (Container, New_Item,
Iterator), with the difference that there is no resize prior to the
insertion proper.  If Size (Container) equals 0, the operation fails and
Constraint_Error is propagated.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert_Sans_Resize (Container, New_Item, Iterator), with
the difference that the iterator parameter is omitted.


(4) The semantics of Delete (Container, Item) and Generic_Keys.Delete
    (Container, Key) differ as follows:

Deletes all the nodes whose elements match Item (Key).  If Length
(Container) equals 0, then Delete does nothing.  Otherwise the buckets
array index is computed from the hash value of Item (Key) and the size
of Container.  Any exception raised during invokation of Hash is
propagated.  The nodes of the list at that index in the buckets array
are compared to Item (Key) using Is_Equal_Key.  The nodes that match
Item (Key) are removed from the multiset and deallocated.  Any
exceptions raised by Is_Equal_Key or during deallocation are propagated.


(5) The semantics of Generic_Equal_Range (Container, Item) and
    Generic_Keys.Generic_Equal_Range (Container, Key) differ as follows.

Attempts to find the first matching element as per Find (Container,
Item) or Find (Container, Key).  If a matching element is found, it
invokes the generic actual bound to Process for each matching element in
the list at that index of the buckets array.  The iteration terminates
when either the list is exhausted, or a non-matching element is found.


(6) The semantics of the insertion operations in the nested generic
    package Generic_Insertion differ as follows:

procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

If Length (Container) equals Size (Container), then Container is resized
to some larger value as per Resize.  The index in the buckets array is
then computed from the hash value of Key and the size of Container.  The
actual subprogram bound to Generic_Keys.Is_Equal_Key is used to compare
Key to the element of each node in the list at that index of the buckets
array.  If the predicate returns True, then a new node is allocated with
the matching node as its successor; otherwise, if there are no elements
that match key, a new node is allocated at the head of the list, and
then Set_Key is invoked with Key as the parameter.  Iterator designates
the newly-inserted node.  Any exception raised during the allocation or
initialization is propagated, and Container is not modified.


procedure Insert_Sans_Resize
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Inserts a new node per Insert (Container, Key, Iterator), with the
difference that Container is not resized.  If Size (Container) equals 0,
the operation fails and Constraint_Error is propagated.

(7) The generic child subprogram is named
    Ada.Containers.Multisets.Hashed.Unbounded.Unchecked_Modification.


!example

The canonical example for multisets is to have a database of people
objects, with the name as the key.  We can set things up like this:

   type Person_Type is record
      Family_Name : Name_Subtype;  -- some kind of String subtype
      Given_Name  : Name_Subtype;
      Gender      : Gender_Type;
      ...
   end Person_Type;

   function Hash (Person : Person_Type) return Integer'Base is
   begin
      return Hash_String_Case_Insensitive (Person.Family_Name);
   end;

   package Person_Multiset_Types is
      new Ada.Containers.Multisets.Hashed.Unbounded
           (Element_Type => Person_Type,
            Hash         => Hash,
            Is_Equal_Key => Equal_String_Case_Insensitive);

   Persons : Person_Multiset_Types.Container_Type;

Now we can add some people to our database:

   procedure Op is
      P : Person_Type;
   begin
      P.Family_Name := "Heaney";
      P.Given_Name := "Matthew";
      ...
      Insert (Persons, New_Item => P);

      P.Family_Name := "Santini";
      P.Given_Name := "Thomas";
      ...
      Insert (Persons, New_Item => P);

      P.Family_Name := "Manchester";
      P.Given_Name := "Janet";
      ...
      Insert (Persons, New_Item => P);
   end;

Now if we instantiate the nested Generic_Keys package, like this:

   function Is_Equal_Key
     (Person : Person_Type;
      Name   : String) is
   begin
      return Equal_String_Case_Insensitive (Person.Name, Name);
   end;

   package Name_Keys is
      new Person_Multiset_Types.Generic_Keys
         (Key_Type => String,
          Hash     => Hash_String_Case_Insensitive);

we can iterate over all the persons that share a family name:

   procedure Op (Family : in String) is

      procedure Print (Person : in Person_Type) is
      begin
         ... -- print this person
      end;

      procedure Print_Family is
        new Name_Keys.Generic_Equal_Range (Print);
   begin
      Print_Family (Persons, Key => Family);
   end;

Of course we could walk the sublist manually:

   procedure Op_v2 (Family : in String) is

      procedure Process (Person : in Person_Type) is
      begin
         ... -- print this person
      end;

      procedure Print is
         new Person_Multiset_Types.Generic_Process_Element;

      I : Person_Multiset_Types.Iterator_Type :=
        Find (Person, Key => Family);

   begin -- Op_v2
   
      if I = Null_Iterator then
         return;
      end if;
      
      loop
         Print (I);
         Increment (I);
         exit when I = Null_Iterator;
         exit when not Is_Equal_Key (I);
      end loop;

   end Op_v2;
   
!end example
   

The specification of the root of the sorted multiset containers subsystem is
as follows:

package Ada.Containers.Multisets.Sorted is
   pragma Pure;
end Ada.Containers.Multisets.Sorted;

The specification of the sorted multiset container differs from the
sorted (unique-element) set container as follows:

(1) The signature and semantics of Insert changes as follows:

procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Inserts the New_Item into Container.  The New_Item is compared to
elements already in the container using the subprogram bound to the
generic formal "<" operator.  New_Item is inserted after equivalent
elements already in the container.  Any exceptions raised during
evaluation of the relational operator or during allocation are
propagated, and Container is not modified.


procedure Insert
  (Container : in out Container_Type;
   New_Item  : in     Element_Type);

Equivalent to Insert (Container, New_Item, Iterator), with the
difference that the iterator parameter is omitted.


procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   New_Item  : in     Element_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert (Container, New_Item, Iterator), with the addition
of a Position parameter, which specifies a hint about where to begin
searching for equivalent keys.  If Position equals Null_Iterator, this
operation is equivalent to the Position-less version of Insert.  If
Position does not designate a node that belongs to Container, program
execution is erroneous.

Insert first assumes Position is a potential successor.  If Position
equals Back (Container) or the element designated by Position is not
less than New_Item, and Position equals First (Container) or New_Item is
not less than the predecessor of Position, then New_Item is inserted
immediately prior to Position.

If Position is not a successor, then Insert assumes Position is a
potential predecessor.  If New_Item is not less than Position, and the
successor of Position is not less than New_Item, then New_Item is
inserted immediately following Position.

Otherwise, New_Item is inserted as per the Position-less version of
Insert.


(2) The semantics of Delete (Container, Item) and Generic_Keys.Delete
    (Container, Key) differ as follows:

Deletes all the nodes whose elements are equivalent to Item (Key).  Any
exceptions raised by "<" or during deallocation are propagated.


(3) The semantics of Find (Container, Item) and
Generic_Keys.Generic_Find (Container, Key) differ as follows:

Finds the front-most node whose element is equivalent to Item (Key), and
returns an iterator that designates that node.  If there are no
equivalent elements, the iterator value Null_Iterator is returned.  Any
exceptions raised during evaluation of "<" are propagated.


(4) The semantics of Generic_Equal_Range (Container, Item) and
    Generic_Keys.Generic_Equal_Range (Container, Key) differ as follows.

Attempts to find the front-most equivalent element as per Find
(Container, Item) or Find (Container, Key).  If the search is
successful, it invokes the generic actual bound to Process for each
equivalent element in Container.


(5) The semantics of the insertion operations in the nested generic
    package Generic_Insertion differ as follows:

procedure Insert
  (Container : in out Container_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Key is compared to elements already in the set using the subprogram
bound to the Generic_Insertion generic formal "<" operators.  A new node
is allocated with an uninitialized element, and then
Generic_Insertion.Set_Key is immediately invoked with the element and
Key as the parameters.  If Set_Key raises an exception, the node is
deallocated and the exception is propagated without modifying Container.
Otherwise, the node is inserted into the tree after any elements that
are equivalent to Key, and Iterator designates the newly-allocated,
key-initialized node.  Any exceptions raised during evaluation of the
relational operator or during allocation are propagated, and Container
is not modified.
   

procedure Insert
  (Container : in out Container_Type;
   Position  : in     Iterator_Type;
   Key       : in     Key_Type;
   Iterator  :    out Iterator_Type);

Equivalent to Insert (Container, Key, Iterator), with the addition of a
Position parameter, which specifies a hint about where to insert the new
element.  If Position equals Null_Iterator, this operation is equivalent
to the Position-less version of Insert.  If Position does not designate
a node that belongs to Container, program execution is erroneous.

Otherwise it allocates a node and key-initializes its element as per
Insert (Container, Key, Iterator), and inserts it in the tree as per
Insert (Container, Position, New_Item, Iterator).


(6) The generic child subprogram is named
    Ada.Containers.Multisets.Sorted.Unbounded.Unchecked_Modification


!example

We could have just as easily implemented our persons database using the
sorted multiset.  To print out all the persons that share a family name,
we would instantiate the Generic_Keys generic nested package this way:

   function "<"
     (Person : Person_Type;
      Name   : String) return Boolean is
   begin
      return Less_String_Case_Insensitive (Person.Name, Name);
   end;

   function "<"
     (Name   : String;
      Person : Person_Type) return Boolean is
   begin
      return Less_String_Case_Insensitive (Name, Person.Name);
   end;

   package Name_Keys is
      new Person_Multiset_Types.Generic_Keys (String);

The syntax for using Generic_Equal_Range is the same as for the hashed
multiset.  For a sorted multiset, however, we walk the equivalent range
like this:

   procedure Op_v3 (Family : in String) is

      procedure Process (Person : in Person_Type) is
      begin
         ... -- print this person
      end;

      procedure Print is
         new Person_Multiset_Types.Generic_Process_Element;

      I : Person_Multiset_Types.Iterator_Type :=
         Lower_Bound (Persons, Key => Family);

      J : constant Person_Multiset_Types.Iterator_Type :=
         Upper_Bound (Persons, Key => Family);

   begin -- Op_v3
   
      while I /= J loop
         Print (I);
         Increment (I);
      end loop;
      
   end Op_v3;
      
!end example    


!example

My streaming media server is essentially a main loop, which works off
"events" from a queue.  Each event has a time tag that specifies when
the event comes due.  Events that come due earlier in time are processed
sooner than events that expire later.

We basically have a priority queue, with element priority determined by
an event's time.  An event looks like this:

   type Event_Type;
   type Event_Access is access all Event_Type;

   function "<" (L, R : Event_Access) return Boolean;

A sorted multiset suits our needs exactly.  We use a multiset because
many events can come due at the same time:

   package Event_Queue_Types is
      new Ada.Containers.Multisets.Sorted.Unbounded (Event_Access);

   type Event_Type is limited record
      Time                 : Time_Type;
      Event_Queue_Iterator : Event_Queue_Types.Iterator_Type;
      ...;
   end record;

   function "<" (L, R : Event_Access) return Boolean is
   begin
      return L.Time < R.Time;
   end;

Note that here the order relation is defined in terms of the time-tag of
the events designated by each access object.  We're not comparing access
objects directly (as we've done in other examples).

In fact the session objects with which we are all by now imtimately
familiar are actually implemented something like this:

   type Session_Type is limited record
      Id        : Id_Subtype;
      RTP_Event : aliased Event_Type;
      ...
   end record;
      
The event queue object is declared the body the sessions package:

   package body Sessions is

      Event_Queue : Event_Queue_Types.Container_Type;
      ...

We work off events in the queue like this:

   Main:
   loop

      while Is_Empty (Event_Queue) loop
         ... -- do some work
         sleep (1);  -- delay for 1ms
      end loop;

      Curr_Time : constant Time_Type := Clock;

      loop

         Event : constant Event_Access :=
            First_Element (Event_Queue);  -- top

         exit when Event.Time > Curr_Time;
         
         Process (Event);  -- Event.Time <= Curr means it's due NOW

         Delete_First (Event_Queue);   -- pop

         exit when Is_Empty (Event_Queue);

      end loop;

      sleep (1);   -- be nice to other processes on this machine

   end loop Main;

Events are placed in the queue when a client issues an RTSP PLAY
request:

   procedure Play_Stream
     (Session : access Session_Type;
      Track   : in String) is

      Success : Boolean;
   begin
      ...
      Insert
        (Container => Event_Queue,
         New_Item  => Session.RTP_Event'Access,
         Iterator  => Session.RTP_Event.Event_Queue_Iterator,
         Success   => Success);
      ...
   end;

Events can leave the queue for many reasons.  One reason is when a
client issues an RTSP PAUSE request:

   procedure Pause_Stream
     (Session : access Session_Type;
      Track   : in String) is
   begin
      ...
      Delete (Event_Queue, Session.RTP_Event.Event_Queue_Iterator);
      ...
   end;

It's not good enough to use the item-form (or even the key-form) of
Delete, because many events can have the same key (remember this is a
multiset).  We need a way to uniquely specify the element we want do
delete, which is what the iterator-form does.

This example also demonstrates a nearly-ubiquitous idiom.  In the body
of a package in which a type is declared, an associative container
object is declared, which keeps track of instances of the type.

!end example


!example

An interesting question is, What is a set?  In the philosophy of this
library, the answer is "any sorted container."

Let's say we have two containers.  One is a sorted set.  The other is a
linked-list that has been sorted according the same order relation as
the set.  Suppose we want to take the union of the elements in both
containers and then print the resulting "set" in sort order.

We have stated in earlier examples that generic algorithms abstract-away
the containers.  We see the benefit of such an approach now, because we
need the union of elements in two different kinds of containers.

The union of a set and a sorted list can be done like this:

   procedure Print_Union
     (Set  : in Set_Types.Container_Type;
      List : in List_Types.Container_Type) is

      procedure Print (E : in Element_Subtype) is ...;
         
      procedure Process is  -- has SI as param
         new Set_Types.Generic_Process_Element (Print);

      procedure Process (LI : List_Types.Iterator_Type) is
         procedure Process (E : in out Element_Subtype) is
         begin
            Print (E);  -- change inout to just in
         end;

         procoedure Print is
            new List_Types.Generic_Process_Element; -- "Process"
      begin
         Print (LI);
      end;

      function Is_Less
        (SI : Set_Types.Iterator_Type;
         LI : List_Types.Iterator_Type) return Boolean is

         LE : Element_Subtype renames To_Access (LI).all;
      begin
         return SI < LE;  -- set has "<" ops for iter_t
      end;

      function Is_Less
        (LI : List_Types.Iterator_Type;
         SI : Set_Types.Iterator_Type) return Boolean is

         LE : Element_Subtype renames To_Access (LI).all;
      begin
         return LE < SI;  
      end;

      procedure Union is
         new Generic_Set_Union_2    -- liberal definition of "set"
           (Set_Types.Iterator_Type,
            List_Types.Iterator_Type);  -- accept defaults

   begin -- Print_Union

      Union (First (Set), Back (Set), First (List), Back (List));

   end Print_Union;

The action of the union algorithm is to print all the elements in both
the set and list containers, in element-order.  The generic algorithm
itself just manipulates iterators.  It doesn't know anything about
containers or even about elements.  A very powerful idea, indeed!

!end example