Version 1.13 of ais/ai-20302.txt

Unformatted version of ais/ai-20302.txt version 1.13
Other versions for file ais/ai-20302.txt

!standard A.18 (00) 04-11-01 AI95-00302-03/08
!standard A.18.1 (00)
!standard A.18.2 (00)
!standard A.18.3 (00)
!standard A.18.4 (00)
!standard A.18.5 (00)
!standard A.18.6 (00)
!standard A.18.7 (00)
!standard A.18.8 (00)
!standard A.18.9 (00)
!standard A.18.10 (00)
!standard A.18.11 (00)
!standard A.18.12 (00)
!standard A.18.13 (00)
!standard A.18.14 (00)
!standard A.18.15 (00)
!standard A.18.16 (00)
!standard A.4.9 (00)
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
!priority Medium
!difficulty Hard
!subject Container library

!summary

The following API describes a standard container library for Ada. The library comprises sequence containers (vectors and lists), for inserting elements at specified positions, and associative containers (sets and maps), which position elements in order by key. The library is general, flexible, and efficient, and its design has been guided by the philosophy that a library should stay out of the programmer's way.

!problem

If is often the case that the solution to a programming problem requires a collection of elements. The Ada language of course provides a built-in array type, but typical problems often require a data structure with better time behavior or more sophisticated semantics. Even if you can get by with using an array, any non-trivial array manipulation quickly becomes unwieldy, and hence error-prone.

An array is also not general enough in that it only provides a mapping from a discrete index to the element type. The developer typically needs a container that can map an element to any arbitrary type. The key type often needs to be a string, but of course this cannot be used as an array index subtype.

With no general-purpose standard container library, a developer is left to craft his own container type. The data structure invariably chosen is some kind of linked-list, because it's relatively simple. However, manipulation of raw access types tends to be error-prone, and is a source of memory leaks. A linked-list also does not perform well as a general-purpose set or map when the number of elements is large.

One argument for having a standard library is that it's nice to be able to use a language right out-of-the-box. If a developer has to leave the language to solve common problems then perhaps that is a sign the language doesn't provide enough support for the developer. Other languages with which Ada competes, such as C++ or Java, come with rich standard container libraries.

Many existing container libraries are either badly designed or difficult to use. One issue is that it should be simple and easy to instantiate a component. If it requires more than a single instantiation to create a useable container, then it's too much pain and few developers will bother. If he does bother his experience will be unpleasant. Programming is work, but it should be fun work, not drudgery.

Libraries often have the problem that they are not sufficiently general, or simply not intended as industrial-strength libraries. The library designer can't possibly predict all the myriad uses to which his library will be put, and so the library must be general and flexible enough to suit unimagined uses.

Another problem is that these libraries often don't scale well to large numbers of elements. Their behavior is neither predictable nor is it even specified. They are often both time and space inefficient for various other reasons. In real-time programs especially, it's important to have predictable run-time behavior. An industrial-strength, general-purpose standard container library must provide containers that perform better than linear time complexity. Searches in particular need to be fast.

!proposal

This library API proposal is modeled on the Standard Template Library (STL), an algorithms and data structure library popularized by Alexander Stepanov, and included in the C++ standard library.

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 linear time complexity. A vector supports constant-time random access of elements.

A linked-list is a sequence container that provides constant-time insertion and deletion at any position, but does not provide random access. The list container is doubly-linked, having nodes with next and previous pointers, and thus supports both forward and reverse iteration.

All of the containers specify positions using a cursor, which is similar to an access type in that it designates an element. Selector functions and procedures allow access to the element. Many cursor operations are common to all containers. Containers also support operations specific to that container; for instance, vectors also specify positions via an integer index subtype.

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.

The hashed map associative containers scatter keys in the container according to a hash function. The size of the hash table is automatically increased when the length of the container equals its capacity (which specifies the length before which it is guaranteed that no automatic hash table resizing occurs), thus preserving constant time complexity for insertions.

The set associative container maintains elements in sort order. Insertions and searches have O(log N) time complexity even in the worst case.

All of the containers have alternate forms that accept an element type that is indefinite. The indefinite hashed maps also accept an indefinite key type, allowing (for example) type String to be used as the generic actual key type.

There are also library-level subprograms for returning the hash value of strings, and generic procedures for sorting an array.

The design of these packages follow the principle that they can be implemented in Ada without any special implementation-specific magic. This is important, as we do not want to burden implementers with special purpose requirements. We also want to follow the principle that any capability used for the implementation of the language is made available to users.

This API is based on an existing container library called Charles. The source code itself and a couple of papers about the design of Charles can be found at:

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

Following the API proper, this proposal concludes with an examples section that illustrates the kinds of problems the library solves, and the most effective way to use the library to solve them.

!wording

Add Ada.Strings.Hash and Ada.Strings.Unbounded.Hash to A.4.7(29).

[This gives us Wide_ versions of these functions.]

A.4.9 String Hashing

Static Semantics

The following library-level subprograms are defined:

with Ada.Containers; function Ada.Strings.Hash (Key : String) return Containers.Hash_Type; pragma Pure (Ada.Strings.Hash);

Return an implementation-defined value which is a function of the value of Key. If A and B are strings such that A equals B, Hash(A) equals Hash(B).

with Ada.Containers; function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return Containers.Hash_Type; pragma Preelaborate (Ada.Strings.Unbounded.Hash);

Return an implementation-defined value which is a function of the value of Key. If A and B are unbounded strings such that A equals B, Hash(A) equals Hash(B).

Implementation Advice

The various Hash functions should be good hash functions, returning a wide spread of values for different string values. It should be unlikely for similar strings to return the same value.

A.18 Containers

This clause presents the specifications of the package Containers and several child packages, which provide facilities for storing collections of elements.

A variety of sequence and associative containers are provided. Each container includes a cursor type. A cursor is a reference to an element within a container. Many operations on cursors are common to all of the containers.

Within this clause we provide Implementation Advice for the desired average or worst case time complexity of certain operations on a container. This advice is expressed using a big-O notation. A complexity of O(f(N)), presuming f is some function of a length parameter N and t(N) is the time the operation takes (on average or worst case, as specified) for the length N, means that there exists a finite A such that for any N, t(N)/f(N) < A.

AARM Note: Of course, an implementation can do better than a specified O(f(N)): for example, O(1) meets the requirements for O(log N).

If the advice suggests that the complexity should be less than O(f(N)), then for any arbitrarily small positive real D, there should exist a positive integer M such that for all N > M, t(N)/f(N) < D.

AARM Text Language Design Principles

This clause provides a number of useful containers for Ada. Only the most useful containers are provided. Ones that are relatively easy to code, redundant, or rarely used are omitted from this set, even if they are generally included in containers libraries.

The containers packages are modeled on the Standard Template Library (STL), an algorithms and data structure library popularized by Alexander Stepanov, and included in the C++ standard library. The structure and terminology differ from the STL where that better maps to common Ada usage. For instance, what the STL calls "iterators" are called "cursors" here.

The following major non-limited containers are provided:

* (Expandable) Vectors of any non-limited type;

* Doubly-linked Lists of any non-limited type;

* Hashed Maps keyed by any non-limited type containing any

non-limited type;

* Ordered Sets of any non-limited type.

Separate versions for definite and indefinite element types are provided, as those for definite types can be implemented more efficiently.

Each container includes a cursor, which is a reference to an element within a container. Cursors generally remain valid as long as the container exists and the element referenced is not deleted. Many operations on cursors are common to all of the containers. This makes it possible to write generic algorithms that work on any kind of container.

The containers packages are structured so that additional packages can be added in the future. Indeed, we hope that these packages provide the basis for a more extensive secondary standard for containers.

If containers with similar functionality (but different performance characteristics) are provided, we suggest that a prefix be used to identify the class of the functionality: "Ada.Containers.Bounded_Sets" (for a set with a maximum number of elements); "Ada.Containers.Protected_Maps" (for a map which can be accessed by multiple tasks at one time); "Ada.Containers.Persistent_Vectors" (for a persistent vector which continues to exist between executions of a program) and so on.

Note that the language already includes several requirements that are important to the use of containers. First, library packages must be reentrant - multiple tasks can use the packages as long as they operate on separate containers. Thus, it is only necessary for a user to protect a container if a single container needs to be used by multiple tasks.

Second, the language requires that language-defined types stream "properly". That means that the stream attributes can be used to implement persistence of containers when necessary, and containers can be passed between partitions of a program.

Finally, the language requires that equality of language-defined types compose "properly". This means that the version of "=" directly used by users is the same one that will be used in generics and in predefined equality operators of types with components of the containers and/or cursors. This prevents the abstraction from breaking unexpectedly.

If a container's element type is controlled, the point at which the element is finalized will depend on the implementation of the container. We do not specify precisely where this will happen (it will happen no later than the finalization of the container, of course) in order to give implementation's flexibility to cache, block, or split the nodes of the container. In particular, Delete does not necessarily finalize the element; the implementation may (or may not) hold the space for reuse. (The reference implementations show this well, as Delete for a Vector does not finalize the element, while Delete for an Ordered_Set does.)

This is not likely to be a hardship, as the element type has to be non-limited. Types used to manage scarce resources generally need to be limited. Otherwise, the amount of resources needed is hard to control, as the language allows a lot of variation in the number or order of adjusts/finalizations. For common uses of non-limited controlled types such as managing storage, the types already have to manage arbitrary copies.

The use of controlled type also brings up the possibility of failure of finalization (and thus deallocation) of an element. This is a "serious bug", as AI-179 puts it, so we don't try to specify what happens in that case. The implementation should propagate the exception.

It is expected that exceptions propagated from these operations do not damage containers. That is, if Storage_Error is propagated because of an allocation failure, or Constraint_Error is propagated by the assignment of elements, the container can continue to be used without further exceptions. The intent is that it should be possible to recover from errors without losing data. We don't try to state this formally in most cases, because it is hard to define precisely what is and is not allowed behavior.

When this clause says that the behavior of something is unspecified, we really mean that any result of executing Ada code short of erroneous execution is allowed. We do not mean that memory not belonging to the parameters of the operation can be trashed. When we mean to allow erroneous behavior, we specifically say that execution is erroneous. All this means if the containers are written in Ada is that checks should not be suppressed or removed assuming some behavior of other code, and that the implementation should take care to avoid creating internal dangling accesses by assuming behavior from generic formals that can't be guaranteed. We don't try to say this normatively because it would be fairly complex, and implementers are unlikely to increase their support costs by fielding implementations that are unstable if given buggy hash functions, et. al. End AARM Text

A.18.1 The Package Containers

The package Containers is the root of the containers subsystem.

Static Semantics

The library package Containers has the following declaration:

package Ada.Containers is pragma Pure;

type Hash_Type is mod <Implementation-Defined>;

type Count_Type is range 0 .. <implementation-defined>;

end Ada.Containers;

Hash_Type represents the range of the result of a hash function. Count_Type represents the (potential or actual) number of elements of a container.

Implementation Advice

Hash_Type'Modulus should be at least 2**32. Count_Type'Last should be at least 2**31-1.

AARM Note: This is not a requirement so that these types can be declared properly on machines with native sizes that are not 32 bits. For instance, a 24-bit target could use 2**24 for Hash_Type'Modulus.

A.18.2 The Package Containers.Vectors

The language-defined package Containers.Vectors provides a private type Vector and a set of operations. A vector container allows insertion and deletion at any position, but it is specifically optimized for insertion and deletion at the high end (the end with the higher index) of the container. A vector container also provides random access to its elements.

A vector container object manages an unconstrained internal array, which expands as necessary as items are inserted. The length of a vector is the number of elements that the vector contains. The capacity of a vector corresponds to the number of elements that can be stored in the internal array, and will always be no less than the length of the vector.

A vector container may contain empty elements. Empty elements do not have a specified value.

AARM Notes:

Vectors are not intended to be sparse (that is, there are elements at all defined positions). Users are expected to use other containers (like a Map) when they need sparse structures (there is a Note to this effect at the end of this subclause).

The internal array is a conceptual model of a vector. There is no requirement for an implementation to be a single contiguous array. End AARM Notes.

Static Semantics

The library package Containers.Vectors has the following declaration:

generic

type Index_Type is range <>;

type Element_Type is private;

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

package Ada.Containers.Vectors is pragma Preelaborate (Vectors);

subtype Extended_Index is Index_Type'Base range Index_Type'First-1 .. Index_Type'Last + Boolean'Pos (Index_Type'Base'Last > Index_Type'Last); No_Index : constant Extended_Index := Extended_Index'First;

subtype Index_Subtype is Index_Type;

type Vector is tagged private;

type Cursor is private;

Empty_Vector : constant Vector;

No_Element : constant Cursor;

function To_Vector (Length : Count_Type) return Vector;

function To_Vector (New_Item : Element_Type; Length : Count_Type) return Vector;

function "&" (Left, Right : Vector) return Vector;

function "&" (Left : Vector; Right : Element_Type) return Vector;

function "&" (Left : Element_Type; Right : Vector) return Vector;

function "&" (Left, Right : Element_Type) return Vector;

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

function Capacity (Container : Vector) return Count_Type;

procedure Reserve_Capacity (Container : in out Vector; Capacity : in Count_Type);

function Length (Container : Vector) return Count_Type;

function Is_Empty (Container : Vector) return Boolean;

procedure Clear (Container : in out Vector);

function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor;

function To_Index (Position : Cursor) return Extended_Index;

function Element (Container : Vector; Index : Index_Type) return Element_Type;

function Element (Position : Cursor) return Element_Type;

procedure Query_Element (Container : in Vector; Index : in Index_Type; Process : not null access procedure (Element : in Element_Type));

procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type));

procedure Update_Element (Container : in Vector; Index : in Index_Type; Process : not null access procedure (Element : in out Element_Type));

procedure Update_Element (Position : in Cursor; Process : not null access procedure (Element : in out Element_Type));

procedure Replace_Element (Container : in Vector; Index : in Index_Type; By : in Element_Type);

procedure Replace_Element (Position : in Cursor; By : in Element_Type);

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

procedure Move (Target : in out Vector; Source : in out Vector);

procedure Insert (Container : in out Vector; Before : in Extended_Index; New_Item : in Vector);

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Vector);

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Vector; Position : out Cursor);

procedure Insert (Container : in out Vector; Before : in Extended_Index; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Element_Type; Position : out Cursor; Count : in Count_Type := 1);

procedure Prepend (Container : in out Vector; New_Item : in Vector);

procedure Prepend (Container : in out Vector; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Append (Container : in out Vector; New_Item : in Vector);

procedure Append (Container : in out Vector; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert_Space (Container : in out Vector; Before : in Extended_Index; Count : in Count_Type := 1);

procedure Insert_Space (Container : in out Vector; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1);

procedure Set_Length (Container : in out Vector; Length : in Count_Type);

procedure Delete (Container : in out Vector; Index : in Extended_Index; Count : in Count_Type := 1);

procedure Delete (Container : in out Vector; Position : in out Cursor; Count : in Count_Type := 1);

procedure Delete_First (Container : in out Vector; Count : in Count_Type := 1);

procedure Delete_Last (Container : in out Vector; Count : in Count_Type := 1);

function First_Index (Container : Vector) return Index_Type;

function First (Container : Vector) return Cursor;

function First_Element (Container : Vector) return Element_Type;

function Last_Index (Container : Vector) return Extended_Index;

function Last (Container : Vector) return Cursor;

function Last_Element (Container : Vector) return Element_Type;

procedure Swap (Container : in Vector; I, J : in Index_Type);

procedure Swap (I, J : in Cursor);

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

function Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'First) return Extended_Index;

function Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

function Reverse_Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'Last) return Extended_Index;

function Reverse_Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

function Contains (Container : Vector; Item : Element_Type) return Boolean;

function Next (Position : Cursor) return Cursor;

function Previous (Position : Cursor) return Cursor;

procedure Next (Position : in out Cursor);

procedure Previous (Position : in out Cursor);

function Has_Element (Position : Cursor) return Boolean;

procedure Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor));

procedure Reverse_Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor));

private

... -- not specified by the language

end Ada.Containers.Vectors;

The type Vector needs finalization (see 7.6).

Empty_Vector represents the empty vector container. It has a length of 0. If an object of type Vector is not otherwise initialized, it will be initialized to the same value as Empty_Vector.

No_Element represents a cursor that designates no element. If an object of type Cursor is not otherwise initialized, it will be initialized to the same value as No_Element.

No_Index represents a position that does not correspond to any element. The subtype Extended_Index includes the indices covered by Index_Type plus the value No_Index and, if it exists, the successor to the Index_Type'Last.

AARM Note: We require the existence of Index_Type'First - 1, so that No_Index and Last_Index of an empty vector is well-defined. We don't require the existence of Index_Type'Last + 1, as it is only used as the position of insertions (and needs to be allowed only when inserting an empty vector).

function To_Vector (Length : Count_Type) return Vector;

Returns a vector with a length of Length. The vector is filled with empty elements.

function To_Vector

(New_Item : Element_Type;

Length : Count_Type) return Vector;

Returns a vector with a length of Length, and elements initialized to the value New_Item.

function "&" (Left, Right : Vector) return Vector;

Returns a vector comprising the elements of Right appended in their original order to the vector Left.

function "&" (Left : Vector;

Right : Element_Type) return Vector;

Returns a vector comprising the element Right appended to the vector Left.

function "&" (Left : Element_Type;

Right : Vector) return Vector;

Returns a vector comprising the element Left prepended to the vector Right.

function "&" (Left, Right : Element_Type) return Vector;

Returns a vector comprising the element Left followed by the element Right.

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

If Left denotes the same object as Right, then this function returns True. Otherwise if Left and Right have different lengths, then this function returns False. Otherwise, it compares each element in Left to the corresponding element in Right using the generic formal equality operator. If element equality returns False, then this function returns False; otherwise, this function returns True. Any exception raised during evaluation of element equality is propagated.

function Capacity (Container : Vector) return Count_Type;

Returns the length of the internal array.

procedure Reserve_Capacity (Container : in out Vector; Capacity : in Count_Type);

Reserve_Capacity sets the capacity of Container to a value which is at least the value Capacity and which is greater than the length of Container, expanding (or contracting) the internal array to hold at least Capacity elements. Expansion or contraction will require allocation, and possibly copying and deallocation of elements. Any exceptions raised by these operations are propagated, leaving the container with at least the original length and elements.

AARM Notes

Expanding the internal array can be done by allocating a new, longer array, copying the elements, and deallocating the original array. This may raise Storage_Error, or cause an exception from a controlled subprogram. We require that a failed Reserve_Capacity does not lose any elements if an exception occurs, but we do not require a specific order of evaluations or copying.

This routine is used to preallocate the internal array to the specified capacity such that future Inserts do not require memory allocation overhead. Therefore, the implementation should allocate the needed memory to make that true at this point, even though the visible semantics could be preserved by waiting until the memory is needed. This doesn't apply to the indefinite element container, because elements will have to be allocated individually.

The implementation does not have to contract the internal array if the capacity is reduced, as any capacity greater than or equal to the specified capacity is allowed.

End AARM Notes

function Length (Container : Vector) return Count_Type;

The Length function returns the number of active elements in Container.

function Is_Empty (Container : Vector) return Boolean;

Equivalent to Length (Container) = 0.

procedure Clear (Container : in out Vector);

Sets the length of Vector to 0. Its capacity does not change.

function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor;

If the value of Index is not in the range First_Index (Container) .. Last_Index (Container), then No_Element is returned. Otherwise, a cursor designating the element currently at Index in Container is returned.

function To_Index (Position : Cursor) return Extended_Index;

If Position is No_Element, No_Index is returned. Otherwise, the index (within its containing vector) of the element designated by Cursor is returned.

AARM Note: This implies that the index is determinable from a bare cursor alone. The basic model is that a vector cursor is implemented as a record containing an access to the vector container and an index value. This does constrain implementations, but it also allows all of the cursor operations to be defined in terms of the corresponding index operation (which should be primary for a vector).

function Element (Container : Vector; Index : Index_Type) return Element_Type;

If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise this function returns the element at position Index.

function Element (Position : Cursor) return Element_Type;

Returns the element designated by Position. If Position equals No_Element, then Constraint_Error is propagated.

procedure Query_Element

(Container : in Vector;

Index : in Index_Type; Process : not null access procedure (Element : in Element_Type));

If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, it calls Process.all with the element at position Index as the parameter. Any exception raised by Process is propagated.

procedure Query_Element

(Position : in Cursor;

Process : not null access procedure (Element : in Element_Type));

Calls Process.all with the element designated by Position as the parameter. If Position equals No_Element, then Constraint_Error is propagated. Any exceptions raised by Process are propagated.

procedure Update_Element

(Container : in Vector;

Index : in Index_Type; Process : not null access procedure (Element : in out Element_Type));

If Element_Type is unconstrained and definite, then the Element parameter of Process.all shall be unconstrained.

AARM Note: This means that the elements cannot be directly allocated from the heap (nor aliased unless AI-363 is included in the Amendment); it must be possible to change the discriminants of the element in place.

The element at position Index is not an empty element after successful completion of this operation.

AARM Note: Since reading an empty element is a bounded error, attempting to use this procedure to replace empty elements may fail. Use Replace_Element to do that reliably.

procedure Update_Element

(Position : in Cursor;

Process : not null access procedure (Element : in out Element_Type));

Calls Process.all with the element designated by Position as the parameter. If Position equals No_Element, then Constraint_Error is propagated. Any exceptions raised by Process are propagated.

If Element_Type is unconstrained and definite, then the Element parameter of Process.all shall be unconstrained.

The element designated by Position is not an empty element after successful completion of this operation.

procedure Replace_Element (Container : in Vector; Index : in Index_Type; By : in Element_Type);

If Index does not specify a value in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise this procedure assigns the value By to the element at position Index. Any exceptions raised during the assignment are propagated. The element at position Index is not an empty element after successful completion of this operation.

procedure Replace_Element (Position : in Cursor; By : in Element_Type);

This procedure assigns the value By to the element designated by Position. If Position equals No_Element, then Constraint_Error is propagated. Any exception raised during the assignment is propagated. The element designated by Position is not an empty element after successful completion of this operation.

AARM Note: Replace_Element and Update_Element are the only ways that an element can change from empty to non-empty.

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

If Target denotes the same object as Source, then the operation has no effect. Otherwise, Assign first calls Clear (Target), then Reserve_Capacity (Target, Length (Source)). It then assigns the active elements of Source to the corresponding positions in Target, and then sets the length of Target to the length of Source. Any exception raised during element assignment is propagated.

