mozilla/rust — pull request #4487 by thestinger (2013-01-14 16:11:56+00:00)
Title: (work in progress!) replace treemap with a balanced tree

This is a full replacement for TreeMap as a balanced tree ([AA Tree](https://en.wikipedia.org/wiki/AA_tree)). I started from scratch so there aren't many similarities with the old implementation.

I'm happy with the quality of *most* of the code now, except for `remove` which is a mess. There are various FIXMEs and TODOs left to deal with and some bells and whistles to implement, but the fundamentals are there and I'm not aware of any bugs.

Improvements over the old implementation:

* neither the key or value type needs to implement `Copy` or `Clone` (only uses moves) and there's no usage of `@`
* insert, find and remove are O(log n) in the worst case instead of O(n)

There's also a `TreeSet` wrapper around it, which will expose `O(n)` (worst case) implementations of set difference, symmetric difference, intersection and union (not implemented yet, only the API is worked out).

The main remaining task is implementing lazy iteration, which is needed to make `Eq` and the set methods `O(n)` as they should be (iterating through both sets in-order).

In the future someone might want to replace this with a full red-black tree, but I think the performance will be pretty competitive as-is. The constant factor for insertion is likely a bit higher than a full rbtree implementation, but searching will be a bit quicker since the tree gets a bit more balanced.