A vector is a generalization of an array-based stack. The container is optimized for pushing and popping items from the back end, but indexing an element at any position is permitted. This vector type is bounded, which means the size of the internal array is fixed at the time of declaration. (There is a complementary unbounded form, which allows the internal array to change in size.) This container can also be used to store limited elements. The length of a vector indicates how many elements of the internal array are "active," and the size indicates the length of the internal array.
type Element_Array_Type is
array (Index_Type range <>) of aliased Element_Type;
pragma Convention (C, Element_Array_Type);
function "=" (L, R : Element_Array_Type) return Boolean is abstract;
subtype Last_Subtype is Index_Type'Base range
Index_Type'Pred (Index_Type'First) .. Index_Type'Last;
type Container_Type;
type Handle_Type (Container : access Container_Type) is
limited null record;
type Container_Type (Elements_Last : Last_Subtype) is
limited record
Handle : Handle_Type (Container_Type'Access);
Elements : aliased Element_Array_Type
(Index_Type'First .. Elements_Last);
Last : Last_Subtype := Last_Subtype'First;
end record;
The container type for bounded vectors.
This specification guarantees that Container_Type
is a pass-by-reference type.
In this implementation, the vector type is a simple limited record.
It does not derive from Controlled,
which means that instantiations of this package are allowed anywhere (and not just at library level).
One way to view a vector is abstractly, as a container that provides constant-time random access of elements. Another way is to view it as a high-level mechanism to manipulate an array. It is often that case we need to view the vector as contiguous array of elements, and thus Container_Type is unencapsulated, to support this latter view.
Note that it is not possible to provide a To_Access function as we do for the unbounded version of this container, because the constrained element array declared above carries no dope. I wish the language would allow me to specify that I want dope generated for the (constrained) array, so that I could provide such a function and thus properly hide the representation. Perhaps this deficiency will be fixed in a future version of the language.
The container also has a handle component, which exists to convert a constant view of the container object into a variable view. (This is known as the "Rosen Trick.") For the unbounded form, the elements can be manipulated even though you only have a constant view, because there is a level of indirection. For the bounded form this is not the case, and the handle component is there to allow the same kind of element modification in similar contexts. For example:
procedure Op (V : in Vector_Subtype.Container_Type) is
procedure Modify (E : in out Element_Subtype) is
begin
--...
end;
procedure Modify_Elements is
new Generic_Modify_Elements (Process => Modify);
begin
Modify_Elements (V.Handle.Container.all, First (V), Back (V));
end;
Of course, this package could have been written to do this automatically (that is indeed the case for the unbounded form), but I thought it would be better to require that array manipulation through a constant view be done explicitly.
generic
with function "=" (L, R : Element_Type) return Boolean is <>;
function Generic_Equality
(Left, Right : Container_Type) return Boolean;
The (generic) equality operator for vectors. (There are no composibility issues for limited types.)
If Left and Right refer to the same
container, then the function returns immediately with the value True.
If Left and Right have different lengths (a different number of logical elements),
then the function returns immediately with the value False.
Otherwise, elements are compared sequentially using the equality operator supplied as the
generic formal subprogram (of this generic operation).
(This specification guarantees that the predefined equality for Element_Type that reemerges is not used.)
Any exception raised during evaluation of element equality is propagated.
generic
with function "<" (L, R : Element_Type) return Boolean is <>;
function Generic_Less
(Left, Right : Container_Type) return Boolean;
Performs a lexicographical comparison of the Left and Right vectors.
If Left and Right refer to the same container, then the function returns immediately with the value False. If Left is longer than Right (i.e. Length (Left) > Length (Right)), then the function returns immediately with the value False. Otherwise, elements are compared sequentially using the less-than operator supplied as the generic formal subprogram. Any exception raised during evaluation of element less-than is propagated.
function Length (Container : Container_Type)
return Natural;
The Length function returns the number of active elements in the vector represented by Container. (This is the logical length of the vector. Contrast this with function Size, which returns the physical length of the internal array.) A bounded vector has a maximum length, equivalent to the size specified as the container discriminant.
function Is_Empty (Container : Container_Type)
return Boolean;
Equivalent to Length (Container) = 0.
procedure Clear (Container : in out Container_Type);
This operation "removes" all the elements in the container, by setting the length to 0.
If element finalization (of whatever nature) is required, the caller is responsible for effecting this himself prior to the call. For example, to finalize the active elements in-place, you could do this:
V : Vector_Subtype (N);
...
for I in First (V) .. Last (V) loop
declare
E : Element_Subtype renames To_Access (V, I).all;
begin
Finalize (E); -- or whatever
end;
end loop;
Clear (V);
In this case, it's simpler to apply a modifier operation to an element, like this:
procedure Finalize_Element is
new Generic_Modify_Element (Process => Finalize);
for I in First (V) .. Last (V) loop
Finalize_Element (V, I);
end loop;
Clear (V);
It's simpler still to just use a passive iterator to modify all the elements:
procedure Finalize_Elements is
new Generic_Modify_Elements (Process => Finalize);
Finalize_Elements (V, First (V), Back (V));
Clear (V);
Note the subtle difference in the examples above: the passive iterator specifies the half-open range [First, Back), but the loop iterator specifies the closed-range [First, Last].
procedure Assign
(Target : in out Container_Type;
Length : in Natural);
Sets the container length to the indicated value. If Length is greater than the size of Target, the operation fails and Contraint_Error is raised.
procedure Push_Back
(Container : in out Container_Type);
If the vector length equals the vector size, the operation fails and Constraint_Error is raised. Otherwise, the operation increments the vector length by 1.
This version of Push_Back is useful when you don't have a value to assign to the new vector element, and just want to modify the element in-place:
procedure New_Stream (File : in out File_Type) is
V : Vector_Subtype renames File.Streams;
begin
Push_Back (V);
declare
Stream : Stream_Type renames
To_Access (V, Last (V)).all;
begin
-- ... initialize stream object
end;
end New_Stream;
In the example above, the insertion of a new element and accessing of the element are separate steps. The steps can be combined using the following function.
function Push_Back
(Container : access Container_Type) return Element_Access;
Equivalent to the procedure form above, except that this function can be used in a declarative region. It returns an access object designating the new element. For example:
procedure New_Stream (File : in out File_Type) is
V : Vector_Subtype renames File.Streams;
Stream : Stream_Type renames Push_Back (V'Access).all;
begin
-- ... initialize stream object
end New_Stream;
Compare this with the previous example. Note that function Push_Back accepts the vector object as an access parameter, which requires that it be aliased.
function Push_Back
(Container : access Container_Type) return Index_Type;
As above, except that the function returns Last (Container), the index value that designates the newly-inserted element.
procedure Push_Back_N
(Container : in out Container_Type;
Count : in Natural);
If the sum of the current length and Count is greater than the vector size, then the operation fails and Constraint_Error is raised. Otherwise, it increments the vector length by Count.
procedure Pop_Back (Container : in out Container_Type);
If the vector length is 0, then the operation fails and Contraint_Error is raised. Otherwise it decrements the vector length by 1. (Should the precondition be weakened? In all the Pop operations, it's not clear whether trying to pop more elements than are present in the vector should be an "error." This behavior is also inconsistent with Delete, which allows N to be greater than the length.)
If finalization (of whatever nature) of the last element is required, the caller is responsible for effecting this himself prior to the call. For example:
V : Vector_Types.Container_Type (N);
...
declare
E : Vector_Types.Element_Subtype renames
To_Access (V, Last (V)).all;
begin
Finalize (E); --or whatever
end;
Pop_Back (V);
A simpler alternative is to apply a modifier to an element, like this:
procedure Finalize_Element is
new Vector_Types.Generic_Modify_Element (Process => Finalize);
V : Vector_Types.Container_Type (N);
...
Finalize_Element (V, Last (V));
Pop_Back (V);
procedure Pop_Back_N
(Container : in out Container_Type;
Count : in Natural);
If the vector length is less than Count, then the operation fails and Constraint_Error is raised. (Should we relax this precondition? See italized note above.) Otherwise it decrements the vector length by Count.
function Size (Container : Container_Type) return Natural;
Returns the value Container.Elements'Length. (This is the physical length of the internal array. Contrast this with function Length, which returns the logical length of the vector.)
function Front
(Container : Container_Type) return Index_Type'Base;
Returns the value Index_Type'Pred (Index_Type'First).
function First
(Container : Container_Type) return Index_Type;
Returns the value Index_Type'First. The First selector for a vector is exactly analogous to the First attribute of an array.
function Last
(Container : Container_Type) return Index_Type'Base;
Returns the index of the element corresponding to the length of the vector. The Last selector for a vector is exactly analogous to the Last attribute of an array.
function Back
(Container : Container_Type) return Index_Type'Base;
Equivalent to Index_Type'Succ (Last (Container)). Returns the index value one beyond the last element of the vector. The Back selector is used for indicating "all the elements in the vector," expressed as a half-open range.
function Element
(Container : Container_Type;
Index : Index_Type) return Element_Type;
Returns the element at the indicated index position. If Index does not specify a value in the range Index_Type'First .. Last (Container), then the operation fails and Constraint_Error is raised. (Should we weaken this precondition? There is already a pre-defined check when indexing the internal array, which has a range from First (Container) .. Size (Container). But that would mean you'd be allowing indexing of elements in the range Index_Type'Succ (Last (Container)) .. Size (Container), which doesn't really make sense, but at worst it's only a bounded error.)
It might seem odd to return limited objects this way, but this function is exactly analogous to returning a "constant reference" in C++, because limited types are passed by reference in Ada95. You can use this container to create a vector of File_Type objects, for example:
with Ada.Text_IO;
package File_Vectors is
new Charles.Vectors.Limited_Bounded (Ada.Text_IO.File_Type);
V : File_Vectors.Container_Type (N);
...
declare
File : File_Type renames Element (V, Index);
begin
Put (File, "this is a test");
end;
To get a variable view of the object, we have to use the following function.
generic
type Element_Access is access all Element_Type;
function Generic_Element
(Container : access Container_Type;
Index : in Index_Type) return Element_Access;
As above, except that an access value designating the element is returned. This is necessary in order to modify an element object. (The Element function returns a constant view of the object, but at some point you're going to need a variable view.) For example:
V : aliased File_Vectors.Container_Type (N);
...
declare
File : File_Type renames To_Access (V'Access, Index).all;
begin
Create (File, Out_File, "testfile.txt");
end;
This function exists because Ada doesn't have reference types a la C++, so there's no way to have a variable view of an element object except through an access value. Don't keep access objects around. Preferably you shouldn't even declare access objects; instead, just immediately dereference the object returned by the function, as in the example above.
Of course, since the internal container element array is exposed, the procedure in the example could have been written as:
declare
File : File_Type renames V.Elements (Index);
begin
Create (File, Out_File, "testfile.txt");
end;
The only essential difference is that you lose the error checking done automatically by To_Access.
generic
with procedure Swap
(L, R : in out Element_Type) is <>;
procedure Generic_Swap
(Container : in out Container_Type;
Index : in Index_Type;
Item : in out Element_Type);
Exchanges the values of Item and the container element designated by Index, using the generic formal subprogram Swap. If Index does not specify a value in the range Index_Type'First .. Last (Container), then the operation fails and Constraint_Error is raised. Any exceptions raised by Swap are propagated.
generic
with procedure Swap
(L, R : in out Element_Type) is <>;
procedure Generic_Swap_Element
(Container : in out Container_Type;
Left, Right : in Index_Type);
Exchanges the values of the container elements designated by Left and Right, using the generic formal subprogram Swap. If either Left or Right does not specify a value in the range Index_Type'First .. Last (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Swap are propagated.
generic
with procedure Process
(Element : in Element_Type) is <>;
procedure Generic_Select_Element
(Container : in out Container_Type;
Index : in Index_Type);
Applies the generic formal subprogram Process to the container element designated by Index. If Index does not designate a value in the range Index_Type'First .. Last (Container), then the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated.
generic
with procedure Process
(Element : in out Element_Type) is <>;
procedure Generic_Modify_Element
(Container : in out Container_Type;
Index : in Index_Type);
Applies the generic formal subprogram Process to the container element designated by Index. If Index does not designate a value in the range Index_Type'First .. Last (Container), then the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated.
This operation (and others like it) is useful for modifying an element object in-place. For example, if you have a vector whose elements are access values (this example is a bit contrived, since this version of the container is really intended only for limited elements), then you can instantiate Generic_Modify_Element using an instantiation of Unchecked_Deallocation:
package Stream_Class_Access_Vectors is -- from Mesh
new Charles.Vectors.Bounded (Stream_Class_Access);
...
procedure Free is
new Unchecked_Deallocation
(Stream_Type'Class,
Stream_Class_Access);
procedure Free_Stream is
new Generic_Modify_Element (Process => Free);
V : Stream_Class_Access_Vectors.Container_Type (N);
...
for I in First (V) .. Last (V) loop
Free_Stream (V, I);
end loop;
The example above could also be implemented using the passive iterators described below.
generic
with procedure Process
(Element : access Element_Type) is <>;
procedure Generic_Access_Element
(Container : access Container_Type;
Index : in Index_Type);
Applies the generic formal subprogram Process to the container element designated by Index. If Index does not designate a value in the range Index_Type'First .. Last (Container), then the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated.
generic
with procedure Process
(Container : in Container_Type;
Index : in Index_Type) is <>;
procedure Generic_Iteration
(Container : in Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Applies the generic formal subpgram Process to the container elements in the range First .. Index_Type'Pred (Back). If Back <= First, the operation has no effect. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated, immediately terminating the iteration.
The generic formal subprogram has the same signature as the generic applicative operations described earlier. We could re-write the earlier example, replacing the explicit loop with this passive iterator:
package Stream_Class_Access_Vectors is -- from Mesh
new Charles.Vectors.Bounded (Stream_Class_Access);
...
procedure Free is
new Unchecked_Deallocation
(Stream_Type'Class,
Stream_Class_Access);
procedure Free_Stream is
new Generic_Modify_Element (Process => Free);
procedure Free_Streams is
new Generic_Iterator (Process => Free_Stream);
V : Stream_Class_Access_Vectors.Container_Type (N);
...
Free_Streams (V, First (V), Back (V)); -- no loop
The passive iterators described below combine the pair of instantiations in the example.
generic
with procedure Process
(Container : in Container_Type;
Index : in Index_Type) is <>;
procedure Generic_Reverse_Iteration
(Container : in Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Applies the generic formal subpgram Process to the container elements in the range First .. Index_Type'Pred (Back), but in reverse. If Back <= First, the operation has no effect. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated, immediately terminating the iteration.
generic
with procedure Process
(Element : in Element_Type) is <>;
procedure Generic_Select_Elements
(Container : in Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Applies the generic formal subpgram Process to the container elements in the range First .. Index_Type'Pred (Back). If Back <= First, the operation has no effect. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated, immediately terminating the iteration.
generic
with procedure Process
(Element : in out Element_Type) is <>;
procedure Generic_Modify_Elements
(Container : in out Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Equivalent to Generic_Select_Elements, except that the generic formal subprogram Process passes the element as an in-out mode parameter.
We can use this to simplify our earlier example:
package Stream_Class_Access_Vectors is -- from Mesh
new Charles.Vectors.Bounded (Stream_Class_Access);
...
procedure Free is
new Unchecked_Deallocation
(Stream_Type'Class,
Stream_Class_Access);
procedure Free_Streams is
new Generic_Modify_Elements (Process => Free);
V : Stream_Class_Access_Vectors.Container_Type (N);
...
Free_Streams (V, First (V), Back (V)); -- no loop
Note again that passive iterators always accept a half-open range.
generic
with procedure Process
(Element : access Element_Type) is <>;
procedure Generic_Access_Elements
(Container : access Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Equivalent to Generic_Select_Elements, except that the generic formal subprogram Process passes the element as an access parameter.
generic
with procedure Process
(Element : in Element_Type) is <>;
procedure Generic_Reverse_Select_Elements
(Container : in Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Applies the generic formal subpgram Process to the container elements in the range First .. Index_Type'Pred (Back), but in reverse order. If Back <= First, the operation has no effect. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Process are propagated, terminating the iteration.
generic
with procedure Process
(Element : in out Element_Type) is <>;
procedure Generic_Reverse_Modify_Elements
(Container : in out Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Equivalent to Generic_Reverse_Select_Elements, except that the generic formal subprogram Process passes the element as an in-out mode parameter.
generic
with procedure Process
(Element : access Element_Type) is <>;
procedure Generic_Reverse_Access_Elements
(Container : access Container_Type;
First : in Index_Type'Base;
Back : in Index_Type'Base);
Equivalent to Generic_Reverse_Select_Elements, except that the generic formal subprogram Process passes the element as an access parameter.
function Find
(Container : Container_Type;
First : Index_Type'Base;
Back : Index_Type'Base;
Item : Element_Type) return Index_Type'Base;
Searches for the first element in the range First .. Index_Type'Pred (Back) that has same value as Item, using the generic formal equality operator to perform comparisons. If Back <= First, the search terminates immediately and the value Back is returned. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by the equality operator are propagated. If no element compares equal to Item, then Back is returned.
function Find
(Container : Container_Type;
Item : Element_Type) return Index_Type'Base;
Equivalent to Find (Container, First (Container), Back (Container), Item).
generic
with function Predicate (Element : Element_Type)
return Boolean is <>;
function Generic_Find
(Container : Container_Type;
First : Index_Type'Base;
Back : Index_Type'Base) return Index_Type'Base;
Searches for the first element in the range First .. Index_Type'Pred (Back) for which the generic formal Predicate function returns True. If Back <= First, the search terminates immediately and the value Back is returned. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Predicate are propagated. If there is no element for which Predicate returns True, then Back is returned.
function Reverse_Find
(Container : Container_Type;
First : Index_Type'Base;
Back : Index_Type'Base;
Item : Element_Type) return Index_Type'Base;
Searches for the last element in the range First .. Index_Type'Pred (Back) that has same value as Item, using the generic formal equality operator to perform comparisons. If Back <= First, the search terminates immediately and the value Back is returned. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by the equality operator are propagated. If no element compares equal to Item, then Back is returned.
function Reverse_Find
(Container : Container_Type;
Item : Element_Type) return Index_Type'Base;
Equivalent to Reverse_Find (Container, First (Container), Back (Container), Item).
generic
with function Predicate (Element : Element_Type)
return Boolean is <>;
function Generic_Reverse_Find
(Container : Container_Type;
First : Index_Type'Base;
Back : Index_Type'Base) return Index_Type'Base;
Searches for the last element in the range First .. Index_Type'Pred (Back) for which the generic formal Predicate function returns True. If Back <= First, the search terminates immediately and the value Back is returned. Otherwise, if First does not specify a value in the range Index_Type'First .. Last (Container), or Back a value in the range Index_Type'First .. Back (Container), the operation fails and Constraint_Error is raised. Any exceptions raised by Predicate are propagated. If there is no element for which Predicate returns True, then Back is returned.