procedure Move (Target : in out Vector; Source : in out Vector);

If Target denotes the same object as Source, then the operation has no effect. If Length (Target) is greater than 0, then it raises Constraint_Error. Otherwise, the internal array is removed from Source (making its capacity 0) and moved to Target (making its capacity the original capacity of Source). The length of Target is set to the length of Source, and the length of Source is set to 0.

AARM Note:

If Capacity (Target) /= 0, the previous internal array may need to be deallocated. We don't mention this explicitly, because it is covered by the "no memory loss" Implementation Requirement. If the deallocation raises an exception, the implementation should leave both Vectors in a consistent state (usually empty for Target and the original state for Source).

procedure Insert (Container : in out Vector; Before : in Extended_Index; New_Item : in Vector);

If Length(New_Item) is 0, then Insert does nothing. Otherwise, it calculates the new length NL as the sum of the current length and Length (New_Item); if the value of Last appropriate for length NL would be greater than Index_Type'Last then Constraint_Error is propagated. If the value of Before is not in the range First_Index (Container) .. Last_Index (Container) + 1, then Constraint_Error is propagated.

If the current vector capacity is less than or equal to the new length, Reserve_Capacity (Container, NL) is called to increase the vector capacity. Then Insert slides the elements in the range Before .. Last_Index (Container) up by Length(New_Item) positions, and then copies the elements of New_Item to the positions starting at Before. Any exception raised during the copying is propagated.

AARM Note:

Moving the elements does not necessarily involve copying. Similarly, since Reserve_Capacity does not require the copying of elements, it does not need to be explicitly called (the implementation can combine the operations if it wishes to). [Note to reviewers: I didn't want to duplicate the messy wording and notes about exceptions not losing anything.] End AARM Note.

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Vector);

If Before is not No_Element, and does not designate an element in Container, then Program_Error is propagated. If Length(New_Item) is 0, then Insert does nothing. If Before is No_Element, then is equivalent to Insert (Container, Last_Index (Container) + 1), New_Item); otherwise is equivalent to Insert (Container, To_Index (Before), New_Item);

AARM Note: The check on Before checks that the cursor does not belong to some other Container. This check implies that a reference to the container is included in the cursor value. This wording is not meant to require detection of dangling cursors; such cursors are defined to be invalid, which means that execution is erroneous, and any result is allowed (including not raising an exception).

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Vector; Position : out Cursor);

If Before is not No_Element, and does not designate an element in Container, then Program_Error is propagated. If Length(New_Item) is 0, then Insert sets Position to Before. Otherwise, create a temporary (call it Temp_Index) and set it to Last_Index (Container) + 1 if Before equals No_Element, and To_Index (Before) otherwise. Then Insert (Container, Before, New_Item) is called, and finally Position is set to To_Cursor (Container, Temp_Index).

AARM Note: The messy wording because Before is invalidated by Insert, and we don't want Position to be invalid after this call. An implementation probably only needs to copy Before to Position.

procedure Insert (Container : in out Vector; Before : in Extended_Index; New_Item : in Element_Type; Count : in Count_Type := 1);

Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1);

Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));

procedure Insert (Container : in out Vector; Before : in Cursor; New_Item : in Element_Type; Position : out Cursor; Count : in Count_Type := 1);

Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);

procedure Prepend (Container : in out Vector; New_Item : in Vector; Count : in Count_Type := 1);

Equivalent to Insert (Container, Index_Type'First, New_Item).

procedure Prepend (Container : in out Vector; New_Item : in Element_Type; Count : in Count_Type := 1);

Equivalent to Insert (Container, Index_Type'First, New_Item, Count).

procedure Append (Container : in out Vector; New_Item : in Vector);

Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item).

procedure Append (Container : in out Vector; New_Item : in Element_Type; Count : in Count_Type := 1);

Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item, Count).

procedure Insert_Space (Container : in out Vector; Before : in Extended_Index; Count : in Count_Type := 1);

Equivalent to Insert (Container, Before, New_Item, Count), with the difference that the inserted elements are empty elements.

procedure Insert_Space (Container : in out Vector; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1);

If Before is not No_Element, and does not designate an element in Container, then Program_Error is propagated. If Length(New_Item) is 0, then Insert does nothing. Otherwise, create a temporary (call it Temp_Index) and set it to Last_Index (Container) + 1 if Before equals No_Element, and To_Index (Before) otherwise. Then Insert_Space (Container, Temp_Index, Count) is called, and finally Position is set to To_Cursor (Container, Temp_Index).

procedure Set_Length (Container : in out Vector; Length : in Count_Type);

If Length is larger than the capacity of Container, calls Reserve_Capacity (Container, Length), then sets the length of the Container to Length. If Length is greater than the original length of Container, the added elements are empty elements.

procedure Delete (Container : in out Vector; Index : in Extended_Index; Count : in Count_Type := 1);

If Count is 0, the operation has no effect. If Index does not specify a value in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise Delete slides the active elements (if any) starting Index plus Count down to Index. Any exceptions raised during element assignment are propagated.

