pragma Preelaborate (Doubly_Linked_Lists);
|
Type Summary
Cursor |
| Primitive Operations: |
Delete,
Element,
Find,
First,
Has_Element,
Insert,
Insert,
Insert,
Last,
Next,
Next,
Previous,
Previous,
Replace_Element,
Reverse_Find,
Splice,
Splice,
Splice,
Swap,
Update_Element
|
Iterate_Process |
List |
| Primitive Operations: |
"=",
Append,
Clear,
Delete,
Delete_First,
Delete_Last,
Find,
First,
First_Element,
Insert,
Insert,
Insert,
Is_Empty,
Is_In,
Iterate,
Last,
Last_Element,
Length,
Move,
Prepend,
Reverse_Find,
Reverse_Iterate,
Reverse_List,
Splice,
Splice,
Splice,
Swap
|
Reverse_Iterate_Process derived from Iterate_Process |
Update_Element_Process |
|
Constants and Named Numbers
Empty_List : constant List;
|
|
Represents the empty list. If an object of type List is not otherwise
initialized, it will be initialized to the same value as
Empty_List.
|
No_Element : constant Cursor;
|
|
Represents a cursor that designates no element. If an object of type
Cursor is not otherwise initialized, it will be initialized
to the same value as No_Element.
|
|
Other Items:
|
type List is tagged private;
|
|
The type List needs finalization (see 7.6).
|
|
|
function "=" (Left, Right : List) return Boolean;
|
|
If Left denotes the same object as Right, then
this function returns True. Otherwise if Left
and Right have different lengths, then this 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 this function returns False;
otherwise, this function returns True. Any exceptions
raised during evaluation of element equality are propagated.
|
|
|
function Is_Empty (Container : List) return Boolean;
|
|
Equivalent to Length (Container) = 0.
|
|
procedure Clear (Container : in out List);
|
|
Removes all the nodes in Container, and sets the length to
0. Any exceptions raised during deallocation of storage are propagated.
|
|
function Element (Position : Cursor)
return Element_Type;
|
|
Returns the element stored on the node designated by Position
. If Position equals No_Element, then
Constraint_Error is propagated.
|
|
type Update_Element_Process is
access procedure (Element : in out Element_Type);
|
|
If Element_Type is unconstrained and definite, then the
Element parameter shall be unconstrained.
|
|
procedure Update_Element
(Position : in Cursor;
Process : Update_Element_Process);
|
Ada0Y
not null access procedure (Element : in out Element_Type));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
If Position equals No_Element, then
Constraint_Error is propagated.
Otherwise, Update_Element invokes Process.all
with the element on node designated by Position as the
argument.
|
|
procedure Replace_Element (Position : in Cursor;
By : in Element_Type);
|
|
Assigns the value By to the element stored on the node
designated by Position. If Position equals
No_Element, then Constraint_Error
is propagated.
|
|
procedure Move (Target : in out List;
Source : in out List);
|
|
If Target denotes the same object as Source,
then the operation has no effect. If Length (Target) is
greater than 0, then it raises Constraint_Error
. Otherwise, the nodes in Source are moved to
Target. The length of Target is set to the
length of Source, and the length of Source
is set to 0.
|
|
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
|
|
Equivalent to Insert (Container, First (Container), New_Item,
Count).
|
|
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
|
|
Equivalent to Insert (Container, No_Element, New_Item, Count)
.
|
|
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
|
|
Insert allocates Count new nodes whose element
is initialized to the value New_Item, and inserts them
prior to the node designated by Before. If Before
equals No_Element, the new node is inserted
immediately following the last node (if any). Any exceptions raised
during allocation of internal storage are propagated, and
Container is not modified.
|
|
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
|
|
Insert allocates Count new nodes whose element
is initialized to the value New_Item, and inserts them
prior to the node designated by Before. If Before
equals No_Element, the new node is inserted
immediately following the last node (if any). Position
designates the first newly-inserted node. Any exceptions raised during
allocation of internal storage are propagated, and Container
is not modified.
|
|
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
|
|
Allocates Count new nodes with elements initialized with
any implicit initial values for any part (as for an object_declaration
with no initialization expression - see 3.3.1), and inserts them prior
to the node designated by Before. If Before
equals No_Element, the new node is inserted immediately
following the last node (if any). Position designates the
first newly-inserted node. Any exceptions raised during allocation of
internal storage are propagated, and Container is not
modified.
|
|
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
|
|
If Position equals No_Element, the operation
has no effect. Otherwise Delete removes Count
nodes starting at the node designated by Position from
Container (or all of the nodes if there are less than
Count nodes starting at Position). Any
exceptions raised during deallocation of internal storage are
propagated.
|
|
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
|
|
If Length (Container) >= Count, Delete_First
removes the first Count nodes from Container;
otherwise, all of the nodes in Container are removed. Any
exceptions raised during deallocation of storage are propagated.
|
|
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
|
|
If Length (Container) >= Count, Delete_Last
removes the last Count nodes from Container;
otherwise, all of the nodes in Container are removed. Any
exceptions raised during deallocation of storage are propagated.
|
|
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Generic_Sort (Container : in out List);
|
|
Reorders the nodes of Container such that the elements are
sorted smallest first as determined by the generic formal "<"
operator provided. The sort must be stable. Any exceptions
raised during evaluation of "<" are propagated.
|
|
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Generic_Merge (Target : in out List;
Source : in out List);
|
|
If Source denotes the same object as Target,
the operation has no effect. Otherwise this operation reorders nodes
such that they are removed from Source and moved to
Target. Target and Source are assumed
to be sorted smallest first as determined by the generic formal
"<" operator. The nodes in Source containing
elements that are less than elements in Target are spliced
in before the elements already in Target. The nodes in
Source container elements that are equal to or greater
than elements in Target are spliced in after the elements
already in Target. Any exceptions raised during evaluation
of "<" are propagated, immediately terminating the merge
operation.
|
|
procedure Reverse_List (Container : in out List);
|
|
Reorders the nodes of Container in reverse order.
|
|
procedure Swap (Container : in List;
I, J : in Cursor);
|
|
Swap exchanges the nodes designated by I and
J.
|
|
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
|
|
If Source denotes the same object as Target,
the operation has no effect. Otherwise, Splice reorders
nodes such that they are removed from Source and moved to
Target, just 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.
|
|
procedure Splice (Target : in out List;
Before : in Cursor;
Position : in Cursor);
|
|
If Position<\CODE> equals No_Element<\CODE>, or if
Position<\CODE> equals Before<\CODE>, or if the successor of
Position<\CODE> equals Before<\CODE>, the operation has no
effect. Otherwise the node designated by Position<\CODE> is
becomes the predecessor of Before<\CODE>. If Before<\CODE>
equals No_Element<\CODE>, then Position<\CODE> is moved
after the last node.
|
|
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in Cursor);
|
|
If Source denotes the same object as Target,
then Splice is equivalent to the Splice
operation sans Source parameter. If Position
equals No_Element, the operation has no effect. Otherwise
the node designated by Position is removed from
Source and moved to Target, immediately prior to
Before. If Before equals No_Element
, then Position is moved after the last node of
Container. The length of Target is
incremented, and the length of Source is decremented.
|
|
function First (Container : List) return Cursor;
|
|
Returns a cursor that designates the first node. If Container
is empty, First returns the value No_Element
.
|
|
function First_Element (Container : List)
return Element_Type;
|
|
If Container is empty, then Constraint_Error
is propagated. Otherwise, it returns Element
(First (Container)).
|
|
function Last (Container : List) return Cursor;
|
|
Returns a cursor that designates the last node. If Container
is empty, Last returns the value No_Element
.
|
|
function Last_Element (Container : List)
return Element_Type;
|
|
If Container is empty, then Constraint_Error
is propagated. Otherwise, it returns Element
(Last (Container)).
|
|
function Is_In (Item : Element_Type;
Container : List)
return Boolean;
|
|
Equivalent to Find (Container, Item) /= No_Element.
|
|
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
|
|
Searches the nodes of Container for an element equal to
Item. The search starts at the node designated by
Position. If Position equals No_Element
, then the search begins at the first node. If no element is
found that matches Item, then Find returns the
value No_Element.
|
|
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
|
|
Searches the nodes of Container in reverse for an element
equal to Item. The search starts at the node designated by
Position. If Position equals No_Element
, then the search begins at the last node. If no element is found
that matches Item, then Find returns the value
No_Element.
|
|
function Next (Position : Cursor) return Cursor;
|
|
If Position equals No_Element or designates
the last node of the container, then Next returns the value
No_Element. Otherwise, returns a cursor that designates the
successor of the node designated by Position.
|
|
function Previous (Position : Cursor) return Cursor;
|
|
If Position equals No_Element or designates
the first node of the container, then Previous returns the
value No_Element. Otherwise, returns a cursor that
designates the predecessor of the node designated by Position
.
|
|
procedure Next (Position : in out Cursor);
|
|
Equivalent to Position := Next (Position).
|
|
procedure Previous (Position : in out Cursor);
|
|
equivalent to Position := Previous (Position).
|
|
function Has_Element (Position : Cursor) return Boolean;
|
|
Returns True if Position designates an
element, and returns False otherwise.
|
|
|
procedure Iterate
(Container : in List;
Process : Iterate_Process);
|
Ada0Y
not null access procedure (Position : in Cursor));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
Invokes Process with a cursor that designates each node in
Container. Any exceptions raised during Process
are propagated.
|
|
|
procedure Reverse_Iterate
(Container : in List;
Process : Reverse_Iterate_Process);
|
Ada0Y
not null access procedure (Position : in Cursor));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
Iterates over the nodes in Container as per Iterate
, except that elements are traversed in reverse order.
|
|
|
private
|