Contents Index Search Related Documents Previous Next
A.18.3 The Package Containers.Doubly_Linked_Lists
1/2
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
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
The
length of a list is the number of
elements it contains.
Static Semantics
4/2
The generic library
package Containers.Doubly_Linked_Lists has the following declaration:
5/2
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);
6/2
type List is tagged private;
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;
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));
18/2
procedure Move (Target : in out List;
Source : in out List);
19/2
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
20/2
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
21/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
22/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
23/2
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
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 out 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 Contains (Container : List;
Item : Element_Type) return Boolean;
38/2
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
39/2
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
40/2
function Next (Position : Cursor) return Cursor;
41/2
function Previous (Position : Cursor) return Cursor;
42/2
procedure Next (Position : in out Cursor);
43/2
procedure Previous (Position : in out Cursor);
44/2
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));
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
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.
56/2
The type List is used to represent lists. The
type List needs finalization (see
7.6).
57/2
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
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
The predefined "=" operator for type
Cursor should return True if both cursors or No_Element, or designate
the same element in the same container.
60/2
Execution of the default implementation of
the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
61/2
Some
operations are assumed to work on a constant set of elements. During
the execution of such an operation, a subprogram is said to
tamper
with cursors of a list object
L if:
62/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/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
64/2
65/2
- it calls the Move procedure with L
as a parameter.
66/2
Some
operations are assumed to not replace elements. During the execution
of such an operation, a subprogram is said to
tamper with elements
of a list object
L if:
67/2
- it tampers with cursors of L;
or
68/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/2
function "=" (Left, Right : List) return Boolean;
70/2
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 element equality returns
False, then the function returns False. If the function has not returned
a result after checking all of the elements, it returns True. Any exception
raised during evaluation of element equality is propagated.
71/2
function Length (Container : List) return Count_Type;
72/2
Returns the number
of elements in Container.
73/2
function Is_Empty (Container : List) return Boolean;
74/2
Equivalent to
Length (Container) = 0.
75/2
procedure Clear (Container : in out List);
76/2
Removes all the
elements from Container.
77/2
function Element (Position : Cursor) return Element_Type;
78/2
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, Element returns
the element designated by Position.
79/2
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
80/2
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.
81/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
82/2
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. Program_Error is propagated if Process.all tampers with
the elements of Container. Any exception raised by Process.all
is propagated.
83/2
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
84/2
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. Program_Error
is propagated if Process.all tampers with the elements of Container.
Any exception raised by Process.all is propagated.
85/2
If Element_Type
is unconstrained and definite, then the Element parameter of Process.all
shall be unconstrained.
86/2
procedure Move (Target : in out List;
Source : in out List);
87/2
If Target denotes
the same object as Source, then Move has no effect. Otherwise, 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.
88/2
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
89/2
Equivalent to
Insert (Container, First (Container), New_Item, Count).
90/2
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
91/2
Equivalent to
Insert (Container, No_Element, New_Item, Count).
92/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
93/2
If Before is
not No_Element, and does not designate an element in Target, 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.
94/2
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
95/2
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.
Any exception raised during allocation of internal storage is propagated,
and Container is not modified.
96/2
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
97/2
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). Any
exception raised during allocation of internal storage is propagated,
and Container is not modified.
98/2
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
99/2
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.
100/2
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
101/2
Equivalent to
Delete (Container, First (Container), Count).
102/2
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
103/2
If Length (Container)
<= Count then Delete_Last is equivalent to Clear (Container). Otherwise
it removes the last Count nodes from Container.
104/2
procedure Reverse_Elements (Container : in out List);
105/2
Reorders the
elements of Container in reverse order.
106/2
procedure Swap (Container : in out List;
I, J : in Cursor);
107/2
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/2
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
109/2
If either I or
J is No_Element, then Constraint_Error is propagated. If 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/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
111/2
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.
112/2
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
113/2
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.
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/2
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in out Cursor);
115/2
Equivalent to
Splice (Target => Container, Before => Before, Source => Container,
Position => Position);
116/2
function First (Container : List) return Cursor;
117/2
If Container
is empty, First returns the value No_Element. Otherwise it returns a
cursor that designates the first node in Container.
118/2
function First_Element (Container : List) return Element_Type;
119/2
Equivalent to
Element (First (Container)).
120/2
function Last (Container : List) return Cursor;
121/2
If Container
is empty, Last returns the value No_Element. Otherwise it returns a cursor
that designates the last node in Container.
122/2
function Last_Element (Container : List) return Element_Type;
123/2
Equivalent to
Element (Last (Container)).
124/2
function Contains (Container : List;
Item : Element_Type) return Boolean;
125/2
Equivalent to
Find (Container, Item) /= No_Element.
126/2
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
127/2
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 (in the sense of 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.
128/2
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
129/2
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 (in the sense of 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.
130/2
function Next (Position : Cursor) return Cursor;
131/2
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.
132/2
function Previous (Position : Cursor) return Cursor;
133/2
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.
134/2
procedure Next (Position : in out Cursor);
135/2
Equivalent to
Position := Next (Position).
136/2
procedure Previous (Position : in out Cursor);
137/2
Equivalent to
Position := Previous (Position).
138/2
function Has_Element (Position : Cursor) return Boolean;
139/2
Returns True
if Position designates an element, and returns False otherwise.
140/2
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
141/2
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.
Program_Error is propagated if Process.all tampers with the cursors
of Container. Any exception raised by Process.all is propagated.
142/2
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
143/2
Iterates over
the nodes in Container as per Iterate, except that elements are traversed
in reverse order, starting with the last node and moving the cursor as
per the Previous function.
144/2
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 ordering relationship, 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. How many times the subprograms
of Generic_Sorting call "<" is unspecified.
145/2
function Is_Sorted (Container : List) return Boolean;
146/2
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.
147/2
procedure Sort (Container : in out List);
148/2
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/2
procedure Merge (Target : in out List;
Source : in out List);
150/2
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.
Bounded (Run-Time) Errors
151/2
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.
Erroneous Execution
152/2
A Cursor value
is
invalid if any of the following have occurred since it was
created:
153/2
- The list that contains the element
it designates has been finalized;
154/2
- The list that contains the element
it designates has been used as the Source or Target of a call to Move;
or
155/2
- The element it designates has been
deleted.
156/2
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.
Implementation Requirements
157/2
No storage associated with a doubly-linked
List object shall be lost upon assignment or scope exit.
158/2
The execution of an assignment_statement
for a a list shall have the effect of copying the elements from the source
list object to the target list object.
Implementation Advice
159/2
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/2
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/2
Move should not copy elements, and should
minimize copying of internal data structures.
162/2
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/2
44 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.
Contents Index Search Related Documents Previous Next Legal