AARM Note: If Index + Count >= Last_Index(Container), this effectively truncates the vector (setting Last_Index to Index - 1 and consequently setting Length to Index - Index_Type'First).

procedure Delete (Container : in out Vector; Position : in out Cursor; Count : in Count_Type := 1);

If Position is No_Element, this operation has no effect. If Position does not designate an element in Container, then Program_Error is raised. If Count is 0, the operation has no effect. Otherwise is equivalent to Delete (Container, To_Index (Position), Count).

procedure Delete_First (Container : in out Vector; Count : in Count_Type := 1);

Equivalent to Delete (Container, Index_Type'First, Count).

procedure Delete_Last (Container : in out Vector; Count : in Count_Type := 1);

If Length (Container) <= Count then is equivalent to Clear (Container); otherwise is equivalent to Delete (Container, Index_Type'Val(Index_Type'Pos(Last_Index(Container)) - Count + 1), Count).

function First_Index (Container : Vector) return Index_Type;

Returns the value Index_Type'First.

AARM Note: We'd rather call this "First", but then calling most routines in here with First (Some_Vect) would be ambiguous.

function First (Container : Vector) return Cursor;

If Container is empty, First returns the value No_Element. Otherwise, returns a cursor that designates the first element in Container.

function First_Element (Container : Vector) return Element_Type;

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

function Last_Index (Container : Vector) return Extended_Index;

If Container is empty, returns No_Index; otherwise, returns the position of the last element in Container.

function Last (Container : Vector) return Cursor;

If Container is empty, Last returns the value No_Element. Otherwise, returns a cursor that designates the last element in Container.

function Last_Element (Container : Vector) return Element_Type;

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

procedure Swap (Container : in Vector; I, J : in Index_Type);

If I or J does not specify a value in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise Swap exchanges the values of the elements at positions I and J.

AARM Notes: To Be Honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed.

procedure Swap (I, J : in Cursor);

If either I or J is No_Element, then Constraint_Error is propagated. If I and J designate elements in different containers, then Program_Error is propagated. Otherwise Swap exchanges the values of the elements designated by I and J.

AARM Notes: After a call to Swap, I designates the element value previously designated by J, and J designates the element value previously designated by I. The cursors do not become ambiguous from this operation.

To Be Honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed. End AARM Notes.

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

Reorders the elements of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. Any exception raised during evalution of "<" is propagated.

AARM Notes: This implies swapping the elements, usually including an intermediate copy. This means that the elements will usually be copied. (As with Swap, if the implementation can do this some other way, it is allowed to.) Since the elements are non-limited, this usually will not be a problem. Note that there is Implementation Advice below that the implementation should use a sort that minimizes copying of elements.

The sort is not required to be stable (and the fast algorithm required will not be stable). If a stable sort is needed, the user can include the original location of the element as an extra "sort key". We considered requiring the implementation to do that, but it is mostly extra overhead -- usually there is something already in the element that provides the needed stability. End AARM Notes

function Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'First) return Extended_Index;

Searches the elements of Container for an element equal to Item, starting at position Index. If there are no elements in the range Index .. Last_Index (Container) equal to Item, then Find_Index returns No_Index. Otherwise, it returns the index of the matching element.

function Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

If Position is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Searches the elements of Container for an element equal to Item, starting at the first element if Cursor equals No_Element, and at the element designated by Cursor otherwise, and searching to the last element in Container. If an item equal to Item is found, Find returns a cursor designating the first element found equal to Item. If no such item is found, it returns No_Element.

function Reverse_Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'Last) return Extended_Index;

Searches the elements of Container in reverse for an element equal to Item, starting at position Index. If Index is greater than Last_Index (Container), then the search begins at position Last_Index (Container). If there are no elements in the range Index_Type'First .. Index equal to Item, then Reverse_Find_Index returns No_Index. Otherwise, it returns the index of the matching element.

function Reverse_Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

If Position is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Searches the elements of Container for an element equal to Item, starting at the last element if Cursor equals No_Element, and at the element designated by Cursor otherwise, and searching backwards to the first element in Container. If an item equal to Item is found, Find returns a cursor designating the first element found equal to Item. If no such item is found, it returns No_Element.

function Contains (Container : Vector; Item : Element_Type) return Boolean;

Equivalent to Has_Element (Find (Container, Item)).

function Next (Position : Cursor) return Cursor;

If Position equals No_Element or designates the last element of the container, then Next returns the value No_Element. Otherwise, returns a cursor that designates the element with index To_Index (Position) + 1 in the same vector as Position.

function Previous (Position : Cursor) return Cursor;

If Position equals No_Element or designates the first element of the container, then Previous returns the value No_Element. Otherwise, returns a cursor that designates the element with index (To_Index (Position) - 1) in the same vector as Position.

The procedure Next is equivalent to Position := Next (Position).

The procedure Previous is equivalent to Position := Previous (Position).

function Has_Element (Position : Cursor) return Boolean;

Returns True if Position designates an element, and returns False otherwise.

AARM Note: To Be Honest: This function may not detect cursors that designate deleted elements; such cursors are invalid (see below) and any use of them (including in this routine) is erroneous.

procedure Iterate

(Container : in Vector;

Process : not null access procedure (Position : in Cursor));

Invokes Process.all with a cursor that designates each element in Container, in index order. Any exception raised by Process is propagated. Program_Error is propagated if:

* Process.all attempts to insert or delete elements from Container; or

* Process.all finalizes Container; or

* Process.all calls Move with Container as a parameter.

AARM Note: This check takes place when the operations that insert or delete elements, etc. are called. There is no check needed if an attempt is made to insert or delete nothing (that is, Count = 0 or Length(Item) = 0).

The check is easy to implement: each container needs a counter. The counter is incremented when Iterate is called, and decremented when Iterate completes. If the counter is nonzero when an operation that inserts or deletes is called, Finalize is called, or one of the other operations in the list occurs, Program_Error is raised.

Swap and Generic_Sort are not included here, as they only copy elements. End AARM Notes.

procedure Reverse_Iterate

(Container : in Vector;

Process : not null access procedure (Position : in Cursor));

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

Legality Rules

An instantiation of Containers.Vectors shall be at the library level.

AARM Note A implementation will typically need to use controlled types to insure that the Implementation Requirements are met. These would require all instantiations to occur at the library level. We certainly do not want to require magic for nested container instantiations, while not giving similar capabilities to users. We've made this a legality rule to enhance portability. This rule will be dropped if AI-344 or some other solution to nested controlled types is adopted.

Bounded (Run-Time) Errors

Reading the value of an empty element by calling Element, Query_Element, Update_Element, Generic_Sort, "=", Find, or Reverse_Find is a bounded error. The implementation may treat the element as having any valid value of the element type, or raise Constraint_Error or Program_Error before modifying the vector.

AARM Notes: For instance, a default initialized element could be returned. Or some previous value of an element. But returning random junk is not allowed if the type has default initial value(s).

Assignment and streaming of empty elements are NOT bounded errors. This is consistent with regular composite types, for which assignment and streaming of uninitialized components do not cause a bounded error, but reading the uninitialized component does cause a bounded error.

There are other operations which are defined in terms of the operations listed above. End AARM Notes.

A Cursor value is ambiguous if any of the following have occurred since it was created:

* Insert or Delete has been called on the vector that contains the element the cursor designates with an index value (or a cursor designating an element at such an index value) less than or equal to the index value of the element designated by the cursor;

* The vector that contains the element it designates has been passed to an instance of Generic_Sort.

It is a bounded error to call any subprogram other than "=" or Has_Element declared in Containers.Vectors with an ambiguous (but not invalid, see below) cursor parameter. Possible results are:

* The cursor may be treated as if it was No_Element;

* The cursor may designate some element in the vector (but not necessarily the element that it originally designated);

* Constraint_Error may be raised; or

* Program_Error may be raised.

AARM Note: Cursors are made ambiguous if an Insert or Delete occurs that moves the elements in the internal array including the designated ones. After such an operation, the cursor probably still designates an element (although it might not after a deletion), but it is a different element. That violates the definition of cursor -- it designates a particular element.

For "=" or Has_Element, the cursor works normally (it would not be No_Element). We don't want to trigger an exception simply for comparing a bad cursor.

While it is possible to check for or prevent these cases, in many cases the overhead necessary to make the check (or prevent the problems) is substantial in time or space. End AARM Notes.

Erroneous Execution

A Cursor value is invalid if any of the following have occurred since it was created:

* The vector that contains the element it designates has been finalized;

* The vector that contains the element it designates has been used as the Source or Target of a call to Move;

* The element it designates has been deleted.

The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Vectors is called with an invalid cursor parameter.

Execution also is erroneous if the called Process procedure of a call to Query_Element or Update_Element executes an operation that causes the Position cursor or To_Cursor of the Index parameter of Query_Element or Update_Element to become invalid or ambiguous.

AARM Notes: The list above (combined with the bounded error cases) is intended to be exhaustive. In other cases, a cursor value continues to designate its original element. For instance, cursor values survive the appending of new elements. End AARM Notes.

Implementation Requirements

No storage associated with a vector object shall be lost upon assignment or scope exit.

Implementation Advice

Containers.Vectors should be implemented similarly to an array. In particular, if the length of a vector is N, then

* the worst-case time complexity of Append with Count=1 and Element should be O(log N);

* the worst-case time complexity of Prepend with Count=1 or Delete_First with Count=1 of the vector should be O(N log N).

AARM Note We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes O(N) time to access elements, that program could be unusable when the vectors are large. We allow O(log N) access because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations.

The worst-case time complexity of a call on an instantiation of Containers.Vectors.Generic_Sort should be O(N**2), and the average time complexity should be better than O(N**2).

AARM Note In other words, we're requiring the use of a better than O(N**2) sorting algorithm, such as Quicksort. No Bubble sorts allowed!

Containers.Vectors.Generic_Sort should minimize copying of elements.

AARM Note - To Be Honest We do not mean "absolutely minimize" here; we're not intending to require a single copy for each element. Rather, we want to suggest that the sorting algorithm chosen is one that does not copy items unnecessarily. Bubble sort would not meet this advice, for instance.

NOTE: All elements of a vector occupy locations in the internal array. If a sparse container is required, a Hashed_Map should be used rather than a vector.

If Index_Type'Base'First = Index_Type'First an instantiation of Ada.Containers.Vectors will raise Constraint_Error. A value below Index_Type'First is required so that an empty vector has a meaningful value of Last_Index.

AARM Note: This property is the main reason why only integer types (as opposed to any discrete type) are allowed as the index type of a vector. An enumeration or modular type would require a subtype in order to meet this requirement.

A.18.3 The Package Containers.Doubly_Linked_Lists

The language-defined package Containers.Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each type. A list container is optimized for insertion and deletion at any position.

A doubly-linked list container object 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. A cursor designates particular storage nodes (and thus elements) within a list.

Static Semantics

The library package Containers.Doubly_Linked_Lists has the following declaration:

generic

type Element_Type is private;

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

package Ada.Containers.Doubly_Linked_Lists is pragma Preelaborate (Doubly_Linked_Lists);

type List is tagged private;

type Cursor is private;

Empty_List : constant List;

No_Element : constant Cursor;

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

function Length (Container : List) return Natural;

function Is_Empty (Container : List) return Boolean;

procedure Clear (Container : in out List);

function Element (Position : Cursor) return Element_Type;

procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type));

