API Reference

type Position

  
   package Implementation is new ASCL.Data_Structures.List_Bounded_Unprotected  
      (Element => Element, Assign => Assign);  
  
   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.

Since we can't have generic protected subprograms, we'll implement Iterate with the access-to-subprogram type Action_Ptr. This means that the actual subprogram passed to Iterate must be declared at the library level to pass accessibility checks.

Used to pass context data to the Action procedure during Iteration.

type Action_Ptr is access procedure , procedure Clear; -- Makes the list empty.

   type Action_Ptr is access procedure (Item     : in out Element;   
                                        Context  : in out Context_Data'Class;  
                                        Pos      : in     Position;  
                                        Continue :    out Boolean);  
  
   protected type Handle  
      (Max_Size : Positive; Ceiling_Priority : System.Any_Priority)  
   is -- Initial value: Empty.  
  
      procedure Clear; -- Makes the list empty.  
  

function First

      function First return Position;   

function Last

      function Last return Position;   

function Off_List

      function Off_List return Position;   

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

This special position is used in those cases.

Each list has a unique Off_List position.

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

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

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

This gives us:

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

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

A similar relation holds for Insert and Append

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

If List is empty, List.Off_List = List.First = List.Last. 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 Prev

      function Next (Pos : Position) return Position; -- raise Invalid_Position.   
      function Prev (Pos : Position) 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   
         (Item : in Element; Before : in Position; New_Pos : out Position);  

Inserts Item before Before.

Returns the position of Item in the list in New_Pos.

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

Nothing is changed if Storage_Exhausted or Invalid_Position are raised.

procedure Append

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

Appends Item after After.

Returns the position of Item in the list in New_Pos.

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

Nothing is changed if Storage_Exhausted or Invalid_Position are raised.

procedure Delete

      procedure Delete (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 the list.

Nothing is changed if Invalid_Position is raised.

function Get

      function Get (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 (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 return Boolean;   

Returns True if this list is empty (Length = 0); returns False otherwise.

function Is_Full

      function Is_Full return Boolean;   

Returns True if this list is full (Length = Max_Size); returns False otherwise.

function Length

      function Length return Natural;   

Returns a count of the number of items in this list.

procedure Iterate

      procedure Iterate   
         (Action : in Action_Ptr; Context : in out Context_Data'Class);  

Calls Action with each Element in the list, & its Position, in turn from First to Last.

Returns immediately if Continue is set to False (remainder of the list is not processed).