Re: List container strawman 1.2

[Darren New <dnew@san.rr.com>]

Ted Dennison wrote:
> 
> In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
> >
> >Ted Dennison wrote:
> >> there is better. "Font" and "Back" are pretty standard terminology for list
> 
> Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't they?

I'm less worried about "usual" than "consistancy". For example, in the
Java libraries, they have things like "insert" for lists, "put" for
vectors, "add" for maps, and such. And it's virtually impossible to keep
straight which is which. If I want to get the first element and I have
to call "First", but a pointer to the first element is "Head", then it's
going to be check-the-docs time every time I use it. 

This is what I liked about the Eiffel libraries. (The ISE version, I
mean.) Adding an item is *always* Put. The element to be added is always
the first argument (well, modulo distinguished-selector syntax). The
current element is always "item". Clearing out the data structure is
always "prune". It doesn't matter what structure it is. It doesn't
matter if you've never even seen that structure before.

> That's actually a very good question. It isn't an array, so you can't tell from
> that. The way the list is designed, I can use it as a queue or as a stack from
> either end and it will work just fine either way.
> 
> The iterator, on the other hand, has a different job to perform. In its world,
> all it has to do is pick a side, and then go the other way until the end. So
> there it makes more sense to talk about "First" and "Last".
> 
> However, you have to pick a side, and it would be useful to know how to relate
> the two. So you are right that this *is* a bit confusing, because somewhere you
> have to realise that "First"="Head". But renaming "Head" to "First" won't remove
> the confusion, because that term has no real meaning in the universe of Push'es
> and Pop's.

type direction is (towards_first, towards_last);
procedure next(L : in out Location; dir : in direction := towards_last);
-- Or however you want to declare the procedure/function/whatever.

No problem. Same thing that the string routines do.

> So how do we get out of this. The best ways that I can see are either:
> 
> o  Make sure the iterator routines are well commented as to which
> directions in the "Head/Tail" world they operate.

Make it a choice on each operation. Symmetry and orthoganality is what
makes a library easy to learn and use.

> o  Rename the iterator routines to match the other routines.
> Unfortunately, this would reqire "Next" and "Previous" to become
> something like "Next_Toward_Tail" and "Next_Toward_Head". The
> passive iterator would still have to be commented as to which
> direction it goes. I suppose a From_Head/From_Tail flag could be
> used instead. That might be useful anyway...

Yes. Especially if you have a sorted list and you want to go in
different directions.
 
> I think the second option is quite doable, if that's what people really want.
> 
> >It's not uncommon, usually when the sub-lists being inserted "mean"
> >different things, like you're inserting the children of the directory
> >after the directory entry during a breadth-first walk, say. And "&" has
> 
> So what you are saying is that there is a hetrogenious structure to your list
> that isn't reflected in the structure of the list itself, but in the contents of
> the elements in the list (and thus has to be parsed back out)?

Basically.

> You could
> accomplish this goal without the extra parsing (and without the middle insertion
> routine) by using lists of lists, could you not?

Except that each element of the list would have to be *either* a file
name *or* a directory name, for example. Just as much work to deal with
either way.

The point is that any time you flatten a tree into a list inorder,
you're going to want to have an operation to insert an entire list into
the middle of another list. Heirarchical data bases, databases of chess
moves, generating HTML, parsing MIME, etc.

Anyway, the places I do such things tend to be very weakly typed
languages. I've not done anything large enough to need that in Ada yet.
 
> You are right about the level-of-effort vs. the append routines, though.

Yeah. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.