Doubly_Linked_Lists #

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.

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.

The length of a list is the number of elements it contains.

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
   with Preelaborate, Remote_Types, Nonblocking,
        Global => in out synchronized is

   type List   is tagged private;
   type Cursor is        private;

   Empty_List: constant List;
   No_Element: constant Cursor;

   function Has_Element(                 Position: Cursor) return Boolean;
   function Has_Element(Container: List; Position: Cursor) return Boolean;

   package List_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

   function "="(Left, Right: List) return Boolean;

   function Tampering_With_Cursors_Prohibited (Container: List) return Boolean;
   function Tampering_With_Elements_Prohibited(Container: List) return Boolean;

   function Empty return List is
      (Empty_List);

   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;
   function Element(Container: List; Position: Cursor) return Element_Type;

   procedure Replace_Element(Container: in out List; Position: Cursor; New_item: Element_Type);
   procedure Query_Element(Position: Cursor;
                           Process : not null access procedure(Element: Element_Type));
   procedure Query_Element(Container: List;
                           Position : Cursor;
                           Process  : not null access procedure(Element: Element_Type));
   procedure Update_Element(Container: in out List;
                            Position : Cursor;
                            Process  : not null access procedure(Element: in out Element_Type));

   type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
   type Reference_Type         (Element: not null access          Element_Type) is private;

   function Constant_Reference(Container: aliased        List; Position: Cursor) return Constant_Reference_Type;
   function Reference         (Container: aliased in out List; Position: Cursor) return Reference_Type;

   procedure Assign(Target: in out List; Source: List);

   function Copy(Source: List) return List;

   procedure Move(Target: in out List; Source: in out List);
   procedure Insert(Container: in out List;
                    Before   : Cursor;
                    New_Item : Element_Type;
                    Position : out Cursor;
                    Count    : Count_Type := 1);
   procedure Insert (Container: in out List; Before: Cursor; Position: out Cursor  ; Count: Count_Type := 1);
   procedure Insert (Container: in out List; Before: Cursor; New_Item: Element_Type; Count: Count_Type := 1);
   procedure Prepend(Container: in out List                ; New_Item: Element_Type; Count: Count_Type := 1);
   procedure Append (Container: in out List                ; New_Item: Element_Type; Count: Count_Type := 1);
   procedure Append (Container: in out List                ; New_Item: Element_Type);
   procedure Delete (Container: in out List; Position : in out Cursor; Count: Count_Type := 1);
   procedure Delete_First(Container: in out List; Count: Count_Type := 1);
   procedure Delete_Last (Container: in out List; Count: Count_Type := 1);
   procedure Reverse_Elements(Container: in out List);
   procedure Swap      (Container: in out List; I, J: Cursor);
   procedure Swap_Links(Container: in out List; I, J: Cursor);
   procedure Splice(Target: in out List; Before: Cursor; Source: in out List);
   procedure Splice(Target: in out List; Before: Cursor; Source: in out List; Position: in out Cursor);
   procedure Splice(Container: in out List; Before: Cursor; Position: 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;
   function Next    (Container: List; Position: Cursor) return Cursor;
   function Previous(Container: List; Position: Cursor) return Cursor;

   procedure Next(Position: in out Cursor);
   procedure Next(Container: List; Position: in out Cursor);
   procedure Previous(Position: in out Cursor);
   procedure Previous(Container: List; 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;
   
   procedure Iterate        (Container: List; Process: not null access procedure(Position: Cursor));
   procedure Reverse_Iterate(Container: List; Process: not null access procedure(Position: Cursor));

   function Iterate(Container: List) return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class;
   function Iterate(Container: List; Start: Cursor) return List_Iterator_Interfaces.Reversible_Iterator'Class;

   generic
      with function "<"(Left, Right: Element_Type) return Boolean is <>;
   package Generic_Sorting
      with Nonblocking, Global => null 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;

   package Stable is
      type List(Base: not null access Doubly_Linked_Lists.List) is tagged limited private;
      type Cursor is private;

      Empty_List: constant List;
      No_Element: constant Cursor;

      function Has_Element(Position: Cursor) return Boolean;

      package List_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

      procedure Assign(Target: in out Doubly_Linked_Lists.List; Source: List);

      function Copy(Source: Doubly_Linked_Lists.List) return List;

      type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
      type Reference_Type         (Element: not null access          Element_Type) is private;
   end Stable;
end Ada.Containers.Doubly_Linked_Lists;

Bounded (Run-Time) Errors

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.

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.

It is a bounded error to call any subprogram declared in the visible part of Containers.Doubly_Linked_Lists 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

A Cursor value is invalid if any of the following have occurred since it was created:

The list that contains the element it designates has been finalized.
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.
The list that contains the element it designates has been used as the Source or Target of a call to Move.
The element it designates has been removed from the list that previously contained the element.

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.

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.

Indefinite Double-Linked Lists #

The language-defined generic package Containers.Indefinite_Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each type. It provides the same operations as the package Containers.Doubly_Linked_Lists (see A.18.3), with the difference that the generic formal Element_Type is indefinite.

Omitted Subprograms

procedure Insert(Container: in out List;
                Before    : Cursor;
                Position  : out Cursor;
                Count     : Count_Type := 1);

Bounded Doubly-Linked Lists #

The language-defined generic package Containers.Bounded_Doubly_Linked_Lists provides a private type List and a set of operations. It provides the same operations as the package Containers.Doubly_Linked_Lists (see A.18.3), with the difference that the maximum storage is bounded.

Containers.Bounded_Doubly_Linked_Lists

type List(Capacity: Count_Type) is tagged private...

Modified Subprograms

function Empty(Capacity: Count_Type := <implementation-defined>) return List;
function Copy(Source: List; Capacity: Count_Type := 0)           return List;

Bounded (Run-Time) Errors

It is a bounded error to assign from a bounded list object while tampering with elements [or cursors] of that object is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object prohibiting tampering with elements [or cursors], or execution proceeds normally.

Erroneous Execution

When a bounded list object L is finalized, if tampering with cursors is prohibited for L other than due to an assignment from another list, then execution is erroneous.

Doubly_Linked_Lists#

Indefinite Double-Linked Lists#

Bounded Doubly-Linked Lists#

Doubly_Linked_Lists #

Indefinite Double-Linked Lists #

Bounded Doubly-Linked Lists #