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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,effb80d4bb7716dd X-Google-Attributes: gid103376,public From: "Alexy V Khrabrov" Subject: Re: Wanted: Ada STL. Reward: Ada's Future Date: 1999/02/01 Message-ID: <7931ej$qqf@bgtnsc02.worldnet.att.net>#1/1 X-Deja-AN: 439204012 References: <790f4q$3l@bgtnsc01.worldnet.att.net> X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Organization: AT&T WorldNet Services Newsgroups: comp.lang.ada Date: 1999-02-01T00:00:00+00:00 List-Id: Matthew Heaney wrote in message ... >On the contrary, a set is next-to-useless as a collection abstraction in >any real program. On the contrary, set is a useful abstraction. In fact, it's the first abstaction in mathematics, used by Euclid to prove that the SET of primes is infinite. Set was used by Euler, Bernoulli, Gauss, Turing, and others, before you or I were born, Matthew, and will be used after us, Ada, C++, or computers in general, for that matter. Set is a part of C++ STL which is used all the time, and emphasized in all STL books. I've seen a gazillion programs using lists for mimicing set behavior, and will see a bazillion more. >A set is an unordered collection without duplicates. Not necessarily unordered. A very useful extension of math set is a set of ordered items, for which a generic taking an "<" parameter along with the Element type and "=" is most suitable form in Ada. That's how in fact the best Ada ADTs I've seen so far, LGL components, were written: http://lglwww.epfl.ch/Components >The problem with a >set is that when you add an item to the set, you have to check the >entire set to make sure that the item isn't already in the set. If it's ordered as above, the search is as efficient as an AVL tree search [read -- any] can be. >That's fine if that's the behavior you want. However, it has been my >personal experience that this is not the abstraction you require. And I do require sets, as many other people do, too. Real world contains sets, and any faithful OOP will need them. >Typically, all you need is an abstraction for an unordered collection. >When you add an item to the collection, it puts (a copy of) the item in >the collection, without any checks. I prefer ordered sets whenever I can supply the "<" -- and I almost always can. Give me one example where you can't. I can even sort files on their last access time, can't I? Tasks on their name, etc. -- even limited private types, that is. >The problem with many data structure texts is that they omit any >discussion of this important abstraction. And so everyone goes through >life thinking that a set (or multiset) is the only kind of unordered >collection that exists. And they also omit ordered sets. >In my work on the ACL (which I suspended until gnat 3.11p came out: it >wouldn't compile otherwise), I call this kind of abstraction a >"container." There is only a minimal set of operations on a Container >type: > >o add an item to the container > >o iterate over items in the container > >o remove the item currently designated by an (active) iterator Where is your ACL? Is it public? >The first thing in the morning you need a Container, not a Set. Well, and I need sets, buddy! Cheers, Alexy V. Khrabrov UPenn CIS/NEC Research Institute/Princeton/CMSC