A.18.3 The Generic Package Containers.Doubly_Linked_Lists
1/2
{
AI95-00302-03}
The language-defined generic package Containers.Doubly_Linked_Lists
provides private types List and Cursor, and a set of operations for each
type. A list container is optimized for insertion and deletion at any
position. 2/2
{
AI95-00302-03}
A doubly-linked list container
object manages a linked list of internal nodes, each of which
contains an element and pointers to the next (successor) and previous
(predecessor) internal nodes. A cursor designates a particular node within
a list (and by extension the element contained in that node). A cursor
keeps designating the same node (and element) as long as the node is
part of the container, even if the node is moved in the container.3/2
{
AI95-00302-03}
The length of a list is the number of elements
it contains.Static Semantics
4/2
{
AI95-00302-03}
The generic library package Containers.Doubly_Linked_Lists
has the following declaration: 5/3
{
AI05-0084-1}
{
AI05-0212-1}
with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists is
pragma Preelaborate(Doubly_Linked_Lists);
pragma Remote_Types(Doubly_Linked_Lists);6/3
{
AI05-0212-1}
type List is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(List);7/2
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
8/2
Empty_List : constant List;
9/2
No_Element : constant Cursor;
9.1/3
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;9.2/3
{
AI05-0212-1}
package List_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);10/2
function "=" (Left, Right : List) return Boolean;
11/2
function Length (Container : List) return Count_Type;
12/2
function Is_Empty (Container : List) return Boolean;
13/2
procedure Clear (Container : in out List);
14/2
function Element (Position : Cursor)
return Element_Type;
15/2
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
16/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
17/2
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
17.1/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;17.2/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;17.3/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type;17.4/3
{
AI05-0212-1}
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type;17.5/3
{
AI05-0001-1}
procedure Assign (Target : in out List; Source : in List);17.6/3
{
AI05-0001-1}
function Copy (Source : List) return List;18/2
procedure Move (Target : in out List;
Source : in out List);
19/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
20/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
21/2
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
22/2
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
23/2
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
24/2
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
25/2
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
26/2
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
27/2
procedure Reverse_Elements (Container : in out List);
28/2
procedure Swap (Container : in out List;
I, J : in Cursor);
29/2
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
30/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
31/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
32/2
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
33/2
function First (Container : List) return Cursor;
34/2
function First_Element (Container : List)
return Element_Type;
35/2
function Last (Container : List) return Cursor;
36/2
function Last_Element (Container : List)
return Element_Type;
37/2
function Next (Position : Cursor) return Cursor;
38/2
function Previous (Position : Cursor) return Cursor;
39/2
procedure Next (Position : in out Cursor);
40/2
procedure Previous (Position : in out Cursor);
41/2
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
42/2
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
43/2
function Contains (Container : List;
Item : Element_Type) return Boolean;
44/3
This paragraph
was deleted. {
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;
45/2
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
46/2
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
46.1/3
{
AI05-0212-1}
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;46.2/3
{
AI05-0212-1}
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class;47/2
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting is
48/2
function Is_Sorted (Container : List) return Boolean;
49/2
procedure Sort (Container : in out List);
50/2
procedure Merge (Target : in out List;
Source : in out List);
51/2
end Generic_Sorting;
52/2
private
53/2
... -- not specified by the language
54/2
end Ada.Containers.Doubly_Linked_Lists;
55/2
{
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 Find, Reverse_Find, and "=" on
list values return an unspecified value. The exact arguments and number
of calls of this generic formal function by the functions Find, Reverse_Find,
and "=" on list values are unspecified.55.a/2
Ramification: If
the actual function for "=" is not symmetric and consistent,
the result returned by the listed functions cannot be predicted. The
implementation is not required to protect against "=" raising
an exception, or returning random results, or any other “bad”
behavior. And it can call "=" in whatever manner makes sense.
But note that only the results of Find, Reverse_Find, and List "="
are unspecified; other subprograms are not allowed to break if "="
is bad (they aren't expected to use "=").
56/2
{
AI95-00302-03}
The type List is used to represent lists. The type
List needs finalization (see 7.6).57/2
{
AI95-00302-03}
Empty_List represents the empty List object. It
has a length of 0. If an object of type List is not otherwise initialized,
it is initialized to the same value as Empty_List.58/2
{
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.59/2
{
AI95-00302-03}
The predefined "=" operator for type
Cursor returns True if both cursors are No_Element, or designate the
same element in the same container.60/2
{
AI95-00302-03}
Execution of the default implementation of the
Input, Output, Read, or Write attribute of type Cursor raises Program_Error.60.a/2
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.
60.1/3
{
AI05-0001-1}
{
AI05-0262-1}
List'Write writes exactly Length(List) elements
of the list to the stream. It may write additional information about
the list as well. List'Read reads exactly Length(List) elements of List
from the stream and consumes any additional information written by List'Write.60.b/3
Ramification: Streaming
more elements than the container length is wrong. For implementation
implications of this rule, see the Implementation Note in A.18.2.
61/2
{
AI95-00302-03}
[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.]62/2
{
AI95-00302-03}
A subprogram is said to tamper
with cursors of a list object L if:63/2
it inserts or deletes elements
of L, that is, it calls the Insert, Clear, Delete, or Delete_Last
procedures with L as a parameter; or
63.a/2
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.
64/2
it reorders the elements
of L, that is, it calls the Splice, Swap_Links, or Reverse_Elements
procedures or the Sort or Merge procedures of an instance of Generic_Sorting
with L as a parameter; or
65/2
it finalizes L; or
65.1/3
{
AI05-0001-1}
it calls the Assign procedure with L as
the Target parameter; or66/2
it calls the Move procedure
with L as a parameter.
66.a/2
Reason: Swap copies
elements rather than reordering them, so it doesn't tamper with cursors.
67/2
{
AI95-00302-03}
A subprogram is said to tamper
with elements of a list object L if:68/2
it tampers with cursors of
L; or
69/2
it replaces one or more elements
of L, that is, it calls the Replace_Element or Swap procedures
with L as a parameter.
69.a/2
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.
69.1/3
{
AI05-0265-1}
If tampering
with cursors is prohibited for a particular list object L,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the cursors of L. Similarly, if tampering
with elements is prohibited for a particular list object L,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the elements of L.69.2/3
function Has_Element (Position : Cursor) return Boolean;
69.3/3
{
AI05-0212-1}
Returns True if Position designates an element,
and returns False otherwise.69.b/3
To be honest: This
function may 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).
70/2
function "=" (Left, Right : List) return Boolean;
71/3
{
AI95-00302-03}
{
AI05-0264-1}
If Left and Right denote the same list object,
then the function returns True. If Left and Right have different lengths,
then the function returns False. Otherwise, it compares each element
in Left to the corresponding element in Right using the generic formal
equality operator. If any such comparison returns False, the function
returns False; otherwise, it returns True. Any exception raised during evaluation of element equality
is propagated. 71.a/2
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.
72/2
function Length (Container : List) return Count_Type;
73/2
74/2
function Is_Empty (Container : List) return Boolean;
75/2
76/2
procedure Clear (Container : in out List);
77/2
78/2
function Element (Position : Cursor) return Element_Type;
79/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Element returns the element designated by Position.80/2
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
81/3
{
AI95-00302-03}
{
AI05-0264-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 the value New_Item to the element designated
by Position.82/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
83/3
{
AI95-00302-03}
{
AI05-0021-1}
{
AI05-0265-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 Program_Error
is propagated if Process.all tampers with the elements of the list that contains
the element designated by Position is prohibited during the execution
of Process.all Container.
Any exception raised by Process.all is propagated.84/2
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
85/3
{
AI95-00302-03}
{
AI05-0264-1}
{
AI05-0265-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 Program_Error
is propagated if Process.all tampers with the elements of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.86/2
If
Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
86.a/2
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.
86.1/3
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
86.2/3
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
86.3/3
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type
need finalization.86.4/3
The default initialization
of an object of type Constant_Reference_Type or Reference_Type propagates
Program_Error.
86.b/3
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.
86.5/3
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type;
86.6/3
{
AI05-0212-1}
This function (combined with the Constant_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
access to the individual elements of a container starting with a cursor.86.7/3
{
AI05-0212-1}
{
AI05-0265-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.86.8/3
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type;
86.9/3
{
AI05-0212-1}
This function (combined with the Variable_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
and write access to the individual elements of a container starting with
a cursor.86.10/3
{
AI05-0212-1}
{
AI05-0265-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.86.11/3
procedure Assign (Target : in out List;
Source : in List);
86.12/3
{
AI05-0001-1}
{
AI05-0248-1}
If Target denotes the same object as Source, the
operation has no effect. Otherwise, the elements of Source are copied
to Target as for an assignment_statement
assigning Source to Target. 86.c/3
Discussion: {
AI05-0005-1}
This routine exists for compatibility with the
bounded list container. For an unbounded list, Assign(A, B)
and A := B behave identically. For a bounded list, := will raise
an exception if the container capacities are different, while Assign
will not raise an exception if there is enough room in the target.
86.13/3
function Copy (Source : List) return List;
86.14/3
{
AI05-0001-1}
Returns a list whose elements match the elements
of Source.87/2
procedure Move (Target : in out List;
Source : in out List);
88/3
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0248-1}
{
AI05-0262-1}
If Target denotes the same object as Source, then
the operation Move has no effect. Otherwise, the operation
is equivalent to Assign (Target, Source) followed by Clear (Source) Move
first calls Clear (Target). Then, the nodes in Source are moved to Target
(in the original order). The length of Target is set to the length of
Source, and the length of Source is set to 0.89/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
90/2
{
AI95-00302-03}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
Insert inserts Count copies of New_Item prior to the element designated
by Before. If Before equals No_Element, the new elements are inserted
after the last node (if any). Any exception raised during allocation
of internal storage is propagated, and Container is not modified.90.a/2
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).
91/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
92/3
{
AI95-00302-03}
{
AI05-0257-1}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
Insert allocates Count copies of New_Item, and inserts them prior to
the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last element (if any). Position designates
the first newly-inserted element, or if
Count equals 0, then Position is assigned the value of Before.
Any exception raised during allocation of internal storage is propagated,
and Container is not modified.93/2
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
94/3
{
AI95-00302-03}
{
AI05-0257-1}
If Before is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Otherwise,
Insert inserts Count new elements prior to the element designated by
Before. If Before equals No_Element, the new elements are inserted after
the last node (if any). The new elements are initialized by default (see
3.3.1). Position
designates the first newly-inserted element, or if Count equals 0, then
Position is assigned the value of Before.
Any exception raised during allocation of internal storage is propagated,
and Container is not modified.95/2
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
96/2
{
AI95-00302-03}
Equivalent to Insert (Container, First (Container),
New_Item, Count).97/2
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
98/2
{
AI95-00302-03}
Equivalent to Insert (Container, No_Element, New_Item,
Count).99/2
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
100/3
{
AI95-00302-03}
{
AI05-0264-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 removes (from Container) Count elements starting at the element
designated by Position (or all of the elements starting at Position if
there are fewer than Count elements starting at Position). Finally, Position
is set to No_Element.101/2
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
102/3
{
AI95-00302-03}
{
AI05-0021-1}
If Length (Container)
<= Count, then Delete_First is equivalent to Clear (Container). Otherwise,
it removes the first Count nodes from Container Equivelent
to Delete (Container, First (Container), Count).103/2
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
104/3
{
AI95-00302-03}
{
AI05-0264-1}
If Length (Container) <= Count, then Delete_Last is equivalent to Clear (Container). Otherwise, it removes the last Count nodes from Container.105/2
procedure Reverse_Elements (Container : in out List);
106/2
{
AI95-00302-03}
Reorders the elements of Container in reverse order.106.a/2
Discussion: Unlike
the similar routine for a vector, elements should not be copied; rather,
the nodes should be exchanged. Cursors are expected to reference the
same elements afterwards.
107/2
procedure Swap (Container : in out List;
I, J : in Cursor);
108/2
{
AI95-00302-03}
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.108.a/2
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.
108.b/2
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.
109/2
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
110/2
{
AI95-00302-03}
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_Links exchanges the
nodes designated by I and J.110.a/2
Ramification: Unlike
Swap, this exchanges the nodes, not the elements. No copying is performed.
I and J designate the same elements after this call as they did before
it. This operation can provide better performance than Swap if the element
size is large.
111/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
112/2
{
AI95-00302-03}
If Before is not No_Element, and does not designate
an element in Target, then Program_Error is propagated. Otherwise, if
Source denotes the same object as Target, the operation has no effect.
Otherwise, Splice reorders elements such that they are removed from Source
and moved to Target, immediately prior to Before. If Before equals No_Element,
the nodes of Source are spliced after the last node of Target. The length
of Target is incremented by the number of nodes in Source, and the length
of Source is set to 0.113/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
114/3
{
AI95-00302-03}
{
AI05-0264-1}
If Position is No_Element, then Constraint_Error is propagated. If Before does not equal No_Element,
and does not designate an element in Target, then Program_Error is propagated.
If Position does not equal No_Element, and does not designate a node
in Source, then Program_Error is propagated. If Source denotes the same
object as Target, then there is no effect if Position equals Before,
else the element designated by Position is moved immediately prior to
Before, or, if Before equals No_Element, after the last element. In both
cases, Position and the length of Target are unchanged. Otherwise, the element designated by Position is removed from Source and moved to
Target, immediately prior to Before, or, if Before equals No_Element,
after the last element of Target. The length of Target is incremented,
the length of Source is decremented, and Position is updated to represent
an element in Target. 114.a/2
Ramification: If
Source is the same as Target, and Position = Before, or Next(Position)
= Before, Splice has no effect, as the element does not have to move
to meet the postcondition.
115/2
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
116/3
{
AI95-00302-03}
{
AI05-0264-1}
If Position is No_Element, then Constraint_Error is propagated. If Before does not equal No_Element,
and does not designate an element in Container, then Program_Error is
propagated. If Position does not equal No_Element, and does not designate
a node in Container, then Program_Error is propagated. If Position equals
Before there is no effect. Otherwise, the element designated by Position
is moved immediately prior to Before, or, if Before equals No_Element,
after the last element. The length of Container is unchanged.117/2
function First (Container : List) return Cursor;
118/3
{
AI95-00302-03}
{
AI05-0264-1}
If Container is empty, First returns the value
No_Element. Otherwise, it returns a cursor that designates the first node in Container.119/2
function First_Element (Container : List) return Element_Type;
120/2
121/2
function Last (Container : List) return Cursor;
122/3
{
AI95-00302-03}
{
AI05-0264-1}
If Container is empty, Last returns the value No_Element.
Otherwise, it returns a cursor that designates the last node in Container.123/2
function Last_Element (Container : List) return Element_Type;
124/2
125/2
function Next (Position : Cursor) return Cursor;
126/2
{
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 successor of the element
designated by Position.127/2
function Previous (Position : Cursor) return Cursor;
128/2
{
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 predecessor of the
element designated by Position.129/2
procedure Next (Position : in out Cursor);
130/2
131/2
procedure Previous (Position : in out Cursor);
132/2
133/2
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
134/2
{
AI95-00302-03}
If Position is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Find searches
the elements of Container for an element equal to Item (using the generic
formal equality operator). The search starts at the element designated
by Position, or at the first element if Position equals No_Element. It
proceeds towards Last (Container). If no equal element is found, then
Find returns No_Element. Otherwise, it returns a cursor designating the
first equal element encountered.135/2
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
136/2
{
AI95-00302-03}
If Position is not No_Element, and does not designate
an element in Container, then Program_Error is propagated. Find searches
the elements of Container for an element equal to Item (using the generic
formal equality operator). The search starts at the element designated
by Position, or at the last element if Position equals No_Element. It
proceeds towards First (Container). If no equal element is found, then
Reverse_Find returns No_Element. Otherwise, it returns a cursor designating
the first equal element encountered.137/2
function Contains (Container : List;
Item : Element_Type) return Boolean;
138/2
{
AI95-00302-03}
Equivalent to Find (Container, Item) /= No_Element.139/3
function Has_Element (Position : Cursor) return Boolean;
140/3
140.a/3
To be honest: {
AI05-0212-1}
This
function may 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).
Paragraphs
139 and 140 were moved above.
141/2
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
142/3
{
AI95-00302-03}
{
AI05-0265-1}
Iterate calls Process.all with a cursor
that designates each node in Container, starting with the first node
and moving the cursor as per the Next function. Tampering Program_Error
is propagated if Process.all tampers with the cursors of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.142.a/2
Implementation Note:
The purpose of the tamper with cursors check is to prevent erroneous
execution from the Position parameter of Process.all becoming
invalid. This check takes place when the operations that tamper with
the cursors of the container are called. The check cannot be made later
(say in the body of Iterate), because that could cause the Position cursor
to be invalid and potentially cause execution to become erroneous --
defeating the purpose of the check.
142.b/2
See Iterate for vectors
(A.18.2) for a suggested implementation
of the check.
143/2
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
144/3
{
AI95-00302-03}
{
AI05-0212-1}
Iterates over the nodes in Container as per procedure
Iterate, except that elements are traversed
in reverse order, starting with the last node and moving the cursor as
per the Previous function.144.1/3
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
144.2/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns a reversible iterator object that
will generate a value for the loop parameter 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. 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.144.3/3
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
144.4/3
{
AI05-0212-1}
{
AI05-0265-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,
the call is equivalent to Iterate (Container). Otherwise, Iterate returns
a reversible iterator object that will generate a value for the loop
parameter 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.144.a/3
Discussion:
Exits are allowed from the loops created using the iterator objects.
In particular, to stop the iteration at a particular cursor, just add
144.b/3
exit when Cur = Stop;
144.c/3
in
the body of the loop (assuming the Cur is the loop parameter
and Stop is the cursor that you want to stop at).
145/3
{
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),
that is, be irreflexive, asymmetric, and transitive;
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 How
many times the subprograms of Generic_Sorting
call "<" is unspecified.146/2
function Is_Sorted (Container : List) return Boolean;
147/2
{
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.148/2
procedure Sort (Container : in out List);
149/2
{
AI95-00302-03}
Reorders the nodes of Container such that the elements
are sorted smallest first as determined by the generic formal "<"
operator provided. The sort is stable. Any exception raised during evaluation
of "<" is propagated.149.a/2
Ramification: Unlike
array sorts, we do require stable sorts here. That's because algorithms
in the merge sort family (as described by Knuth) can be both fast and
stable. Such sorts use the extra memory as offered by the links to provide
better performance.
149.b/2
Note that list sorts never
copy elements; it is the nodes, not the elements, that are reordered.
150/2
procedure Merge (Target : in out List;
Source : in out List);
151/3
{
AI95-00302-03}
{
AI05-0021-1}
If Source is empty,
then Merge does nothing. If Source and Target are the same non-empty
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.151.a/2
Ramification: It
is a bounded error if either of the lists is unsorted, see below. The
bounded error can be recovered by sorting Target after the merge call,
or the lists can be pretested with Is_Sorted.
Bounded (Run-Time) Errors
152/2
{
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.152.1/3
{
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
List parameter of the operation. Either Program_Error is raised, or the
operation works as defined on the value of the List either prior to,
or subsequent to, some or all of the modifications to the List.152.2/3
{
AI05-0027-1}
It is a bounded error to call
any subprogram declared in the visible part of Containers.Doubly_Linked_List
when the associated container has been finalized. If the operation takes
Container as an in out parameter, then it raises Constraint_Error
or Program_Error. Otherwise, the operation either proceeds as it would
for an empty container, or it raises Constraint_Error or Program_Error.
Erroneous Execution
153/2
{
AI95-00302-03}
A Cursor value is invalid if any of the
following have occurred since it was created: 154/2
The list that contains the
element it designates has been finalized;
154.1/3
{
AI05-0160-1}
The list that contains the element it designates
has been used as the Target of a call to Assign, or as the target of
an assignment_statement;155/2
[The list that contains the
element it designates has been used as the Source or Target of a call
to Move;] or
155.a/3
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.
156/3
{
AI05-0160-1}
{
AI05-0262-1}
The element it designates has been removed
from the list that previously contained the element deleted.
156.a/3
To be honest: {
AI05-0160-1}
The cursor modified by the four parameter Splice
is not invalid, even though the element it designates has been removed
from the source list, because that cursor has been modified to designate
that element in the target list – the cursor no longer designates
an element in the source list.
156.b/3
Ramification: {
AI05-0160-1}
This can happen directly via calls to Delete, Delete_Last,
Clear, Splice with a Source parameter, and Merge; and indirectly via
calls to Delete_First, Assign, and Move.
157/2
{
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.Doubly_Linked_Lists is
called with an invalid cursor parameter. 157.a/2
Discussion: The
list above is intended to be exhaustive. In other cases, a cursor value
continues to designate its original element. For instance, cursor values
survive the insertion and deletion of other nodes.
157.b/2
While it is possible to
check for these cases, in many cases the overhead necessary to make the
check is substantial in time or space. Implementations are encouraged
to check for as many of these cases as possible and raise Program_Error
if detected.
157.1/3
{
AI05-0212-1}
Execution is erroneous if the list associated with
the result of a call to Reference or Constant_Reference is finalized
before the result object returned by the call to Reference or Constant_Reference
is finalized. 157.c/3
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 non-existent object. This is a normal case of a
dangling pointer created by Unchecked_Deallocation; we have to explicitly
mention it here as the pointer in question is not visible in the specification
of the type. (This is the same reason we have to say this for invalid
cursors.)
Implementation Requirements
158/2
{
AI95-00302-03}
No storage associated with a doubly-linked List
object shall be lost upon assignment or scope exit.159/3
{
AI95-00302-03}
{
AI05-0262-1}
The execution of an assignment_statement
for a list shall have the effect of copying the elements from the source
list object to the target list object and
changing the length of the target object to that of the source object.159.a/2
Implementation Note:
An assignment of a List is a “deep” copy; that is the
elements are copied as well as the data structures. We say “effect
of” in order to allow the implementation to avoid copying elements
immediately if it wishes. For instance, an implementation that avoided
copying until one of the containers is modified would be allowed.
Implementation Advice
160/2
{
AI95-00302-03}
Containers.Doubly_Linked_Lists should be implemented
similarly to a linked list. In particular, if N is the length
of a list, then the worst-case time complexity of Element, Insert with
Count=1, and Delete with Count=1 should be O(log N).
160.a/2
Implementation Advice:
The worst-case time complexity of Element,
Insert with Count=1, and Delete with Count=1 for Containers.Doubly_Linked_Lists
should be O(log N).
160.b/2
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 lists are large. We
allow O(log N) access because the proportionality constant
and caching effects are likely to be larger than the log factor, and
we don't want to discourage innovative implementations.
161/2
{
AI95-00302-03}
The worst-case time complexity of a call on procedure
Sort of an instance of Containers.Doubly_Linked_Lists.Generic_Sorting
should be O(N**2), and the average time complexity should
be better than O(N**2). 161.a/2
Implementation Advice:
A call on procedure Sort of an instance
of Containers.Doubly_Linked_Lists.Generic_Sorting should have an average
time complexity better than O(N**2) and worst case no worse
than O(N**2).
161.b/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!
162/2
{
AI95-00302-03}
Move should not copy elements, and should minimize
copying of internal data structures. 162.a/2
Implementation Advice:
Containers.Doubly_Linked_Lists.Move
should not copy elements, and should minimize copying of internal data
structures.
162.b/2
Implementation Note:
Usually that can be accomplished simply by moving the pointer(s)
to the internal data structures from the Source container to the Target
container.
163/2
{
AI95-00302-03}
If an exception is propagated from a list operation,
no storage should be lost, nor any elements removed from a list unless
specified by the operation. 163.a/2
Implementation Advice:
If an exception is propagated from a
list operation, no storage should be lost, nor any elements removed from
a list unless specified by the operation.
163.b/2
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.
164/2
50 {
AI95-00302-03}
Sorting a list never copies elements, and is a
stable sort (equal elements remain in the original order). This is different
than sorting an array or vector, which may need to copy elements, and
is probably not a stable sort. Extensions to Ada 95
164.a/2
{
AI95-00302-03}
The generic package Containers.Doubly_Linked_Lists
is new. Inconsistencies With Ada 2005
164.b/3
{
AI05-0248-1}
{
AI05-0257-1}
Correction: The Insert
versions that return a Position parameter are now defined to return Position
= Before if Count = 0. This was unspecified for Ada 2005; so this will
only be inconsistent if an implementation did something else and a program
depended on that something else — this should be very rare.
Incompatibilities With Ada 2005
164.c/3
{
AI05-0001-1}
Subprograms Assign and Copy
are newly added to Containers.Doubly_Linked_Lists. If an instance of
Containers.Doubly_Linked_Lists is referenced in a use_clause,
and an entity E with the same defining_identifier
as a new entity in Containers.Doubly_Linked_Lists 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
164.d/3
{
AI05-0212-1}
Added iterator, reference,
and indexing support to make list containers more convenient to use.
Wording Changes from Ada 2005
164.e/3
{
AI05-0001-1}
Generalized the definition of Move. Specified which
elements are read/written by stream attributes.164.f/3
{
AI05-0022-1}
Correction: Added a Bounded (Run-Time) Error
to cover tampering by generic actual subprograms.164.g/3
{
AI05-0027-1}
Correction: Added a Bounded (Run-Time) Error
to cover access to finalized list containers.164.h/3
{
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.164.i/3
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.164.j/3
{
AI05-0160-1}
Correction: Revised the definition of invalid
cursors to cover missing (and new) cases.164.k/3
{
AI05-0257-1}
Correction: Added missing wording to describe
the Position after Inserting 0 elements.164.l/3
{
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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
