API Reference

type Skip_List , procedure Clear

   type Skip_List is limited private; -- Initial value: empty.  
   procedure Clear (List : in out Skip_List);  

Makes List empty.

Time: O(N).

procedure Assign

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

Makes To a copy of From.

May raise Storage_Exhausted.

The state of To if Storage_Exhausted is raised is undefined.

function Search

   function Search (List : Skip_List; Item : Element) return Result;   

If there exists a value stored in List such that Value = Item, returns (Found => True, Item => Value).

Returns (Found => False) otherwise.

procedure Insert

   procedure Insert (List               : in out Skip_List;   
                     Item               : in     Element;  
                     Duplicates_Allowed : in     Boolean := False);  

raise Storage_Exhausted.

Adds Item to List in the order specified by "<".

If Duplicates_Allowed, adds Item after any values in List which are = Item.

If not Duplicates_Allowed and there is a value in List which is = Item, replaces the value with Item.

It is recommended that Duplicates_Allowed always be False (see comments for Delete).

Raises Storage_Exhausted if there is insufficient memory available for a list node.

List is unchanged if Storage_Exhausted is raised.

procedure Delete

   procedure Delete (List : in out Skip_List; Item : in Element);   

Deletes the first value in List which is = Item.

If there is no such value in List, this procedure has no effect. The user is expected to have checked for the existence of such a value before calling this procedure, using Search, Get_First, or Get_Last. Note that, if duplicates are allowed, Delete may delete a different node than the one found through Search, Get_First, or Get_Last, with possible unexpected results.

function Get_First

   function Get_First (List : Skip_List) return Element; -- raise Empty.   

Returns the first value stored in List (values are ordered by "<" and by the order in which they are inserted).

Raises Empty if List is empty.

Time: O(1).

function Get_Last

   function Get_Last (List : Skip_List) return Element; -- raise Empty.   

Similar to Get_First except it returns the last value stored in List. Raises Empty if List is empty.

Time: O(1).

function Is_Empty

   function Is_Empty (List : Skip_List) return Boolean;   

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

function Length

   function Length (List : Skip_List) return Natural;   

Returns a count of the number of values stored 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;  
                             Continue :    out Boolean);  
   procedure Iterate (List : in out Skip_List; Context : in out Context_Data);  

Applies Action to each value in List in order. Returns immediately if Action sets Continue to False.