summaryrefslogtreecommitdiff
path: root/lib/fmap.ml
diff options
context:
space:
mode:
Diffstat (limited to 'lib/fmap.ml')
-rw-r--r--lib/fmap.ml133
1 files changed, 0 insertions, 133 deletions
diff --git a/lib/fmap.ml b/lib/fmap.ml
deleted file mode 100644
index 8ca56fe7..00000000
--- a/lib/fmap.ml
+++ /dev/null
@@ -1,133 +0,0 @@
-
-module Make = functor (X:Map.OrderedType) -> struct
- type key = X.t
- type 'a t =
- Empty
- | Node of 'a t * key * 'a * 'a t * int
-
- let empty = Empty
-
- let is_empty = function Empty -> true | _ -> false
-
- let height = function
- Empty -> 0
- | Node(_,_,_,_,h) -> h
-
- let create l x d r =
- let hl = height l and hr = height r in
- Node(l, x, d, r, (if hl >= hr then hl + 1 else hr + 1))
-
- let bal l x d r =
- let hl = match l with Empty -> 0 | Node(_,_,_,_,h) -> h in
- let hr = match r with Empty -> 0 | Node(_,_,_,_,h) -> h in
- if hl > hr + 2 then begin
- match l with
- Empty -> invalid_arg "Map.bal"
- | Node(ll, lv, ld, lr, _) ->
- if height ll >= height lr then
- create ll lv ld (create lr x d r)
- else begin
- match lr with
- Empty -> invalid_arg "Map.bal"
- | Node(lrl, lrv, lrd, lrr, _)->
- create (create ll lv ld lrl) lrv lrd (create lrr x d r)
- end
- end else if hr > hl + 2 then begin
- match r with
- Empty -> invalid_arg "Map.bal"
- | Node(rl, rv, rd, rr, _) ->
- if height rr >= height rl then
- create (create l x d rl) rv rd rr
- else begin
- match rl with
- Empty -> invalid_arg "Map.bal"
- | Node(rll, rlv, rld, rlr, _) ->
- create (create l x d rll) rlv rld (create rlr rv rd rr)
- end
- end else
- Node(l, x, d, r, (if hl >= hr then hl + 1 else hr + 1))
-
- let rec add x data = function
- Empty ->
- Node(Empty, x, data, Empty, 1)
- | Node(l, v, d, r, h) ->
- let c = X.compare x v in
- if c = 0 then
- Node(l, x, data, r, h)
- else if c < 0 then
- bal (add x data l) v d r
- else
- bal l v d (add x data r)
-
- let rec find x = function
- Empty ->
- raise Not_found
- | Node(l, v, d, r, _) ->
- let c = X.compare x v in
- if c = 0 then d
- else find x (if c < 0 then l else r)
-
- let rec mem x = function
- Empty ->
- false
- | Node(l, v, d, r, _) ->
- let c = X.compare x v in
- c = 0 || mem x (if c < 0 then l else r)
-
- let rec min_binding = function
- Empty -> raise Not_found
- | Node(Empty, x, d, r, _) -> (x, d)
- | Node(l, x, d, r, _) -> min_binding l
-
- let rec remove_min_binding = function
- Empty -> invalid_arg "Map.remove_min_elt"
- | Node(Empty, x, d, r, _) -> r
- | Node(l, x, d, r, _) -> bal (remove_min_binding l) x d r
-
- let merge t1 t2 =
- match (t1, t2) with
- (Empty, t) -> t
- | (t, Empty) -> t
- | (_, _) ->
- let (x, d) = min_binding t2 in
- bal t1 x d (remove_min_binding t2)
-
- let rec remove x = function
- Empty ->
- Empty
- | Node(l, v, d, r, h) ->
- let c = X.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, _) ->
- iter f l; f v d; iter f r
-
- let rec map f = function
- Empty -> Empty
- | Node(l, v, d, r, h) -> Node(map f l, v, f d, map f r, h)
-
- (* Maintien de fold_right par compatibilité (changé en fold_left dans
- ocaml-3.09.0) *)
-
- let rec fold f m accu =
- match m with
- Empty -> accu
- | Node(l, v, d, r, _) ->
- fold f l (f v d (fold f r accu))
-
-(* Added with respect to ocaml standard library. *)
-
- let dom m = fold (fun x _ acc -> x::acc) m []
-
- let rng m = fold (fun _ y acc -> y::acc) m []
-
- let to_list m = fold (fun x y acc -> (x,y)::acc) m []
-
-end