[−][src]Struct rbtset::RBTreeSet
A set based on a RB-Tree for efficient operations.
This implementation tries to be equally efficient for search, insert and delete
operations. Being based on a RB-Tree performing any of these operations is
O(log n)
for an O(n)
space complexity.
It is possible to iterate on a specific part of the set providing a Node
reference using iter_from or values_from avoiding unnecessary operations.
This data structure is made with very long usage in mind, think loads of operations, and allows to optimize inner complexity and memory usage on demand providing the stored data implements Consecutive. See repack for more informations.
Like most of set implementations an RBTreeSet
keeps its element sorted at
any time.
Examples
use rbtset::RBTreeSet; // Type inference lets us omit an explicit type signature (which // would be `RBTreeSet<isize>` in this example). let mut numbers = RBTreeSet::new(); // Add some numbers. numbers.insert(2); numbers.insert(11); numbers.insert(6); numbers.insert(10); numbers.insert(26); numbers.insert(7); numbers.insert(18); numbers.insert(8); numbers.insert(13); numbers.insert(22); // Check for a specific one. if numbers.get(&101).is_none() { println!("We have {} numbers, but 101 ain't one.", numbers.len()); } // Remove a number. numbers.remove(&26); // Iterate over everything. for number in numbers.values() { println!("{}", number); }
Implementations
impl<T: Ord> RBTreeSet<T>
[src]
pub fn new() -> RBTreeSet<T>
[src]
Makes a new RBTreeSet
.
pub fn get(&self, data: &T) -> Option<T> where
T: Clone,
[src]
T: Clone,
Returns the value in the set, if any, that is matching the given value.
Use get_node in pair with Node::data if you want to avoid value cloning.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [1, 2, 3].iter().cloned().collect(); assert_eq!(set.get(&2), Some(2)); assert_eq!(set.get(&4), None);
pub fn insert(&mut self, data: T) -> Option<Node<T>>
[src]
Adds a value to the set.
If the set did not have a matching value present, the new node is returned.
If the set did have a matching value present, None is returned, and the entry is not updated.
Examples
use rbtset::RBTreeSet; let mut set = RBTreeSet::new(); assert!(set.insert(2).is_some()); assert!(set.insert(2).is_none()); assert_eq!(set.len(), 1);
pub fn remove(&mut self, data: &T) -> bool
[src]
Removes a matching value from the set. Returns whether a matching value was present in the set.
Examples
use rbtset::RBTreeSet; let mut set = RBTreeSet::new(); set.insert(2); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false);
pub fn clear(&mut self)
[src]
Clears the set, removing all values.
Examples
use rbtset::RBTreeSet; let mut v = RBTreeSet::new(); v.insert(1); v.clear(); assert!(v.is_empty());
pub fn get_node(&self, data: &T) -> Option<Node<T>>
[src]
Returns the node in the set, if any, that is matching the given value.
If the value is cheap to clone get should be more convenient to use.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [1, 2, 3].iter().cloned().collect(); assert_eq!(*set.get_node(&2).unwrap().data(), 2); assert_eq!(set.get_node(&4), None);
pub fn remove_node(&mut self, node: &mut Node<T>)
[src]
Removes a node from the set. This method expects a matching node to be present in the set.
Examples
use rbtset::RBTreeSet; let mut set = RBTreeSet::new(); set.insert(2); let mut node = set.get_node(&2).unwrap(); set.remove_node(&mut node); assert!(set.is_empty());
pub fn first(&self) -> Option<Node<T>>
[src]
Returns the first node of the set if not empty.
Examples
use rbtset::RBTreeSet; let mut set: RBTreeSet<_> = [1, 2, 3].iter().cloned().collect(); assert_eq!(*set.first().unwrap().data(), 1); set.clear(); assert_eq!(set.first(), None);
pub fn last(&self) -> Option<Node<T>>
[src]
Returns the last node of the set if not empty.
Examples
use rbtset::RBTreeSet; let mut set: RBTreeSet<_> = [1, 2, 3].iter().cloned().collect(); assert_eq!(*set.last().unwrap().data(), 3); set.clear(); assert_eq!(set.last(), None);
pub fn len(&self) -> usize
[src]
Returns the number of elements in the set.
Examples
use rbtset::RBTreeSet; let mut v = RBTreeSet::new(); assert_eq!(v.len(), 0); v.insert(1); assert_eq!(v.len(), 1);
pub fn is_empty(&self) -> bool
[src]
Returns true if the set contains no elements.
Examples
use rbtset::RBTreeSet; let mut v = RBTreeSet::new(); assert!(v.is_empty()); v.insert(1); assert!(!v.is_empty());
pub fn iter(&self) -> Iter<T>ⓘ
[src]
Gets an iterator that visits the nodes in the RBTreeSet in ascending order.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [3, 1, 2].iter().cloned().collect(); let mut set_iter = set.iter(); assert_eq!(*set_iter.next().unwrap().data(), 1); assert_eq!(*set_iter.next().unwrap().data(), 2); assert_eq!(*set_iter.next().unwrap().data(), 3); assert_eq!(set_iter.next(), None);
pub fn iter_from(&self, node: &Node<T>) -> Iter<T>ⓘ
[src]
Gets an iterator that visits the nodes in the RBTreeSet in ascending order, starting at the given node.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [3, 1, 2].iter().cloned().collect(); let node = set.get_node(&2).unwrap(); let mut set_iter = set.iter_from(&node); assert_eq!(*set_iter.next().unwrap().data(), 2); assert_eq!(*set_iter.next().unwrap().data(), 3); assert_eq!(set_iter.next(), None);
pub fn values(&self) -> IterValues<T>ⓘNotable traits for IterValues<T>
impl<T: Clone + Ord> Iterator for IterValues<T> type Item = T;
where
T: Clone,
[src]
Notable traits for IterValues<T>
impl<T: Clone + Ord> Iterator for IterValues<T> type Item = T;
T: Clone,
Gets an iterator that visit the nodes values in the RBTreeSet in ascending order.
This iterator clones the values. Use iter in pair with Node::data if you want to avoid the cloning.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [3, 1, 2].iter().cloned().collect(); let mut set_values = set.values(); assert_eq!(set_values.next(), Some(1)); assert_eq!(set_values.next(), Some(2)); assert_eq!(set_values.next(), Some(3)); assert_eq!(set_values.next(), None);
pub fn values_from(&self, node: &Node<T>) -> IterValues<T>ⓘNotable traits for IterValues<T>
impl<T: Clone + Ord> Iterator for IterValues<T> type Item = T;
where
T: Clone,
[src]
Notable traits for IterValues<T>
impl<T: Clone + Ord> Iterator for IterValues<T> type Item = T;
T: Clone,
Gets an iterator that visit the nodes values in the RBTreeSet in ascending order, starting at the given node.
This iterator clones the values. Use iter_from in pair with Node::data if you want to avoid the cloning.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = [3, 1, 2].iter().cloned().collect(); let node = set.get_node(&2).unwrap(); let mut set_values = set.values_from(&node); assert_eq!(set_values.next(), Some(2)); assert_eq!(set_values.next(), Some(3)); assert_eq!(set_values.next(), None);
pub fn repack(&mut self) where
T: Clone + Consecutive,
[src]
T: Clone + Consecutive,
Optimize the set by merging nodes where applicable while keeping the ordering.
Two nodes can be merged together when consecutive.
Examples
use std::cmp::Ordering; use rbtset::{Consecutive, RBTreeSet}; #[derive(Debug, Clone, Eq)] struct Seq(std::ops::Range<usize>); impl Ord for Seq { fn cmp(&self, other: &Seq) -> Ordering { self.0.start.cmp(&other.0.start) } } impl PartialOrd for Seq { fn partial_cmp(&self, other: &Seq) -> Option<Ordering> { Some(self.cmp(other)) } } impl PartialEq for Seq { fn eq(&self, other: &Seq) -> bool { other.0.start <= self.0.start && self.0.start < other.0.end } } impl Consecutive for Seq { fn consecutive(&self, other: &Seq) -> bool { self.0.end == other.0.start } fn merged(&self, other: &Seq) -> Seq { Seq(self.0.start..other.0.end) } } let mut set = RBTreeSet::new(); set.insert(Seq(1..3)); set.insert(Seq(5..8)); set.insert(Seq(8..13)); set.insert(Seq(13..16)); set.insert(Seq(23..26)); assert_eq!( set.values().collect::<Vec<Seq>>(), vec![Seq(1..3), Seq(5..8), Seq(8..13), Seq(13..16), Seq(23..26)] ); set.repack(); assert_eq!( set.values().collect::<Vec<Seq>>(), vec![Seq(1..3), Seq(5..16), Seq(23..26)] );
pub fn dump_tree_as_dot(&self) -> String where
T: Debug,
[src]
T: Debug,
Returns the serialization of the set as an RB-tree in DOT.
Examples
use rbtset::RBTreeSet; let set: RBTreeSet<_> = vec![2, 11, 22, 7].iter().cloned().collect(); print!("{}", set.dump_tree_as_dot());
Trait Implementations
impl<T: Clone> Clone for RBTreeSet<T>
[src]
pub fn clone(&self) -> Self
[src]
pub fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T> Debug for RBTreeSet<T>
[src]
impl<T: Default> Default for RBTreeSet<T>
[src]
impl<T: Ord> FromIterator<T> for RBTreeSet<T>
[src]
pub fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
Auto Trait Implementations
impl<T> !RefUnwindSafe for RBTreeSet<T>
[src]
impl<T> !Send for RBTreeSet<T>
[src]
impl<T> !Sync for RBTreeSet<T>
[src]
impl<T> Unpin for RBTreeSet<T>
[src]
impl<T> !UnwindSafe for RBTreeSet<T>
[src]
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> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
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>,