diff options
Diffstat (limited to 'stdlib')
| -rw-r--r-- | stdlib/map.ml | 20 | ||||
| -rw-r--r-- | stdlib/map.mli | 3 |
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. |