Red-Black Cells and Sets?

grignaak Joined: 05/25/07 Posts: 5

Posted: 05/25/07 19:26:24 Item 1. Why is the red-black tree implemented as a heirarchy of cell classes instead of a template with RB methods that are mixed into the classes. It seems to me that the latter would dramatically Reduce code duplication. Item 2. Why is there no TreeSet?? Item 3. I have code for a top-down red-black tree in D. Would this be useful? --Michael

Author	Message
kris Joined: 03/27/04 Posts: 388	Posted: 05/28/07 16:35:45 grignaak wrote: Item 1. Why is the red-black tree implemented as a heirarchy of cell classes instead of a template with RB methods that are mixed into the classes. It seems to me that the latter would dramatically Reduce code duplication. Item 2. Why is there no TreeSet?? Item 3. I have code for a top-down red-black tree in D. Would this be useful? --Michael 1. it was done before templates were useful. Mixins still have major issues 2. Didn't see much use for it, and the semantics of 'order' might become questionable? No other reason I can think of 3. yes -- certainly worth a look. Thanks for the offer :)
grignaak Joined: 05/25/07 Posts: 5	Posted: 06/28/07 18:02:06 Sorry it's taken me a while to respond. I'm in Seattle, the computer my code is stored on is in Utah, and has turned itself off (Yes, very inconvienient). When I get back to Utah in late August, I'll send the code on to you. (But before I do, i'll make the tree threaded for better iteration.)
kris Joined: 03/27/04 Posts: 388	Posted: 07/02/07 15:25:27 grignaak wrote: Sorry it's taken me a while to respond. I'm in Seattle, the computer my code is stored on is in Utah, and has turned itself off (Yes, very inconvienient). When I get back to Utah in late August, I'll send the code on to you. (But before I do, i'll make the tree threaded for better iteration.) cool :)
grignaak Joined: 05/25/07 Posts: 5	Posted: 07/03/08 13:18:07 -- Modified: 07/04/08 10:52:10 by grignaak So, I have finally got through my internship and a few crazy semesters. But I am still faithful. Here is a threaded, top-down implementation of a RedBlackTree?. I also included TreeSet?, TreeBag?, and TreeMap? with a short jump to a TreeMultiMap?. It is the only threaded, top-down implementation I know of. The code is at http://codepad.org/jyb5EmJu (unfortuneatly, codepad uses phobos). I got this compatible with the collections library, but not the containers library---I just noticed it last night. I could port it over to the containers (but I didn't see too much of an interface). What do you think? --Michael PS. I did some experiments between a top-down and a bottom-up approach, and the top-down approach is 2x faster--imperceptible as it is to the human: shaves off a second for 100,000 inserts).
larsivi Joined: 03/27/04 Posts: 392	Posted: 07/04/08 14:57:52 The new containers are meant to simplify the somewhat cumbersome interface of the collection package, and the only real of interest is the one in container.model.IContainer. collection will probably be kept somewhere, but it will be deprecated in Tango in favour of the container package, so depending on what you want, you may have to look closer at that one? In any case, thanks for the effort :) As for codepad.org, it did use to have Tango with Tangobos installed, but I don't know which version of Tango that is currently there, neither whether there's been any changes recently.
torhu Joined: 03/30/06 Posts: 24	Posted: 07/04/08 16:17:33 -- Modified: 07/04/08 16:18:22 by torhu http://codepad.org/zLIDz7Zx codepad.org uses 0.99.4 and dmd 1.026. So it's time to upgrade...
larsivi Joined: 03/27/04 Posts: 392	Posted: 07/04/08 16:34:10 torhu: Maybe you can help with contacting the people responsible after 0.99.7 is released? (next few days)
grignaak Joined: 05/25/07 Posts: 5	Posted: 07/04/08 23:17:26 Sure thing (re. looking at the new containers) Actually, I am willing to do the whole containers library if you need a hand at it---I know some of you prefer lower-level stuff and I love data structures. I don't know what you are looking for in your containers library. I cold find precious little with google; just a couple references to past threads about stl vs java-isms and iterators (but I couldn't find the threads). My 2 bits in regards to what I think the threads were discussing: Concerning stl iterators: if you need an iterator to stop at a certain portion of a container, an iterator of a slice would do nicely, but that creates an extra referential object (although it does share the internal structure). Java does this with, for example, List.subList(). Concerning stl templates vs java interfaces: I really liked the view-only interfaces available through the interfaces. I saw one complaint that you could upcast to a mutable version so he suggested const methods; but you cold also upcast to a non-const version as well. I suggest having a limited view through interfaces that allow for iteration, containment checking, etc. and have the rest implement in the stl-style. Of course it's not entirely up to me, yet as soon as it gets discussed, we'll get M views from N people (where M >= N). Anyway, a thought stream. --Michael Happy 4th for you Americans out there. Happy 1st to you Canadians.
kris Joined: 03/27/04 Posts: 388	Posted: 07/04/08 23:52:25 nice :) Have you looked at "left leaning trees" yet? The design looks to be very much simplified, and thus considerably faster than RedBlack? trees ... just a thought to pass along. Also, we intend to add the read-only views when time permits. I find them to be a useful asset too. If you can come up with a set of containers that have similar functionality, are simple to use and are faster too, then we'd certainly be interested in them. Thanks for offering and, as you pointed out, it's easy to get lost trying to satisfy everyone's ideals :)