From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA26723; Mon, 26 May 2003 09:12:04 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA26783 for ; Mon, 26 May 2003 09:12:02 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h4Q7C2H29374 for ; Mon, 26 May 2003 09:12:02 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.9/jtpda-5.4) with ESMTP id h4Q7C1ru042324 ; Mon, 26 May 2003 09:12:01 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id JAA24524 ; Mon, 26 May 2003 09:11:10 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id JAA409624 ; Mon, 26 May 2003 09:11:09 +0200 Date: Mon, 26 May 2003 09:11:08 +0200 (DST) From: Diego Olivier Fernandez Pons To: Yamagata Yoriyuki cc: caml-list@inria.fr Subject: Re: [Caml-list] Set/Map with intervals and/or order-related operations In-Reply-To: <20030525.192604.07647392.yoriyuki@mbg.sphere.ne.jp> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 etu:99 caml-list:01 unions:01 compliments:99 baire:01 misses:01 erwig's:01 vol:99 627:99 andrieu:01 generic:01 'data:01 fernandez:01 caml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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=B06, 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