From: Amit Dubey <adubey@CoLi.UniSB.DE>  20030606 09:35:20

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 multipart message in MIME format. > > =_NextPart_000_0015_01C32C45.52938130 > ContentType: text/plain; > charset="iso88591" > ContentTransferEncoding: 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 > ContentType: application/octetstream; > name="binTree.ml" > ContentTransferEncoding: 7bit > ContentDisposition: 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 ((len1)/2) in > Tree(k,i,ref left,ref right) > end > in > t.t := opt_list len > =_NextPart_000_0015_01C32C45.52938130 > ContentType: application/octetstream; > name="binTree.mli" > ContentTransferEncoding: 7bit > ContentDisposition: 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 http://www.etnus.com. > _______________________________________________ > ocamllibdevel mailing list > ocamllibdevel@... > https://lists.sourceforge.net/lists/listinfo/ocamllibdevel > 