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 unbounded, which means (here) that the size of the internal array can be resized (although not automatically). (There is a complementary bounded form, which fixes the size of the internal array.) This container can 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;
type Element_Array_Access is access all Element_Array_Type;
type Container_Type is limited private;
The container type for unbounded vectors.
This specification guarantees that Container_Type
is a pass-by-reference type.
In this implementation,
the vector type privately derives from Controlled,
extending it with a record containing an access object designating an unbounded
array of Element_Type, and a count of
the number of active elements.
This implementation also guarantees that there is no cost for simply declaring
a vector object, in the sense that no memory is dynamically allocated during initialization.
Specifically, the size of a default-initialized vector is 0.
Because elements are limited, the internal array does not automatically resize, and the client must explicitly specify the size before using the vector. The Assign or Resize operations can be used to grow the array, and "swap trick" (described below) can be used to shrink it.
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.
(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 To_Access (Container : Container_Type) return Element_Array_Access;
The function To_Access returns an access object that designates the current internal array. This specification guarantees that if the access object is not null, then the array object it designates has an index subtype whose range starts with the value Index_Type'First.
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 unconstrained array whose length can vary. It is often that case we need to view the vector as contiguous array of elements, and the To_Access function exists to support this latter view.
When a vector object is declared, no internal memory is allocated, which means that To_Access can return a null access value. (I would prefer to initialize a vector by designating a statically-allocated zero-length array, but for subtle language reasons having to do with whether an unconstrained array object has dope, I cannot do this.) So when dereferencing the value returned by To_Access, you must be careful.
The only way to clear out the internal array is by using Swap, to replace the internal array with that of another vector, whose own access object is null. (The internal access object is also set to null under certain pathological conditions, such as when an exception is raised when Free'ing the internal array.) So unless you take explicit action, once there is an internal array, then there will always be an internal array. (And again, remember that of course the internal array object can change because of automatic and manual reallocation.)
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.) Because this vector does not automatically resize, there is a "current" maximum length, equal to the size of the array.
function Is_Empty (Container : Container_Type)
return Boolean;
Equivalent to Length (Container) = 0.
procedure Clear (Container : in out Container_Type);
This operation sets the length to 0, thus "removing" all the elements in the container.
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;
...
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].
Note also that Clear doesn't actually deallocate the internal array -- it merely adjusts the element count. To deallocate the array you can use the swap trick described below.
procedure Swap (Left, Right : in out Container_Type);
Exchanges the internal array and element count of the Left vector with that of the Right vector. Elements that were in the Left vector are now in the Right vector, and vice versa. The time complexity of this operation is O(1).
You can use Resize to manipulate the size of the internal array,
but if the requested size is smaller than the actual size,
that operation no effect.
To shrink the array, you can use the swap trick:
V : Vector_Subtype;
...
declare
Temp : Vector_Subtype;
begin
Swap (V, Temp);
end;
In the example above, as a result of the swap Temp has the internal array that formerly belonged to V, and the internal array of V is null. When the scope of Temp ends, Temp is finalized, which deallocates the array. This has the same effect as Clear, but also ensures that the internal array is deallocated.
procedure Assign
(Target : in out Container_Type;
Length : in Natural);
If the current size of the internal array is smaller than the requested size, this operation sets the vector length to the indicated value. Otherwise, a new array is allocated having at least the length specified. Storage_Error is propagated if allocation fails; the state of the container object is not changed.
Assign is an important alternative to Resize, because Assign will unconditionally increase the size of the internal array as necessary. This is not true for Resize, which only conditionally allocates a new internal array. There is the additional difference that Assign changes the (logical) length of the vector (and the (physical) size if necessary), but Resize only changes the size, never the length.
Assign is very similar to Clear, in the sense that it simply modifies the internal length component of the container record type (unless allocation of the internal array is required). It is up to you to either finalize or initialize the elements as necessary either preceeding or following the Assign. If the elements are controlled, finalization will occur automatically as a side effect of deallocation (assuming a new internal array needs to be allocated).
If you want to guarantee that a "fresh" array is allocated (and hence, that the existing array is deallocated), use the swap trick:
V : Vector_Subtype;
...
declare
Temp : Vector_Subtype;
begin
Swap (V, Temp);
end;
Assign (V, Length => N);
In the example, the Swap with a temporary forces the existing array
to be deallocated.
The post-swap vector now has length of 0, but the Assign is then used to allocate a new array
and update the vector length.
If the element type is controlled (the vector has no way of knowing),
these kinds of tricks might be simpler than manually finalizing and initializing array elements
(but of course it means reallocation must also occur).
procedure Push_Back
(Container : in out Container_Type);
If the length of the vector is equal to the size, the operation fails and Constraint_Error is raised. Otherwise, it increments the vector length by 1.
This operation opens up a single "slot" at the back of the vector, so you can then 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;
Note that the behavior of Push_Back for this limited unbounded form is different from the nonlimited unbounded form. The latter will automatically resize the internal array if it isn't large enough to contain the new item, and copy the existing elements onto the new array. For the former this is impossible, because assignment of the elements isn't available. If you do need to grow the internal array, then you can declare a temporary vector with the required size, copy the existing elements (by whatever mechanism is available for the limited elements), and then swap the two vectors:
V : Vector_Subtype;
procedure Add (Item : Element_Subtype) is
begin
if Length (V) = Size (V) then
declare
Temp : Vector_Subtype;
begin
Assign (Temp, Length => Length (V) + 1);
for I in First (V) .. Last (V) loop
--copy V (I) to Temp (I)
end loop;
Swap (Temp, V);
end;
else
Push_Back (V);
end if;
declare
Last_Element : Element_Type renames
To_Access (V, Last (V).all;
begin
--copy Item to Last_Element
end;
end Add;
In the example, we could also have used Resize immediately prior to Assign in order to more directly control the size of the internal array. This would be useful if we know in advance the ultimate size of the internal array, or we anticipate repeated use of Push_Back.
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.
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;
...
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;
...
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?) Otherwise it decrements the vector length by Count.
function Size (Container : Container_Type) return Natural;
Returns the length of the internal array. (This is the physical length of the internal array. Contrast this with function Length, which returns the logical length of the vector.)
procedure Resize
(Container : in out Container_Type;
Size : in Natural);
If no internal array has been allocated, a new array is allocated having indicated length. Otherwise, if the container isn't empty, or the existing size is greater than the indicated size, then the operation has no effect. If none of these other conditions apply, then it deallocates the existing array, and allocates a new array having at least the size specified. If the allocation fails, Storage_Error is propagated.
A vector object is default-initialized to a zero size, which means before you can store elements in the container you must (re)size it first. As an example, post-elaboration initialization of a statically-declared vector object could be done like this:
package body P is
V : Vector_Subtype;
procedure Initialize (N : Positive) is
begin
Resize (V, Size => N);
...
end Initialize;
...
end P;
See the description of Assign for more information.
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_Unbounded (Ada.Text_IO.File_Type);
V : File_Vectors.Container_Type;
...
declare
File : File_Type renames Element (V, Index);
begin
Put (File, "this is a test");
end;
generic
type Element_Access is access all Element_Type;
function Generic_Element
(Container : Container_Type;
Index : 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 : File_Vectors.Container_Type;
function To_Access is new Generic_Element (File_Access);
...
declare
File : File_Type renames To_Access (V, 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 refer to 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.
An alternative way to implement the algorithm above is to use the To_Access function that returns a pointer to the internal array:
declare
File : File_Type renames To_Access (V)(Index);
begin
Create (File, Out_File, "testfile.txt");
end;
The only essential difference is that you lose the error checking that Generic_Element provides automatically.
generic
with procedure Swap
(L, R : in out Element_Type) is <>;
procedure Generic_Swap
(Container : in 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 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 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 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, then you can instantiate Generic_Modify_Element using an instantiation of Unchecked_Deallocation:
package Stream_Class_Access_Vectors is -- from Mesh
new Charles.Vectors.Unbounded (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;
...
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 : in 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, 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.Unbounded (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;
...
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, 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, terminating the iteration.
generic
with procedure Process
(Element : in out Element_Type) is <>;
procedure Generic_Modify_Elements
(Container : in 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.Unbounded (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;
...
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 : in 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 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 : in 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.