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,e382b50ddc696050 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-12-07 07:06:18 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.tele.dk!small.news.tele.dk!209.98.98.64!news-out.visi.com!hermes.visi.com!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: <3C0DB9D0.7184868A@acm.org> <3C0EB851.77E7172A@boeing.com> <3C0FAF78.6F006DF7@boeing.com> Subject: Re: List Strawman JC01 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: Fri, 07 Dec 2001 10:06:02 EST Organization: http://www.newsranger.com Date: Fri, 07 Dec 2001 15:06:02 GMT Xref: archiver1.google.com comp.lang.ada:17569 Date: 2001-12-07T15:06:02+00:00 List-Id: In article <3C0FAF78.6F006DF7@boeing.com>, Jeffrey Carter says... > >Since the time complexity comments were in my package, I thought we were >talking about it. Its name is "List_Strawman_JC01", it has no parent >package, and we have no other kind of list to compare it to. The whole goal here is to progressively modify the strawman to a point where there can be enough of a consensus to move forward on it. To that end, I thought you were presenting your ideas in package form, rather than just arguing them verbally. If there a consensus around any of those ideas, I would then put them in the strawman. Remember that the strawman is not *my* baby, its *ours*. There is certianly stuff in there that I would do completely differently if I were writing the package by myself. I hope we are not involved in a process where everyone feels like they are going to go out and make their own package and convince people to use that package instead. That's not drawing people together, its splintering them apart. If that starts happening, clearly this whole process is doomed. Perhaps I am just overreacting, and you are only trying to say that you think the strawman doesn't need to be in a package hierarchy? >Much of your discussion of "<" does not seem to be about package >List_Strawman_JC01, which is what we are discussing here. For example > >> "Next" requires a direction parameter to disambiguate. >> The only directional terminology we have at all is "Front" and "Back". > >These do not apply to this package. Ahhh. So what you are saying is that I need to take more of a holistic approach on the naming issue. That's a good point. So really the lynchpin in your argument here is that we change our terminology from talking about "Front" and "Back" to "First" and "Last". This way we arbitrarily assign a direction to what is otherwise a directionless data structure, and then terms that rely on the notion of progressing suddenly make sense. I don't think I'd be in favor of that, because that lack of direction is really an integral part of a (doubly-linked) list, and I don't see directionality gaining us a great deal of anything for the loss of flexability. But of course if I turn out to be in the minority on this, I'll so change the strawman. >I'll ask you to go look at the spec (of List_Strawman_JC01) again. There >is a First function, since this is a basic property of a list. There is No its not. Its a basic property of a *singly* linked list. For a doubly-linked list, there is no logical "first" element, and working from either end is equivalent. >The ordering property applies for all lists, regardless of >implementation, just as it applies for arrays. An array is sorted in >ascending order if no element is less than a preceding element. The fact >that you can do (examples using other data structures deleted) You can't use examples of *other* data structures to make your point, because they aren't doubly-linked lists. This reflexive property is what makes a doubly-linked list different from arrays and singly-linked lists. OK. Lets try a thought experiment here. Picture in your mind's eye an array rotating slowing in space. You don't have any markers on it; its just a string of values. How do you know which is the "first" element? That's easy right? You just find the side with the lowest index. Now lets try the same thought experiment with a singly linked list. You've got a string of cells linked with directional arrows rotating in space with directional arrows going between them. How do you know which is the "first" element? Again, this is easy. Its the element that only has an arrow going out of it, and no arrow going into it. Now lets do the same thing with a doubly-linked list. We have a string of cells with bidirectional arrows between them rotating in space. Now how do you find which element is the "first" one? The answer of course is that you *can't*. What we have here is a truly direction-neutral structure. We could always go "eeny-meeny-miny-mo" and pick one of course. But just because we did that doesn't suddenly make a directional bias inherent in the data structure. Its something the user imposes, and its there only in as much as the user believes in it and adheres to it. I'd like to hear from one of the instructors in the audience about this. After all, you are the ones who have to teach students data structures using this thing. --- 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.