[rust-dev] purely function red-black tree

Steve Jenson stevej at fruitless.org
Tue Dec 18 16:55:35 PST 2012


Thanks, I started with this definition and implemented BaseIter for my
RBTree.

https://github.com/stevej/rustled/commit/85cf4340eb1c0b985e27a48fe2603e6b75ffcb45

size_hint returns None as I'm not tracking size. I think that's ok? It's
hard to tell from the BaseIter documentation.


On Mon, Dec 17, 2012 at 1:34 PM, Erick Tryzelaar
<erick.tryzelaar at gmail.com>wrote:

> Is it important for `traverse` to pass along an option type? Is it
> important to inform end users that a key has been deleted? Or is that
> implementation specific? If so, I suggest rewriting `traverse` to something
> like this (assuming this actually works):
>
>
>
> impl<K, V> RBMap<K, V>: iter::BaseIter<(&K, &V)> {
>
>
>   pure fn each(f: fn(&(&K, &V))) {
>     match *self {
>
>
>       Leaf => (),
>       Tree(_, left, ref key, maybe_value, right) => {
>
>
>         left.traverse(f);
>         match maybe_value {
>
>
>           Some(ref value) => f(&(key, value)),
>           None => {},
>
>
>         }
>         right.traverse(f);
>       }
>
>
>
>     }
>   }
> }
>
>
>
>
> On Mon, Dec 17, 2012 at 11:46 AM, Graydon Hoare <graydon at mozilla.com>wrote:
>
>> On 12-12-17 11:28 AM, Graydon Hoare wrote:
>> > On 12-12-14 03:51 PM, Steve Jenson wrote:
>> >> I recently ported Matt Might's Scala port of Okasaki's purely
>> functional
>> >> red-black tree to Rust and am looking for some feedback.
>> >>
>> >> https://github.com/stevej/rustled/blob/master/red_black_tree.rs
>> >>
>> >> I've written this for 0.4 and will update it with other feedback I've
>> >> received for 0.5 when that lands.
>> >
>> > Nice! The only things I'd ask are:
>> >
>> >   - I can't tell at a glance (sorry, RB-trees are always very subtle)
>> >     whether this is an LLRB. If not, could you make it so? It's likely
>> >     just a simplification to a couple of the functions.
>>
>> Er, except of course, there's also:
>>
>>   https://github.com/fawek/llrbt.rs
>>
>> I think we need some better coordination of library development :)
>>
>> -Graydon
>>
>> _______________________________________________
>> Rust-dev mailing list
>> Rust-dev at mozilla.org
>> https://mail.mozilla.org/listinfo/rust-dev
>>
>
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20121218/aec8ec76/attachment-0001.html>


More information about the Rust-dev mailing list