From: Nicolas C. <war...@fr...> - 2004-09-07 08:49:55
|
What about the two newest data structures dllist and index tree ? Is there final implementation proposal available somewhere to include in ExtLib ? Nicolas Cannasse |
From: Jesse G. <je...@wi...> - 2004-09-07 12:52:07
|
Nicolas Cannasse wrote: > What about the two newest data structures dllist and index tree ? > Is there final implementation proposal available somewhere to include in > ExtLib ? Gimme a day or two to finalize Dllist. I had planned to work on it this past weekend (Monday was a Holiday and all), but instead I took a little road trip with my wife and son. I'll try to work on it tonight and maybe have something final by tommorrow. -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Nicolas C. <war...@fr...> - 2004-09-07 13:06:12
|
> Nicolas Cannasse wrote: > > > What about the two newest data structures dllist and index tree ? > > Is there final implementation proposal available somewhere to include in > > ExtLib ? > > Gimme a day or two to finalize Dllist. I had planned to work on it this > past weekend (Monday was a Holiday and all), but instead I took a little > road trip with my wife and son. I'll try to work on it tonight and maybe > have something final by tommorrow. It's ok you don't need to hurry that much :) Nicolas |
From: Brian H. <bh...@sp...> - 2004-09-07 15:34:22
|
On Tue, 7 Sep 2004, Jesse Guardiani wrote: > Nicolas Cannasse wrote: > > > What about the two newest data structures dllist and index tree ? > > Is there final implementation proposal available somewhere to include in > > ExtLib ? > > Gimme a day or two to finalize Dllist. I had planned to work on it this > past weekend (Monday was a Holiday and all), but instead I took a little > road trip with my wife and son. I'll try to work on it tonight and maybe > have something final by tommorrow. > > > I too have been distracted by life. I'll try to get something akin to a release out today. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Richard J. <ri...@an...> - 2004-09-07 23:03:55
|
On Tue, Sep 07, 2004 at 10:48:43AM +0200, Nicolas Cannasse wrote: > What about the two newest data structures dllist and index tree ? > Is there final implementation proposal available somewhere to include in > ExtLib ? I wasn't intending it for inclusion, but I have a very complete CSV (comma-separated-values) library which could go in. http://www.merjis.com/developers/csv/ Any licensing changes necessary can be incorporated. Rich. --=20 Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment Learning Objective CAML for C, C++, Perl and Java programmers: http://www.merjis.com/richj/computers/ocaml/tutorial/ |
From: Jesse D. G. <je...@wi...> - 2004-09-09 05:54:16
|
Nicolas Cannasse wrote: >>Nicolas Cannasse wrote: >> >> >> >>>What about the two newest data structures dllist and index tree ? >>>Is there final implementation proposal available somewhere to include in >>>ExtLib ? >>> >>> >>Gimme a day or two to finalize Dllist. I had planned to work on it this >>past weekend (Monday was a Holiday and all), but instead I took a little >>road trip with my wife and son. I'll try to work on it tonight and maybe >>have something final by tommorrow. >> >> > >It's ok you don't need to hurry that much :) > > New version available here: http://www.wingnet.net/~jesse/ocaml/dllist/index.html Changes: - merge -> splice - jump -> skip - enums reimplemented - added rev_enum function My sourceforge ID is 'trevarthan'. I'll be the maintainer. Thanks! -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Nicolas C. <war...@fr...> - 2004-09-11 03:28:29
|
> New version available here: > http://www.wingnet.net/~jesse/ocaml/dllist/index.html > > Changes: > - merge -> splice > - jump -> skip > - enums reimplemented > - added rev_enum function > > My sourceforge ID is 'trevarthan'. I'll be the maintainer. > > Thanks! I would add an "add" function to would be an append returning "unit" (because I don't want all the time to write ignore...). I would also eliminate the use of a data structure for enum operations , the "valid" test can be replaced everywhere by a curr == node , this might simplify implementation. For the syntax/typo : - remove all ;; because they are not needed - please replace your 8 chars indentation by tabs or 2/4 spaces indents It's ok for inclusion into ExtLib, you are now developer of ExtLib and you can commit to the CVS once ready. Please check (that goes for Brian IdxTree too) that your module builds well with Makefile and with install.ml script, and that the documentation generated by ocamldoc , with install script ( and ExtLib CSS ) is consistent with other modules. Thanks Nicolas Cannasse |
From: Jesse G. <je...@wi...> - 2004-09-11 03:11:09
|
On Friday 10 September 2004 5:17 pm, Nicolas Cannasse wrote: > > New version available here: > > http://www.wingnet.net/~jesse/ocaml/dllist/index.html > > > > Changes: > > - merge -> splice > > - jump -> skip > > - enums reimplemented > > - added rev_enum function > > > > My sourceforge ID is 'trevarthan'. I'll be the maintainer. > > > > Thanks! > > I would add an "add" function to would be an append returning "unit" > (because I don't want all the time to write ignore...) OK. Do you think something like "add_before" might be useful too? (prepend with unit return value) I suck with function naming, so please feel free to help me out. > . I would also > eliminate the use of a data structure for enum operations , the "valid" test > can be replaced everywhere by a curr == node , this might simplify > implementation. Actually, I tried this before I submitted the current implementation and I couldn't get it to work. The problem seemed to be that Dllist has no concept of Empty, so the length function becomes really difficult to implement. Brian, do you think it's possible to implement enums without the "valid" test? If everyone thinks it's possible then I'll give it another shot. I just didn't have much luck the first time around. > For the syntax/typo : > - remove all ;; because they are not needed > - please replace your 8 chars indentation by tabs or 2/4 spaces indents OK. I'll make these changes this weekend. -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Bardur A. <oca...@sc...> - 2004-09-11 06:32:06
|
On Fri, Sep 10, 2004 at 05:39:22PM -0400, Jesse Guardiani wrote: > Actually, I tried this before I submitted the current implementation and I > couldn't get it to work. The problem seemed to be that Dllist has no > concept of Empty, so the length function becomes really difficult to > implement. > > Brian, do you think it's possible to implement enums without the "valid" > test? If everyone thinks it's possible then I'll give it another shot. I just > didn't have much luck the first time around. > On the subject of Dllist.enum... I noticed that the count () function always computes the length of the remaining nodes by traversing the list. It would be more efficient to do this, I think: 1) The first time count () is called, compute the length and store it "in the enum". 2) Subsequent calls to count () just return the computed length. 2) Every time next () is called, decrese the number of remaining elements by 1 (if the number hasn't been set, you don't need to do anything). This would only incur minimal overhead for next () and for any code the uses count () it basically reduces count () to O(1) averaged over all the elements. -- Bardur Arantsson <ba...@im...> <ba...@sc...> - Be ot or bot ne ot, taht is the nestquoi. | Monty Python's Flying Circus |
From: Nicolas C. <war...@fr...> - 2004-09-11 10:02:33
|
> On the subject of Dllist.enum... I noticed that the count () > function always computes the length of the remaining nodes > by traversing the list. It would be more efficient to do > this, I think: > > 1) The first time count () is called, compute the length > and store it "in the enum". > > 2) Subsequent calls to count () just return the computed > length. > > 2) Every time next () is called, decrese the number of > remaining elements by 1 (if the number hasn't been set, > you don't need to do anything). > > This would only incur minimal overhead for next () and for > any code the uses count () it basically reduces count () > to O(1) averaged over all the elements. This is actually the implementation of List.enum. Jesse you can have a look at it to implement it. Nicolas |
From: Jesse G. <je...@wi...> - 2004-09-11 22:01:52
|
Nicolas Cannasse wrote: >> On the subject of Dllist.enum... I noticed that the count () >> function always computes the length of the remaining nodes >> by traversing the list. It would be more efficient to do >> this, I think: >> >> 1) The first time count () is called, compute the length >> and store it "in the enum". >> >> 2) Subsequent calls to count () just return the computed >> length. >> >> 2) Every time next () is called, decrese the number of >> remaining elements by 1 (if the number hasn't been set, >> you don't need to do anything). >> >> This would only incur minimal overhead for next () and for >> any code the uses count () it basically reduces count () >> to O(1) averaged over all the elements. > > This is actually the implementation of List.enum. > Jesse you can have a look at it to implement it. OK. I'll see what I can do. -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Brian H. <bh...@sp...> - 2004-09-11 14:37:23
|
On Fri, 10 Sep 2004, Jesse Guardiani wrote: > Actually, I tried this before I submitted the current implementation and I > couldn't get it to work. The problem seemed to be that Dllist has no > concept of Empty, so the length function becomes really difficult to > implement. I moved the concept of "empty" one level up in my implementation. This is because I didn't want to deal with options on the next/prev links. > > Brian, do you think it's possible to implement enums without the "valid" > test? If everyone thinks it's possible then I'll give it another shot. I just > didn't have much luck the first time around. Actually, changing things so that x.next == x is the sign of the end of the list should make enums easier. let rec enum_done = { data = Obj.magic (); next = enum_done; prev = enum_done };; let enum dlst = match dlst.head with | None -> Enum.empty () | Some(hd) -> let next r () = if (!r) == enum_done then raise Enum.no_more_elements else begin let rval = (!r).data in if (!r).next == (!r) then r := enum_done else r := (!r).next; rval end and count r () = let rec loop cnt node = if node.next == node then cnt + 1 else loop (cnt + 1) node.next in if (!r) == enum_done then 0 else loop 0 node in let rec clone r () = let r = ref (!r) in Enum.make ~next:(next r) ~count:(count r) ~clone:(clone r) in let r = ref hd in Enum.make ~next:(next r) ~count:(count r) ~clone:(clone r) ;; -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Jesse G. <je...@wi...> - 2004-09-11 21:53:35
|
Brian Hurt wrote: > On Fri, 10 Sep 2004, Jesse Guardiani wrote: > >> Actually, I tried this before I submitted the current implementation and >> I couldn't get it to work. The problem seemed to be that Dllist has no >> concept of Empty, so the length function becomes really difficult to >> implement. > > I moved the concept of "empty" one level up in my implementation. This is > because I didn't want to deal with options on the next/prev links. > >> >> Brian, do you think it's possible to implement enums without the "valid" >> test? If everyone thinks it's possible then I'll give it another shot. I >> just didn't have much luck the first time around. > > Actually, changing things so that x.next == x is the sign of the end of > the list should make enums easier. > > let rec enum_done = { data = Obj.magic (); next = enum_done; > prev = enum_done };; > > let enum dlst = > match dlst.head with The concept of "head" was removed along with the concept of "Empty" in the last release. -- Jesse Guardiani, Systems Administrator WingNET Internet Services, P.O. Box 2605 // Cleveland, TN 37320-2605 423-559-LINK (v) 423-559-5145 (f) http://www.wingnet.net |
From: Brian H. <bh...@sp...> - 2004-09-11 14:41:38
|
On Fri, 10 Sep 2004, Nicolas Cannasse wrote: > - remove all ;; because they are not needed These were me. I've found it usefull to have the ;; when first compiling modules because they help limit where errors can be. They can be actually usefull. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |