Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney <matthewjheaney@earthlink.net>]

Mikhail Terekhov <terekhov@emc.com> writes, in response to me:

> > The Generic_Find algorithm is actually a good example, since it
> > works for any container.  That is, it works irrespective of the
> > order in which a container delivers elements via the active iterator
> > (cursor), since the algorithm itself doesn't depend on a specific
> > order.
> 
> Again, that is very true. Can't believe you say it.


But I was referring to all of your earlier the claims:

<<  - First is that all containers have an order.
    Again, sets and hashes in general are *not ordered*.>>

As was pointed out in another post, it is helpful to distiguish between
the order of the elements themselves (the "external" order), and how the
container organizes its elements in order to satisfy time complexity
requirements (the "internal" order).

Clearly, all of the containers have some internal order; the container
itself is simply a high-level wrapper around some low-level data
structure such as a tree or a hash table.

Now of course, we're talking about the containers in the Ada 2005
standard container library.  You refer to sets and hashes "in general"
in the quoted text above, but our concern here is with sets and hashed
"in particular" (that is, in the standard container library). What is
true of sets and hashes "in general" is of no interest.

So if you are saying that containers in the standard library have no
"internal" order, then that claim is obviously false.  Lacking any
internal order, containers simply wouldn't work.  

So you must be making a statement about the "external" order of a
container.  Obviously the Ordered_Sets and Ordered_Maps do have an
(external) order, that corresponds to the element order; indeed that's
the whole point of the "ordered" container category.

That leaves the hashed containers.  The generic formal region of those
containers only requires that elements have a hash function (which is
very different from an order relation), so clearly the hashed containers
have no external order (at least one that is specified).  It would not
be meaningful to speak about the "external order" of a hashed container,
since a hash table works by scattering elements far and wide.

But that's not the same thing as saying a hashed container has no order
at all.  Of course it has an order: the internal order, that of the hash
table itself.  The difference is that the standard doesn't specify what
that internal order is.


<<  To impose an order on them standard needs to put a
    restriction on implementarion algorithms.>>

Do you mean the internal order (how the container choses to organize the
elements internally), or do you mean the external order (the order in
which elements are delivered via an iterator)?

Of course the standard does say something about the (external) order of
the Ordered_Sets and Ordered_Maps.  Vendors are free to choose any
implementation that meets the requirements.  But does that put a
restriction on implementation algorithms?  The restriction really comes
from what the generic formal region requires from its elements.
Obviously you wouldn't be able to implement an Ordered_Set using a hash
table (for example), since the generic formal region doesn't pass in a
hash function.


<<  Your example
    is completely legal generic function in the current
    Ada.Containers framework. >>

Well of course it is, because the Ada.Containers subsystem is a
framework for implementing generic algorithms!  (Hint: that's why it has
cursors.)


<<  But if you decide at some
    point to add unordered containers, then you generic
    function became invalid because for unordered containers
    "first" and "last" have no sense at all.>>

This statement is false.  In the example we're talking about, the
Generic_Find algorithm works for *any* container, no matter what it's
order (internal or external, it doesn't matter).  Give it an unordered
container ("unordered" in the external sense, e.g. a hashed container),
and the algorithms works just fine.

First and Last have well-defined semantics: they define the endpoints
(half-open style) of a sequence of elements.  The algorithm works
irrespective of whether the elements of the sequence are ordered or not.


<< - Second is that find/search operation makes sense only
    for a mapping container i.e. vector or hash; >>

This statement is false.  The find operation simply tests each element
in the sequence, irrespective of its logical order.  Give it a set
container, and the algorithm works just fine.  Eppur si muove...


<<  in this case it returns a key corresponding to the element
    they search for (index for vectors is just a special
    kind of key) if element has been found and some kind
    of No_Element key or exception if there is no such
    element. >>

Well, if this is a simple membership test (to determine whether the item
is among a range of elements), then it can just return Boolean.  I
re-wrote Georg's example to return a cursor, which is more or less the
container analog of an access type.  The function returns the
distinguished cursor value No_Element (analogous to the distinguished
access value "null") if no match was found.

Certainly the algorithm doesn't have to be written that way, and if you
prefer you can return a key (or index) instead.  It is ultimately the
decision of the author of the generic algorithm.  The design of the
algorithm is orthogonal to the design of the library, which merely
provides a flexible framework that allows either possibility.


<<  For a not mapping container i.e. set, list
    or tree the find/search degenerates into membership test
    because there is no sense to search for the element
    if you already have it.>>

I don't think you understand the original algorithm.  (Indeed, I don't
think you even understand the concept of a generic algorithm.)  The
cursors passed as subprogram parameters specify the endpoints of the
range.  The container element you're looking for is (or is not) a member
of the range.

Note that it is an element *value* that is passed as a parameter, which
is then compared to the actual elements in the container.  It is not
correct to say that "you have an element" unless you have either a
cursor that designates that element, or (less efficiently) you have the
key (or index) associated with that element.  If all you have is an
element value, then you don't in any sense have a container element.
(Container elements always belong to a container, and to refer to a
container element you need some kind of handle, which means either a
cursor or a key.)