Re: [Caml-list] Map + Set

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

    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