Re: GCC 4.0 Ada.Containers Cursor danger.

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Fri, 08 Jul 2005 12:41:18 +0200, Georg Bauhaus wrote:

> 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.

No. You cannot use an arbitrary order, because it is an implementation
detail which no user application should rely on. "Location" is either a
contract or does not exist. A naive user might reason: last time I found it
by the iteration number 32. So be it the next time. Is s/he right?

> 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.

I think it would be a bad design. Unordered containers should not allow
iteration.

> In fact, I wonder whether it might be useful to have an operation
> that allows picking a really arbitrary element.

No problem if that is a primitive operation, as well as to copy a
container, set theoretic operations (and, or, xor).

> (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.

Then elements are unordered, a hash function is the parameter.

> 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.

This is why it is IMO safer to provide no iteration here, because the order
is in fact arbitrary. There could be other ways. For example: one could
provide a "Sort" operation which would return a sorted container. That
container can be iterated.

The order iteration is based on has to be documented. I.e. the user should
know how and when the operations on the container influence that order.
When order is induced by some "hard" facts as below, then you can document
it. But I cannot see a way to document an implementation detail!
 
>>>>BTW the parameters of the type Cursor are routinely named
>>>>"Position"!
>>>
>>>Anything better?
>> 
>> "Element", isn't cursor <=> element? (:-))
> 
> What about No_Element then?

Are you now defending my point? (:-))

>>>>>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.

Right, and what should "Replace" mean for a hashed set? Is it
Remove/Insert? Which influence does it have on iterations?

>>>>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.

Right.

> 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.?

It is just a possible information source for defining what's going on. To
iterate you have to get an order somewhere. The problem is that having at
least three ways to define that order, it becomes quite difficult to bring
all types of containers supporting iterations under one roof.

>> 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?

It does not. But it does in an ordered set. Also see above.

>> 3. Instances of elements (value semantics)
> 
> ?

The values you are working with.

>> 4. References to elements (=locations in some third container! (:-))
> 
> Which third container is this? A container of references?

The memory pool the objects live in.

>> We need to define what "Next" does in terms of 1-4.
> 
> Uhm, why is that?

Because I cannot think up 5,6... (:-)) Which other sources for ordering
exist?

>> 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. ;-)

Exactly!

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de