Re: List Strawman JC01

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Ted Dennison wrote:
> 
> In article <3C0EB851.77E7172A@boeing.com>, Jeffrey Carter says...
> >
> >Ted Dennison wrote:
> >> be better to put this information in a matrix in the parent pacakge so that
> >Except we're talking about one package for unbounded lists. In the case
> >of this strawman, there's no parent package.
> 
> Not true. Since the name is "Containers.Lists.Unbounded", there are actually
> *two* parent packages. I'm compiling the strawman before I post it, so those
> packages do exist. Its just that there isn't anything in them to look at yet, so
> I haven't bothered to post them. :-)

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.

> >that, we can decide what notation to adopt. If we want a bounded list
> >package at some point with similar semantics, we probably will need list
> >parameters.
> 
> That may be an issue, but it doesn't have to be done that way. We could decide
> to still keep a pointer to the list in the iterator, which would allow the same
> iterface as the current Unbounded strawman. But that's a discussion for another
> time.

Yes, any other package should be decided later. The basic issue is that
I didn't want to constrain an implementation.

> >As a general principle, a package should not be propagating predefined
> >exceptions to its clients. Also, this helps allow differing
> 
> By "predefined" I take it you mean "declared in the standard Ada libarary
> somewhere". Considering that the ultimate goal of this facility is to be part of
> the standard Ada library, I don't think your principle applies here. :-)

This may end up being true in the final package. In the meantime, I
don't want to constrain an implementation.

> >This is much less clear than "<". Everyone knows what "<" does.
> >"Swap_Items (L, R ...) return Boolean;" is meaningless.
> 
> In the context of a boolean expression, yes everyone knows. In the context of
> the internals of a sort routine, its completely undefined. Is the "Left"
> parameter the "Front" side or the "Back" side? Does a "True" result mean its out
> of order or in order? You can supply answers to these questions I'm sure, but
> the answers will be fairly arbitrary. They are certianly not self-evident.

They don't matter. All that matters is that the generic needs to be able
to apply "<" to Elements. 
The client supplies "<", so he knows what "<" means.

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.

> >the First element, the Next element, the Next element, ... , the Last
> ..
> >First and Second are perfectly well defined for a list. The first
> >element in List is designated by First (List); the second by Next (First
> 
> You are probably thinking of a singly-linked list. That makes a bit of sense for
> a singly-linked list because there is only one way you can iterate. Therefore we
> know what ascending order is, because there's only one direction to traverse the
> list. For a doubly-linked list, either end is equal. There may be an ordering,
> but the direction of it is entirely imposed by the user. I'll ask you to go look
> at the spec again. There is no "First" function, only a "Side" function, which
> takes a directional parameter to disambiguate. "Next" also requires a
> directional parameter to disambigute.

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 Side function. There are no directional parameters.

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

for I in reverse Some_Array'range loop

and traverse the elements in reverse order doesn't change this.

The fact that you can traverse an array backwards does not change the
fact that there is a specific, well defined, and well known ordering
that is "forward".

The fact that you can traverse a doubly linked list backwards does not
change the fact that there is a specific, well defined, and well known
ordering that is "forward". This is a basic property of a list known by
everyone who understands lists. Sequences, by definition, impose an
order on their elements from the first to the last. Both arrays and
lists are sequences.

Using the notation of List_Strawman_JC01 (since they use the same names
as these basic properties of lists), we can formally state that a list L
is sorted into ascending order according to "<" if

Length (L) < 2

OR

for all I, J : Location such that
  Valid (I, L) AND
  Valid (J, L) AND
  Next (I, L) = J
not (Get (L, J) < Get (L, I) )

-- 
Jeffrey Carter