A.18.2 The Generic Package Containers.Vectors
The 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.
Implementation Note: 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
{
AI95-00302-03}
The generic library package Containers.Vectors has the following declaration:
{
AI05-0084-1}
{
AI05-0212-1}
{
AI12-0112-1}
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
is
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
pragma Preelaborate(Vectors);
pragma Remote_Types(Vectors);
Discussion: {
AI12-0112-1}
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).
{
AI12-0112-1}
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;
Ramification: {
AI12-0112-1}
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.
{
AI05-0212-1}
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0212-1}
{
AI12-0339-1}
{
AI12-0399-1}
{
AI12-0400-1}
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)),;
pragma Preelaborable_Initialization
(Vector);
{
AI12-0399-1}
type Cursor
is private;
with pragma Preelaborable_Initialization
(Cursor);
Empty_Vector :
constant Vector;
No_Element :
constant Cursor;
{
AI05-0212-1}
{
AI12-0112-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Discussion: {
AI12-0112-1}
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.
{
AI12-0112-1}
function Has_Element (Container : Vector; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Discussion: {
AI12-0112-1}
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.
{
AI05-0212-1}
package Vector_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Vector) return Boolean;
{
AI12-0112-1}
function Tampering_With_Cursors_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
function Tampering_With_Elements_Prohibited
(Container : Vector) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
function Maximum_Length return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0339-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0212-1}
function New_Vector (First, Last : Index_Type) return Vector is
(To_Vector (Count_Type (Last - First + 1)))
with Pre => First = Index_Type'First;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function Capacity (Container : Vector)
return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function Length (Container : Vector)
return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function Is_Empty (Container : Vector)
return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
{
AI12-0112-1}
procedure Clear (Container :
in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function To_Index (Position : Cursor)
return Extended_Index
with Nonblocking, Global => in all;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
Discussion: {
AI12-0112-1}
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.
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI05-0212-1}
{
AI12-0112-1}
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);
Discussion: {
AI12-0112-1}
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.
{
AI05-0212-1}
{
AI12-0112-1}
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);
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0001-1}
{
AI12-0112-1}
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);
{
AI05-0001-1}
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Insert_Vector Insert (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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Insert_Vector Insert (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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Insert_Vector Insert (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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Prepend_Vector Prepend (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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Append_Vector Append (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);
{
AI12-0112-1}
{
AI12-0400-1}
procedure Append (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);
{
AI12-0112-1}
{
AI12-0212-1}
{
AI12-0400-1}
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);
{
AI12-0112-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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
procedure Reverse_Elements (Container :
in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
function First_Index (Container : Vector)
return Index_Type
with Nonblocking, Global => null, Use_Formal => null,
Post => First_Index'Result = Index_Type'First;
{
AI12-0112-1}
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);
{
AI12-0112-1}
function First_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI12-0112-1}
function Last_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Next (Position : Cursor)
return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
{
AI12-0112-1}
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);
{
AI12-0112-1}
procedure Next (Position :
in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
{
AI12-0112-1}
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));
{
AI12-0112-1}
function Previous (Position : Cursor)
return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Previous'Result = No_Element);
{
AI12-0112-1}
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);
{
AI12-0112-1}
procedure Previous (Position :
in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
{
AI12-0112-1}
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));
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
{
AI12-0112-1}
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));
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
{
AI12-0112-1}
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));
function Contains (Container : Vector;
Item : Element_Type)
return Boolean;
{
AI12-0112-1}
procedure Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI12-0112-1}
procedure Reverse_Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI05-0212-1}
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Vector)
return Vector_Iterator_Interfaces.
Parallel_Reversible_Iterator Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0212-1}
{
AI12-0112-1}
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);
{
AI12-0112-1}
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
with Nonblocking, Global => null is
function Is_Sorted (Container : Vector)
return Boolean;
{
AI12-0112-1}
procedure Sort (Container :
in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
{
AI12-0112-1}
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));
end Generic_Sorting;
{
AI12-0111-1}
{
AI12-0339-1}
{
AI12-0400-1}
{
AI12-0407-1}
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;
Discussion: {
AI05-0112-1}
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.
{
AI12-0111-1}
type Cursor is private
with Preelaborable_Initialization;
{
AI12-0111-1}
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
{
AI12-0111-1}
package Vector_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
{
AI12-0111-1}
procedure Assign (Target : in out Vectors.Vector;
Source : in Vector)
with Post => Length (Source) = Length (Target) and then
Capacity (Target) >= Length (Target);
{
AI12-0111-1}
function Copy (Source : Vectors.Vector) return Vector
with Post => Length (Copy'Result) = Length (Source);
{
AI12-0111-1}
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);
{
AI12-0111-1}
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);
{
AI12-0111-1}
-- Additional subprograms as described in the text
-- are declared here.
private
... -- not specified by the language
end Ada.Containers.Vectors;
{
AI95-00302-03}
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.
Ramification: 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.
{
AI95-00302-03}
The type Vector is used to represent vectors. The type Vector needs finalization
(see
7.6).
{
AI95-00302-03}
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.
{
AI95-00302-03}
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.
{
AI95-00302-03}
{
AI12-0434-1}
The
primitive predefined
"=" operator for type Cursor returns True if both cursors are
No_Element, or designate the same element in the same container.
To be honest: {
AI12-0434-1}
“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
"=".
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
Reason: 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.
{
AI05-0001-1}
{
AI05-0262-1}
{
AI12-0437-1}
Vector'Write for a Vector object
V writes Length(
V) elements
of the vector to the stream. It
may also
may write additional information about the vector.
{
AI05-0001-1}
{
AI05-0262-1}
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.
Implementation Note: 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.
{
AI95-00302-03}
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.
Discussion: 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).
{
AI05-0001-1}
{
AI12-0112-1}
If an operation attempts to modify the vector such
that the position of the last element would be greater than Index_Type'Last,
then the operation propagates Constraint_Error.
Reason: We don't
want to require an implementation to go to heroic efforts to handle index
values larger than the base type of the index subtype.
{
AI95-00302-03}
{
AI12-0111-1}
{
AI12-0112-1}
[Some operations
of this generic package have access-to-subprogram parameters. To ensure
such operations are well-defined, they guard against certain actions
by the designated subprogram. In particular, 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.
it inserts or deletes elements
of V, that is, it calls the Insert, Insert_Space, Clear, Delete,
or Set_Length procedures with V as a parameter; or
To be honest: Operations
which are defined to be equivalent to a call on one of these operations
also are included. Similarly, operations which call one of these as part
of their definition are included.
it finalizes V; or
{
AI05-0001-1}
it calls the Assign procedure with V as
the Target parameter; or
Ramification: 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.
it calls the Move procedure
with V as a parameter.
Discussion: {
AI12-0111-1}
Swap, Sort, and Merge copy elements rather than
reordering them, so they don't tamper with cursors.
it tampers with cursors of
V; or
it replaces one or more elements
of V, that is, it calls the Replace_Element, Reverse_Elements,
or Swap procedures or the Sort or Merge procedures of an instance of
Generic_Sorting with V as a parameter.
Reason: Complete
replacement of an element can cause its memory to be deallocated while
another operation is holding onto a reference to it. That can't be allowed.
However, a simple modification of (part of) an element is not a problem,
so Update_Element does not cause a problem.
{
AI05-0265-1}
{
AI12-0110-1}
{
AI12-0112-1}
When tampering
with cursors is prohibited for a particular vector object V,
Program_Error is propagated by a call of any language-defined subprogram
that is defined to tamper with the cursors of V, leaving V
unmodified. Similarly, when tampering with elements is prohibited
for a particular vector object V, Program_Error is propagated
by a call of any language-defined subprogram that is defined to tamper
with the elements of V [(or tamper with the cursors of V)],
leaving V unmodified. These checks are made before any other defined behavior of the body of
the language-defined subprogram.
Proof: Tampering
with elements includes tampering with cursors, so we mention it only
from completeness in the second sentence.
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
{
AI05-0212-1}
Returns True if Position designates an element, and returns False otherwise.
To be honest: {
AI05-0005-1}
{
AI05-0212-1}
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;
{
AI12-0112-1}
Returns True if Position designates an element
in Container, and returns False otherwise.
Ramification: If
Position is No_Element, Has_Element returns False.
function "=" (Left, Right : Vector) return Boolean;
{
AI95-00302-03}
{
AI05-0264-1}
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.
Implementation Note: 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;
{
AI12-0112-1}
Returns True if tampering with cursors or tampering
with elements is currently prohibited for Container, and returns False
otherwise.
Reason: {
AI12-0112-1}
Prohibiting tampering with elements also needs
to prohibit tampering with cursors, as deleting an element is similar
to replacing it.
Implementation Note:
{
AI12-0112-1}
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;
{
AI12-0112-1}
Always returns False[, regardless of whether tampering
with elements is prohibited].
Reason: {
AI12-0111-1}
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;
{
AI12-0112-1}
Returns the maximum Length of a Vector, based on
the index type.
Implementation
Note: 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;
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;
{
AI95-00302-03}
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;
{
AI95-00302-03}
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);
{
AI95-00302-03}
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;
{
AI95-00302-03}
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;
{
AI95-00302-03}
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;
{
AI95-00302-03}
Returns a vector comprising the element Left followed by the element
Right.
{
AI12-0112-1}
function Capacity (Container : Vector)
return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
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;
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0264-1}
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.
Discussion: 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;
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;
{
AI95-00302-03}
{
AI05-0264-1}
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.
Ramification: 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);
procedure Clear (Container : in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
{
AI95-00302-03}
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;
{
AI95-00302-03}
{
AI12-0112-1}
{
AI12-0196-1}
Returns If Index is
not in the range First_Index (Container) .. Last_Index (Container), then
No_Element is returned. Otherwise, a cursor designating the element
at position Index in Container
; returns No_Element
if Index does not designate an element is
returned.
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)].
Reason: {
AI12-0196-1}
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;
{
AI95-00302-03}
If Position is No_Element, No_Index is returned. Otherwise, the index
(within its containing vector) of the element designated by Position
is returned.
Ramification: 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;
{
AI12-0112-1}
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;
{
AI95-00302-03}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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;
{
AI95-00302-03}
{
AI12-0112-1}
If If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, 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;
{
AI12-0112-1}
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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
{
AI12-0196-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
{
AI12-0196-1}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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)].
Ramification: {
AI05-0212-1}
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;
{
AI95-00302-03}
{
AI05-0265-1}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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.
Reason: {
AI05-0005-1}
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;
{
AI95-00302-03}
{
AI05-0021-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, 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);
{
AI12-0112-1}
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;
{
AI95-00302-03}
{
AI05-0265-1}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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.
Ramification: 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.
Ramification: 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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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.
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type need finalization.
This paragraph
was deleted.{
AI12-0112-1}
The default initialization of an object of type
Constant_Reference_Type or Reference_Type propagates Program_Error.
Reason: 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.
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI05-0269-1}
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.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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.
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI05-0269-1}
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.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
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.
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI05-0269-1}
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.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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.
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI05-0269-1}
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.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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);
{
AI05-0001-1}
{
AI05-0248-1}
{
AI05-0262-1}
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).
Discussion: {
AI05-0005-1}
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);
{
AI05-0001-1}
{
AI12-0112-1}
Returns a vector whose elements are initialized from the corresponding
elements of Source.
If Capacity is 0, then the
vector capacity is the length of Source; if Capacity is equal to or greater
than the length of Source, the vector capacity is at least the specified
value. Otherwise, the operation propagates Capacity_Error.
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);
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0248-1}
{
AI12-0112-1}
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 length of Source is 0 after a successful call to Move.
Discussion: The idea is that the internal
array is removed from Source and moved to Target. (See the Implementation
Advice 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 Insert (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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
{
AI12-0400-1}
If Before is not in the range First_Index (Container)
.. Last_Index (Container) + 1, then Constraint_Error is propagated. If
Length(New_Item) is 0, then
Insert_Vector Insert
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.
{
AI12-0400-1}
If the current vector capacity is less than
NL, Reserve_Capacity
(Container,
NL) is called to increase the vector capacity. Then
Insert_Vector Insert
slides the elements in the range Before .. Last_Index (Container) up
by Length(New_Item) positions, and then copies the elements of New_Item
to the positions starting at Before. Any exception raised during the
copying is propagated.
Ramification: 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 Insert (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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
{
AI12-0400-1}
If
Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
if Length(New_Item) is 0, then
Insert_Vector Insert
does nothing. If Before is No_Element, then the call is equivalent to
Insert_Vector Insert
(Container, Last_Index (Container) + 1, New_Item); otherwise, the call
is equivalent to
Insert_Vector Insert
(Container, To_Index (Before), New_Item);
Ramification: 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 Insert (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);
{
AI95-00302-03}
{
AI12-0112-1}
{
AI12-0400-1}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. If
Before equals No_Element, then let
T be Last_Index (Container)
+ 1; otherwise, let
T be To_Index (Before).
Insert_Vector Insert
(Container,
T, New_Item) is called, and then Position is set to
To_Cursor (Container,
T).
Discussion: {
AI12-0400-1}
The messy wording is needed because Before is invalidated by
Insert_Vector Insert,
and we don't want Position to be invalid after this call. An implementation
probably only needs to copy Before to Position.
{
AI12-0112-1}
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);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
{
AI12-0112-1}
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);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
{
AI12-0112-1}
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);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count),
Position);
Ramification: {
AI05-0257-1}
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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
If Before is not in the range First_Index (Container)
.. Last_Index (Container) + 1, then Constraint_Error is propagated. 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);
{
AI95-00302-03}
{
AI12-0112-1}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. 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).
Reason: 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.
{
AI12-0080-1}
{
AI12-0112-1}
{
AI12-0400-1}
procedure Prepend_Vector Prepend (Container :
in out Vector;
New_Item :
in Vector
;
Count : in Count_Type := 1)
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);
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container), New_Item).
{
AI12-0112-1}
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);
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container), New_Item, Count).
{
AI12-0112-1}
{
AI12-0400-1}
procedure Append_Vector Append (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);
{
AI95-00302-03}
Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item).
{
AI12-0112-1}
{
AI12-0400-1}
procedure Append (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);
{
AI95-00302-03}
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);
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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
If Before is not in the range First_Index (Container)
.. Last_Index (Container) + 1, then Constraint_Error is propagated. 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);
{
AI95-00302-03}
{
AI12-0112-1}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. 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);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
If Index is not in the range First_Index (Container)
.. Last_Index (Container) + 1, then Constraint_Error is propagated. 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.
Ramification: 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;
{
AI95-00302-03}
{
AI12-0112-1}
If Position equals No_Element, then Constraint_Error
is propagated. If Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Delete (Container,
To_Index (Position), Count) is called, and then Position is set to No_Element.
{
AI12-0112-1}
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);
{
AI95-00302-03}
Equivalent to Delete (Container, First_Index (Container), Count).
{
AI12-0112-1}
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);
{
AI95-00302-03}
{
AI05-0264-1}
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).
{
AI05-0092-1}
{
AI12-0112-1}
procedure Reverse_Elements (Container :
in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
{
AI95-00302-03}
Reorders the elements of Container in reverse order.
Discussion: 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);
{
AI95-00302-03}
{
AI12-0112-1}
If either I or J is not in the range First_Index
(Container) .. Last_Index (Container), then Constraint_Error is propagated.
Otherwise, Swap exchanges the values of the elements at positions
I and J.
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);
{
AI95-00302-03}
{
AI12-0112-1}
If either I or J is No_Element, then Constraint_Error
is propagated. If either I or J do not designate an element in Container,
then Program_Error is propagated. Otherwise, Swap exchanges the
values of the elements designated by I and J.
Ramification: 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.
{
AI12-0112-1}
function First_Index (Container : Vector)
return Index_Type
with Nonblocking, Global => null, Use_Formal => null,
Post => First_Index'Result = Index_Type'First;
Discussion: We'd rather call this “First”,
but then calling most routines in here with First (Some_Vect) would be
ambiguous.
{
AI12-0112-1}
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);
{
AI95-00302-03}
If Container is empty, First returns No_Element. Otherwise, it returns
a cursor that designates the first element in Container.
{
AI12-0112-1}
function First_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
{
AI95-00302-03}
Equivalent to Element (Container, First_Index (Container)).
{
AI12-0112-1}
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);
{
AI95-00302-03}
If Container is empty, Last_Index returns No_Index. Otherwise, it returns
the position of the last element in Container.
{
AI12-0112-1}
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);
{
AI95-00302-03}
If Container is empty, Last returns No_Element. Otherwise, it returns
a cursor that designates the last element in Container.
{
AI12-0112-1}
function Last_Element (Container : Vector)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);
{
AI95-00302-03}
Equivalent to Element (Container, Last_Index (Container)).
{
AI12-0112-1}
function Next (Position : Cursor)
return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
{
AI95-00302-03}
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);
{
AI12-0112-1}
Returns a cursor designating the next element in
Container, if any.
{
AI12-0112-1}
procedure Next (Position :
in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
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));
{
AI12-0112-1}
Equivalent to Position := Next (Container, Position).
{
AI12-0112-1}
function Previous (Position : Cursor)
return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Previous'Result = No_Element);
{
AI95-00302-03}
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);
{
AI12-0112-1}
Returns a cursor designating the previous element
in Container, if any.
{
AI12-0112-1}
procedure Previous (Position :
in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
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));
{
AI12-0112-1}
Equivalent to Position := Previous (Container,
Position).
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
{
AI95-00302-03}
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));
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
If Position is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
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;
{
AI95-00302-03}
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));
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
If Position is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
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;
{
AI95-00302-03}
Equivalent to Has_Element (Find (Container, Item)).
Paragraphs 225
and 226 were moved above.
{
AI12-0112-1}
procedure Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI95-00302-03}
{
AI05-0265-1}
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.
Discussion: 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.
{
AI12-0112-1}
procedure Reverse_Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI95-00302-03}
{
AI05-0212-1}
Iterates over the elements in Container as per procedure Iterate, except
that elements are traversed in reverse index order.
{
AI12-0212-1}
{
AI12-0266-1}
function Iterate (Container :
in Vector)
return Vector_Iterator_Interfaces.
Parallel_Reversible_Iterator Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0212-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0266-1}
Iterate returns
an 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 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);
{
AI05-0212-1}
{
AI05-0262-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0212-1}
If Start is not No_Element and does not designate
an item in Container, then Program_Error is propagated. If Start is No_Element,
then Constraint_Error is propagated. Otherwise, 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.
Discussion:
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).
{
AI05-0044-1}
{
AI05-0262-1}
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;
{
AI95-00302-03}
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.
{
AI12-0112-1}
procedure Sort (Container :
in out Vector)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;
{
AI95-00302-03}
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.
Ramification: 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 Implementation
Advice below that the implementation should use a sort that minimizes
copying of elements.
The sort is not required to be stable (and the
fast algorithm required will not be stable). If a stable sort is needed,
the user can include the original location of the element as an extra
"sort key". We considered requiring the implementation to do
that, but it is mostly extra overhead -- usually there is something already
in the element that provides the needed stability.
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));
{
AI95-00302-03}
{
AI05-0021-1}
{
AI12-0112-1}
If Source is empty, then Merge does nothing. If
Source and Target are the same nonempty container object, then Program_Error
is propagated. Otherwise, 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.
Discussion: 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.
Implementation Note: 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.
{
AI12-0111-1}
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.
{
AI12-0111-1}
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:
{
AI12-0111-1}
{
AI12-0400-1}
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.
Ramification: The
names Vector and Cursor mean the types declared in the nested package
in these subprogram specifications.
Reason: 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.
{
AI12-0111-1}
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.
{
AI12-0111-1}
{
AI12-0439-1}
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)].
{
AI12-0111-1}
{
AI12-0438-1}
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.
Proof: {
AI12-0438-1}
Initialization is required as the type is indefinite,
see 3.3.1.
Bounded (Run-Time) Errors
{
AI95-00302-03}
{
AI05-0212-1}
Reading 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.
Ramification: 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.
{
AI95-00302-03}
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.
{
AI05-0022-1}
{
AI05-0248-1}
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.
{
AI05-0027-1}
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.
{
AI95-00302-03}
A Cursor value is
ambiguous
if any of the following have occurred since it was created:
{
AI12-0400-1}
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.
{
AI95-00302-03}
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.
Reason: 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
{
AI95-00302-03}
A Cursor value is
invalid if any of the following have occurred
since it was created:
The vector that contains the element it designates
has been finalized;
{
AI05-0160-1}
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;
[The vector that contains the element it designates
has been used as the Source or Target of a call to Move;] or
Proof: {
AI05-0001-1}
Move has been reworded in terms of Assign and Clear, which are covered
by other bullets, so this text is redundant.
{
AI05-0160-1}
{
AI05-0262-1}
The element it designates has been deleted or removed from the vector
that previously contained the element.
Ramification: {
AI05-0160-1}
An element can be removed via calls to Set_Length, Clear, and Merge;
and indirectly via calls to Assign and Move.
{
AI95-00302-03}
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.
Discussion: 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.
{
AI05-0212-1}
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.
Reason: 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
{
AI95-00302-03}
No storage associated with a vector object shall be lost upon assignment
or scope exit.
{
AI95-00302-03}
{
AI05-0262-1}
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.
Implementation Note: {
AI05-0298-1}
{
AI12-0005-1}
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
be 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
{
AI95-00302-03}
Containers.Vectors should be implemented similarly to an array. In particular,
if the length of a vector is
N, then
the worst-case time complexity of Element should
be O(log N);
Implementation Advice: 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
Implementation Advice: 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).
Implementation Advice: 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).
Reason: 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.
{
AI95-00302-03}
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).
Implementation Advice: 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).
Ramification: In other words, we're requiring
the use of a better than O(N**2) sorting algorithm, such
as Quicksort. No bubble sorts allowed!
{
AI95-00302-03}
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
should minimize copying of elements.
Implementation Advice: 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.
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Containers.Vectors.Move
should not copy elements, and should minimize copying of internal data
structures.
Implementation Note: Usually that can
be accomplished simply by moving the pointer(s) to the internal data
structures from the Source vector to the Target vector.
{
AI95-00302-03}
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.
Implementation Advice: 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.
Reason: 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 {
AI12-0440-1}
All elements of a vector occupy locations in the internal array. If a
sparse container is required, a Hashed_Map
can should
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.
Discussion: 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
{
AI05-0001-1}
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
{
AI05-0212-1}
Added iterator, reference, and indexing support to
make vector containers more convenient to use.
Wording Changes from Ada 2005
{
AI05-0001-1}
Generalized the definition of Reserve_Capacity and Move. Specified which
elements are read/written by stream attributes.
{
AI05-0022-1}
Correction: Added a Bounded (Run-Time) Error to cover tampering
by generic actual subprograms.
{
AI05-0027-1}
Correction: Added a Bounded (Run-Time) Error to cover access to
finalized vector containers.
{
AI05-0044-1}
Correction: Redefined "<" actuals to require a strict
weak ordering; the old definition allowed indeterminant comparisons that
would not have worked in a container.
{
AI05-0084-1}
Correction: Added a pragma Remote_Types so that containers can
be used in distributed programs.
{
AI05-0160-1}
Correction: Revised the definition of invalid cursors to cover
missing (and new) cases.
{
AI05-0265-1}
Correction: 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
{
AI12-0111-1}
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.
{
AI12-0112-1}
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
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0339-1}
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.
{
AI12-0005-1}
{
AI12-0212-1}
{
AI12-0400-1}
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.
{
AI12-0400-1}
Correction: 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
{
AI12-0196-1}
Correction: 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.
{
AI12-0212-1}
Vectors now support indexed container aggregates,
so aggregate
syntax can be used to create Vectors.
{
AI12-0266-1}
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
{
AI12-0110-1}
Corrigendum: Clarified that tampering checks
precede all other checks made by a subprogram (but come after those associated
with the call).
{
AI12-0112-1}
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).
{
AI12-0400-1}
Correction: 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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe