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,ce0900b60ca3f616 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-02 09:53:02 PST Newsgroups: comp.lang.ada Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newspeer.radix.net!uunet!ash.uu.net!xyzzy!nntp From: Jeffrey Carter Subject: Re: List container strawman X-Nntp-Posting-Host: e246420.msc.az.boeing.com Content-Type: text/plain; charset=us-ascii Message-ID: <3BE2DB99.B707D409@boeing.com> Sender: nntp@news.boeing.com (Boeing NNTP News Access) Content-Transfer-Encoding: 7bit Organization: The Boeing Company X-Accept-Language: en References: <3BE29AF4.80804@telepath.com> <3BE29BD4.10401@telepath.com> Mime-Version: 1.0 Date: Fri, 2 Nov 2001 17:44:57 GMT X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit (WinNT; U) Xref: archiver1.google.com comp.lang.ada:15680 Date: 2001-11-02T17:44:57+00:00 List-Id: Ted Dennison wrote: > > -- This file contains a proposal for a standard Ada list package. This is NOT a list. A list allows insertions at any point in the sequence. This is a dequeue. > -- > -- version - Strawman 1.0 > ------------------------------------------------------------------------------- > generic > type Element is private; This specifies that the package requires "=" for Element. I see no need for "=" in implementing a dequeue. The generic formal part is improperly specified. > package Containers.Lists.Unbounded is > > ----------------------------------------------------------------------------- > -- The list type. I know the name's a bit redundant, but it doesn't look too > -- bad, and any fully-named use will have to have a different name for the > -- package anyway. > ----------------------------------------------------------------------------- > type List is private; This either needs to be limited private or a controlled type. Since this is an unbounded dequeue, assignment of one dequeue to another will result in sharing the internal structure implementing the source dequeue. What are the time/space implications for the operations. For example, is Size O(1) or O(N)? > > ----------------------------------------------------------------------------- > -- List construction operations. The returned list will contain *copies* of > -- all the elements in the source lists, so these routines could get > -- time-consuming. However, they should be useful for Lisp-like processing. > -- > -- I considered using unary minus ("-") for the "Construct" routine, but > -- that's not a common idiom right now. > ----------------------------------------------------------------------------- > function "&" (Left, Right : Element) return List; > function "&" (Left : Element; Right : List) return List; > function "&" (Left : List; Right : Element) return List; > function "&" (Left, Right : List) return List; > function Construct (Initial_Element : Element) return List; I suggest Make rather than Construct. > > ----------------------------------------------------------------------------- > -- "push" and "pop" operations. > ----------------------------------------------------------------------------- > procedure Push_Front (Target : in out List; New_Element : in Element); > procedure Pop_Front (Target : in out List; Old_Element : out Element); > procedure Push_Back (Target : in out List; New_Element : in Element); > procedure Pop_Back (Target : in out List; Old_Element : out Element); What happens if you Pop from an empty list? > > ----------------------------------------------------------------------------- > -- Non-modifying query operations. > ----------------------------------------------------------------------------- > function Is_Empty (Subject : List) return Boolean; > function Size (Subject : List) return Natural; > function Front (Subject : List) return Element; > function Back (Subject : List) return Element; > > ----------------------------------------------------------------------------- > -- I'm not too sure how useful these are, since they have to work on global > -- data. They are global to Operation, but they are no more global to the client code than are any variables used in the "do stuff" part of your examples below. > ----------------------------------------------------------------------------- > generic > with procedure Operation (Target : in out Element); > procedure Closure_Operation (Target : in out List); This is an iterator and should be so named ("Iterate"). I recommend adding a Quit or Continue out Boolean parameter to Operation to allow the client to terminate the iteration early. > > ----------------------------------------------------------------------------- > -- Iteration routines. Next and Previous raise No_More if there is no item in > -- the given direction. For an empty list, First = Last. As written, a > -- typical iteration idiom would look like: > -- > -- i := My_Lists.First (My_List); > -- loop > -- do stuff with My_Lists.Item(i); > -- exit when i = My_Lists.Last (My_List); > -- i := My_Lists.Next (i); > -- end loop; > -- > -- Another alternative using exception handling would be: > -- > -- declare > -- i := My_Lists.First (My_List); > -- begin > -- loop > -- do stuff with My_Lists.Item(i); > -- i := My_Lists.Next (i); > -- end loop; > -- exception > -- when My_Lists.No_More => > -- null; > -- end; > -- > -- A third alternative using "Size" would be: > -- > -- i := My_Lists.First (My_List); > -- for iteration_count in 1..My_Lists.Size (My_List) loop > -- do stuff with My_Lists.Item (i); > -- i := My_Lists.Next (i); > -- end loop; > -- > ----------------------------------------------------------------------------- This is really ugly. Why should the client have to include all this framing code every time he uses an iterator? The passive iterator (generic) given above does the same thing without all this extra client code, and allows the value stored in the dequeue to be changed as well. > type Iterator is private; > No_More : exception; > > function First (Subject : List) return Iterator; > function Last (Subject : List) return Iterator; > function Next (Location : Iterator) return Iterator; > function Previous (Location : Iterator) return Iterator; > function Item (Location : Iterator) return Element; > > -- Ideally this routine would verify that Location was issued for the Subject > -- list and is still valid, but that would be tough to enforce. Better to call > -- such misuse a "bounded error", or somesuch. This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for an example. > procedure Remove (Subject : in out List; Location : Iterator); Using a given Iterator value, what is the value of Next or Previous after Remove? How about Item? What about when you remove the first or last Elements in the dequeue? > > ----------------------------------------------------------------------------- > -- Sorting routine. > -- To sort in increasing order, use the ">" routine for the Reverse_Order > -- parameter. To sort in decreasing order, substitute your "<" routine for > -- the Reverse_Order parameter. :-) > ----------------------------------------------------------------------------- This seems ugly and easy to get wrong. Why not import "<" and specify that after calling Sort, the Elements in Subject will be in order according to "<"? Then the meaning of the imported function is clear without such a comment. > generic > with function Reverse_Order (Left, Right : in Element) return Boolean; > procedure Sort (Subject : in out List); > > private > -- Placebo entries to make the compiler happy (so I know the syntax above is correct) > type List is new Boolean; > type Iterator is new Boolean; > > end Containers.Lists.Unbounded; -- Jeffrey Carter