Re: [Ocaml-lib-devel] Proposal : BinTree

[Amit D. <ad...@Co...>]

    Just a quick question,

    is there any advantage of 

> type ('a,'b) t = {
> 	cmp : ('a -> 'a -> int);
> 	t : ('a ,'b) tree ref;
> }

over:

type ('a,'b) t = {
    cmp : ('a -> 'a -> int);
    mutable t : ('a, 'b) tree;
}

Doesn't the first version require a little bit more memory?
I don't think it's a big deal, but...

Also, what are the relative advantages of having this vs.
putting a mutable wrapper around Map?  Map, if I'm not mistaken,
makes some guarantees of the trees being balanced (both add 
and remove in Map call the balancing function).

    -Amit


> 
> This is a multi-part message in MIME format.
> 
> ------=_NextPart_000_0015_01C32C45.52938130
> Content-Type: text/plain;
> 	charset="iso-8859-1"
> Content-Transfer-Encoding: 7bit
> 
> Hi list,
> 
> Here's a module proposal for adding to the ExtLib.
> This is a binary search tree ( module BinTree ).
> Operations  add, remove, find are done in Log(n) when the tree is optimized.
> This is a mutable version of the data structure.
> 
> Nicolas Cannasse
> 
> ------=_NextPart_000_0015_01C32C45.52938130
> Content-Type: application/octet-stream;
> 	name="binTree.ml"
> Content-Transfer-Encoding: 7bit
> Content-Disposition: attachment;
> 	filename="binTree.ml"
> 
> 
> type ('a,'b) tree =
> 	| Empty
> 	| Tree of ('a * 'b * ('a,'b) tree ref * ('a,'b) tree ref)
> 
> type ('a,'b) t = {
> 	cmp : ('a -> 'a -> int);
> 	t : ('a ,'b) tree ref;
> }
> 	
> let empty() =
> 	{
> 		cmp = compare;
> 		t = ref Empty;
> 	}
> 
> let make cmp =
> 	{
> 		cmp = cmp;
> 		t = ref Empty;
> 	}
> 
> let rec add t key item =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> r := Tree(key,item,ref Empty,ref Empty)
> 		| Tree(k,i,tl,tr) ->
> 			let n = t.cmp k key in
> 			if n = 0 then r := Tree(key,item,tl,ref (Tree(k,i,ref Empty,tr)))
> 			else if n > 0 then loop tl
> 			else loop tr
> 	in
> 	loop t.t
> 
> let rec length t =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> 0
> 		| Tree(_,_,tl,tr) -> 1+(loop tl)+(loop tr)
> 	in
> 	loop t.t
> 
> let rec depth t =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> 0
> 		| Tree(_,_,tl,tr) -> 1+(max (loop tl) (loop tr))
> 	in
> 	loop t.t
> 
> let rec find t key =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> raise Not_found
> 		| Tree(k,i,tl,tr) ->
> 			let n = t.cmp k key in
> 			if n = 0 then i
> 			else if n > 0 then loop tl
> 			else loop tr
> 	in
> 	loop t.t
> 
> let iter f t =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> ()
> 		| Tree(k,i,tl,tr) ->
> 			loop tl;
> 			f k i;
> 			loop tr
> 	in
> 	loop t.t
> 
> let copy t =
> 	let rec loop r =
> 		match !r with
> 		| Empty -> ref Empty
> 		| Tree (k,i,tl,tr) ->
> 			ref (Tree(k,i,loop tl,loop tr))
> 	in
> 	{
> 		cmp = t.cmp;
> 		t = loop t.t;
> 	}
> 
> let clear t = t.t := Empty
> 
> let rec remove t key =
> 	let p = ref Empty in
> 	let rec remove_aux r =
> 		match !r with
> 		| Empty -> raise Not_found
> 		| Tree(k,i,tleft,tright) ->
> 			let n = t.cmp k key in
> 			if n = 0 then r else begin
> 				p := !r;
> 				if n > 0 then remove_aux tleft else remove_aux tright
> 			end
> 		in
> 	let found = remove_aux t.t in
> 	match !found with
> 	| Empty -> assert false
> 	| Tree(k,i,fleft,fright) ->
> 		let attach subtree = 
> 			match !p with
> 			| Empty -> t.t := subtree
> 			| Tree(_,_,pleft,pright) -> 
> 				if found == pleft then
> 					pleft := subtree
> 				else
> 					pright := subtree
> 		in
> 		if !fright = Empty then attach !fleft
> 		else begin
> 			let lp = ref Empty in
> 			let rec mostleft_aux t =
> 				match !t with
> 				| Empty -> assert false
> 				| Tree(_,_,left,_) -> 
> 					if !left = Empty then t else begin
> 						lp := !t;
> 						mostleft_aux left;
> 					end
> 			in
> 			let mostleft = mostleft_aux fright in
> 			let mkey,mitem,mleft,mright =
> 				(match !mostleft with
> 				| Empty -> assert false
> 				| Tree infos -> infos) in
> 			match !lp with
> 			| Empty ->
> 				attach (Tree(mkey,mitem,fleft,mright))
> 			| Tree(_,_,lpleft,lpright) ->
> 				attach (Tree(mkey,mitem,fleft,fright));
> 				lpleft := !mright;
> 		end
> 
> type ('a,'b) istack =
> 	| SItem of ('a * 'b)
> 	| STree of ('a , 'b) tree ref
> 
> let rec make_enum f s = 
> 	let rec next () =
> 		match !s with
> 		| [] -> raise Enum.No_more_elements
> 		| (SItem x) :: h ->
> 			s := h;
> 			f x
> 		| (STree t) :: h ->
> 			let rec loop t =
> 				match !t with
> 				| Empty ->
> 					s := h;
> 					next()
> 				| Tree (k,i,left,right) ->
> 					s := (SItem (k,i)) :: (STree right) :: !s;
> 					loop left
> 			in
> 			loop t
> 	in
> 	let rec tcount t =
> 		match !t with
> 		| Empty -> 0
> 		| Tree(_,_,tl,tr) -> 1 + tcount tl + tcount tr
> 	in
> 	let count() =
> 		List.fold_left (fun acc c ->
> 			match c with
> 			| SItem _ -> acc + 1
> 			| STree t -> acc + tcount t
> 		) 0 !s
> 	in
> 	let clone() =
> 		make_enum f (ref !s)
> 	in
> 	Enum.make ~next ~count ~clone
> 
> let pairs t =
> 	make_enum (fun x -> x) (ref [STree t.t])
> 
> let enum t =
> 	make_enum snd (ref [STree t.t])
> 
> let keys t =
> 	make_enum fst (ref [STree t.t])
> 
> let optimize t = assert false
> 
> let to_list t =
> 	let rec loop dst r =
> 		match !r with
> 		| Empty -> dst
> 		| Tree(k,i,tl,tr) ->
> 			let dst = loop dst tl in
> 			let r = [ (k,i) ] in
> 			Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
> 			loop r tr
> 	in
> 	let x = [Obj.magic()] in
> 	ignore(loop x t.t);
> 	List.tl x
> 
> let optimize t =
> 	let l = ref (to_list t) in
> 	let len = List.length !l in
> 	let rec opt_list len =
> 		if len = 0 then
> 			Empty 
> 		else if len = 1 then begin
> 			match !l with
> 			| [] -> assert false
> 			| (k,i) :: q ->
> 				l := q;
> 				Tree(k,i,ref Empty,ref Empty)
> 		end else begin
> 			let left = opt_list (len/2) in
> 			let k, i = (match !l with
> 			| [] -> assert false
> 			| x :: q ->
> 				l := q;
> 				x) in
> 			let right = opt_list ((len-1)/2) in
> 			Tree(k,i,ref left,ref right)
> 		end
> 	in
> 	t.t := opt_list len
> ------=_NextPart_000_0015_01C32C45.52938130
> Content-Type: application/octet-stream;
> 	name="binTree.mli"
> Content-Transfer-Encoding: 7bit
> Content-Disposition: attachment;
> 	filename="binTree.mli"
> 
> 
> type ('a,'b) t
> 
> val empty : unit -> ('a,'b) t
> val make : ('a -> 'a -> int) -> ('a,'b) t
> 
> (* O(N) *)
> val length : ('a,'b) t -> int
> val depth : ('a,'b) t -> int
> val copy : ('a,'b) t -> ('a,'b) t
> val optimize : ('a,'b) t -> unit
> 
> (* log N *)
> val add : ('a,'b) t -> 'a -> 'b -> unit
> val find : ('a,'b) t -> 'a -> 'b (* raise Not_found *)
> val remove : ('a,'b) t -> 'a -> unit (* raise Not_found *)
> 
> val enum : ('a,'b) t -> 'b Enum.t
> val keys : ('a,'b) t -> 'a Enum.t
> val pairs : ('a,'b) t -> ('a * 'b) Enum.t
> val to_list : ('a,'b) t -> ('a * 'b) list
> 
> val iter : ('a -> 'b -> unit) -> ('a,'b) t -> unit
> 
> val clear : ('a,'b) t -> unit
> ------=_NextPart_000_0015_01C32C45.52938130--
> 
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>