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.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ecfc0548c2df0d76 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-11-08 02:22:09 PST Path: archiver1.google.com!news2.google.com!fu-berlin.de!uni-berlin.de!dialin-145-254-038-165.arcor-ip.NET!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: MI ammunition : linked lists Date: Sat, 08 Nov 2003 11:27:28 +0100 Organization: At home Message-ID: References: Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: dialin-145-254-038-165.arcor-ip.net (145.254.38.165) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7Bit X-Trace: news.uni-berlin.de 1068286928 48954992 145.254.38.165 (16 [77047]) User-Agent: KNode/0.7.2 Xref: archiver1.google.com comp.lang.ada:2252 Date: 2003-11-08T11:27:28+01:00 List-Id: Frank J. Lhota wrote: > Even where MI is available, I would not implement linked lists this way. > Do we really want the type of a node vary depending on its position on the > list? Do we want to convert the type of end nodes when a new node is > added, or when an end node is removed? YES! There are two opposite variants of list design. One of them, most people seems keeping in mind, is to have a list element and then to add object specific things: type List_Element is ...; type My_Object_In_A_List is new List_Element with private; This sort of design faces many problems. What if My_Object_... has to be in many lists simultaneously? No way. Then to the problem you and others mention. It exists because an inheritance by extension from List_Element fixes the representation of My_Object_... This is inherently bad. You can argue that to have different representations for root, middle and end nodes is wrong, and flatten them to be of same type, as all here propose. Let accept it for a minute. How about another challenge. What if we have different list representation? What if there is Double_Linked_List_Element, Array_List_Element, Persistent_List_Element, Remote_List_Element and My_Object could be put in either of them? By inheriting form a specific element type, we produce different object types, depending on the element representation. And if you move an object from one list to another it still has to mutate! - This has nothing to do with MI! - An alternative design could be objects independent from list elements. A "list element" could act as a smart pointer to My_Object_...'Class. If you do this, then mutating a list element would cause no problem, because it would not affect the object itself. It is just like to get another pointer to it. Because List_Elements are small (up to two fields), it would be very efficient [assuming that List_Elements could be by-value]. In this case MI would offer a type-safe representation for list elements. It is a clear advantage. The problem with this approach is that: 1. user-defined access types are presently not supported, which makes implementation of smart pointers (by controlled types) very difficult and inefficient; 2. access types and user-defined by-value types cannot be tagged; 3. initialization / finalization is allowed for controlled types only; 4. there is no MI, after all. I think that to fix 1-3 [and arguably 4] would drastically improve Ada, at least much more than introdicing += or saturated arithmetics. -- Regards, Dmitry A. Kazakov www.dmitry-kazakov.de