Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> I'm looking for the Set/Map like data-structures which can efficiently
> add and remove large intervals over integers, and support
> intersections, unions and compliments.  Does anybody make such
> libraries?  Baire contains interval.ml[i] but misses these
> functionalities.  Is it easy to add them to Baire, or are Baire's
> intervals something different than I thought?

Baire's interval Set/Map data structure is based on Martin Erwig's
paper 'Diets for fat sets, Journal of Functional programming Vol 8,
N°6, 627-632, 1998'. It seems to be the data structure you are looking
for (that is an extension to usual sets and maps with a better support
for interval query, insertion, removal, ...)

Erwig's paper is available from his home page, there is also a version
by Olivier Andrieu.

There are interval data structures used in computational geometry
(interval tree, ...) but I don't think this is what you are refering
to, is it ?

Martin Erwig's paper presents the data structure and says that one
could easily add
- a balancing scheme
- the set operations (union, intersection, ...)

I did the first one longtime ago (should clean the data structure and
remove some bugs) but didn't have the courage to face the 23 cases of
interval respective positions needed to implement the 'difference'
operation over sets.  I also tried some generic implementation
(extending the 'partition' operation) but never ended that work.

> Failing that, is there Set/Map with order-related operations?
> Actually I have one but if there is one actively developed, I would
> like to use it.

I dont understand exactly what do you mean by 'order-related
operations'. Anyway, if you have some code, it would be interesting to
release it.

> By the way, I have a library for arbitrary orders on (finite sets of)
> integers.  I think comparison of two integer is O(log n ^ 2)
> time. (n for the size of the finite set.)  Do you think it is worth to
> make public?

Yes. It could be included to one of the 'data structure projects'
being developed in Caml.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners