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 SAA12846; Mon, 26 Jul 2004 18:54:40 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA12797 for ; Mon, 26 Jul 2004 18:54:39 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6QGscEV024762 for ; Mon, 26 Jul 2004 18:54:38 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id i6QGsVr6006547 ; Mon, 26 Jul 2004 18:54:31 +0200 (CEST) X-Ids: 167 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 SAA22532 ; Mon, 26 Jul 2004 18:52:37 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id SAA958704 ; Mon, 26 Jul 2004 18:52:51 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Mon, 26 Jul 2004 18:52:50 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Martin Jambon cc: caml-list@inria.fr Subject: Re: [Caml-list] Map + Set In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 4105374E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 41053747.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 inserts:01 worst-case:01 logarithmic:01 baire:01 pointers:01 baire:01 fernandez:01 fernandez:01 olivier:02 olivier:02 complexity:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > I define a `merge' function so that: > merge { ("a", {1;2;4}); ("b", {1}) } { ("a", {3;2;7;8}) } = > { ("a", {1;2;3;4;7;8}); ("b", {1}) } > > For this I define a `really_add' function so that: > really_add ("a", {1}) { ("a", {3;2;7;8}); ... } = > { ("a", {1;3;2;7;8}); ... } > > which should perform O(log n) comparisons of keys (the strings) and > not O(n). This is where I need an O(log n) find, or a remove that returns > me the element that was removed. It seems to me that what you are looking for is an ('a, 'b set) map in which the insertion does not replace the existing data but applies a given function (like Set.add) to the current data. I sometimes need an insert_with function for ('a, 'b list) map that inserts the data in the list if any or creates a new list otherwise. It is a simple modification of the 'insert' (resp. union, difference) function. On the other hand, if you are using strings as keys you should use a trie instead of a map in order to ensure worst-case logarithmic complexity (have a look to lexicalmaps in /trie of Baire). Finally since the data part seems to be a set (and not a list as in my example) the best solution would be a ternary tree (that is a binary tree with one extra pointer to the set represented by a tree, which makes 3 tree pointers) Look in Baire the ternary tree implementation of the /graph directory 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