Re: List container strawman 1.2

[Ted Dennison<dennison@telepath.com>]

In article <3BF05337.75BE0A18@san.rr.com>, Darren New says...
>
>Darren New wrote:
>    function "&" (Left, Right : Element) return List;
>        -- O(1)

I much prefer pre-comments to post-comments. The reason is that you read them
before you get to the source, rather than after you have already tried to read
the source and are perhaps already confused and/or misled. Forewarned is
forearmed. :-)

However, the bit about specifying the time behavior for the routines is a good
point.


>    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.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.