procedure Update_Element (Position : in Cursor; Process : not null access procedure (Element : in out Element_Type));

procedure Replace_Element (Position : in Cursor; By : in Element_Type);

procedure Move (Target : in out List; Source : in out List);

procedure Prepend (Container : in out List; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Append (Container : in out List; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert (Container : in out List; Before : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert (Container : in out List; Before : in Cursor; New_Item : in Element_Type; Position : out Cursor; Count : in Count_Type := 1);

procedure Insert (Container : in out List; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1);

procedure Delete (Container : in out List; Position : in out Cursor; Count : in Count_Type := 1);

procedure Delete_First (Container : in out List; Count : in Count_Type := 1);

procedure Delete_Last (Container : in out List; Count : in Count_Type := 1);

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

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

procedure Reverse_List (Container : in out List);

procedure Swap (I, J : in Cursor);

procedure Swap_Links (Container : in out List; I, J : in Cursor);

procedure Splice (Target : in out List; Before : in Cursor; Source : in out List);

procedure Splice (Target : in out List; Before : in Cursor; Position : in Cursor);

procedure Splice (Target : in out List; Before : in Cursor; Source : in out List; Position : in Cursor);

function First (Container : List) return Cursor;

function First_Element (Container : List) return Element_Type;

function Last (Container : List) return Cursor;

function Last_Element (Container : List) return Element_Type;

function Contains (Container : List; Item : Element_Type) return Boolean;

function Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

function Reverse_Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

function Next (Position : Cursor) return Cursor;

function Previous (Position : Cursor) return Cursor;

procedure Next (Position : in out Cursor);

procedure Previous (Position : in out Cursor);

function Has_Element (Position : Cursor) return Boolean;

procedure Iterate (Container : in List; Process : not null access procedure (Position : in Cursor));

procedure Reverse_Iterate (Container : in List; Process : not null access procedure (Position : in Cursor));

private

... -- not specified by the language

end Ada.Containers.Doubly_Linked_Lists;

The type List needs finalization (see 7.6).

Empty_List represents the empty list. If an object of type List is not otherwise initialized, it will be initialized to the same value as Empty_List.

No_Element represents a cursor that designates no element. If an object of type Cursor is not otherwise initialized, it will be initialized to the same value as No_Element.

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

The function Length returns the number of elements in Container.

The function Is_Empty is equivalent to Length (Container) = 0.

Clear removes all the nodes in Container, and sets the length to 0. Any exceptions raised during deallocation of storage are propagated.

function Element (Position : Cursor) return Element_Type;

Returns the element stored on the node designated by Position. If Position equals No_Element, then Constraint_Error is propagated.

procedure Query_Element

(Position : in Cursor;

Process : not null access procedure (Element : in Element_Type));

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Query_Element invokes Process.all with the element on node designated by Position as the argument.

procedure Update_Element

(Position : in Cursor;

Process : not null access procedure (Element : in out Element_Type));

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Update_Element invokes Process.all with the element on node designated by Position as the argument.

If Element_Type is unconstrained and definite, then the Element parameter of Process.all shall be unconstrained.

procedure Replace_Element (Position : Cursor; By : Element_Type);

Assigns the value By to the element stored on the node designated by Position. If Position equals No_Element, then Constraint_Error is propagated.

procedure Move (Target : in out List; Source : in out List);

If Target denotes the same object as Source, then the operation has no effect. If Length (Target) is greater than 0, then it raises Constraint_Error. Otherwise, the nodes in Source are moved to Target. The length of Target is set to the length of Source, and the length of Source is set to 0.

Prepend is equivalent to Insert (Container, First (Container), New_Item, Count).

Append is equivalent to Insert (Container, No_Element, New_Item, Count).

procedure Insert (Container : in out List; Before : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1);

procedure Insert (Container : in out List; Before : in Cursor; New_Item : in Element_Type; Position : out Cursor; Count : in Count_Type := 1);

If Before is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Insert allocates Count new nodes whose element is initialized to the value New_Item, and inserts them prior to the node designated by Before. If Before equals No_Element, the new nodes are inserted immediately following the last node (if any). Position designates the first newly-inserted node. Any exception raised during allocation of internal storage is propagated, and Container is not modified.

procedure Insert (Container : in out List; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1);

If Before is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Allocates Count new nodes with elements initialized with any implicit initial values for any part (as for an object_declaration with no initialization expression - see 3.3.1), and inserts them prior to the node designated by Before. If Before equals No_Element, the new node is inserted immediately following the last node (if any). Position designates the first newly-inserted node. Any exception raised during allocation of internal storage is propagated, and Container is not modified.

procedure Delete (Container : in out List; Position : in out Cursor; Count : in Count_Type := 1);

If Position equals No_Element, this operation has no effect. If Position does not designate an element in Container, then Program_Error is propagated. Otherwise Delete removes Count nodes starting at the node designated by Position from Container (or all of the nodes if there are less than Count nodes starting at Position). Any exception raised during deallocation of internal storage is propagated.

procedure Delete_First (Container : in out List; Count : in Count_Type := 1);

If Length(Container) >= Count, Delete_First removes the first Count nodes from Container; otherwise, all of the nodes in Container are removed. Any exceptions raised during deallocation of storage are propagated.

procedure Delete_Last (Container : in out List; Count : in Count_Type := 1);

If Length(Container) >= Count, Delete_Last removes the last Count nodes from Container; otherwise, all of the nodes in Container are removed. Any exceptions raised during deallocation of storage are propagated.

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

Reorders the nodes of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. The sort must be stable. Any exception raised during evaluation of "<" is propagated.

AARM Notes Unlike array sorts, we do require stable sorts here. That's because algorithms in the merge sort family (as described by Knuth) can be both fast and stable. Such sorts use the extra memory as offered by the links to provide better performance.

Note that list sorts never copy elements; it is the nodes, not the elements, that are reordered. End AARM Notes

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

If Source denotes the same object as Target, the operation has no effect. Otherwise this operation reorders nodes such that they are removed from Source and moved to Target. Target and Source are assumed to be sorted smallest first as determined by the generic formal "<" operator. The nodes in Source containing elements that are less than elements in Target are spliced in before the elements already in Target. The nodes in Source container elements that are equal to or greater than elements in Target are spliced in after the elements already in Target. Any exception raised during evaluation of "<" is propagated, immediately terminating the merge operation.

procedure Reverse_List (Container : in out List);

Reorders the nodes of Container in reverse order.

procedure Swap (I, J : in Cursor);

AARM Notes: To Be Honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed.

procedure Swap_Links (Container : in out List; I, J : in Cursor);

If either I or J is No_Element, then Constraint_Error is propagated. If I or J do not designate an element in Container, then Program_Error is propagated. Otherwise, Swap_Links exchanges the nodes designated by I and J.

AARM Note: Unlike Swap, this exchanges the nodes, not the elements. No copying is performed. I and J designate the same elements after this call as they did before it. This operation can provide better performance than Swap if the element size is large.

procedure Splice (Target : in out List; Before : in Cursor; Source : in out List);

If Before is not No_Element, and does not designate an element in Target, then Program_Error is propagated. If Source denotes the same object as Target, the operation has no effect. Otherwise, Splice reorders nodes such that they are removed from Source and moved to Target, just prior to Before. If Before equals No_Element, the nodes of Source are spliced after the last node of Target. The length of Target is incremented by the number of nodes in Source, and the length of Source is set to 0.

procedure Splice (Target : in out List; Before : in Cursor; Position : in Cursor);

If either of Before or Position is not No_Element, and does not designate an element in Target, then Program_Error is propagated. If Position equals No_Element, or if Position equals Before, or if the successor of Position equals Before, the operation has no effect. Otherwise the node designated by Position becomes the predecessor of Before. If Before equals No_Element, then Position is moved after the last node.

procedure Splice (Target : in out List; Before : in Cursor; Source : in out List; Position : in Cursor);

If Before does not equal No_Element, and does not designate a node in Target, then Program_Error is propagated. If Position does not equal No_Element, and does not designate a node in Source, then Program_Error is propagated. If Source denotes the same object as Target, then Splice is equivalent to the Splice operation sans Source parameter. If Position equals No_Element, the operation has no effect. Otherwise the node designated by Position is removed from Source and moved to Target, immediately prior to Before. If Before equals No_Element, then Position is moved after the last node of Target. The length of Target is incremented, and the length of Source is decremented.

function First (Container : List) return Cursor;

Returns a cursor that designates the first node. If Container is empty, First returns the value No_Element.

function First_Element (Container : List) return Element_Type;

If Container is empty, then Constraint_Error is propagated. Otherwise, it returns Element (First (Container)).

function Last (Container : List) return Cursor;

Returns a cursor that designates the last node. If Container is empty, Last returns the value No_Element.

function Last_Element (Container : List) return Element_Type;

If Container is empty, then Constraint_Error is propagated. Otherwise, it returns Element (Last (Container)).

function Contains (Container : List; Item : Element_Type) return Boolean;

Equivalent to Find (Container, Item) /= No_Element.

function Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

If Position is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Searches the nodes of Container for an element equal to Item. The search starts at the node designated by Position. If Position equals No_Element, then the search begins at the first node. If no element is found that matches Item, then Find returns the value No_Element.

function Reverse_Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor;

If Position is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Searches the nodes of Container in reverse for an element equal to Item. The search starts at the node designated by Position. If Position equals No_Element, then the search begins at the last node. If no element is found that matches Item, then Find returns the value No_Element.

function Next (Position : Cursor) return Cursor;

If Position equals No_Element or designates the last node of the container, then Next returns the value No_Element. Otherwise, returns a cursor that designates the successor of the node designated by Position.

function Previous (Position : Cursor) return Cursor;

If Position equals No_Element or designates the first node of the container, then Previous returns the value No_Element. Otherwise, returns a cursor that designates the predecessor of the node designated by Position.

The procedure Next is equivalent to Position := Next (Position).

The procedure Previous is equivalent to Position := Previous (Position).

function Has_Element (Position : Cursor) return Boolean;

Returns True if Position designates an element, and returns False otherwise.

AARM Note: To Be Honest: This function may not detect cursors that designate deleted elements; such cursors are invalid (see below) and any use of them (including in this routine) is erroneous.

procedure Iterate

(Container : in List;

Process : not null access procedure (Position : in Cursor));

Invokes Process.all with a cursor that designates each node in Container. Any exceptions raised during Process are propagated. Program_Error is propagated if:

* Process.all attempts to insert or delete elements from Container; or

* Process.all calls a routine that reorders the elements of Container (Swap_Links, Splice, Generic_Sort, or Generic_Merge); or

* Process.all finalizes Container; or

* Process.all calls Move with Container as a parameter.

AARM Note: This check takes place when the operations that insert or delete elements, etc. are called. There is no check needed if an attempt is made to insert or delete nothing (that is, Count = 0).

See Iterate for vectors for a suggested implementation of the check.

Swap is not included here, as it only copies elements. End AARM Notes.

procedure Reverse_Iterate

(Container : in List;

Process : not null access procedure (Position : in Cursor));

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

Erroneous Execution

A Cursor value is invalid if any of the following have occurred since it was created:

* The list that contains the element it designates has been finalized;

* The list that contains the element it designates has been used as the Source or Target of a call to Move;

* The element it designates has been deleted.

The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Doubly_Linked_Lists is called with an invalid cursor parameter.

Execution also is erroneous if the called Process procedure of a call to Query_Element or Update_Element executes an operation that causes the Position cursor of Query_Element or Update_Element to become invalid.

AARM Notes: The list above is intended to be exhaustive. In other cases, a cursor value continues to designate its original element. For instance, cursor values survive the insertion and deletion of other nodes.

While it is possible to check for these cases, in many cases the overhead necessary to make the check is substantial in time or space. Implementations are encouraged to check for as many of these cases as possible and raise Constraint_Error if detected. End AARM Notes.

Implementation Requirements

No storage associated with a doubly-linked List object shall be lost upon assignment or scope exit.

Implementation Advice

Containers.Doubly_Linked_Lists should be implemented similarly to a linked list. In particular, if N is the length of a list, then the worst-case time complexity of Element, Insert with Count=1, and Delete with Count=1 should be O(log N).

AARM Note We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes O(N) time to access elements, that program could be unusable when the lists are large. We allow O(log N) access because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations.

The worst-case time complexity of a call on an instantiation of Containers.Doubly_Linked_Lists.Generic_Sort should be O(N**2), and the average time complexity should be better than O(N**2).

AARM Note In other words, we're requiring the use of a better than O(N**2) sorting algorithm, such as Quicksort. No Bubble sorts allowed!

NOTE Sorting a list never copies elements, and is a stable sort (equal elements remain in the original order). This is different than sorting an array or vector, which may need to copy elements, and is probably not a stable sort.

A.18.4 Maps

The language-defined packages Containers.Hashed_Maps and Containers.Ordered_Maps provide private types Map and Cursor, and a set of operations for each type. A map container allows an arbitrary type to be used as a key to find the element associated with that key. A hashed map uses a hash function to organize the keys, while an ordered map orders the keys per a specified relation.

This section describes the declarations that are common to both kinds of maps. See A.18.5 for a description of the semantics specific to Containers.Hashed_Maps and A.18.6 for a description of the semantics specific to Containers.Ordered_Maps.

The type Map is used to represent maps. The type Map needs finalization (see 7.6).

A map contains pairs of keys and elements, called nodes. Map cursors designate nodes, but also can be thought of as designating an element (the element contained in the node) for consistency with the other containers. There exists an equivalence relation on keys, whose definition is different for hashed maps and ordered maps. A map never contains two or more nodes with equivalent keys. The length of a map is the number of nodes it contains.

Each nonempty map has two particular nodes called the *first node* and the *last node* (which may be the same). Each node except for the last node has a successor node. If there are no other intervening operations, starting with the first node and repeatedly going to the successor node will visit each node in the map exactly once until the last node is reached. The exact definition of these terms is different for hashed maps and ordered maps.

Empty_Map represents the empty Map object. It has a length of 0. If an object of type Map is not otherwise initialized, it is initialized to the same value as Empty_Map.

No_Element represents a cursor that designates no node. If an object of type Cursor is not otherwise initialized, it is initialized to the same value as No_Element.

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

If Left and Right denote the same map object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, for each key K in Left, the function returns False if:

* a key equivalent to K is not present in Right; or

* the element associated with K in Left is not equal to the element associated with K in Right (using the generic formal equality operator for elements).

If the function has not returned a result after checking all of the keys, it returns True. Any exception raised during evaluation of key equivalence or element equality is propagated.

function Length (Container : Map) return Count_Type;

Returns the number of nodes in Container.

function Is_Empty (Container : Map) return Boolean;

Equivalent to Length (Container) = 0.

procedure Clear (Container : in out Map);

Removes all the nodes from Container. Any exception raised during deallocation of storage is propagated.

function Key (Position : Cursor) return Key_Type;

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Key returns the key component of the node designated by Position.

function Element (Position : Cursor) return Element_Type;

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Element returns the element component of the node designated by Position.

procedure Query_Element

(Position : in Cursor;

Process : not null access procedure (Key : in Key_Type; Element : in Element_Type));

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Query_Element calls Process.all with the key and element from the node designated by Position as the arguments.

procedure Update_Element

(Position : in Cursor;

Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));

If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Update_Element calls Process.all with the key and element from the node designated by Position as the arguments.

If Element_Type is unconstrained and definite, then the Element parameter of Process.all shall be unconstrained.

procedure Replace_Element (Position : in Cursor; By : in Element_Type);

If Position equals No_Element, then Constraint_Error is propagated. Otherwise this operation assigns By to the element of the node designated by Position.

procedure Move (Target : in out Map; Source : in out Map);

Move first clears Target. Then each node from Source is removed from Source and inserted into Target. The length of Source is 0 after a successful call to Move.

procedure Insert (Container : in out Map; Key : in Key_Type; New_Item : in Element_Type; Position : out Cursor; Inserted : out Boolean);

Insert checks if a node with a key equivalent to Key is already present in Container. If a match is found, Inserted is set to False and Position designates the element with the matching key. Otherwise, Insert allocates a new node, initializes it to Key and New_Item, and adds it to Container; Inserted is set to True and Position designates the newly-inserted node. Any exception raised during allocation is propagated and Container is not modified.

procedure Insert (Container : in out Map; Key : in Key_Type; Position : out Cursor; Inserted : out Boolean);

Insert inserts Key into Container as per the five-parameter Insert, with the difference that an element initialized with any implicit initial values for any part (as for an object_declaration with no initialization expression - see 3.3.1) is inserted.

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

Insert inserts Key and New_Item into Container as per the five-parameter Insert, with the difference that if a node with a key equivalent to Key is already in the map, then Constraint_Error is propagated.

AARM Note: This is equivalent to:

declare Inserted : Boolean; C : Cursor; begin Insert (Container, Key, New_Item, C, Inserted); if not Inserted then raise Constraint_Error; end if; end;

but doesn't require the hassle of out parameters.

procedure Include (Container : in out Map; Key : in Key_Type; New_Item : in Element_Type);

Include inserts Key and New_Item into Container as per the five-parameter Insert, with the difference that if a node with a key equivalent to Key is already in the map, then this operation assigns Key and New_Item to the matching node. Any exception raised during assignment is propagated.

AARM Note: This is equivalent to:

declare C : Cursor := Find (Container, Key); begin if C = No_Element then Insert (Container, Key, New_Item); else Replace (Container, Key, New_Item); end if; end;

but this avoids doing the search twice.

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

Replace checks if a node with a key equivalent to Key is present in Container. If a match is found, Replace assigns Key and New_Item to the matching node; otherwise, Constraint_Error is propagated.

AARM Note: We update the key as well as the element, as the key might include additional information that does not participate in equivalence. If only the element needs to be updated, use Replace_Element (Find (Container, Key), New_Element).

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

Delete checks if a node with a key equivalent to Key is present in Container. If a match is found, Delete removes the node from the map; otherwise, Constraint_Error is propagated.

procedure Delete (Container : in out Map; Position : in out Cursor);

If Position equals No_Element, Delete has no effect. If Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Delete removes the node designated by Position from the map. Position is set to No_Element on return.

AARM Note: The check on Position checks that the cursor does not belong to some other map. This check implies that a reference to the map is included in the cursor value. This wording is not meant to require detection of dangling cursors; such cursors are defined to be invalid, which means that execution is erroneous, and any result is allowed (including not raising an exception).

procedure Exclude (Container : in out Map; Key : in Key_Type);

Exclude checks if a node with a key equivalent to Key is present in Container. If a match is found, Exclude removes the node from the map and then deallocates the node.

function Contains (Container : Map; Key : Key_Type) return Boolean;

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

function Find (Container : Map; Key : Key_Type) return Cursor;

If Length (Container) equals 0, then Find returns No_Element. Otherwise, Find checks if a node with a key equivalent to Key is present in Container. If a match is found, a cursor designating the matching node is returned; otherwise, No_Element is returned.

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

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

function First (Container : Map) return Cursor;

If Length (Container) = 0, then First returns No_Element. Otherwise, First returns a cursor that designates the first node in Container.

function Next (Position : Cursor) return Cursor;

Returns a cursor that designates the successor of the node designated by Position. If Position designates the last node, then No_Element is returned. If Position equals No_Element, then No_Element is returned.

procedure Next (Position : in out Cursor);

Equivalent to Position := Next (Position).

function Has_Element (Position : Cursor) return Boolean;

Returns True if Position designates a node, and returns False otherwise.

AARM Note: To Be Honest: This function may not detect cursors that designate deleted elements; such cursors are invalid (see below).

procedure Iterate

(Container : in Map;

Process : not null access procedure (Position : in Cursor));

Iterate calls Process.all with a cursor that designates each node in Container, starting with the first node and moving the cursor according to the successor relation. Any exception raised by Process.all is propagated. Program_Error is propagated if:

* Process.all attempts to insert or delete nodes from Container; or

* Process.all finalizes Container; or

* Process.all calls Move with Container as a parameter.

AARM Note: This check takes place when the operations that insert or delete elements, etc. are called.

See Iterate for vectors for a suggested implementation of the check. End AARM Notes.

Erroneous Execution

A Cursor value is invalid if any of the following have occurred since it was created:

* The map that contains the node it designates has been finalized;

* The map that contains the node it designates has been used as the Source or Target of a call to Move;

* The node it designates has been deleted from the map.

The result of "=" or Has_Element is unspecified if these function are called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps is called with an invalid cursor parameter.

Execution also is erroneous if the called Process.all procedure of a call to Query_Element or Update_Element executes an operation that causes the Position cursor of Query_Element or Update_Element to become invalid.

Implementation Requirements

No storage associated with a Map object shall be lost upon assignment or scope exit.

A.18.5 The Package Containers.Hashed_Maps

Static Semantics

The library package Containers.Hashed_Maps has the following declaration:

generic

type Key_Type is private;

type Element_Type is private;

with function Hash (Key : Key_Type) return Hash_Type;

with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;

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

package Ada.Containers.Hashed_Maps is pragma Preelaborate (Hashed_Maps);

type Map is tagged private;

type Cursor is private;

Empty_Map : constant Map;

No_Element : constant Cursor;

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

function Length (Container : Map) return Count_Type;

function Is_Empty (Container : Map) return Boolean;

procedure Clear (Container : in out Map);

function Key (Position : Cursor) return Key_Type;

function Element (Position : Cursor) return Element_Type;

procedure Query_Element (Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in Element_Type));

procedure Update_Element (Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));