From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,a644fa9cd1a3869a
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2001-11-12 14:54:40 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!cyclone.bc.net!sjcppf01.usenetserver.com!usenetserver.com!news-west.rr.com!lsnws01.we.mediaone.net!typhoon.san.rr.com!not-for-mail
Message-ID: <3BF05337.75BE0A18@san.rr.com>
From: Darren New <dnew@san.rr.com>
Organization: Boxes!
X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language: en
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: List container strawman 1.2
References: <3BECA3B7.5020702@telepath.com> <3BF0247D.4500975E@san.rr.com>
 <5BXH7.22252$xS6.34813@www.newsranger.com> <3BF052D3.ECEF3FF2@san.rr.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Date: Mon, 12 Nov 2001 22:55:05 GMT
NNTP-Posting-Host: 66.75.151.160
X-Complaints-To: abuse@rr.com
X-Trace: typhoon.san.rr.com 1005605705 66.75.151.160 (Mon,
 12 Nov 2001 14:55:05 PST)
NNTP-Posting-Date: Mon, 12 Nov 2001 14:55:05 PST
Xref: archiver1.google.com comp.lang.ada:16379
Date: 2001-11-12T22:55:05+00:00
List-Id: <comp.lang.ada>

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.