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,start X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-09 19:51:16 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!sn-xit-01!supernews.com!newshub2.rdc1.sfba.home.com!news.home.com!news1.denver1.co.home.com.POSTED!not-for-mail Message-ID: <3BECA3B7.5020702@telepath.com> From: Ted Dennison User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.5) Gecko/20011011 X-Accept-Language: en-us MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: List container strawman 1.2 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Date: Sat, 10 Nov 2001 03:51:15 GMT NNTP-Posting-Host: 24.10.28.160 X-Complaints-To: abuse@home.net X-Trace: news1.denver1.co.home.com 1005364275 24.10.28.160 (Fri, 09 Nov 2001 19:51:15 PST) NNTP-Posting-Date: Fri, 09 Nov 2001 19:51:15 PST Organization: Excite@Home - The Leader in Broadband http://home.com/faster Xref: archiver1.google.com comp.lang.ada:16191 Date: 2001-11-10T03:51:15+00:00 List-Id: I've attached a slightly updated version of the list container strawman. This contains a few changes which I think there was consensus for, and some oversight corrections. Specificly: A version of Insert using a List rather than just a single element was added. A "Modify" routine was added. The Done_Iterating constant was transmogrified into a Has_Item boolean function. Unary "+" changed to "Singleton". (I know the name is still contravesial, but there does appear to be general agreement to not use "+".) Added Pop functions. Changed the name of the "Iterator" type to "Index", and "Passive_Iterator" to "Iterator". I'm trying out this solution before taking the more drastic step of making a safe active iterator. We don't quite yet seem to have reached a consensus for making that drastic of a change. However, it seems to me that the terminology I was using may have been a bit of a stumbling block for some, so I'd like everyone to think about it with the new name a bit and re-formulate your opinions. As an "index" it makes sense that you would supply it along with its List to routines, and that it isn't particularly safe, as that is how array indexes work too. --- code attached below ---- with Ada.Finalization; with Ada.Streams; ------------------------------------------------------------------------------- -- This file contains a proposal for a standard Ada list package. -- -- version - Strawman 1.2 ------------------------------------------------------------------------------- generic type Element is private; 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; ----------------------------------------------------------------------------- -- 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. -- -- Unary plus ("+") wasn't a big hit for the "Construct" routine, so now I'm -- floating "Singleton". ----------------------------------------------------------------------------- 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 Singleton (Initial_Element : Element) return List; ----------------------------------------------------------------------------- -- "push" and "pop" operations. Pops on empty lists raise No_Item. ----------------------------------------------------------------------------- No_Item : exception; 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); function Pop_Front (Source : List) return List; function Pop_Back (Source : List) return 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; ----------------------------------------------------------------------------- -- Passive iterator. Operation will be applied on each element on the list -- Opertion can terminate this process early by setting Quit to True. ----------------------------------------------------------------------------- generic with procedure Operation (Target : in out Element; Quit : out Boolean); procedure Iterator (Target : in out List); ----------------------------------------------------------------------------- -- List index routines. For an empty list, Has_Item(First) = False. Item and -- Remove raise No_Item if they are called when Has_Item(Location) = False. -- As written, a typical iteration idiom would look like: -- -- i := My_Lists.First (My_List); -- while My_Lists.Has_Item (i) loop -- do stuff with My_Lists.Item(i); -- i := My_Lists.Next (i); -- end loop; -- -- Another 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; -- ----------------------------------------------------------------------------- type Index is private; function Has_Item (Location : Index) return Boolean; function First (Subject : List) return Index; function Last (Subject : List) return Index; function Next (Location : Index) return Index; function Previous (Location : Index) return Index; function Item (Location : Index) return Element; -- Ideally these routines 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. ----------------------------------------------------------------------------- -- Remove the element at the given location, and advance Location to the next -- element. -- If Done_Iterating then No_Item will be raised. -- If Location=First, then Location will be set to the new First. -- If Location=Last, then Location will be set to Done_Iterating. -- otherwise, Location will be set to what Next was previously (the next -- element after the removal). ----------------------------------------------------------------------------- procedure Remove (Subject : in out List; Location : in out Index); ----------------------------------------------------------------------------- -- Insert a copy of the given element (or list) at the given location in the -- list (in front of the element that is already there). Location will -- continue to point to the same element. -- If Done_Iterating, then the element will be put at the end of the -- list. Otherwise, the element will be placed immediately before the element -- at Location. Location will continue to reference that element. ----------------------------------------------------------------------------- procedure Insert (Subject : in out List; Location : in Index; New_Item : in Element); procedure Insert (Subject : in out List; Location : in Index; New_Items : in List); ----------------------------------------------------------------------------- -- Modify the element at the given location in the list. Location will -- continue to point to the same element, but the value at that location will -- be changed to New_Value. -- If Done_Iterating, then No_Item will be raised. ----------------------------------------------------------------------------- procedure Modify (Subject : in out List; Location : in Index; New_Value : in Element); ----------------------------------------------------------------------------- -- 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. :-) ----------------------------------------------------------------------------- generic with function Reverse_Order (Left, Right : in Element) return Boolean; procedure Sort (Subject : in out List); ----------------------------------------------------------------------------- -- Stream attributes. ----------------------------------------------------------------------------- procedure Stream_Read (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out List); procedure Stream_Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in List); private -- Placebo entries to make the compiler happy (so I know the syntax above is correct) type List is new Ada.Finalization.Controlled with null record; for List'Read use Stream_Read; type Index is new Boolean; for List'Write use Stream_Write; end Containers.Lists.Unbounded;