Struct rbtset::RBTreeSet

pub struct RBTreeSet<T> { /* fields omitted */ }

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>

pub fn new() -> RBTreeSet<T>

Makes a new RBTreeSet.

pub fn get(&self, data: &T) -> Option<T> where
    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>>

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

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)

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>>

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>)

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>>

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>>

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

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

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>

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>

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> where
    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> where
    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, 

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, 

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>

pub fn clone(&self) -> Self

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for RBTreeSet<T>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for RBTreeSet<T>

pub fn default() -> RBTreeSet<T>

Returns the "default value" for a type.

impl<T: Ord> FromIterator<T> for RBTreeSet<T>

pub fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.