[−][src]Struct rb_tree::RBTree
A red black tree that can be used to store elements sorted by their PartialOrd provided ordering.
Implementations
impl<T: PartialOrd> RBTree<T>
[src]
pub fn new() -> RBTree<T>
[src]
Creates and returns a new RBTree.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(3); t.insert(2); assert_eq!(t.take(&2).unwrap(), 2);
pub fn clear(&mut self)
[src]
Clears all entries from the tree.
Example:
use rb_tree::RBTree; let mut tree = RBTree::new(); tree.insert(2); tree.insert(5); tree.clear(); assert_eq!(tree.len(), 0); assert!(!tree.contains(&2));
pub fn drain(&mut self) -> Drain<T>ⓘNotable traits for Drain<T>
impl<T: PartialOrd> Iterator for Drain<T> type Item = T;
[src]
Notable traits for Drain<T>
impl<T: PartialOrd> Iterator for Drain<T> type Item = T;
Clears the tree and returns all values as an iterator in their PartialOrd order.
Example:
use rb_tree::RBTree; let mut tree = RBTree::new(); tree.insert(2); tree.insert(5); assert_eq!(tree.len(), 2); let mut drain = tree.drain(); assert_eq!(drain.next().unwrap(), 2); assert_eq!(drain.next().unwrap(), 5); assert!(drain.next().is_none()); assert_eq!(tree.len(), 0);
pub fn ordered(&self) -> Vec<&T>
[src]
Returns a vector presenting the contained elements of the RBTree in the order by which they are prioritised (that is, in the in-order tree traversal order).
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(3); t.insert(1); t.insert(2); let order = t.ordered(); assert_eq!(*order[1], 2);
pub fn len(&self) -> usize
[src]
Returns the number of elements contained in the tree.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(3); t.insert(1); t.insert(2); assert_eq!(t.len(), 3); t.remove(&2); assert_eq!(t.len(), 2);
pub fn is_empty(&self) -> bool
[src]
Returns true if there are no items present in the tree, false otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); assert!(t.is_empty()); t.insert(3); assert!(!t.is_empty());
pub fn insert(&mut self, val: T) -> bool
[src]
Inserts a new element into the RBTree. Returns true if this item was not already in the tree, and false otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); assert_eq!(t.insert("Hello".to_string()), true); assert_eq!(t.insert("Hello".to_string()), false);
pub fn replace(&mut self, val: T) -> Option<T>
[src]
Inserts a new element into the RBTree. Returns None if this item was not already in the tree, and the previously contained item otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); assert_eq!(t.replace("Hello".to_string()), None); assert_eq!(t.replace("Hello".to_string()), Some("Hello".to_string()));
pub fn contains(&self, val: &T) -> bool
[src]
Returns true if the tree contains the specified item, false otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(2); assert!(!t.contains(&3)); assert!(t.contains(&2));
pub fn get<K: PartialOrd<T>>(&self, val: &K) -> Option<&T>
[src]
Returns the item specified if contained, None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(1); assert_eq!(*t.get(&1).unwrap(), 1); assert_eq!(t.get(&2), None);
pub fn take<K: PartialOrd<T>>(&mut self, val: &K) -> Option<T>
[src]
Removes an item the tree. Returns the matching item if it was contained in the tree, None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(4); t.insert(2); assert_eq!(t.take(&2).unwrap(), 2); assert_eq!(t.len(), 1); assert_eq!(t.take(&2), None);
pub fn remove<K: PartialOrd<T>>(&mut self, val: &K) -> bool
[src]
Removes an item the tree. Returns true if it was contained in the tree, false otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(4); t.insert(2); assert_eq!(t.remove(&2), true); assert_eq!(t.len(), 1); assert_eq!(t.remove(&2), false);
pub fn pop(&mut self) -> Option<T>
[src]
Removes the item at the front of the priority queue that the RBTree represents if any elements are present, or None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(2); t.insert(1); t.insert(3); assert_eq!(t.pop().unwrap(), 1);
pub fn peek(&self) -> Option<&T>
[src]
Peeks the item at the front of the priority queue that the RBTree represents if any elements are present, or None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(2); t.insert(1); t.insert(3); assert_eq!(*t.peek().unwrap(), 1);
pub fn pop_back(&mut self) -> Option<T>
[src]
Removes the item at the back of the priority queue that the RBTree represents if any elements are present, or None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(2); t.insert(1); t.insert(3); assert_eq!(t.pop_back().unwrap(), 3);
pub fn peek_back(&self) -> Option<&T>
[src]
Peeks the item at the back of the priority queue that the RBTree represents if any elements are present, or None otherwise.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(2); t.insert(1); t.insert(3); assert_eq!(*t.peek_back().unwrap(), 3);
pub fn iter(&self) -> Iter<'_, T>ⓘ
[src]
Returns an iterator over the elements contained in this RBTree.
Example:
use rb_tree::RBTree; let mut t = RBTree::new(); t.insert(3); t.insert(1); t.insert(5); assert_eq!(t.iter().collect::<Vec<&usize>>(), vec!(&1, &3, &5));
pub fn difference<'a>(&'a self, other: &'a RBTree<T>) -> Difference<'a, T>ⓘNotable traits for Difference<'a, T>
impl<'a, T: PartialOrd> Iterator for Difference<'a, T> type Item = &'a T;
[src]
Notable traits for Difference<'a, T>
impl<'a, T: PartialOrd> Iterator for Difference<'a, T> type Item = &'a T;
Returns an iterator representing the
difference between the items in this RBTree
and those in another RBTree, i.e. the values
in self
but not in other
.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..5).for_each(|v| {t2.insert(v);}); assert_eq!( t1.difference(&t2).collect::<Vec<&usize>>(), vec!(&0, &1) ); assert_eq!( t2.difference(&t1).collect::<Vec<&usize>>(), vec!(&3, &4) );
pub fn symmetric_difference<'a>(
&'a self,
other: &'a RBTree<T>
) -> SymmetricDifference<'a, T>ⓘNotable traits for SymmetricDifference<'a, T>
impl<'a, T: PartialOrd> Iterator for SymmetricDifference<'a, T> type Item = &'a T;
[src]
&'a self,
other: &'a RBTree<T>
) -> SymmetricDifference<'a, T>ⓘ
Notable traits for SymmetricDifference<'a, T>
impl<'a, T: PartialOrd> Iterator for SymmetricDifference<'a, T> type Item = &'a T;
Returns an iterator representing the
symmetric difference between the items
in this RBTree and those in another, i.e.
the values in self
or other
but not in both.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..5).for_each(|v| {t2.insert(v);}); assert_eq!( t1.symmetric_difference(&t2).collect::<Vec<&usize>>(), vec!(&0, &1, &3, &4) ); assert_eq!( t2.symmetric_difference(&t1).collect::<Vec<&usize>>(), vec!(&0, &1, &3, &4) );
pub fn intersection<'a>(&'a self, other: &'a RBTree<T>) -> Intersection<'a, T>ⓘNotable traits for Intersection<'a, T>
impl<'a, T: PartialOrd> Iterator for Intersection<'a, T> type Item = &'a T;
[src]
Notable traits for Intersection<'a, T>
impl<'a, T: PartialOrd> Iterator for Intersection<'a, T> type Item = &'a T;
Returns an iterator representing the intersection
of this RBTree and another, i.e. the values that
appear in both self
and other
.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..5).for_each(|v| {t2.insert(v);}); assert_eq!( t1.intersection(&t2).collect::<Vec<&usize>>(), vec!(&2) );
pub fn union<'a>(&'a self, other: &'a RBTree<T>) -> Union<'a, T>ⓘ
[src]
Returns an iterator representing the union of this RBTree and another, i.e. the values that appear in at least one of the RBTrees.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..5).for_each(|v| {t2.insert(v);}); assert_eq!( t1.union(&t2).collect::<Vec<&usize>>(), vec!(&0, &1, &2, &3, &4) );
pub fn is_disjoint(&self, other: &RBTree<T>) -> bool
[src]
Returns true if this RBTree and another are disjoint,
i.e. there are no values in self
that appear in other
and vice versa, false otherwise.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..5).for_each(|v| {t2.insert(v);}); assert!(!t1.is_disjoint(&t2)); t2.pop(); // remove '2' from t2 assert!(t1.is_disjoint(&t2));
pub fn is_subset(&self, other: &RBTree<T>) -> bool
[src]
Returns true if this RBTree is a subset of another,
i.e. at least all values in self
also appear in
other
, false otherwise.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); let mut t3 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..10).for_each(|v| {t2.insert(v);}); (3..7).for_each(|v| {t3.insert(v);}); assert!(!t1.is_subset(&t2)); assert!(t3.is_subset(&t2));
pub fn is_superset(&self, other: &RBTree<T>) -> bool
[src]
Returns true if this RBTree is a superset of another,
i.e. at least all values in other
also appear in
self
, false otherwise.
Example:
use rb_tree::RBTree; let mut t1 = RBTree::new(); let mut t2 = RBTree::new(); let mut t3 = RBTree::new(); (0..3).for_each(|v| {t1.insert(v);}); (2..10).for_each(|v| {t2.insert(v);}); (3..7).for_each(|v| {t3.insert(v);}); assert!(!t2.is_superset(&t1)); assert!(t2.is_superset(&t3));
pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F)
[src]
Retains in this RBTree only those values for which the passed closure returns true.
Example:
use rb_tree::RBTree; let mut t: RBTree<usize> = (0..10).collect(); t.retain(|v| v % 2 == 0); assert_eq!(t.iter().collect::<Vec<&usize>>(), vec!(&0, &2, &4, &6, &8));
Trait Implementations
impl<T: PartialOrd + Debug> Debug for RBTree<T>
[src]
impl<T: PartialOrd + Debug> Display for RBTree<T>
[src]
impl<T: PartialOrd> FromIterator<T> for RBTree<T>
[src]
pub fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
impl<T: PartialOrd> IntoIterator for RBTree<T>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for RBTree<T> where
T: RefUnwindSafe,
[src]
T: RefUnwindSafe,
impl<T> Send for RBTree<T> where
T: Send,
[src]
T: Send,
impl<T> Sync for RBTree<T> where
T: Sync,
[src]
T: Sync,
impl<T> Unpin for RBTree<T> where
T: Unpin,
[src]
T: Unpin,
impl<T> UnwindSafe for RBTree<T> where
T: UnwindSafe,
[src]
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToString for T where
T: Display + ?Sized,
[src]
T: Display + ?Sized,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,