apasel422 / tree Goto Github PK
View Code? Open in Web Editor NEWAn ordered map and set based on a binary search tree.
Home Page: https://apasel422.github.io/tree/tree
An ordered map and set based on a binary search tree.
Home Page: https://apasel422.github.io/tree/tree
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.