A.18 Containers
This Reference Manual output has not been verified, and may contain omissions or errors. Report any problems on the tracking issue
This clause presents the specifications of the package Containers and several child packages, which provide facilities for storing collections of elements.
Term entry: container — structured object that represents a collection of elements all of the same (potentially class-wide) type, such as a vector or a tree
Note: Several predefined container types are provided by the children of package Ada.Containers (see A.18.1).
A variety of sequence and associative containers are provided. Each container package defines a cursor type as well as a container type. A cursor is a reference to an element within a container. Many operations on cursors are common to all of the containers. A cursor referencing an element in a container is considered to be overlapping only with the element itself.
The last sentence is intended to clarify that operations that just use a cursor do not interfere if the cursor objects designated different elements of the container in terms of the concurrent call rules of Annex A.
A cursor is not considered to overlap with other elements of the associated container, thus parallel operations involving a set of cursors each operating on mutually exclusive sets of elements from the same container are expected to work.
We use the term “container” alone when it is clear from context what kind of entity (package, type, or object) that we are talking about. Otherwise, we use “container package”, “container type”, or “container object”. Note that "container type" is defined in 4.3.5 for a different usage; in all of A.18 we mean “container type” to be one of the primary types declared in the child packages of package Containers, such as Vector, List, or Map.
Some operations of the language-defined child units of Ada.Containers have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. An action on a container that can add or remove an element is considered to tamper with cursors, and these are prohibited during all such operations. An action on a container that can replace an element with one of a different size is considered to tamper with elements, and these are prohibited during certain of such operations. The details of the specific actions that are considered to tamper with cursors or elements are defined for each child unit of Ada.Containers.
Several of the language-defined child units of Ada.Containers include a nested package named Stable, which provides a view of a container that prohibits any operations that would tamper with elements. By using a Stable view for manipulating a container, the number of tampering checks performed while performing the operations can be reduced. The details of the Stable subpackage are defined separately for each child unit of Ada.Containers that includes such a nested package.
Within this clause we provide O(X). 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, a complexity of O(f(N)) means that there exists a finite A such that for any N, t(N)/f(N) < A.
Of course, an implementation can do better than a specified O(f(N)): for example, O(1) meets the requirements for O(log N).
This concept seems to have as many names as there are authors. We used “Landau symbol” because that's what our reference does. But we'd also seen this referred as big-O notation (sometimes written as big-oh), and as Bachmann notation. Whatever the name, it always has the above definition.
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.
When a formal function is used to provide an ordering for a container, it is generally required to define a strict weak ordering. A function "<" defines a strict weak ordering if it is irreflexive, asymmetric, transitive, and in addition, if x < y for any values x and y, then for all other values z, (x < z) or (z < y). Elements are in a smallest first order using such an operator if, for every element y with a predecessor x in the order, (y < x) is false.
Given a "<" operator that provides a strict weak ordering, knowing that (y < x) is false is enough to know that (x <= y) is true. For a strict weak ordering, (x = y) when both (x < y) and (y < x) are false. Therefore, it is not necessary to use the "=" operator or test (x < y). We only need to discuss adjacent elements since a strict weak ordering is transitive.
Language Design Principles
This subclause 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 nonlimited containers are provided:
- (Expandable) Vectors of any nonlimited type;
- Doubly-linked Lists of any nonlimited type;
- Hashed Maps keyed by any nonlimited hashable type, and containing any nonlimited type;
- Ordered Maps keyed by any nonlimited ordered type, and containing any nonlimited type;
- Hashed Sets of any nonlimited hashable type;
- Ordered Sets of any nonlimited ordered type;
- Multiway Trees of any nonlimited type;
- Holders of any (indefinite) nonlimited type;
- Synchronized queues of any definite nonlimited type; and
- Priority queues of any definite nonlimited type.
Separate versions for definite and indefinite element types are provided, as those for definite types can be implemented more efficiently. Similarly, a separate bounded version is provided in order to give more predictable memory usage.
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 (by the implementation or by a secondary standard), 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. These include:
- Library packages must allow concurrent calls – 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 and concurrent calls to operations of the container have overlapping parameters.
- Language-defined types must 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.
- Equality of language-defined types must 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.
- Redispatching is not allowed (unless it is required). That means that overriding a container operation will not change the behavior of any other predefined container operation. This provides a stable base for extensions.
If a container's element type is controlled, the point at which the element is finalized will depend on the implementation of the container. For certain kinds of containers, we require finalization behavior based on the canonical implementation of the container (see the Implementation Requirements below). For the "normal" containers, 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 implementations flexibility to cache, block, split , or reusethe nodes of the container.
The use of controlled types also brings up the possibility of failure of finalization (and thus deallocation) of an element. This is a “serious bug”, as AI95-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 that, if the containers are written in Ada, 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.
Static Semantics
6/5Certain subprograms declared within instances of some of the generic packages presented in this clause are said to perform indefinite insertion. These subprograms are those corresponding (in the sense of the copying described in 12.3) to subprograms that have formal parameters of a generic formal indefinite type and that are identified as performing indefinite insertion in the subclause defining the generic package.
If a subprogram performs indefinite insertion, then certain run-time checks are performed as part of a call to the subprogram; if any of these checks fail, then the resulting exception is propagated to the caller and the container is not modified by the call. These checks are performed for each parameter corresponding (in the sense of the copying described in 12.3) to a parameter in the corresponding generic whose type is a generic formal indefinite type. The checks performed for a given parameter are those checks explicitly specified in 4.8 that would be performed as part of the evaluation of an initialized allocator whose access type is declared immediately within the instance, where:
- the value of the
qualified_expressionis that of the parameter; and 9/4 - the designated subtype of the access type is the subtype of the parameter; and
- finalization of the collection of the access type has started if and only if the finalization of the instance has started.
The phrase "explicitly specified" means those checks for which 4.8 includes the phrase "<some exception> is raised if ...". It does not refer, for example, to any checks performed as part of any subtype conversion. In particular, this wording includes the checks described in 4.8 to be performed in the case of a class-wide designated type, and of a designated subtype that has access discriminant parts. These checks are needed to prevent containers from outliving their contained (Element_Type or Key_Type) values.
These rules have a dual purpose. Mainly, we are requiring checks needed to prevent dangling references. As a side effect, we are also allowing checks needed to permit an implementation of a container generic to make use of access types in a straightforward way. As an example of the second purpose, suppose that an implementation does declare such an access type and suppose further that the finalization of the collection of the access type has started. These rules allow Program_Error to be propagated in this case (as specified in 4.8); this is necessary to allow an all-Ada implementation of these packages.
Implementation Requirements
11/5For an indefinite container (one whose type is defined in an instance of a child package of Containers whose defining_identifier contains "Indefinite"), each element of the container shall be created when it is inserted into the container and finalized when it is deleted from the container (or when the container object is finalized if the element has not been deleted). For a bounded container (one whose type is defined in an instance of a child package of Containers whose defining_identifier starts with "Bounded") that is not an indefinite container, all of the elements of the capacity of the container shall be created and default initialized when the container object is created; the elements shall be finalized when the container object is finalized. [For other kinds of containers, when elements are created and finalized is unspecified.]
This allows a user to be able to reason about the behavior of elements that have controlled parts. In most cases, such elements need to be stored in an indefinite container.
If the containers are implemented in Ada, this implies that elements for an indefinite container are allocated individually, and that a bounded container contains an array of elements or other data structure that is initialized for the entire capacity of the container when it is created. There is no such restriction on the implementation of the "normal" containers; these can be handled in any way convenient to the implementation — in particular, node reuse is allowed.
For an instance I of a container package with a container type, the specific type T of the object returned from a function that returns an object of an iterator interface, as well as the primitive operations of T, shall be nonblocking. The Global aspect specified for T and the primitive operations of T shall be (in all, out synchronized) or a specification that allows access to fewer global objects.
This requires that the traversal and iteration operations of a container do not create, destroy, or assign any objects of a formal type of I, nor call any formal subprograms of I. Those objects and subprograms might be blocking (depending on the actual parameters). We put similar requirements on the individual traversal operations in the container package definitions.
These requirements allows users to use container iterators inside of parallel constructs, regardless of the actual parameters to the instantiation. If such an iterator allowed blocking, it would be illegal inside of a parallel construct (see 9.5). If such an iterator allowed writing of unsynchronized global objects, it would be illegal when the default conflict checking policy is in effect (see 9.10.1). These requirements include sequential iterators; the iterator does not need to appear in a parallel loop to trigger these requirements.
We have to give these requirements as a text rule, as there is no place to declare suitable aspects. The specific type of a container iterator is declared by the implementation and is not part of the visible specification (iterator functions just return a value of a class-wide type). The iterator interface itself cannot impose such a requirement since it needs to be able to work with user-defined types that do need to allow blocking. We give this as a global requirement to avoid duplication.
Extensions to Ada 95
Wording Changes from Ada 2005
Extensions to Ada 2012
We now say that a cursor only overlaps with the element it designates, rather than with the whole container. This allows some reading operations to operate on the container in parallel without separate synchronization.
Wording Changes from Ada 2012
Corrigendum: Added a definition of “performs indefinite insertion”. This is used in other subclauses and any resulting inconsistencies are documented there.
Moved the basic description of tampering checks here, to cut duplication in description of the individual containers. Added a description of stable views of containers.
Added a global requirement that iterators returned from containers are nonblocking if the instance is nonblocking.
Defined when objects are created and finalized for Bounded and Indefinite containers, so that these can be used reliably with controlled element types. This is not incompatible as this behavior was previously unspecified; code depending on specific behavior was wrong.
Added a definition of “smallest first” ordering, so that the behavior of the Sort procedures when elements are equal is well-defined.
A.18.1 The Package Containers
1/2The package Containers is the root of the containers subsystem.
Static Semantics
2/2The library package Containers has the following declaration:
package Ada.Containers
with Pure is
4/2
type Hash_Type is mod implementation-defined;
5/2
type Count_Type is range 0 .. implementation-defined;
5.1/3
Capacity_Error : exception;
6/2
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.
The value of Containers.Hash_Type'Modulus. The value of Containers.Count_Type'Last.
Capacity_Error is raised when the capacity of a container is exceeded.
Implementation Advice
8/2Hash_Type'Modulus should be at least 2**32. Count_Type'Last should be at least 2**31–1.
Containers.Hash_Type'Modulus should be at least 2**32. Containers.Count_Type'Last should be at least 2**31–1.
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.
Extensions to Ada 95
Incompatibilities With Ada 2005
Exception Capacity_Error is added to Containers. If Containers is referenced in a use_clause, and an entity with the name Capacity_Error is defined in a package that is also referenced in a use_clause, the entity Capacity_Error may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur.
A.18.2 The Generic Package Containers.Vectors
1/2The language-defined generic package Containers.Vectors provides private types Vector and Cursor, and a set of operations for each type. 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 behaves conceptually as an array that 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 is the maximum number of elements that can be inserted into the vector prior to it being automatically expanded.
Elements in a vector container can be referred to by an index value of a generic formal type. The first element of a vector always has its index value equal to the lower bound of the formal type.
A vector container may contain empty elements. Empty elements do not have a specified value.
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.
Static Semantics
5/2The generic library package Containers.Vectors has the following declaration:
with Ada.Iterator_Interfaces;
generic
type Index_Type is range <>;
type Element_Type is private;
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
package Ada.Containers.Vectors
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
For the Global aspect, any side-effects of the actual parameters of an instance are ignored. So Global => in out synchronized means that the only global side-effects allowed are associated with the actual generic parameters of the instance or with any synchronized state. Unsynchronized package state is not allowed for any container package, and pure packages do not allow any package state at all (they typically have Global => null).
Similarly, when Nonblocking is set to True for a generic unit, it still includes the blocking effects of the actual parameters to the instance. Thus, the only blocking allowed is that associated with the actual generic parameters. If none of the actual paramerters allow blocking, then no operation of the generic instance may block.
subtype Extended_Index is
Index_Type'Base range
Index_Type'First-1 ..
Index_Type'Min (Index_Type'Base'Last - 1, Index_Type'Last) + 1;
No_Index : constant Extended_Index := Extended_Index'First;
The base type of a scalar type is always nonblocking and has Global => null. Therefore, so long as this type is used in the implementation, whether or not the actual type for Index_Type allows blocking or side-effects does not matter. Therefore, we require that operations that only operate on the container implementation be nonblocking and have Global => null regardless of the actual parameters.
type Vector is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Vector,
Aggregate => (Empty => Empty,
Add_Unnamed => Append,
New_Indexed => New_Vector,
Assign_Indexed => Replace_Element),
Stable_Properties => (Length, Capacity,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Length (Vector) = 0 and then
(not Tampering_With_Cursors_Prohibited (Vector)) and then
(not Tampering_With_Elements_Prohibited (Vector)),
Preelaborable_Initialization;
9/5
type Cursor is private
with Preelaborable_Initialization;
10/2
Empty_Vector : constant Vector;
11/2
No_Element : constant Cursor;
11.1/5
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Any operation that takes a cursor but no vector can read the vector associated with the cursor. We only know that there is some object of type Vector. Since we don't have a global specification that describes all objects of a specific type, we have to allow reading any object by specifying in all. For such functions, we don't allow writing any object, even those associated with generic formal parameters, thus we also specify Use_Formal => null.
function Has_Element (Container : Vector; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
For operations that do not depend on any of the operations of the generic formal parameters (including those of formal types), we specify that the operation has no side-effects of any kind. This requires specifying that there is no dependence on the generic formal parameters with Use_Formal => null in addition to no usual side-effects with null. We also specify Nonblocking on such operations in order that the operation never blocks even if some of the actual parameters allow blocking.
package Vector_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
12/2
function "=" (Left, Right : Vector) return Boolean;
12.1/5
function Tampering_With_Cursors_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
12.2/5
function Tampering_With_Elements_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
12.3/5
function Maximum_Length return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
12.4/5
function Empty (Capacity : Count_Type := implementation-defined)
return Vector
with Pre => Capacity <= Maximum_Length
or else raise Constraint_Error,
Post =>
Capacity (Empty'Result) >= Capacity and then
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
13/5
function To_Vector (Length : Count_Type) return Vector
with Pre => Length <= Maximum_Length or else raise Constraint_Error,
Post =>
To_Vector'Result.Length = Length and then
not Tampering_With_Elements_Prohibited (To_Vector'Result)
and then
not Tampering_With_Cursors_Prohibited (To_Vector'Result)
and then
To_Vector'Result.Capacity >= Length;
14/5
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector
with Pre => Length <= Maximum_Length or else raise Constraint_Error,
Post =>
To_Vector'Result.Length = Length and then
not Tampering_With_Elements_Prohibited (To_Vector'Result)
and then
not Tampering_With_Cursors_Prohibited (To_Vector'Result)
and then
To_Vector'Result.Capacity >= Length;
14.1/5
function New_Vector (First, Last : Index_Type) return Vector is
(To_Vector (Count_Type (Last - First + 1)))
with Pre => First = Index_Type'First;
15/5
function "&" (Left, Right : Vector) return Vector
with Pre => Length (Left) <= Maximum_Length - Length (Right)
or else raise Constraint_Error,
Post => Length (Vectors."&"'Result) =
Length (Left) + Length (Right) and then
not Tampering_With_Elements_Prohibited
(Vectors."&"'Result) and then
not Tampering_With_Cursors_Prohibited
(Vectors."&"'Result) and then
Vectors."&"'Result.Capacity >=
Length (Left) + Length (Right);
16/5
function "&" (Left : Vector;
Right : Element_Type) return Vector
with Pre => Length (Left) <= Maximum_Length - 1
or else raise Constraint_Error,
Post => Vectors."&"'Result.Length = Length (Left) + 1 and then
not Tampering_With_Elements_Prohibited
(Vectors."&"'Result) and then
not Tampering_With_Cursors_Prohibited
(Vectors."&"'Result) and then
Vectors."&"'Result.Capacity >= Length (Left) + 1;
17/5
function "&" (Left : Element_Type;
Right : Vector) return Vector
with Pre => Length (Right) <= Maximum_Length - 1
or else raise Constraint_Error,
Post => Length (Vectors."&"'Result) = Length (Right) + 1 and then
not Tampering_With_Elements_Prohibited
(Vectors."&"'Result) and then
not Tampering_With_Cursors_Prohibited
(Vectors."&"'Result) and then
Vectors."&"'Result.Capacity >= Length (Right) + 1;
18/5
function "&" (Left, Right : Element_Type) return Vector
with Pre => Maximum_Length >= 2 or else raise Constraint_Error,
Post => Length ("&"'Result) = 2 and then
not Tampering_With_Elements_Prohibited
(Vectors."&"'Result) and then
not Tampering_With_Cursors_Prohibited
(Vectors."&"'Result) and then
Vectors."&"'Result.Capacity >= 2;
19/5
function Capacity (Container : Vector) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
20/5
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
21/5
function Length (Container : Vector) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
22/5
procedure Set_Length (Container : in out Vector;
Length : in Count_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length <= Maximum_Length
or else raise Constraint_Error),
Post => Container.Length = Length and then
Capacity (Container) >= Length;
23/5
function Is_Empty (Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
24/5
procedure Clear (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
25/5
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor
with Post => (if Index in
First_Index (Container) .. Last_Index (Container)
then Has_Element (Container, To_Cursor'Result)
else To_Cursor'Result = No_Element),
Nonblocking, Global => null, Use_Formal => null;
26/5
function To_Index (Position : Cursor) return Extended_Index
with Nonblocking, Global => in all;
26.1/5
function To_Index (Container : Vector;
Position : Cursor) return Extended_Index
with Pre => Position = No_Element or else
Has_Element (Container, Position) or else
raise Program_Error,
Post => (if Position = No_Element then To_Index'Result = No_Index
else To_Index'Result in First_Index (Container) ..
Last_Index (Container)),
Nonblocking, Global => null, Use_Formal => null;
27/5
function Element (Container : Vector;
Index : Index_Type)
return Element_Type
with Pre => Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Nonblocking, Global => null, Use_Formal => Element_Type;
Here the Nonblocking and Global contracts are saying that Element depends on the properties of the actual for Element_Type, but not on the properties of the actuals for Index_Type or "=". This is necessary as copying the element may require calling Adjust and Finalize for the actual Element_Type, and those may have side-effects or block.
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
28.1/5
function Element (Container : Vector;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
29/5
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error);
30/5
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
31/5
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type))
with Pre => Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error;
32/5
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;
32.1/5
procedure Query_Element
(Container : in Vector;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
33/5
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error;
34/5
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
34.1/5
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
Finalization of this type will update the tampering counter of an associated container. We know this has to be an object of type Vector, but we don't have a way to specify that. We need this separate Global in case an object of this type is declared to exist separately from the short-lived object associated with a call of the Constant_Reference function.
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
34.3/5
function Constant_Reference (Container : aliased in Vector;
Index : in Index_Type)
return Constant_Reference_Type
with Pre => Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
34.4/5
function Reference (Container : aliased in out Vector;
Index : in Index_Type)
return Reference_Type
with Pre => Index in
First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
34.5/5
function Constant_Reference (Container : aliased in Vector;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
34.6/5
function Reference (Container : aliased in out Vector;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
34.7/5
procedure Assign (Target : in out Vector; Source : in Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target) and then
Capacity (Target) >= Length (Target);
34.8/5
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post => Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result)
and then
Copy'Result.Capacity >= (if Capacity = 0 then
Length (Source) else Capacity);
35/5
procedure Move (Target : in out Vector;
Source : in out Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source)'Old and then
Length (Source) = 0 and then
Capacity (Target) >= Length (Source)'Old);
36/5
procedure Insert_Vector (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
37/5
procedure Insert_Vector (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
38/5
procedure Insert_Vector (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
39/5
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Capacity (Container) >= Length (Container);
40/5
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Capacity (Container) >= Length (Container);
41/5
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
42/5
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Capacity (Container) >= Length (Container);
43/5
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
44/5
procedure Prepend_Vector (Container : in out Vector;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
45/5
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Capacity (Container) >= Length (Container);
46/5
procedure Append_Vector (Container : in out Vector;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
47/5
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post =>
Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
47.1/5
procedure Append (Container : in out Vector;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - 1
or else raise Constraint_Error),
Post => Length (Container)'Old + 1 = Length (Container) and then
Capacity (Container) >= Length (Container);
48/5
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Capacity (Container) >= Length (Container);
49/5
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count =
Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
50/5
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Index in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error),
Post => Length (Container)'Old - Count <=
Length (Container);
51/5
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container)'Old - Count <=
Length (Container) and then
Position = No_Element;
52/5
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
53/5
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
54/5
procedure Reverse_Elements (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
55/5
procedure Swap (Container : in out Vector;
I, J : in Index_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error) and then
(J in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error);
56/5
procedure Swap (Container : in out Vector;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
57/5
function First_Index (Container : Vector) return Index_Type
with Nonblocking, Global => null, Use_Formal => null,
Post => First_Index'Result = Index_Type'First;
58/5
function First (Container : Vector) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
59/5
function First_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
60/5
function Last_Index (Container : Vector) return Extended_Index
with Nonblocking, Global => null, Use_Formal => null,
Post => (if Length (Container) = 0
then Last_Index'Result = No_Index
else Count_Type(Last_Index'Result - Index_Type'First) =
Length (Container) - 1);
61/5
function Last (Container : Vector) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
62/5
function Last_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
63/5
function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
63.1/5
function Next (Container : Vector; Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Has_Element (Container, Next'Result) then
To_Index (Container, Next'Result) =
To_Index (Container, Position) + 1
elsif Next'Result = No_Element then
Position = Last (Container)
else False);
64/5
procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
64.1/5
procedure Next (Container : in Vector;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
65/5
function Previous (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Previous'Result = No_Element);
65.1/5
function Previous (Container : Vector;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element
then Previous'Result = No_Element
elsif Has_Element (Container, Previous'Result) then
To_Index (Container, Previous'Result) =
To_Index (Container, Position) - 1
elsif Previous'Result = No_Element then
Position = First (Container)
else False);
66/5
procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
66.1/5
procedure Previous (Container : in Vector;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
67/2
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
68/5
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
69/2
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
70/5
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Reverse_Find'Result /= No_Element
then Has_Element (Container, Reverse_Find'Result));
71/2
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
72/3
This paragraph was deleted.
73/5
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
74/5
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
74.1/5
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
74.2/5
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
75/5
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
with Nonblocking, Global => null is
76/2
function Is_Sorted (Container : Vector) return Boolean;
77/5
procedure Sort (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
78/5
procedure Merge (Target : in out Vector;
Source : in out Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Length (Target) <= Maximum_Length - Length (Source)
or else raise Constraint_Error) and then
((Length (Source) = 0 or else
not Target'Has_Same_Storage (Source))
or else raise Program_Error),
Post => (declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
(Length (Source) = 0 and then
Length (Target) = Result_Length and then
Capacity (Target) >= Result_Length));
79/2
end Generic_Sorting;
79.1/5
package Stable is
79.2/5
type Vector (Base : not null access Vectors.Vector) is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length, Capacity),
Global => null,
Default_Initial_Condition => Length (Vector) = 0,
Preelaborable_Initialization;
The Global of null assumes that the user of a stable object is including effects associated with the access discriminant. For operations with in parameters (after any overriding), the object designated by the access discriminant is assumed to be read, and for other operations (including initialization and finalization) the object designated by the access discriminant is assumed to be read and updated.
type Cursor is private
with Preelaborable_Initialization;
79.4/5
Empty_Vector : constant Vector;
79.5/5
No_Element : constant Cursor;
79.6/5
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
79.7/5
package Vector_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
79.8/5
procedure Assign (Target : in out Vectors.Vector;
Source : in Vector)
with Post => Length (Source) = Length (Target) and then
Capacity (Target) >= Length (Target);
79.9/5
function Copy (Source : Vectors.Vector) return Vector
with Post => Length (Copy'Result) = Length (Source);
79.10/5
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (raise Program_Error);
79.11/5
type Reference_Type
(Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (raise Program_Error);
79.12/5
-- Additional subprograms as described in the text
-- are declared here.
79.13/5
private
79.14/5
... -- not specified by the language
79.15/5
end Stable;
80/2
private
81/2
... -- not specified by the language
82/2
end Ada.Containers.Vectors;
The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the functions defined to use it return an unspecified value. The exact arguments and number of calls of this generic formal function by the functions defined to use it are unspecified.
The “functions defined to use it” are Find, Find_Index, Reverse_Find, Reverse_Find_Index, and "=" for Vectors. This list is a bit too long to give explicitly.
If the actual function for "=" is not symmetric and consistent, the result returned by any of the functions defined to use "=" cannot be predicted. The implementation is not required to protect against "=" raising an exception, or returning random results, or any other “bad” behavior. And it can call "=" in whatever manner makes sense. But note that only the results of the functions defined to use "=" are unspecified; other subprograms are not allowed to break if "=" is bad.
The type Vector is used to represent vectors. The type Vector needs finalization (see 7.6).
Empty_Vector represents the empty vector object. It has a length of 0. If an object of type Vector is not otherwise initialized, it is 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 is initialized to the same value as No_Element.
The primitive "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.
To be honest: “The primitive "=" operator” is the one with two parameters of type Cursor which returns Boolean. We're not talking about some other (hidden) primitive function named "=".
Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
A cursor will probably be implemented in terms of one or more access values, and the effects of streaming access values is unspecified. Rather than letting the user stream junk by accident, we mandate that streaming of cursors raise Program_Error by default. The attributes can always be specified if there is a need to support streaming.
Vector'Write for a Vector object V writes Length(V) elements of the vector to the stream. It may also write additional information about the vector.
Vector'Read reads the representation of a vector from the stream, and assigns to Item a vector with the same length and elements as was written by Vector'Write.
The Reference Manual requires streaming of all language-defined nonlimited types (including containers) to "work" (see 13.13.2). In addition, we do not want all of the elements that make up the capacity of the vector streamed, as those beyond the length of the container have undefined contents (and might cause bad things when read back in). This will require a custom stream attribute implementation; the language-defined default implementation will not work (even for a bounded form, as that would most likely stream the entire capacity of the vector). There is a separate requirement that the unbounded and Bounded form use the same streaming representation for the same element type, see A.18.19.
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.
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).
[Some operations check for “tampering with cursors” of a container because they depend on the set of elements of the container remaining constant, and others check for “tampering with elements” of a container because they depend on elements of the container not being replaced.] When tampering with cursors is prohibited for a particular vector object V, Program_Error is propagated by the finalization of V[, as well as by a call that passes V to certain of the operations of this package, as indicated by the precondition of such an operation]. Similarly, when tampering with elements is prohibited for V, Program_Error is propagated by a call that passes V to certain of the other operations of this package, as indicated by the precondition of such an operation.
Paragraphs 91 through 97 are removed as preconditions now describe these rules.
We don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with cursors.
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Returns True if Position designates an element, and returns False otherwise.
To be honest: This function might not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of calling Has_Element with an invalid cursor is unspecified (but not erroneous).
function Has_Element (Container : Vector; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if Position designates an element in Container, and returns False otherwise.
If Position is No_Element, Has_Element returns False.
function "=" (Left, Right : Vector) return Boolean;
If Left and Right denote the same vector object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, it compares each element in Left to the corresponding element in Right using the generic formal equality operator. If any such comparison returns False, the function returns False; otherwise, it returns True. Any exception raised during evaluation of element equality is propagated.
This wording describes the canonical semantics. However, the order and number of calls on the formal equality function is unspecified for all of the operations that use it in this package, so an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality additional times once the answer has been determined.
function Tampering_With_Cursors_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if tampering with cursors or tampering with elements is currently prohibited for Container, and returns False otherwise.
Prohibiting tampering with elements also needs to prohibit tampering with cursors, as deleting an element is similar to replacing it.
Various contracts elsewhere in this specification require that this function be implemented with synchronized data. Moreover, it is possible for tampering to be prohibited by multiple operations (sequentially or in parallel). Therefore, tampering needs to be implemented with an atomic or protected counter. The counter is initialized to zero, and is incremented when tampering is prohibited, and decremented when leaving an area that prohibited tampering. Function Tampering_With_Cursors_Prohibited returns True if the counter is nonzero. (Note that any case where the result is not well-defined for one task is incorrect use of shared variables and would be erroneous by the rules of 9.10, so no special protection is needed to read the counter.)
function Tampering_With_Elements_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Always returns False[, regardless of whether tampering with elements is prohibited].
A definite element cannot change size, so we allow operations that tamper with elements even when tampering with elements is prohibited. That's not true for the indefinite containers, which is why this kind of tampering exists.
function Maximum_Length return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Returns the maximum Length of a Vector, based on the index type.
This is just:
Count_Type (Index_Type'Last - Index_Type'First + 1)
but since the inner calculation can overflow or the type conversion can fail, this can't be evaluated in general with an expression function. Note that if this expression raises Constraint_Error, then the result is Count_Type'Last, since the Capacity of a Vector cannot exceed Count_Type'Last.
function Empty (Capacity : Count_Type := implementation-defined)
return Vector
with Pre => Capacity <= Maximum_Length
or else raise Constraint_Error,
Post =>
Capacity (Empty'Result) >= Capacity and then
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
Returns an empty vector.
function To_Vector (Length : Count_Type) return Vector
with Pre => Length <= Maximum_Length or else raise Constraint_Error,
Post =>
To_Vector'Result.Length = Length and then
not Tampering_With_Elements_Prohibited (To_Vector'Result)
and then
not Tampering_With_Cursors_Prohibited (To_Vector'Result)
and then
To_Vector'Result.Capacity >= Length;
Returns a vector with a length of Length, filled with empty elements.
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector
with Pre => Length <= Maximum_Length or else raise Constraint_Error,
Post =>
To_Vector'Result.Length = Length and then
not Tampering_With_Elements_Prohibited (To_Vector'Result)
and then
not Tampering_With_Cursors_Prohibited (To_Vector'Result)
and then
To_Vector'Result.Capacity >= Length;
Returns a vector with a length of Length, filled with elements initialized to the value New_Item.
function "&" (Left, Right : Vector) return Vector
with Pre => Length (Left) <= Maximum_Length - Length (Right)
or else raise Constraint_Error,
Post => Length (Vectors."&"'Result) =
Length (Left) + Length (Right) and then
not Tampering_With_Elements_Prohibited (Vectors."&"'Result)
and then
not Tampering_With_Cursors_Prohibited (Vectors."&"'Result)
and then
Vectors."&"'Result.Capacity >=
Length (Left) + Length (Right);
Returns a vector comprising the elements of Left followed by the elements of Right.
function "&" (Left : Vector;
Right : Element_Type) return Vector
with Pre => Length (Left) <= Maximum_Length - 1
or else raise Constraint_Error,
Post => Vectors."&"'Result.Length = Length (Left) + 1 and then
not Tampering_With_Elements_Prohibited (Vectors."&"'Result)
and then
not Tampering_With_Cursors_Prohibited (Vectors."&"'Result)
and then
Vectors."&"'Result.Capacity >= Length (Left) + 1;
Returns a vector comprising the elements of Left followed by the element Right.
function "&" (Left : Element_Type;
Right : Vector) return Vector
with Pre => Length (Right) <= Maximum_Length - 1
or else raise Constraint_Error,
Post => Length (Vectors."&"'Result) = Length (Right) + 1 and then
not Tampering_With_Elements_Prohibited (Vectors."&"'Result)
and then
not Tampering_With_Cursors_Prohibited (Vectors."&"'Result)
and then
Vectors."&"'Result.Capacity >= Length (Right) + 1;
Returns a vector comprising the element Left followed by the elements of Right.
function "&" (Left, Right : Element_Type) return Vector
with Pre => Maximum_Length >= 2 or else raise Constraint_Error,
Post => Length ("&"'Result) = 2 and then
not Tampering_With_Elements_Prohibited (Vectors."&"'Result)
and then
not Tampering_With_Cursors_Prohibited (Vectors."&"'Result)
and then
Vectors."&"'Result.Capacity >= 2;
Returns a vector comprising the element Left followed by the element Right.
function Capacity (Container : Vector) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Returns the capacity of Container.
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
If the capacity of Container is already greater than or equal to Capacity, then Reserve_Capacity has no effect. Otherwise, Reserve_Capacity allocates additional storage as necessary to ensure that the length of the resulting vector can become at least the value Capacity without requiring an additional call to Reserve_Capacity, and is large enough to hold the current length of Container. Reserve_Capacity then, as necessary, moves elements into the new storage and deallocates any storage no longer needed. Any exception raised during allocation is propagated and Container is not modified.
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.
function Length (Container : Vector) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Returns the number of elements in Container.
procedure Set_Length (Container : in out Vector;
Length : in Count_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length <= Maximum_Length or else raise Constraint_Error),
Post => Container.Length = Length and then
Capacity (Container) >= Length;
If Length is larger than the capacity of Container, Set_Length calls Reserve_Capacity (Container, Length), then sets the length of the Container to Length. If Length is greater than the original length of Container, empty elements are added to Container; otherwise, elements are removed from Container.
No elements are moved by this operation; any new empty elements are added at the end. This follows from the rules that a cursor continues to designate the same element unless the routine is defined to make the cursor ambiguous or invalid; this operation does not do that.
function Is_Empty (Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
Returns True if Container is empty.
procedure Clear (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
Removes all the elements from Container. The capacity of Container does not change.
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor
with Post => (if Index in
First_Index (Container) .. Last_Index (Container)
then Has_Element (Container, To_Cursor'Result)
else To_Cursor'Result = No_Element),
Nonblocking, Global => null, Use_Formal => null;
Returns a cursor designating the element at position Index in Container; returns No_Element if Index does not designate an element. For the purposes of determining whether the parameters overlap in a call to To_Cursor, the Container parameter is not considered to overlap with any object [(including itself)].
Without the preceding rule, concurrent calls to To_Cursor on the same container would interfere by the concurrent call rules in Annex A, since the container object of the concurrent calls would overlap with itself. We want these to not interfere, for example to allow the Vector elements to be split into separate “chunks” for parallel processing.
function To_Index (Position : Cursor) return Extended_Index
with Nonblocking, Global => in all, Use_Formal => null;
If Position is No_Element, No_Index is returned. Otherwise, the index (within its containing vector) of the element designated by Position is returned.
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 To_Index (Container : Vector;
Position : Cursor) return Extended_Index
with Pre => Position = No_Element or else
Has_Element (Container, Position) or else
raise Program_Error,
Post => (if Position = No_Element then To_Index'Result = No_Index
else To_Index'Result in First_Index (Container) ..
Last_Index (Container)),
Nonblocking, Global => null, Use_Formal => null;
Returns the index (within Container) of the element designated by Position; returns No_Index if Position does not designate an element. For the purposes of determining whether the parameters overlap in a call to To_Index, the Container parameter is not considered to overlap with any object [(including itself)].
function Element (Container : Vector;
Index : Index_Type)
return Element_Type
with Pre => Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Nonblocking, Global => null, Use_Formal => Element_Type;
Element returns the element at position Index.
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
Element returns the element designated by Position.
function Element (Container : Vector;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
Element returns the element designated by Position in Container.
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error);
Replace_Element assigns the value New_Item to the element at position Index. Any exception raised during the assignment is propagated. The element at position Index is not an empty element after successful call to Replace_Element. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object [(including itself)], and the Index parameter is considered to overlap with the element at position Index.
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Replace_Element assigns New_Item to the element designated by Position. Any exception raised during the assignment is propagated. The element at Position is not an empty element after successful call to Replace_Element. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object [(including itself)].
Replace_Element, Update_Element, and Reference are the only ways that an element can change from empty to nonempty. Also see the note following Update_Element.
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type))
with Pre => Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error;
Query_Element calls Process.all with the element at position Index as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
The “tamper with the elements” check is intended to prevent the Element parameter of Process from being replaced or deleted outside of Process. The check prevents data loss (if Element_Type is passed by copy) or erroneous execution (if Element_Type is an unconstrained type in an indefinite container).
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element or else raise Constraint_Error
Global => in all;
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of the vector that contains the element designated by Position is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
procedure Query_Element
(Container : in Vector;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error;
Update_Element calls Process.all with the element at position Index as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
This means that the elements cannot be directly allocated from the heap; 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.
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
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Update_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
The element designated by Position is not an empty element after successful completion of this operation.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
147.2/5
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
The types Constant_Reference_Type and Reference_Type need finalization.
This paragraph was deleted.
It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.
function Constant_Reference (Container : aliased in Vector;
Index : in Index_Type)
return Constant_Reference_Type
with Pre => Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a vector given an index value.
Constant_Reference returns an object whose discriminant is an access value that designates the element at position Index. Tampering with the elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector;
Index : in Index_Type)
return Reference_Type
with Pre => Index in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to an individual element of a vector given an index value.
Reference returns an object whose discriminant is an access value that designates the element at position Index. Tampering with the elements of Container is prohibited while the object returned by Reference exists and has not been finalized.
The element at position Index is not an empty element after successful completion of this operation.
function Constant_Reference (Container : aliased in Vector;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a vector given a cursor.
Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to an individual element of a vector given a cursor.
Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Reference exists and has not been finalized.
The element designated by Position is not an empty element after successful completion of this operation.
procedure Assign (Target : in out Vector; Source : in Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target) and then
Capacity (Target) >= Length (Target);
If Target denotes the same object as Source, the operation has no effect. If the length of Source is greater than the capacity of Target, Reserve_Capacity (Target, Length (Source)) is called. The elements of Source are then copied to Target as for an assignment_statement assigning Source to Target (this includes setting the length of Target to be that of Source).
This routine exists for compatibility with the bounded vector container. For an unbounded vector, Assign(A, B) and A := B behave identically. For a bounded vector, := will raise an exception if the container capacities are different, while Assign will not raise an exception if there is enough room in the target.
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post => Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result)
and then
Copy'Result.Capacity >= (if Capacity = 0 then
Length (Source) else Capacity);
Returns a vector whose elements are initialized from the corresponding elements of Source.
procedure Move (Target : in out Vector;
Source : in out Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source)'Old and then
Length (Source) = 0 and then
Capacity (Target) >= Length (Source)'Old);
If Target denotes the same object as Source, then the operation has no effect. Otherwise, Move first calls Reserve_Capacity (Target, Length (Source)) and then Clear (Target); then, each element from Source is removed from Source and inserted into Target in the original order.
The idea is that the internal array is removed from Source and moved to Target. (See the for Move). 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.
procedure Insert_Vector (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
If Length(New_Item) is 0, then Insert_Vector does nothing. Otherwise, it computes 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 current vector capacity is less than NL, Reserve_Capacity (Container, NL) is called to increase the vector capacity. Then Insert_Vector 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.
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).
procedure Insert_Vector (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
If Length(New_Item) is 0, then Insert_Vector does nothing. If Before is No_Element, then the call is equivalent to Insert_Vector (Container, Last_Index (Container) + 1, New_Item); otherwise, the call is equivalent to Insert_Vector (Container, To_Index (Before), New_Item);
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_Vector (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
If Before equals No_Element, then let T be Last_Index (Container) + 1; otherwise, let T be To_Index (Before). Insert_Vector (Container, T, New_Item) is called, and then Position is set to To_Cursor (Container, T).
The messy wording is needed because Before is invalidated by Insert_Vector, 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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);
If Count equals 0, Position will designate the element designated by Before, rather than a newly inserted element. Otherwise, Position will designate the first newly inserted element.
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
If Count is 0, then Insert does nothing. Otherwise, it computes the new length NL as the sum of the current length and Count; if the value of Last appropriate for length NL would be greater than Index_Type'Last, then Constraint_Error is propagated.
If the current vector capacity is less than NL, 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 Count positions, and then inserts elements that are initialized by default (see 3.3.1) in the positions starting at Before.
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
If Before equals No_Element, then let T be Last_Index (Container) + 1; otherwise, let T be To_Index (Before). Insert (Container, T, Count) is called, and then Position is set to To_Cursor (Container, T).
This routine exists mainly to ease conversion between Vector and List containers. Unlike Insert_Space, this routine default initializes the elements it inserts, which can be more expensive for some element types.
procedure Prepend_Vector (Container : in out Vector;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
Equivalent to Insert (Container, First_Index (Container), New_Item).
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
Equivalent to Insert (Container, First_Index (Container), New_Item, Count).
procedure Append_Vector (Container : in out Vector;
New_Item : in Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Length (New_Item)
or else raise Constraint_Error),
Post => Length (Container)'Old + Length (New_Item) =
Length (Container) and then
Capacity (Container) >= Length (Container);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item, Count).
procedure Append (Container : in out Vector;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - 1
or else raise Constraint_Error),
Post => Length (Container)'Old + 1 = Length (Container) and then
Capacity (Container) >= Length (Container);
Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item, 1).
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Capacity (Container) >= Length (Container);
If Count is 0, then Insert_Space does nothing. Otherwise, it computes the new length NL as the sum of the current length and Count; if the value of Last appropriate for length NL would be greater than Index_Type'Last, then Constraint_Error is propagated.
If the current vector capacity is less than NL, Reserve_Capacity (Container, NL) is called to increase the vector capacity. Then Insert_Space slides the elements in the range Before .. Last_Index (Container) up by Count positions, and then inserts empty elements in the positions starting at Before.
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Maximum_Length - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container) and then
Has_Element (Container, Position) and then
Capacity (Container) >= Length (Container);
If Before equals No_Element, then let T be Last_Index (Container) + 1; otherwise, let T be To_Index (Before). Insert_Space (Container, T, Count) is called, and then Position is set to To_Cursor (Container, T).
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Index in
First_Index (Container) .. Last_Index (Container) + 1
or else raise Constraint_Error),
Post => Length (Container)'Old - Count <= Length (Container);
If Count is 0, Delete has no effect. Otherwise, Delete slides the elements (if any) starting at position Index + Count down to Index. Any exception raised during element assignment is propagated.
If Index + Count >= Last_Index(Container), this effectively truncates the vector (setting Last_Index to Index – 1 and consequently sets Length to Index – Index_Type'First).
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container)'Old - Count <= Length (Container)
and then Position = No_Element;
Delete (Container, To_Index (Position), Count) is called, and then Position is set to No_Element.
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
Equivalent to Delete (Container, First_Index (Container), Count).
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
If Length (Container) <= Count, then Delete_Last is equivalent to Clear (Container). Otherwise, it is equivalent to Delete (Container, Index_Type'Val(Index_Type'Pos(Last_Index (Container)) – Count + 1), Count).
procedure Reverse_Elements (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
Reorders the elements of Container in reverse order.
This can copy the elements of the vector — all cursors referencing the vector are ambiguous afterwards and may designate different elements afterwards.
procedure Swap (Container : in out Vector;
I, J : in Index_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error) and then
(J in First_Index (Container) .. Last_Index (Container)
or else raise Constraint_Error);
Swap exchanges the values of the elements at positions I and J.
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 (Container : in out Vector;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
Swap exchanges the values of the elements designated by I and J.
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.
function First_Index (Container : Vector) return Index_Type
with Nonblocking, Global => null, Use_Formal => null,
Post => First_Index'Result = Index_Type'First;
Returns the value Index_Type'First.
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
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
If Container is empty, First returns No_Element. Otherwise, it returns a cursor that designates the first element in Container.
function First_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
Equivalent to Element (Container, First_Index (Container)).
function Last_Index (Container : Vector) return Extended_Index
with Nonblocking, Global => null, Use_Formal => null,
Post => (if Length (Container) = 0 then Last_Index'Result = No_Index
else Count_Type(Last_Index'Result - Index_Type'First) =
Length (Container) - 1);
If Container is empty, Last_Index returns No_Index. Otherwise, it returns the position of the last element in Container.
function Last (Container : Vector) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
If Container is empty, Last returns No_Element. Otherwise, it returns a cursor that designates the last element in Container.
function Last_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
Equivalent to Element (Container, Last_Index (Container)).
function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
If Position equals No_Element or designates the last element of the container, then Next returns the value No_Element. Otherwise, it returns a cursor that designates the element with index To_Index (Position) + 1 in the same vector as Position.
function Next (Container : Vector;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Has_Element (Container, Next'Result) then
To_Index (Container, Next'Result) =
To_Index (Container, Position) + 1
elsif Next'Result = No_Element then
Position = Last (Container)
else False);
Returns a cursor designating the next element in Container, if any.
procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position := Next (Position).
procedure Next (Container : in Vector;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position := Next (Container, Position).
function Previous (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Previous'Result = No_Element);
If Position equals No_Element or designates the first element of the container, then Previous returns the value No_Element. Otherwise, it returns a cursor that designates the element with index To_Index (Position) – 1 in the same vector as Position.
function Previous (Container : Vector;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Previous'Result = No_Element
elsif Has_Element (Container, Previous'Result) then
To_Index (Container, Previous'Result) =
To_Index (Container, Position) - 1
elsif Previous'Result = No_Element then
Position = First (Container)
else False);
Returns a cursor designating the previous element in Container, if any.
procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position := Previous (Position).
procedure Previous (Container : in Vector;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position := Previous (Container, Position).
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 (using the generic formal equality operator). The search starts at position Index and proceeds towards Last_Index (Container). If no equal element is found, then Find_Index returns No_Index. Otherwise, it returns the index of the first equal element encountered.
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the first element if Position equals No_Element, and at the element designated by Position otherwise. It proceeds towards the last element of Container. If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
Searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at position Index or, if Index is greater than Last_Index (Container), at position Last_Index (Container). It proceeds towards First_Index (Container). If no equal element is found, then Reverse_Find_Index returns No_Index. Otherwise, it returns the index of the first equal element encountered.
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Reverse_Find'Result /= No_Element
then Has_Element (Container, Reverse_Find'Result));
Reverse_Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the last element if Position equals No_Element, and at the element designated by Position otherwise. It proceeds towards the first element of Container. If no equal element is found, then Reverse_Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
Equivalent to Has_Element (Find (Container, Item)).
Paragraphs 225 and 226 were moved above.
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
Invokes Process.all with a cursor that designates each element in Container, in index order. Tampering with the cursors of Container is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
The purpose of the “tamper with the cursors” check is to prevent erroneous execution from the Position parameter of Process.all becoming invalid. This check takes place when the operations that tamper with the cursors of the container are called. The check cannot be made later (say in the body of Iterate), because that could cause the Position cursor to be invalid and potentially cause execution to become erroneous -- defeating the purpose of the check.
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.
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
Iterates over the elements in Container as per procedure Iterate, except that elements are traversed in reverse index order.
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
Iterate returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator, and processing all nodes concurrently when used as a parallel iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Iterate returns a reversible iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
Exits are allowed from the loops created using the iterator objects. In particular, to stop the iteration at a particular cursor, just add
exit when Cur = Stop;
in the body of the loop (assuming that Cur is the loop parameter and Stop is the cursor that you want to stop at).
The actual function for the generic formal function "<" of Generic_Sorting is expected to return the same value each time it is called with a particular pair of element values. It should define a strict weak ordering relationship (see A.18); it should not modify Container. If the actual for "<" behaves in some other manner, the behavior of the subprograms of Generic_Sorting are unspecified. The number of times the subprograms of Generic_Sorting call "<" is unspecified.
function Is_Sorted (Container : Vector) return Boolean;
Returns True if the elements are sorted smallest first as determined by the generic formal "<" operator; otherwise, Is_Sorted returns False. Any exception raised during evaluation of "<" is propagated.
procedure Sort (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
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 evaluation of "<" is propagated.
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 nonlimited, this usually will not be a problem. Note that there is 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.
procedure Merge (Target : in out Vector;
Source : in out Vector)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Length (Target) <= Maximum_Length - Length (Source)
or else raise Constraint_Error) and then
((Length (Source) = 0 or else
not Target'Has_Same_Storage (Source))
or else raise Program_Error),
Post => (declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
(Length (Source) = 0 and then
Length (Target) = Result_Length and then
Capacity (Target) >= Result_Length));
Merge removes elements from Source and inserts them into Target; afterwards, Target contains the union of the elements that were initially in Source and Target; Source is left empty. If Target and Source are initially sorted smallest first, then Target is ordered smallest first as determined by the generic formal "<" operator; otherwise, the order of elements in Target is unspecified. Any exception raised during evaluation of "<" is propagated.
It is a bounded error if either of the vectors is unsorted, see below. The bounded error can be recovered by sorting Target after the merge call, or the vectors can be pretested with Is_Sorted.
The Merge operation will usually require copying almost all of the elements. One implementation strategy would be to extend Target to the appropriate length, then copying elements from the back of the vectors working towards the front. An alternative approach would be to allocate a new internal data array of the appropriate length, copy the elements into it in an appropriate order, and then replacing the data array in Target with the temporary.
The nested package Vectors.Stable provides a type Stable.Vector that represents a stable vector, which is one that cannot grow and shrink. Such a vector can be created by calling the To_Vector or Copy functions, or by establishing a stabilized view of an ordinary vector.
The subprograms of package Containers.Vectors that have a parameter or result of type Vector are included in the nested package Stable with the same specification, except that the following are omitted:
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited, Reserve_Capacity, Assign, Move, Insert, Insert_Space, Insert_Vector, Append, Append_Vector, Prepend, Prepend_Vector, Clear, Delete, Delete_First, Delete_Last, and Set_Length
The generic package Generic_Sorting is also included with the same specification, except that Merge is omitted.
The names Vector and Cursor mean the types declared in the nested package in these subprogram specifications.
The omitted routines are those that tamper with cursors or elements (or test that state). The model is that it is impossible to tamper with cursors or elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view, and we omit the operations associated with those checks.
The operations of this package are equivalent to those for ordinary vectors, except that the calls to Tampering_With_Cursors_Prohibited and Tampering_With_Elements_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.
If a stable vector is declared with the Base discriminant designating a pre-existing ordinary vector, the stable vector represents a stabilized view of the underlying ordinary vector, and any operation on the stable vector is reflected on the underlying ordinary vector. While a stabilized view exists, any operation that tampers with elements performed on the underlying vector is prohibited. The finalization of a stable vector that provides such a view removes this restriction on the underlying ordinary vector [(though some other restriction can exist due to other concurrent iterations or stabilized views)].
If a stable vector is declared without specifying Base, the object is necessarily initialized. The initializing expression of the stable vector, [typically a call on To_Vector or Copy], determines the Length of the vector. The Length of a stable vector never changes after initialization.
Bounded (Run-Time) Errors
238/3Reading the value of an empty element by calling Element, Query_Element, Update_Element, Constant_Reference, Reference, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a bounded error. The implementation may treat the element as having any normal value (see 13.9.1) of the element type, or raise Constraint_Error or Program_Error before modifying the vector.
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.
Calling Merge in an instance of Generic_Sorting with either Source or Target not ordered smallest first using the provided generic formal "<" operator is a bounded error. Either Program_Error is raised after Target is updated as described for Merge, or the operation works as defined.
It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any Vector parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the Vector either prior to, or subsequent to, some or all of the modifications to the Vector.
It is a bounded error to call any subprogram declared in the visible part of Containers.Vectors when the associated container has been finalized. If the operation takes Container as an in out parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error.
A Cursor value is ambiguous if any of the following have occurred since it was created:
- Insert, Insert_Space, Insert_Vector, 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; or
- The vector that contains the element it designates has been passed to the Sort or Merge procedures of an instance of Generic_Sorting, or to the Reverse_Elements procedure.
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 were 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.
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 these cases or ensure that cursors survive such operations, in many cases the overhead necessary to make the check (or ensure cursors continue to designate the same element) is substantial in time or space.
Erroneous Execution
248/2A 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 Target of a call to Assign, or as the target of an
assignment_statement; 250/2 - [The vector that contains the element it designates has been used as the Source or Target of a call to Move;] or
Move has been reworded in terms of Assign and Clear, which are covered by other bullets, so this text is redundant.
- The element it designates has been deleted or removed from the vector that previously contained the element.
An element can be removed via calls to Set_Length, Clear, and Merge; and indirectly via calls to Assign and Move.
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.
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.
Execution is erroneous if the vector associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a nonexistent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)
Implementation Requirements
253/2No storage associated with a vector object shall be lost upon assignment or scope exit.
The execution of an assignment_statement for a vector shall have the effect of copying the elements from the source vector object to the target vector object and changing the length of the target object to that of the source object.
An assignment of a Vector is a “deep” copy; that is the elements are copied as well as the data structures. We say “effect of” in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed. (Note that such an implementation would require care, as Query_Element and Constant_Reference both could be used to access an element which later needs to be reallocated while the parameter or reference still exists, potentially leaving the parameter or reference pointing at the wrong element.)
Implementation Advice
255/2Containers.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 Element should be O(log N);
The worst-case time complexity of Element for Containers.Vector should be O(log N).
- the worst-case time complexity of Append with Count=1 when N is less than the capacity of the vector should be O(log N); and
The worst-case time complexity of Append with Count = 1 when N is less than the capacity for Containers.Vector should be O(log N).
- the worst-case time complexity of Prepend with Count=1 and Delete_First with Count=1 should be O(N log N).
The worst-case time complexity of Prepend with Count = 1 and Delete_First with Count=1 for Containers.Vectors should be O(N log N).
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 procedure Sort of an instance of Containers.Vectors.Generic_Sorting should be O(N**2), and the average time complexity should be better than O(N**2).
The worst-case time complexity of a call on procedure Sort of an instance of Containers.Vectors.Generic_Sorting should be O(N**2), and the average time complexity should be better than O(N**2).
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_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge should minimize copying of elements.
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge should minimize copying of elements.
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.
Move should not copy elements, and should minimize copying of internal data structures.
Containers.Vectors.Move should not copy elements, and should minimize copying of internal data structures.
Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source vector to the Target vector.
If an exception is propagated from a vector operation, no storage should be lost, nor any elements removed from a vector unless specified by the operation.
If an exception is propagated from a vector operation, no storage should be lost, nor any elements removed from a vector unless specified by the operation.
This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished.
NOTE 1 All elements of a vector occupy locations in the internal array. If a sparse container is required, a Hashed_Map can be used rather than a vector.
NOTE 2 If Index_Type'Base'First = Index_Type'First an instance 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.
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.
Extensions to Ada 95
Incompatibilities With Ada 2005
Subprograms Assign and Copy are added to Containers.Vectors. If an instance of Containers.Vectors is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Vectors is defined in a package that is also referenced in a use_clause, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur.
Extensions to Ada 2005
Added iterator, reference, and indexing support to make vector containers more convenient to use.
Wording Changes from Ada 2005
Generalized the definition of Reserve_Capacity and Move. Specified which elements are read/written by stream attributes.
Added a Bounded (Run-Time) Error to cover tampering by generic actual subprograms.
Redefined "<" actuals to require a strict weak ordering; the old definition allowed indeterminant comparisons that would not have worked in a container.
Added a pragma Remote_Types so that containers can be used in distributed programs.
Defined when a container prohibits tampering in order to more clearly define where the check is made and the exception raised.
Inconsistencies With Ada 2012
Tampering with elements is now defined to be equivalent to tampering with cursors for ordinary containers. If a program requires tampering detection to work, it might fail in Ada 2022. Specifically, if a program requires Program_Error to be raised by a routine that (only) tampers with elements in Ada 2012 (such as Replace_Element) when called in a context that does not allow tampering with elements (such as Update_Element), the routine will work as defined instead of raising Program_Error in Ada 2022. Needless to say, this shouldn't happen outside of test programs. Note that such contexts still prohibit tampering with cursors, so routines like Insert and Delete will still raise Program_Error in this case.
Trying to insert or concatenate more than Count_Type'Last elements will now raise Constraint_Error rather than Capacity_Error. This is extremely unlikely to happen, as Count_Type'Last is typically at least 2**31-1, so most such vectors will exceed memory before reaching this error.
Incompatibilities With Ada 2012
A number of new subprograms, types, and even a nested package were added to Containers.Vectors to better support contracts and stable views. Therefore, a use clause conflict is possible; see the introduction of Annex A for more on this topic.
Vector objects now support aggregates. This introduces a potential incompatibility for overloaded routines, including the "&" operations defined in this package. If the Element_Type of the vector is a type that allows aggregates (such as a record type), then calls to the "&" operations with an aggregate element will become ambiguous in Ada 2022, while they would have been legal in Ada 2012. This can be fixed by qualifying the aggregate with the element type.
The Insert, Append, and Prepend operations that operate on two vectors have been renamed Insert_Vector, Append_Vector, and Prepend_Vector, respectively. This was done in order to eliminate the aggregate ambiguity for the commonly used single element Append and Insert routines. The renamed routines are rarely used in Ada 2012 code, so the impact should be minimal.
Extensions to Ada 2012
To_Cursor and Replace_Element are now defined such that they can be used concurrently so long as they operate on different elements. This allows some container operations to be used in parallel without separate synchronization.
Vectors now support indexed container aggregates, so aggregate syntax can be used to create Vectors.
The iterator for the entire container now can return a parallel iterator which can be used to process the container in parallel.
Wording Changes from Ada 2012
Corrigendum: Clarified that tampering checks precede all other checks made by a subprogram (but come after those associated with the call).
Added contracts to this container. This includes describing some of the semantics with pre- and postconditions, rather than English text. Note that the preconditions can be Suppressed (see 11.5).
Split the Append routine into two routines rather than having a single routine with a default parameter, in order that a routine with the appropriate profile for the Aggregate aspect exists. This change should not change the behavior of any existing code.
A.18.3 The Generic Package Containers.Doubly_Linked_Lists
1/2The language-defined generic 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 nodes, each of which contains an element and pointers to the next (successor) and previous (predecessor) internal nodes. A cursor designates a particular node within a list (and by extension the element contained in that node). A cursor keeps designating the same node (and element) as long as the node is part of the container, even if the node is moved in the container.
The length of a list is the number of elements it contains.
Static Semantics
4/2The generic library package Containers.Doubly_Linked_Lists has the following declaration:
with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
For discussion on the reasons and meaning of the specifications of the Global and Nonblocking aspects in this generic package, see the notes on the equivalent operations in the specification of the Containers.Vectors package (see A.18.2).
type List is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.List,
Aggregate => (Empty => Empty,
Add_Unnamed => Append),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Length (List) = 0 and then
(not Tampering_With_Cursors_Prohibited (List)) and then
(not Tampering_With_Elements_Prohibited (List)),
Preelaborable_Initialization;
7/5
type Cursor is private
with Preelaborable_Initialization;
8/2
Empty_List : constant List;
9/2
No_Element : constant Cursor;
9.1/5
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
9.2/5
function Has_Element (Container : List; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
9.3/3
package List_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
10/2
function "=" (Left, Right : List) return Boolean;
10.1/5
function Tampering_With_Cursors_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
10.2/5
function Tampering_With_Elements_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
10.3/5
function Empty return List
is (Empty_List)
with Post =>
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
11/5
function Length (Container : List) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
12/5
function Is_Empty (Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
13/5
procedure Clear (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
14/5
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
14.1/5
function Element (Container : List;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
15/5
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
16/5
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;
16.1/5
procedure Query_Element
(Container : in List;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
17/5
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
17.1/5
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
17.2/5
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
17.3/5
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
17.4/5
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
17.5/5
procedure Assign (Target : in out List; Source : in List)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
17.6/5
function Copy (Source : List)
return List
with Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
18/5
procedure Move (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);
19/5
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
20/5
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);
21/5
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);
22/5
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
23/5
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
23.1/5
procedure Append (Container : in out List;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container)'Old + 1 = Length (Container);
24/5
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container)'Old - Count <= Length (Container)
and then Position = No_Element;
25/5
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
26/5
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
27/5
procedure Reverse_Elements (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
28/5
procedure Swap (Container : in out List;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
29/5
procedure Swap_Links (Container : in out List;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
30/5
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Target, Before)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Length (Target) <= Count_Type'Last - Length (Source)
or else raise Constraint_Error),
Post => (if not Target'Has_Same_Storage (Source) then
(declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
Length (Source) = 0 and then
Length (Target) = Result_Length));
31/5
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Source, Position)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Target, Before)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Length (Target) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Org_Target_Length : constant Count_Type :=
Length (Target)'Old;
Org_Source_Length : constant Count_Type :=
Length (Source)'Old;
begin
(if Target'Has_Same_Storage (Source) then
Position = Position'Old
else
Length (Source) = Org_Source_Length - 1 and then
Length (Target) = Org_Target_Length + 1 and then
Has_Element (Target, Position)));
32/2
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error),
Post => Length (Container) = Length (Container)'Old;
33/5
function First (Container : List) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
34/5
function First_Element (Container : List)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
35/5
function Last (Container : List) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
36/5
function Last_Element (Container : List)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
37/5
function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
37.1/5
function Next (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Next'Result = No_Element then
Position = Last (Container)
else Has_Element (Container, Next'Result));
38/5
function Previous (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then
Previous'Result = No_Element);
38.1/5
function Previous (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));
39/5
procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
39.1/5
procedure Next (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
40/5
procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
40.1/5
procedure Previous (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element then
Has_Element (Container, Position));
41/5
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
42/5
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Reverse_Find'Result /= No_Element
then Has_Element (Container, Reverse_Find'Result));
43/2
function Contains (Container : List;
Item : Element_Type) return Boolean;
44/3
This paragraph was deleted.
45/5
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
46/5
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
46.1/5
function Iterate (Container : in List)
return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
46.2/5
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
47/5
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
with Nonblocking, Global => null is
48/2
function Is_Sorted (Container : List) return Boolean;
49/5
procedure Sort (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
50/5
procedure Merge (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Elements_Prohibited (Source)
or else raise Program_Error) and then
(Length (Target) <= Count_Type'Last - Length (Source)
or else raise Constraint_Error) and then
((Length (Source) = 0 or else
not Target'Has_Same_Storage (Source))
or else raise Constraint_Error),
Post => (declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
(Length (Source) = 0 and then
Length (Target) = Result_Length));
51/2
end Generic_Sorting;
51.1/5
package Stable is
51.2/5
type List (Base : not null access Doubly_Linked_Lists.List) is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global => null,
Default_Initial_Condition => Length (List) = 0,
Preelaborable_Initialization;
51.3/5
type Cursor is private
with Preelaborable_Initialization;
51.4/5
Empty_List : constant List;
51.5/5
No_Element : constant Cursor;
51.6/5
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
51.7/5
package List_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
51.8/5
procedure Assign (Target : in out Doubly_Linked_Lists.List;
Source : in List)
with Post => Length (Source) = Length (Target);
51.9/5
function Copy (Source : Doubly_Linked_Lists.List) return List
with Post => Length (Copy'Result) = Length (Source);
51.10/5
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (raise Program_Error);
51.11/5
type Reference_Type
(Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (raise Program_Error);
51.12/5
-- Additional subprograms as described in the text
-- are declared here.
51.13/5
private
51.14/5
... -- not specified by the language
51.15/5
end Stable;
52/2
private
53/2
... -- not specified by the language
54/2
end Ada.Containers.Doubly_Linked_Lists;
The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the functions Find, Reverse_Find, and "=" on list values return an unspecified value. The exact arguments and number of calls of this generic formal function by the functions Find, Reverse_Find, and "=" on list values are unspecified.
If the actual function for "=" is not symmetric and consistent, the result returned by the listed functions cannot be predicted. The implementation is not required to protect against "=" raising an exception, or returning random results, or any other “bad” behavior. And it can call "=" in whatever manner makes sense. But note that only the results of Find, Reverse_Find, and List "=" are unspecified; other subprograms are not allowed to break if "=" is bad (they aren't expected to use "=").
The type List is used to represent lists. The type List needs finalization (see 7.6).
Empty_List represents the empty List object. It has a length of 0. If an object of type List is not otherwise initialized, it is 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 is initialized to the same value as No_Element.
The primitive "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.
To be honest: “The primitive "=" operator” is the one with two parameters of type Cursor which returns Boolean. We're not talking about some other (hidden) primitive function named "=".
Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
A cursor will probably be implemented in terms of one or more access values, and the effects of streaming access values is unspecified. Rather than letting the user stream junk by accident, we mandate that streaming of cursors raise Program_Error by default. The attributes can always be specified if there is a need to support streaming.
List'Write for a List object L writes Length(L) elements of the list to the stream. It may also write additional information about the list.
List'Read reads the representation of a list from the stream, and assigns to Item a list with the same length and elements as was written by List'Write.
Streaming more elements than the container length is wrong. For implementation implications of this rule, see the Implementation Note in A.18.2.
[Some operations check for “tampering with cursors” of a container because they depend on the set of elements of the container remaining constant, and others check for “tampering with elements” of a container because they depend on elements of the container not being replaced.] When tampering with cursors is prohibited for a particular list object L, Program_Error is propagated by the finalization of L[, as well as by a call that passes L to certain of the operations of this package, as indicated by the precondition of such an operation]. Similarly, when tampering with elements is prohibited for L, Program_Error is propagated by a call that passes L to certain of the other operations of this package, as indicated by the precondition of such an operation.
Paragraphs 62 through 69 are removed as preconditions now describe these rules.
We don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with cursors.
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Returns True if Position designates an element, and returns False otherwise.
To be honest: This function might not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of calling Has_Element with an invalid cursor is unspecified (but not erroneous).
function Has_Element (Container : List; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if Position designates an element in Container, and returns False otherwise.
If Position is No_Element, Has_Element returns False.
function "=" (Left, Right : List) return Boolean;
If Left and Right denote the same list object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, it compares each element in Left to the corresponding element in Right using the generic formal equality operator. If any such comparison returns False, the function returns False; otherwise, it returns True. Any exception raised during evaluation of element equality is propagated.
This wording describes the canonical semantics. However, the order and number of calls on the formal equality function is unspecified for all of the operations that use it in this package, so an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality additional times once the answer has been determined.
function Tampering_With_Cursors_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if tampering with cursors or tampering with elements is currently prohibited for Container, and returns False otherwise.
Prohibiting tampering with elements also needs to prohibit tampering with cursors, as deleting an element is similar to replacing it.
Various contracts elsewhere in this specification require that this function be implemented with synchronized data. Moreover, it is possible for tampering to be prohibited by multiple operations (sequentially or in parallel). Therefore, tampering needs to be implemented with an atomic or protected counter. The counter is initialized to zero, and is incremented when tampering is prohibited, and decremented when leaving an area that prohibited tampering. Function Tampering_With_Cursors_Prohibited returns True if the counter is nonzero. (Note that any case where the result is not well-defined for one task is incorrect use of shared variables and would be erroneous by the rules of 9.10, so no special protection is needed to read the counter.)
function Tampering_With_Elements_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Always returns False[, regardless of whether tampering with elements is prohibited].
A definite element cannot change size, so we allow operations that tamper with elements even when tampering with elements is prohibited. That's not true for the indefinite containers, which is why this kind of tampering exists.
function Length (Container : List) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Returns the number of elements in Container.
function Is_Empty (Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
Returns True if Container is empty.
procedure Clear (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
Removes all the elements from Container.
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
Element returns the element designated by Position.
function Element (Container : List;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
Element returns the element designated by Position in Container.
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Replace_Element assigns the value New_Item to the element designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object [(including itself)].
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of the list that contains the element designated by Position is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
procedure Query_Element
(Container : in List;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Update_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
This means that the elements cannot be directly allocated from the heap; it must be possible to change the discriminants of the element in place.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
86.2/5
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
The types Constant_Reference_Type and Reference_Type need finalization.
This paragraph was deleted.
It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a list given a cursor.
Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to an individual element of a list given a cursor.
Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Reference exists and has not been finalized.
procedure Assign (Target : in out List; Source : in List)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
If Target denotes the same object as Source, the operation has no effect. Otherwise, the elements of Source are copied to Target as for an assignment_statement assigning Source to Target.
This routine exists for compatibility with the bounded list container. For an unbounded list, Assign(A, B) and A := B behave identically. For a bounded list, := will raise an exception if the container capacities are different, while Assign will not raise an exception if there is enough room in the target.
function Copy (Source : List)
return List
with Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
Returns a list whose elements match the elements of Source.
procedure Move (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);
If Target denotes the same object as Source, then the operation has no effect. Otherwise, the operation is equivalent to Assign (Target, Source) followed by Clear (Source).
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
Insert inserts Count copies of New_Item prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last node (if any). Any exception raised during allocation of internal storage is propagated, and Container is not modified.
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 List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);
Insert allocates Count copies of New_Item, and inserts them prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last element (if any). Position designates the first newly-inserted element, or if Count equals 0, then Position is assigned the value of Before. 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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);
Insert inserts Count new elements prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last node (if any). The new elements are initialized by default (see 3.3.1). Position designates the first newly-inserted element, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
Equivalent to Insert (Container, First (Container), New_Item, Count).
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);
Equivalent to Insert (Container, No_Element, New_Item, Count).
procedure Append (Container : in out List;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container)'Old + 1 = Length (Container);
Equivalent to Insert (Container, No_Element, New_Item, 1).
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container)'Old - Count <= Length (Container)
and then Position = No_Element;
Delete removes (from Container) Count elements starting at the element designated by Position (or all of the elements starting at Position if there are fewer than Count elements starting at Position). Finally, Position is set to No_Element.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
If Length (Container) <= Count, then Delete_First is equivalent to Clear (Container). Otherwise, it removes the first Count nodes from Container.
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container)'Old - Count <= Length (Container);
If Length (Container) <= Count, then Delete_Last is equivalent to Clear (Container). Otherwise, it removes the last Count nodes from Container.
procedure Reverse_Elements (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
Reorders the elements of Container in reverse order.
Unlike the similar routine for a vector, elements should not be copied; rather, the nodes should be exchanged. Cursors are expected to reference the same elements afterwards.
procedure Swap (Container : in out List;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
Swap exchanges the values of the elements designated by I and J.
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.
procedure Swap_Links (Container : in out List;
I, J : in Cursor)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
Swap_Links exchanges the nodes designated by I and J.
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Target, Before)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Length (Target) <= Count_Type'Last - Length (Source)
or else raise Constraint_Error),
Post => (if not Target'Has_Same_Storage (Source) then
(declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
Length (Source) = 0 and then
Length (Target) = Result_Length));
If Source denotes the same object as Target, the operation has no effect. Otherwise, Splice reorders elements such that they are removed from Source and moved to Target, immediately prior to Before. If Before equals No_Element, the nodes of Source are spliced after the last node of Target.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Source, Position)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Target, Before)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Length (Target) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Org_Target_Length : constant Count_Type :=
Length (Target)'Old;
Org_Source_Length : constant Count_Type :=
Length (Source)'Old;
begin
(if Target'Has_Same_Storage (Source) then
Position = Position'Old
else Length (Source) = Org_Source_Length - 1 and then
Length (Target) = Org_Target_Length + 1 and then
Has_Element (Target, Position)));
If Source denotes the same object as Target, then there is no effect if Position equals Before, else the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last element. Otherwise, the element designated by Position is removed from Source and moved to Target, immediately prior to Before, or, if Before equals No_Element, after the last element of Target. Position is updated to represent an element in Target.
If Source is the same as Target, and Position = Before, or Next(Position) = Before, Splice has no effect, as the element does not have to move to meet the postcondition.
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error),
Post => Length (Container) = Length (Container)'Old;
If Position equals Before there is no effect. Otherwise, the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last element.
function First (Container : List) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
If Container is empty, First returns No_Element. Otherwise, it returns a cursor that designates the first node in Container.
function First_Element (Container : List)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
Equivalent to Element (Container, First_Index (Container)).
function Last (Container : List) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
If Container is empty, Last returns No_Element. Otherwise, it returns a cursor that designates the last node in Container.
function Last_Element (Container : List)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
Equivalent to Element (Last (Container)).
function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
If Position equals No_Element or designates the last element of the container, then Next returns the value No_Element. Otherwise, it returns a cursor that designates the successor of the element designated by Position.
function Next (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Next'Result = No_Element then
Position = Last (Container)
else Has_Element (Container, Next'Result));
Returns a cursor designating the successor of the element designated by Position in Container.
function Previous (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then
Previous'Result = No_Element);
If Position equals No_Element or designates the first element of the container, then Previous returns the value No_Element. Otherwise, it returns a cursor that designates the predecessor of the element designated by Position.
function Previous (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));
Returns a cursor designating the predecessor of the element designated by Position in Container, if any.
procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position := Next (Position).
procedure Next (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position := Next (Container, Position).
procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position := Previous (Position).
procedure Previous (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position := Previous (Container, Position).
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position, or at the first element if Position equals No_Element. It proceeds towards Last (Container). If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Reverse_Find'Result /= No_Element
then Has_Element (Container, Reverse_Find'Result));
Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position, or at the last element if Position equals No_Element. It proceeds towards First (Container). If no equal element is found, then Reverse_Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
function Contains (Container : List;
Item : Element_Type) return Boolean;
Equivalent to Find (Container, Item) /= No_Element.
Paragraphs 139 and 140 were moved above.
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
Iterate calls Process.all with a cursor that designates each node in Container, starting with the first node and moving the cursor as per the Next function. Tampering with the cursors of Container is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
The purpose of the tamper with cursors check is to prevent erroneous execution from the Position parameter of Process.all becoming invalid. This check takes place when the operations that tamper with the cursors of the container are called. The check cannot be made later (say in the body of Iterate), because that could cause the Position cursor to be invalid and potentially cause execution to become erroneous -- defeating the purpose of the check.
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
Iterates over the nodes in Container as per procedure Iterate, except that elements are traversed in reverse order, starting with the last node and moving the cursor as per the Previous function.
function Iterate (Container : in List)
return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
Iterate returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator, and processing all nodes concurrently when used as a parallel iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Iterate returns a reversible iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
Exits are allowed from the loops created using the iterator objects. In particular, to stop the iteration at a particular cursor, just add
exit when Cur = Stop;
in the body of the loop (assuming that Cur is the loop parameter and Stop is the cursor that you want to stop at).
The actual function for the generic formal function "<" of Generic_Sorting is expected to return the same value each time it is called with a particular pair of element values. It should define a strict weak ordering relationship (see A.18); it should not modify Container. If the actual for "<" behaves in some other manner, the behavior of the subprograms of Generic_Sorting are unspecified. The number of times the subprograms of Generic_Sorting call "<" is unspecified.
function Is_Sorted (Container : List) return Boolean;
Returns True if the elements are sorted smallest first as determined by the generic formal "<" operator; otherwise, Is_Sorted returns False. Any exception raised during evaluation of "<" is propagated.
procedure Sort (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
Reorders the nodes of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. The sort is stable. Any exception raised during evaluation of "<" is propagated.
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.
procedure Merge (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Elements_Prohibited (Source)
or else raise Program_Error) and then
(Length (Target) <= Count_Type'Last - Length (Source)
or else raise Constraint_Error) and then
((Length (Source) = 0 or else
not Target'Has_Same_Storage (Source))
or else raise Constraint_Error),
Post => (declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
(Length (Source) = 0 and then
Length (Target) = Result_Length));
Merge removes elements from Source and inserts them into Target; afterwards, Target contains the union of the elements that were initially in Source and Target; Source is left empty. If Target and Source are initially sorted smallest first, then Target is ordered smallest first as determined by the generic formal "<" operator; otherwise, the order of elements in Target is unspecified. Any exception raised during evaluation of "<" is propagated.
It is a bounded error if either of the lists is unsorted, see below. The bounded error can be recovered by sorting Target after the merge call, or the lists can be pretested with Is_Sorted.
The nested package Doubly_Linked_Lists.Stable provides a type Stable.List that represents a stable list, which is one that cannot grow and shrink. Such a list can be created by calling the Copy function, or by establishing a stabilized view of an ordinary list.
The subprograms of package Containers.Doubly_Linked_Lists that have a parameter or result of type List are included in the nested package Stable with the same specification, except that the following are omitted:
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited, Assign, Move, Insert, Append, Prepend, Clear, Delete, Delete_First, Delete_Last, Splice, Swap_Links, and Reverse_Elements
The names List and Cursor mean the types declared in the nested package in these subprogram specifications.
The omitted routines are those that tamper with cursors or elements (or test that state). The model is that it is impossible to tamper with cursors or elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view, and we omit the operations associated with those checks.
The Generic_Sorting generic is omitted entirely, as only function Is_Sorting does not tamper with cursors. It isn't useful enough by itself to include.
The operations of this package are equivalent to those for ordinary lists, except that the calls to Tampering_With_Cursors_Prohibited and Tampering_With_Elements_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.
If a stable list is declared with the Base discriminant designating a pre-existing ordinary list, the stable list represents a stabilized view of the underlying ordinary list, and any operation on the stable list is reflected on the underlying ordinary list. While a stabilized view exists, any operation that tampers with elements performed on the underlying list is prohibited. The finalization of a stable list that provides such a view removes this restriction on the underlying ordinary list [(though some other restriction can exist due to other concurrent iterations or stabilized views)].
If a stable list is declared without specifying Base, the object is necessarily initialized. The initializing expression of the stable list, [typically a call on Copy], determines the Length of the list. The Length of a stable list never changes after initialization.
Bounded (Run-Time) Errors
152/2Calling Merge in an instance of Generic_Sorting with either Source or Target not ordered smallest first using the provided generic formal "<" operator is a bounded error. Either Program_Error is raised after Target is updated as described for Merge, or the operation works as defined.
It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any List parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the List either prior to, or subsequent to, some or all of the modifications to the List.
It is a bounded error to call any subprogram declared in the visible part of Containers.Doubly_Linked_Lists when the associated container has been finalized. If the operation takes Container as an in out parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error.
Erroneous Execution
153/2A 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 Target of a call to Assign, or as the target of an
assignment_statement; 155/2 - [The list that contains the element it designates has been used as the Source or Target of a call to Move;] or
Move has been reworded in terms of Assign and Clear, which are covered by other bullets, so this text is redundant.
- The element it designates has been removed from the list that previously contained the element.
To be honest: The cursor modified by the four parameter Splice is not invalid, even though the element it designates has been removed from the source list, because that cursor has been modified to designate that element in the target list – the cursor no longer designates an element in the source list.
This can happen directly via calls to Delete, Delete_Last, Clear, Splice with a Source parameter, and Merge; and indirectly via calls to Delete_First, Assign, and Move.
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.
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 Program_Error if detected.
Execution is erroneous if the list associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a nonexistent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)
Implementation Requirements
158/5No storage associated with a doubly-linked list object shall be lost upon assignment or scope exit.
The execution of an assignment_statement for a list shall have the effect of copying the elements from the source list object to the target list object and changing the length of the target object to that of the source object.
An assignment of a List is a “deep” copy; that is the elements are copied as well as the data structures. We say “effect of” in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed. (Note that this implementation would require care, see A.18.2 for more.)
Implementation Advice
160/2Containers.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).
The worst-case time complexity of Element, Insert with Count=1, and Delete with Count=1 for Containers.Doubly_Linked_Lists should be O(log N).
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 procedure Sort of an instance of Containers.Doubly_Linked_Lists.Generic_Sorting should be O(N**2), and the average time complexity should be better than O(N**2).
A call on procedure Sort of an instance of Containers.Doubly_Linked_Lists.Generic_Sorting should have an average time complexity better than O(N**2) and worst case no worse than O(N**2).
In other words, we're requiring the use of a better than O(N**2) sorting algorithm, such as Quicksort. No bubble sorts allowed!
Move should not copy elements, and should minimize copying of internal data structures.
Containers.Doubly_Linked_Lists.Move should not copy elements, and should minimize copying of internal data structures.
Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source container to the Target container.
If an exception is propagated from a list operation, no storage should be lost, nor any elements removed from a list unless specified by the operation.
If an exception is propagated from a list operation, no storage should be lost, nor any elements removed from a list unless specified by the operation.
This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished.