A.18.3 The Package Containers.Doubly_Linked_Lists
{
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.
{list container} {container
(list)} {
AI95-00302-03}
{node (of a list)} 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.
{
AI95-00302-03}
The
length of a list is the number of elements it contains.
{length
(of a list container)} Static Semantics
{
AI95-00302-03}
The generic library package Containers.Doubly_Linked_Lists has the following
declaration:
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);
type List
is tagged private;
pragma Preelaborable_Initialization(List);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_List :
constant List;
No_Element :
constant Cursor;
function "=" (Left, Right : List) return Boolean;
function Length (Container : List)
return Count_Type;
function Is_Empty (Container : List)
return Boolean;
procedure Clear (Container :
in out List);
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out List;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type));
procedure Update_Element
(Container :
in out List;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type));
procedure Move (Target :
in out List;
Source :
in out List);
procedure Insert (Container :
in out List;
Before :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out List;
Before :
in Cursor;
New_Item :
in Element_Type;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out List;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Prepend (Container :
in out List;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Append (Container :
in out List;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Delete (Container :
in out List;
Position :
in out Cursor;
Count :
in Count_Type := 1);
procedure Delete_First (Container :
in out List;
Count :
in Count_Type := 1);
procedure Delete_Last (Container :
in out List;
Count :
in Count_Type := 1);
procedure Reverse_Elements (Container :
in out List);
procedure Swap (Container :
in out List;
I, J :
in Cursor);
procedure Swap_Links (Container :
in out List;
I, J :
in Cursor);
procedure Splice (Target :
in out List;
Before :
in Cursor;
Source :
in out List);
procedure Splice (Target :
in out List;
Before :
in Cursor;
Source :
in out List;
Position :
in out Cursor);
procedure Splice (Container:
in out List;
Before :
in Cursor;
Position :
in Cursor);
function First (Container : List)
return Cursor;
function First_Element (Container : List)
return Element_Type;
function Last (Container : List)
return Cursor;
function Last_Element (Container : List)
return Element_Type;
function Next (Position : Cursor)
return Cursor;
function Previous (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
procedure Previous (Position :
in out Cursor);
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Contains (Container : List;
Item : Element_Type)
return Boolean;
function Has_Element (Position : Cursor)
return Boolean;
procedure Iterate
(Container :
in List;
Process :
not null access procedure (Position :
in Cursor));
procedure Reverse_Iterate
(Container :
in List;
Process :
not null access procedure (Position :
in Cursor));
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
is
function Is_Sorted (Container : List)
return Boolean;
procedure Sort (Container :
in out List);
procedure Merge (Target :
in out List;
Source :
in out List);
end Generic_Sorting;
private
... -- not specified by the language
end Ada.Containers.Doubly_Linked_Lists;
{
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.
{unspecified
[partial]} 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 "=").
{
AI95-00302-03}
The type List is used to represent lists. The type List needs finalization
(see
7.6).
{
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.
{
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.
{
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.
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
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.
{
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.]
{
AI95-00302-03}
{tamper with cursors (of a list)}
A subprogram is said to
tamper with cursors
of a list object
L if:
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
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.
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
it finalizes L; or
it calls the Move procedure with L as a
parameter.
Reason: Swap copies elements rather than
reordering them, so it doesn't tamper with cursors.
{
AI95-00302-03}
{tamper with elements (of a list)}
A subprogram is said to
tamper with elements
of a list object
L if:
it tampers with cursors of L; or
it replaces one or more elements of L, that
is, it calls the Replace_Element or Swap procedures with L as
a parameter.
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.
function "=" (Left, Right : List) return Boolean;
{
AI95-00302-03}
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.
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.
function Length (Container : List) return Count_Type;
function Is_Empty (Container : List) return Boolean;
procedure Clear (Container : in out List);
function Element (Position : Cursor) return Element_Type;
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
{
AI95-00302-03}
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.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
{
AI95-00302-03}
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.
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
{
AI95-00302-03}
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.
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
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.
procedure Move (Target : in out List;
Source : in out List);
{
AI95-00302-03}
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.
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
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.
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).
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
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.
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
{
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 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.
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI95-00302-03}
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);
{
AI95-00302-03}
Equivalent to Insert (Container, No_Element, New_Item, Count).
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
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.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Delete (Container, First (Container), Count).
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it removes the last Count nodes from Container.
procedure Reverse_Elements (Container : in out List);
{
AI95-00302-03}
Reorders the elements of Container in reverse order.
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.
procedure Swap (Container : in out List;
I, J : in Cursor);
{
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.
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.
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.
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
{
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.
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.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
{
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.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
{
AI95-00302-03}
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.
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.
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
{
AI95-00302-03}
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.
function First (Container : List) return Cursor;
{
AI95-00302-03}
If Container is empty, First returns the value No_Element. Otherwise
it returns a cursor that designates the first node in Container.
function First_Element (Container : List) return Element_Type;
function Last (Container : List) return Cursor;
{
AI95-00302-03}
If Container is empty, Last returns the value No_Element. Otherwise it
returns a cursor that designates the last node in Container.
function Last_Element (Container : List) return Element_Type;
function Next (Position : Cursor) return Cursor;
{
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.
function Previous (Position : Cursor) return Cursor;
{
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.
procedure Next (Position : in out Cursor);
procedure Previous (Position : in out Cursor);
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
{
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.
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
{
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.
function Contains (Container : List;
Item : Element_Type) return Boolean;
{
AI95-00302-03}
Equivalent to Find (Container, Item) /= No_Element.
function Has_Element (Position : Cursor) return Boolean;
{
AI95-00302-03}
Returns True if Position designates an element, and returns False otherwise.
To be honest: This function may not detect
cursors that designate deleted elements; such cursors are invalid (see
below) and the result of Has_Element for an invalid cursor is unspecified
(but not erroneous).
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
{
AI95-00302-03}
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.
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.
See Iterate for vectors (
A.18.2)
for a suggested implementation of the check.
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
{
AI95-00302-03}
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.
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.
{unspecified
[partial]} function Is_Sorted (Container : List) return Boolean;
{
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.
procedure Sort (Container : in out List);
{
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.
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.
Note that list sorts never copy elements; it
is the nodes, not the elements, that are reordered.
procedure Merge (Target : in out List;
Source : in out List);
{
AI95-00302-03}
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.
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
{
AI95-00302-03}
{bounded error (cause) [partial]}
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
{
AI95-00302-03}
A Cursor value is
invalid if any of the following have occurred
since it was created:
{invalid cursor
(of a list container)} {cursor
(invalid) [partial]} The list that contains the element it designates
has been finalized;
The list that contains the element it designates
has been used as the Source or Target of a call to Move; or
The element it designates has been deleted.
{
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.
{unspecified
[partial]} {erroneous
execution (cause) [partial]} 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.
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.
Implementation Requirements
{
AI95-00302-03}
No storage associated with a doubly-linked List object shall be lost
upon assignment or scope exit.
{
AI95-00302-03}
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.
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
{
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).
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).
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.
{
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).
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).
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!
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Containers.Doubly_Link_Lists.Move
should not copy elements, and should minimize copying of internal data
structures.
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.
{
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.
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.
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.
44 {
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
{
AI95-00302-03}
{
extensions to Ada 95}
The generic package
Containers.Doubly_Linked_Lists is new.
Sponsored by Ada-Europe