Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus <bauhaus@futureapps.de>]

Dmitry A. Kazakov wrote:

>>As long as we have no clear definition of "location",
>>the argument can go on.
> 
> That's easy. Enumerate all elements in the container [i.e. define an order
> there.] Location will be that number 1..n.

I can see about N! ways of enumerating elements in an unordered
container. Any such enumeration is fine. All I need is the operations
defined for containers and possibly cursors. There is no need for
me to think of the possible location of an element in an
unordered container. I can also pretty much ignore the
arbitrary order established by the finished enumeration
in _my_ program.

In fact, I wonder whether it might be useful to have an operation
that allows picking a really arbitrary element.
(Could be done in a program using a random number modulo
the number of elements in the set, and then approaching
the element by iteration or by index, but I guess this is
rather slow, at least for sets.)



>> Or I could be your container
>>as long as my operations will give you what the operation
>>descriptions tell. Do I have to tell you where (and whether)
>>I store your information in locations?
> 
> 
> You did, if elements are ordered.

But elements aren't ordered when I play the part of the hashed
set container, and decide to hide any internal order.

Even if I, the hashed set container, store your elements in some
internal order, I'm allowed to change locations of elements at will,
as a function of execution time, as long as A.18 isn't violated.
Provided I store elements in locations at all, and do not remember
them in a different way.
I'm just not allowed to disturb your algorithms. For example,
I have to make sure that when you call Next, I present to you
a cursor to some (!) next element. No need for a location.
An order may be established *after* the fact. During iteration,
the elements have been presented in some order, but this order may be
quite volatile. So from this perspective there is no need to
think of the location of an element in this container. I find
it misleading to do so.


>>>BTW the parameters of the type Cursor are routinely named
>>>"Position"!
>>
>>Anything better?
> 
> 
> "Element", isn't cursor <=> element? (:-))

What about No_Element then?

>>>>I don't think there an implied requirement to think of locations.
>>>
>>>Then you have to throw out "Next", "First" etc.
>>
>>I don't understand. I'm just thinking in terms of elements
>>and cursors that designate elements.
> 
> 
> But the elements type don't have "Next" and "First". If Integer X is in A
> then Integer'Succ (X) is not necessarily in A. And A'First is not
> necessarily Integer'First.

Well, yes, but containers can store
non-scalar values, too. Did you mean that if some value is an
element in a container, then another element given by its successor
in the type should be an element in the container, too?
Like numbers defined by the Peano axioms? How could I store
pointers in hashed sets, then, that have no 'succ?


>>There are subprograms
>>named Next, First, etc. with a description of what they do.
>>Where is the pressing need for a location? How do you use
>>"location" in your programs?
> 
> 
> A (Location) := X;

For vectors, yes, that is the Index_Type. For containers
like hashed sets I don't see how location should be needed.


>>>As I said before, it is difficult if possible to assign any definite
>>>semantics to cursors, such that would be consistent across all operations
>>>on them.
>>
>>Could you explain some inconsistencies among the Cursor
>>operations?
> 
> 
> What is the semantics they implement? See your example with Next. We have:
> 
> 1. An order defined on elements (=locations in some "pre-container" (:-))

It isn't always relevant that some Ada types are ordered, some not.
Not every container needs elements that can be ordered, for a start.
Next, First etc. do not have to refer to a type's order if any,
so why and when should we have to respect the type's ordering in Cursor's
First, Next etc.?

> 2. An order defined by the container (=locations)

What is this? Ordered containers can be made to exhibit a kind of
ordered collection only because (a) they are made for this
and (b) because you, the programmer, provides ordering
functions or (c) if your algorithm orders the elements.
What other order needs to be defined by an unordered set?
How does it make sense to speak of the unique location of an
element in an unordered set?


> 3. Instances of elements (value semantics)

?

> 4. References to elements (=locations in some third container! (:-))

Which third container is this? A container of references?


> We need to define what "Next" does in terms of 1-4.

Uhm, why is that?


> In other cases 2
> could be an order completely unrelated to 1, like it is in the case of
> unsorted arrays.

I think that in other cases an order could be completely
redundant. ;-)