Re: Generic Package

[Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net...
>> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote:
> ...
>> > Yes, in the sense that the specifics of memory layout and such are
>> > unknown and irrelevant to the client; in particular, no order needs
>> > to be specified.
>>
>> Apart from obvious uselessness of contracts referencing to the memory
>> layout, the above is self-contradictory. Memory layout defines an order.
> It
>> also is a part of the contract. Hence the interface is ordered.
>
> And now all is clear.

No. The only thing that is clear to me, is, that DK is splitting hairs
again, just to win the argument.

> It is impossible to implement a set with having some form of order. So, for
                      ^^^^^^^^^

Implement, yes. But it is possible to implement a set interface
without forcing the user to provide an order function to instantiate
the set. It is also possible to provide a mechanism for such an
implementation that gives you all the elements in this set in some
arbitary order/sequence which might change with every invocation. This
is called iteration.

DK originally stated, it is not possible to iterate over an unordered
set: It is.

It is possible to specify the contract for this iteration without
referring to an order (I did it in one of my recent post). DK denied
this. He is wrong.

Implementing a set as a linked list might not be efficient enough for
a large number of items -- still: It is a set in any sane sense and
one can provide an interface to iterate over the items. And it has
even been implemented without using an order defined on the elements
of the set.

So the even the statement "one cannot implement a set (with or without
iteration) without providing an order over the elements" is plainly
wrong. 

(And no: The linked list doesn't define an order on all possible
elements of the set.)

Regards -- Markus