Ajout de Map.remove.

git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@739 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

2 files changed, 23 insertions, 0 deletions

diff --git a/stdlib/map.ml b/stdlib/map.ml
index 1e7338bf2..578fac6f0 100644
--- a/stdlib/map.ml
+++ b/stdlib/map.ml
@@ -24,6 +24,7 @@ module type S =
     val empty: 'a t
     val add: key -> 'a -> 'a t -> 'a t
     val find: key -> 'a t -> 'a
+    val remove: key -> 'a t -> 'a t
     val iter: (key -> 'a -> 'b) -> 'a t -> unit
     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
   end
@@ -96,6 +97,25 @@ module Make(Ord: OrderedType) = struct
           if c = 0 then d
           else find x (if c < 0 then l else r)
 
+    let rec merge t1 t2 =
+      match (t1, t2) with
+        (Empty, t) -> t
+      | (t, Empty) -> t
+      | (Node(l1, v1, d1, r1, h1), Node(l2, v2, d2, r2, h2)) ->
+          bal l1 v1 d1 (bal (merge r1 l2) v2 d2 r2)
+
+    let rec remove x = function
+        Empty ->
+          Empty
+      | Node(l, v, d, r, h) as t ->
+          let c = Ord.compare x v in
+          if c = 0 then
+            merge l r
+          else if c < 0 then
+            bal (remove x l) v d r
+          else
+            bal l v d (remove x r)
+
     let rec iter f = function
         Empty -> ()
       | Node(l, v, d, r, _) ->
diff --git a/stdlib/map.mli b/stdlib/map.mli
index d2460eb4b..3da155581 100644
--- a/stdlib/map.mli
+++ b/stdlib/map.mli
@@ -51,6 +51,9 @@ module type S =
     val find: key -> 'a t -> 'a
         (* [find x m] returns the current binding of [x] in [m],
            or raises [Not_found] if no such binding exists. *)
+    val remove: key -> 'a t -> 'a t
+        (* [remove x m] returns a map containing the same bindings as
+           [m], except for [x] which is unbound in the returned map. *)
     val iter: (key -> 'a -> 'b) -> 'a t -> unit
         (* [iter f m] applies [f] to all bindings in map [m],
 	   discarding the results.