Re: List container strawman 1.2

[Darren New <dnew@san.rr.com>]

Darren New wrote:
> 
> Ted Dennison wrote:
> 
> > I can't always read all parts of a MIME message w/ my regular newsreader. In
> > this case, your spec came through as garbage.
> 
> Sorry. MIME's been around for longer than Ada95, so I figured everyone
> could handle it. The plaintext version is pasted at the bottom, then.

Oops.

generic 
    type Element is private;
package AdaLists is

    type List is private;
    type Location is private;

    -- List construction, as already specified
    function "&" (Left, Right : Element) return List;
        -- O(1)
    function "&" (Left : Element; Right : List) return List;
        -- O(Size(Right))
    function "&" (Left : List; Right : Element) return List;
        -- O(Size(Left))
    function "&" (Left, Right : List) return List;
        -- O(Size(Left)+Size(Right))
    function "+" (Initial_Element : Element) return List;
        -- O(1)

    -- List access
    --   These should all be obvious, except for error cases.
    --   All of these raise No_Item if the specified item doesn't exist.
    --   I.e., front and back raise No_Item if Has_Item(L) is empty.
    --         Item raises No_Item if Size(L)<I.
    No_Item : exception;
    function Front(L : List) return Element; -- O(1)
    function Back(L : List) return Element; -- O(1)
    function Front(L : List) return Location; -- O(1)
    function Back(L : List) return Location; -- O(1)
    function Item(L : List; I : Positive) return Element; -- O(I)
    function Item(L : List; I : Positive) return Location; -- O(I)
    function Size(L : List) return Natural; -- O(1)
    function Has_Item(L : List) return Boolean; -- O(1)
        -- Same as Size(L)/=0
    function Has_Item(L : List; I : Positive) return Boolean; -- O(1)
        -- Same as I<=Size(L)
    function List_Of(L : Location) return List; -- O(1)
    function Index_Of(L : Location) return Positive; --
O(Size(List_Of(L))
        -- Raises No_Item if Has_Item(L)=False
        -- Item(List_Of(L),Index_Of(L))=Item(L)
    procedure Wipe(L : in out List); -- O(Size(L))
        -- Unlinks all links in List without affecting any elements
        -- After this, Size(L)=0
    procedure Copy(In_L : in List; Out_L : out List);
        -- Creates new list, puts copy of In_L into Out_L.

    -- Location manipulation
    function Has_Next(L : Location) return Boolean;
        -- Current location is not the last on the list and
        -- list is not empty. O(1)
    function Has_Previous(L : Location) return Boolean;
        -- Current location is not the first on the list and
        -- list is not empty. O(1)
    function Has_Item(L : Location) return Boolean;
        -- Current item has not been removed and list is not empty. O(1)
    procedure Next(L : in out Location);
        -- Raises No_Item if Has_Next(L) is false
        -- Ensures Has_Previous(L) is true if no exception
        -- May change Has_Next(L) and Has_Item(L)
        -- O(1)
    procedure Previous(L : in out Location);
        -- Raises No_Item if Has_Previous(L) is false
        -- Ensures Has_Next(L) if no exception thrown
        -- O(1)
    function Item(L : Location) return Element;
        -- Raises No_Item if Has_Item(L) is false
        -- O(1)

    -- List modification
    procedure Remove(L : in out Location);
        -- Raises No_Item if Has_Item(L) is false
        -- After this, Has_Item(L) will be false
        -- O(1)
    procedure Replace(L : in out Location; 
                Item : in Element);
        -- Does the obvious. Raises No_Item if Has_Item(L)=False
        -- O(1)

    procedure Insert_Before(L : in out Location;
                Item : in Element);
        -- Inserts copy of Item into list at location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) increases by one. 
        -- Works even on empty lists and even if not Has_Item(L)
        -- O(1)
    procedure Insert_After(L : in out Location;
                Item : in Element);
        -- Inserts a copy of Item into list after location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) remains the same, 
        --    but Size(List_Of(L)) increases.
        -- Works even on empty lists and even if not Has_Item(L)
        -- O(1)

    procedure Insert_Before(L : in out Location;
                Other : in out List);
        -- Inserts contents of Other into list at location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) increases by Size(Other). 
        -- Works even on empty lists and even if not Has_Item(L).
        -- After this, Size(Other)=0 -- Contents *moved*.
        -- O(1)
    procedure Insert_After(L : in out Location;
                Other : in out List);
        -- Inserts a copy of Item into list after location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) remains the same, 
        --    but Size(List_Of(L)) increases by Size(Other).
        -- Works even on empty lists and even if not Has_Item(L)
        -- After this, Size(Other)=0 -- Contents *moved*.
        -- O(1)

    generic
        with function "<"(Left, Right : in Element) return Boolean;
    procedure Sort(L : in out List);
    -- Old Size(L)=new Size(L), but all elements are sorted
    -- such that Item(L) < Item(Next(L)) for all locations.
    -- OK, do we want a stable sort? Probably. I'm not sure if
    -- we need "<=" or "=" or what.

    generic
        with function "<"(Left, Right : in Element) return Boolean;
    procedure Insert_Sorted(L : in out List; I : in Element);
    -- Inserts I into list L such that 

    -- I can also see a number of operations if "=" is defined
    -- for elements, such as "count the number of elements equal
    -- to this" or "give a Location where Item(L)=I" and such.

    -- Iterating would look something like this:
    -- Li : List; Lo : Location;
    -- Lo := Front(Li);
    -- while Has_Item(Lo) loop
    --   if Item(Lo) = George then
    --     Replace(Lo, Sally);
    --   end if;
    --   Next(Lo);
    -- end while;

private
    type Link;
    type Link_Access is access Link;
    type Link is record
        Next, Prev : Link_Access;
        Elem : Element;
    end record;

    type List is record
        Head, Tail : Link_Access;
        Size : Natural;
    end record;
    -- Size=0 -> head=null and tail=null
    -- Size=1 -> head=tail
    -- Size>1 -> head/=tail
    type List_Access is access List;

    type Location is record
        L : List_Access; -- What am I pointing into?
        Next, Prev : Link_Access; -- prev and next
        Curr : Link_Access; -- Do I have a current?
    end record;
    -- L.Size=0 -> next, prev, curr=nul
    -- Has_Item(this) -> Curr/=null
    -- Has_Next(this) -> Next/=null
    -- Has_Previous(this) -> Prev/=null

    -- It is possible by to add Invalid_Change to all Location
    -- operations that will catch using two locations into the 
    -- same list and modifying them in ways that they invalidate
    -- the other, but that's additional overhead we might not want.
    -- It consists of basically adding a "change counter" to each
    -- location and list, incrementing both with each change, and
    -- then revalidating each location that refers to a list whose
    -- change counter doesn't match, eliminating most of the 
    -- overhead for the normal case of only one location being
    -- manipulated at a time.
end AdaLists;


-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.