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=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no 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-13 07:54:37 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!sfo2-feed1.news.digex.net!intermedia!news-out.spamkiller.net!propagator-la!news-in-la.newsfeeds.com!news-in.superfeed.net!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: <3BECA3B7.5020702@telepath.com> <3BF0247D.4500975E@san.rr.com> <5BXH7.22252$xS6.34813@www.newsranger.com> <3BF052D3.ECEF3FF2@san.rr.com> <3BF05337.75BE0A18@san.rr.com> Subject: Re: List container strawman 1.2 Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Tue, 13 Nov 2001 10:54:32 EST Organization: http://www.newsranger.com Date: Tue, 13 Nov 2001 15:54:32 GMT Xref: archiver1.google.com comp.lang.ada:16413 Date: 2001-11-13T15:54:32+00:00 List-Id: 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) 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.