You can subscribe to this list here.
2003 
_{Jan}

_{Feb}
(81) 
_{Mar}
(97) 
_{Apr}
(88) 
_{May}
(80) 
_{Jun}
(170) 
_{Jul}
(9) 
_{Aug}

_{Sep}
(18) 
_{Oct}
(58) 
_{Nov}
(19) 
_{Dec}
(7) 

2004 
_{Jan}
(22) 
_{Feb}
(9) 
_{Mar}
(28) 
_{Apr}
(164) 
_{May}
(186) 
_{Jun}
(101) 
_{Jul}
(143) 
_{Aug}
(387) 
_{Sep}
(69) 
_{Oct}
(14) 
_{Nov}
(8) 
_{Dec}
(99) 
2005 
_{Jan}
(10) 
_{Feb}
(34) 
_{Mar}
(24) 
_{Apr}
(7) 
_{May}
(41) 
_{Jun}
(20) 
_{Jul}
(3) 
_{Aug}
(23) 
_{Sep}
(2) 
_{Oct}
(26) 
_{Nov}
(41) 
_{Dec}
(7) 
2006 
_{Jan}
(6) 
_{Feb}
(3) 
_{Mar}
(11) 
_{Apr}

_{May}

_{Jun}
(5) 
_{Jul}
(8) 
_{Aug}
(20) 
_{Sep}

_{Oct}
(6) 
_{Nov}
(5) 
_{Dec}

2007 
_{Jan}

_{Feb}
(1) 
_{Mar}

_{Apr}
(3) 
_{May}
(2) 
_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}
(7) 
_{Oct}
(6) 
_{Nov}
(19) 
_{Dec}
(11) 
2008 
_{Jan}

_{Feb}
(7) 
_{Mar}
(9) 
_{Apr}
(21) 
_{May}
(42) 
_{Jun}
(27) 
_{Jul}
(28) 
_{Aug}
(26) 
_{Sep}
(16) 
_{Oct}
(32) 
_{Nov}
(49) 
_{Dec}
(65) 
2009 
_{Jan}
(35) 
_{Feb}
(20) 
_{Mar}
(36) 
_{Apr}
(42) 
_{May}
(111) 
_{Jun}
(99) 
_{Jul}
(70) 
_{Aug}
(25) 
_{Sep}
(15) 
_{Oct}
(29) 
_{Nov}
(3) 
_{Dec}
(18) 
2010 
_{Jan}
(10) 
_{Feb}
(4) 
_{Mar}
(57) 
_{Apr}
(63) 
_{May}
(71) 
_{Jun}
(64) 
_{Jul}
(30) 
_{Aug}
(49) 
_{Sep}
(11) 
_{Oct}
(4) 
_{Nov}
(2) 
_{Dec}
(3) 
2011 
_{Jan}
(1) 
_{Feb}
(1) 
_{Mar}

_{Apr}

_{May}

_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}
(2) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}
(1) 
2012 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

2013 
_{Jan}

_{Feb}
(1) 
_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}
(2) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}
(1) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 

1
(1) 
2
(8) 
3
(2) 
4
(9) 
5
(3) 
6
(7) 
7

8
(4) 
9
(4) 
10
(5) 
11
(5) 
12
(6) 
13
(4) 
14
(2) 
15
(1) 
16
(9) 
17
(15) 
18
(1) 
19
(12) 
20
(18) 
21
(10) 
22
(5) 
23
(10) 
24
(1) 
25
(8) 
26
(3) 
27
(6) 
28
(1) 
29
(2) 
30
(8) 





From: Brian Hurt <bhurt@sp...>  20030606 18:12:43

On Fri, 6 Jun 2003, Nicolas Cannasse wrote: > 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. > Is there a reason you did this as a mutable tree and not the "standard" applicative version? Brian 
From: Amit Dubey <adubey@CoLi.UniSB.DE>  20030606 11:22:46

> > is there any advantage of > > > > > t : ('a ,'b) tree ref; > > over: > > > > mutable t : ('a, 'b) tree; > It's for recursion, since are left and right trees are both ('a , 'b ) tree > ref. The problem is that you cannot pass a mutable field to a function > like a ref. I'm a bit confused... unless you want to make a change to a subtree from two places, this shouldn't be necessary. Taking a quick peek at the code, it doesn't seem like this happens (but maybe I missed something). If this isn't the case, you could just as easily pass around the unmutable structure, and assign it where you need. > > > 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). > > Map does not allow to have several items with the same key in it. > Calling add is replacing the current binded item if any. > I think it's more convenient to have a structure that can "shadow" items > just like Hashtbl do. Ok, makes sense! However, the main thrust behind my suggestion was more about the worstcase performance of insertion and removal... Map already has the balancing code written, even if a wrapper isn't appropriate, perhaps you could steal'n'hack the bal, add and remove functions from there? Amit 
From: Nicolas Cannasse <warplayer@fr...>  20030606 10:27:06

> 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... It's for recursion, since are left and right trees are both ('a , 'b ) tree ref. The problem is that you cannot pass a mutable field to a function like a ref. > 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). Map does not allow to have several items with the same key in it. Calling add is replacing the current binded item if any. I think it's more convenient to have a structure that can "shadow" items just like Hashtbl do. Nicolas Cannasse 
From: Nicolas Cannasse <warplayer@fr...>  20030606 10:26:10

> 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... It's for recursion, since are left and right trees are both ('a , 'b ) tree ref. The problem is that you cannot pass a mutable field to a function like a ref. > 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). Map does not allow to have several items with the same key in it. Calling add is replacing the current binded item if any. I think it's more convenient to have a structure that can "shadow" items just like Hashtbl do. Nicolas Cannasse 
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 > 
From: Nicolas Cannasse <warplayer@fr...>  20030606 09:30:01

> Tree node here takes 3 (for Tree+tuple, and two refs) allocations where > it can take 2 (or 1?) with: > >  Tree of ('a, 'b) tree_rec > > and type ('a, 'b) tree_rec = > { > a : 'a; > b : 'b; > mutable left : ('a, 'b) tree; > mutable right : ('a, 'b) tree; > } > > and this is more readable IMHO. True, thanks. That piece of code is pretty old, I just added the enum features without thinking about the internal representation. I'll update it this way when I have some time. Nicolas Cannasse 
From: Nicolas Cannasse <warplayer@fr...>  20030606 07:06:03

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 