Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Nicolas C. <war...@fr...>]

> I did add some other things in reply to your query which you
> haven't quoted.
>
> Dlists have the following properties:
>
> (1) bidirectional iteration
> (2) keys stable under all mutations
> (3) keys are zero cost
> (4) keys are generated by the data structure to support
> any user defined ordering.

I don't agree with your definition of a node being a key to the item.
Several reasons for that :
- a node does not describe any interesting property of the item, it is just
a pointer to the item. You cannot by any way produce a node by your own
means, and only a node returned by add is valid for a given dllist.
- nodes are not ordered, comparing them will just blow the stack since
they're recursive. You can check for equality with == and != operators but
nothing else.
- node adresses are not stable since they can be moved by the GC.
Taken apart advantages of keys, you get only bidrectional iteration, which
is IMHO not interesting enough to justify adding a new data structure to
ExtLib.

Nicolas