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 SAA11375; Mon, 26 Jul 2004 18:24:44 +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 SAA09960 for <caml-list@pauillac.inria.fr>; Mon, 26 Jul 2004 18:24:43 +0200 (MET DST)
Received: from out2.smtp.messagingengine.com (out2.smtp.messagingengine.com [66.111.4.26])
	by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i6QGOgSH019190
	for <caml-list@inria.fr>; Mon, 26 Jul 2004 18:24:42 +0200
X-Sasl-enc: DThXAAfZGgAVMr0mP3Mffg 1090859079
Received: from [192.168.1.100] (unknown [218.81.125.200])
	by mail.messagingengine.com (Postfix) with ESMTP id 86FB9C12E1A;
	Mon, 26 Jul 2004 12:24:37 -0400 (EDT)
Date: Tue, 27 Jul 2004 00:24:33 +0800 (HKT)
From: Martin Jambon <martin_jambon@emailuser.net>
X-X-Sender: martin@localhost
To: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>
Cc: Martin Jambon <martin_jambon@emailuser.net>, <caml-list@inria.fr>
Subject: Re: [Caml-list] Map + Set
In-Reply-To: <Pine.A41.4.44.0407260937090.962652-100000@ibm1>
Message-ID: <Pine.LNX.4.44.0407262348460.879-100000@localhost>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Miltered: at concorde with ID 4105304A.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; caml-list:01 pons:01 char:01 fernandez:01 caml:01 olivier:02 tree:02 jambon:02 jambon:02 string:03 add':03 wrote:03 abstract:03 data:03 data:03 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

On Mon, 26 Jul 2004, Diego Olivier Fernandez Pons wrote:

>     Bonjour,
>
> > I need a functional data structure that has a decent efficiency
> > (i.e. not lists) and can represent `sets of named containers' so
> > that I can find a container in a set, remove it from the set, update
> > it and put it back into the set.
>
> Do you mean the containers will be indexed by a string or a list of
> elements (list of char, list of abstract keys) ? If this is the case
> what you are looking for is a trie (or lexical tree).
>
> There are many Caml implementation available including JCF's and
> various data structures libraries.
>
> I am not sure I understood properly what you meant. Could you give an
> example using "union" or "difference" of keys ?

diff { ("a", {1;2;4}); ("b", {1}) } { ("a", {3;2;7;8}) } = { "b" }
union { ("b", [1]) } { ("a", {3;2;7;8}) } = { "a"; "b" }
inter { ("b", [1]) } { ("a", {3;2;7;8}) } = { }

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.


Martin

-------------------
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