apasel422 / tree Goto Github PK

This applies to all insertion methods.

It doesn't need to be a usize.

To allow for things like order statistic trees.

This requires modifying ordered_iter to support comparators.

Every method should have quickcheck tests.

• remove_pred
• remove_succ
• pred_entry
• succ_entry

There's a method in Vec called iter_mut(). It is essentially iter() but with mutable references.

This would shrink the Iter struct from one byte of overhead per node to two bits per node. Unfortunately, BitVec doesn't seem to support deque usage.

This would allow an item to be examined before deciding whether to remove it.

They do not maintain the Andersson tree level invariants.

Would it be possible to implement an iterator using Morris Traversal?

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and perform the inorder-operation on the data using these links, and finally revert the changes to restore original tree.

http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

As tree is modified through the traversal, it might be necessary to implement Drop-Trait for Map or Set, to ensure the tree is restored even if iterator does not reach the "end".

TreeMap should implement {PartialEq, Eq, PartialOrd, Ord}, but this needs to be reconciled with comparators.

• Map::max_entry
• Map::min_entry
• Map::pred_entry
• Map::succ_entry
• Set::entry
• Set::max_entry
• Set::min_entry
• Set::pred_entry
• Set::succ_entry

• TreeMap::pred_mut
• TreeMap::pred_or_eq_mut
• TreeMap::succ_mut
• TreeMap::succ_or_eq_mut

In rust-lang/rust#42496, methods min and max were added to the Ord trait.

These methods are shadowing the inherent min and max on Set and Map (see: rust-lang/rust#43682), and unfortunately don't have the same signature, and there doesn't seem to be a single obvious fix for tree.

The easiest thing to do is rename Map.min/max and Set.min/max or just remove those methods. It might also be possible to design around the issue by exposing the min and max functions on a type that doesn't implement Ord. Maybe something like Map.find().min() and Map.find_mut().min()?

This could simplify a lot of code, but the only solution I'm aware of involves twice the memory usage: maintaining two stacks.

• difference
• intersection
• union
• symmetric_difference