API Reference

type Handle , type Position

  
   type Handle is limited private; -- Initial value: empty.  
  
   type Position is private;  

A position is initially invalid until assigned a value by First, Last, or Off_List.

Other positions accessible via Next and Prev.

   Invalid_Position : exception;  

Raised if a position is invalid or if the Off_List position is used for Delete, Get, or Put.

procedure Assign

   procedure Assign (To : out Handle; From : in Handle);   

Makes To a copy of From.

May raise Storage_Exhausted.

The state of To is unknown if Storage_Exhausted is raised.

procedure Clear

   procedure Clear (List : in out Handle); -- Makes List empty.   

Time: O(N).

Operations to obtain valid positions for lists:

function First

   function First (List : Handle) return Position;   

function Last

   function Last (List : Handle) return Position;   

function Off_List

   function Off_List (List : Handle) return Position;   

Next (Last (List), List) and Prev (First (List), List) refer to positions which are "off the list".

This special position is used in those cases.

Each list has a unique Off_List position.

Next (Last (List), List) = Off_List (List).

Prev (First (List), List) = Off_List (List).

Next and Prev are supposed to reverse each other. For a valid Position P of Handle L, Next (Prev (P, L), L) = P and Prev (Next (P, L), L) = P.

This gives us:

Next (Off_List (List), List) = First (List).

Prev (Off_List (List), List) = Last (List).

A similar relation holds for Insert and Append

Insert (List, X, Off_List (List), P) <=> Append (List, X, Last (List), P). Append (List, X, Off_List (List), P) <=>

Insert (List, X, First (List), P).

If List is empty, Off_List (List) = First (List) = Last (List). The Off_List position cannot be used for Delete, Get, or Put.

Time: O(1).

Operations to obtain valid positions from valid positions:

function Next

   function Next (Pos : Position; List : Handle) return Position;   

function Prev

   function Prev (Pos : Position; List : Handle) return Position;   

raise Invalid_Position.

Next and Prev raise Invalid_Position if Pos is invalid.

Time: O(1).

Operations to manipulate lists:

procedure Insert

   procedure Insert (Into    : in out Handle;   
                     Item    : in     Element;  
                     Before  : in     Position;  
                     New_Pos :    out Position);  

Inserts Item before Before.

Returns the position of Item in Into in New_Pos.

Raises Storage_Exhausted if no more storage is available for Into. Raises Invalid_Position if Pos is invalid.

Nothing is changed if Storage_Exhausted or Invalid_Position are raised.

procedure Append

   procedure Append (Into    : in out Handle;   
                     Item    : in     Element;  
                     After   : in     Position;  
                     New_Pos :    out Position);  

Appends Item after After.

Returns the position of Item in Into in New_Pos.

Raises Storage_Exhausted if no more storage is available for Into. Raises Invalid_Position if Pos is invalid.

Nothing is changed if Storage_Exhausted or Invalid_Position are raised.

procedure Delete

   procedure Delete (From : in out Handle; Pos : in out Position);   

raise Invalid_Position.

Deletes the item at Pos.

Pos is made invalid.

Raises Invalid_Position if Pos is invalid or is the Off_List position for From.

Nothing is changed if Invalid_Position is raised.

function Get

   function Get (From : Handle; Pos : Position) return Element;   

raise Invalid_Position.

Returns the item at Pos.

Raises Invalid_Position if Pos is invalid or the Off_List position.

procedure Put

   procedure Put (Into : in out Handle; Pos : in Position; Item : in Element);   

raise Invalid_Position.

Makes the Element stored at Pos be Item.

Raises Invalid_Position if Pos is invalid or is the Off_List position for Into.

Nothing is changed if Invalid_Position is raised.

function Is_Empty

   function Is_Empty (List : Handle) return Boolean;   

Returns True if List is empty [Length (List) = 0]; returns False otherwise.

function Length

   function Length (List : Handle) return Natural;   

Returns a count of the number of items in List.

type Context_Data (<>) , with procedure Action , procedure Iterate

   generic -- Iterate   
      type Context_Data (<>) is limited private;  
  
      with procedure Action (Item     : in out Element;  
                             Context  : in out Context_Data;  
                             Pos      : in     Position;  
                             Continue :    out Boolean);  
   procedure Iterate (Over : in out Handle; Context : in out Context_Data);  

Calls Action with each Element in Over, & its Position, in turn. Returns immediately if Continue is set to False (remainder of Over is not processed).

with function "<" , procedure Sort

   generic -- Sort   
      with function "<" (Left : Element; Right : Element) return Boolean is <>;  
   procedure Sort (List : in out Handle); -- raise Storage_Exhausted.  

Sorts List into ascending order as defined by "<".

Requires one additional list node.

Raises Storage_Exhausted if no more storage is available for this extra node.

List is unchanged if Storage_Exhausted is raised.