Struct index_set::IndexSet

pub struct IndexSet<T> where
    T: ToIndex,  { /* fields omitted */ }

An ordered set that stores indices in a sparse bit field.

At first glance, IndexSet looks a lot like a normal set, however there is an important difference: rather than owning and storing elements, IndexSet only stores their indices. Thus IndexSet is less about storing elements, and more about logical groupings of elements; IndexSets do not take ownership of their elements, or even a reference to them, and elements can appear in multiple IndexSets at once.

Of course, to store items by index requires them to be indexable in the first place; IndexSet works with any type that implements ToIndex (and optionally FromIndex).

Examples

Basic usage:

use index_set::*;

struct User {
    id: u32,
    // And so on...
}

impl ToIndex for User {
    type Index = u32;

    #[inline]
    fn to_index(&self) -> u32 { self.id }
}

let alice = User { id: 0 };
let bob   = User { id: 1 };
let eve   = User { id: 2 };

let mut admin_users = IndexSet::<User>::new();
admin_users.insert(&alice);

let mut trusted_users = IndexSet::<User>::new();
trusted_users.insert(&alice);
trusted_users.insert(&bob);

assert_eq!(admin_users.contains(&alice), true);
assert_eq!(trusted_users.contains(&alice), true);
assert_eq!(trusted_users.contains(&bob), true);
assert_eq!(trusted_users.contains(&eve), false);

For types that implement FromIndex, IndexSet can iterate through the actual elements, working much like a normal collection:

use index_set::*;

#[derive(Debug, PartialEq, Eq)]
struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    #[inline]
    fn to_index(&self) -> u32 { self.0 }
}

impl FromIndex for Token {
    #[inline]
    fn from_index(index: u32) -> Option<Token> { Some(Token(index)) }
}

let mut token_set = IndexSet::<Token>::new();
token_set.insert(&Token(0));
token_set.insert(&Token(1));

let tokens: Vec<Token> = token_set.iter().collect();

assert_eq!(tokens, [Token(0), Token(1)]);

ToIndex and FromIndex are defined for all the primitive integer types:

use index_set::IndexSet;

let a: IndexSet<u32> = [0, 1, 2, 3, 4].iter().collect();
let b: IndexSet<u32> = [0, 2, 4, 6, 8].iter().collect();

let intersection: Vec<u32> = a.intersection(&b).collect();

assert_eq!(intersection, [0, 2, 4]);

ToIndex and FromIndex are defined for a few other useful types:

use index_set::IndexSet;
use std::net::Ipv4Addr;

let mut blacklist = IndexSet::<Ipv4Addr>::new();
blacklist.insert(&"127.0.0.1".parse().unwrap());

assert!(blacklist.contains(&"127.0.0.1".parse().unwrap()));

Methods

impl<T> IndexSet<T> where     T: ToIndex,

pub fn new() -> Self

Creates an empty set.

Examples

use index_set::IndexSet;

let set = IndexSet::<u32>::new();
assert_eq!(set.len(), 0);

pub fn from_indices<I>(iter: I) -> Self where     I: IntoIterator<Item = T::Index>,

Creates a set from an iterator of indices.

Panics

This method does not panic, but using it to insert an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic when iterating through the set.

Examples

use index_set::IndexSet;

let set = IndexSet::<u32>::from_indices([1, 2].iter().cloned());
assert!(set.contains_index(1));
assert!(set.contains_index(2));
assert!(!set.contains_index(3));

pub fn clear(&mut self)

Removes all elements from the set.

Examples

use index_set::IndexSet;

let mut set: IndexSet<_> = [1, 64].iter().collect();
assert_eq!(set.len(), 2);
set.clear();
assert_eq!(set.len(), 0);

pub fn contains(&self, element: &T) -> bool

Returns true if the set contains the given element.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();

assert!(!set.contains(&3));
set.insert(&3);
assert!(set.contains(&3));

pub fn contains_index(&self, index: T::Index) -> bool

Returns true if the set contains the given index.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();

assert!(!set.contains_index(3));
set.insert(&3);
assert!(set.contains_index(3));

pub fn insert(&mut self, element: &T) -> bool

Inserts the given element into the set, returning true if the set did not already contain the element.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();

assert_eq!(set.insert(&3), true);
assert_eq!(set.insert(&3), false);

pub fn insert_index(&mut self, index: T::Index) -> bool

Inserts the given index into the set, returning true if the set did not already contain the index.

Panics

This method does not panic, but using it to insert an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic when iterating through the set.

Examples

use index_set::IndexSet;

let mut set = IndexSet::<u32>::new();

assert_eq!(set.insert_index(3), true);
assert_eq!(set.insert_index(3), false);

pub fn remove(&mut self, element: &T) -> bool

Removes the given element from the set, returning true if the set previously contained the element.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();
set.insert(&42);

assert_eq!(set.remove(&42), true);
assert_eq!(set.remove(&42), false);

pub fn remove_index(&mut self, index: T::Index) -> bool

Removes the given index from the set, returning true if the set previously contained the index.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();
set.insert(&42);

assert_eq!(set.remove_index(42), true);
assert_eq!(set.remove_index(42), false);

pub fn len(&self) -> usize

Returns the number of elements in the set.

Examples

use index_set::IndexSet;

let set: IndexSet<_> = [1, 2, 3].iter().collect();
assert_eq!(set.len(), 3);

pub fn is_empty(&self) -> bool

Returns true if the set contains no eements.

Examples

use index_set::IndexSet;

let mut set = IndexSet::new();

assert!(set.is_empty());
set.insert(&42);
assert!(!set.is_empty());

Important traits for Indices<'a, T>

impl<'a, T> Iterator for Indices<'a, T> where
    T: ToIndex,  type Item = T::Index;

pub fn indices(&self) -> Indices<T>

Returns an iterator that yields the indices in the set, in ascending order.

Examples

use index_set::{IndexSet, ToIndex};

struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    fn to_index(&self) -> u32 { self.0 * 10 }
}

let mut set = IndexSet::new();
set.insert(&Token(1));
set.insert(&Token(2));
set.insert(&Token(3));

let indices: Vec<_> = set.indices().collect();
assert_eq!(indices, [10, 20, 30]);

Important traits for DifferenceIndices<'a, T>

impl<'a, T> Iterator for DifferenceIndices<'a, T> where
    T: ToIndex,  type Item = T::Index;

pub fn difference_indices<'a>(     &'a self,     other: &'a IndexSet<T> ) -> DifferenceIndices<'a, T>

Returns an iterator that yields the indices that are in self but not in other, in ascending order.

Examples

use index_set::{IndexSet, ToIndex};

struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    fn to_index(&self) -> u32 { self.0 * 10 }
}

let mut a = IndexSet::new();
a.insert(&Token(1));
a.insert(&Token(2));

let mut b = IndexSet::new();
b.insert(&Token(2));
b.insert(&Token(3));

let difference: Vec<_> = a.difference_indices(&b).collect();
assert_eq!(difference, [10]);

Important traits for SymmetricDifferenceIndices<'a, T>

impl<'a, T> Iterator for SymmetricDifferenceIndices<'a, T> where
    T: ToIndex,  type Item = T::Index;

pub fn symmetric_difference_indices<'a>(     &'a self,     other: &'a IndexSet<T> ) -> SymmetricDifferenceIndices<'a, T>

Returns an iterator that yields the indices that are in self or in other but not in both, in ascending order.

Examples

use index_set::{IndexSet, ToIndex};

struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    fn to_index(&self) -> u32 { self.0 * 10 }
}

let mut a = IndexSet::new();
a.insert(&Token(1));
a.insert(&Token(2));

let mut b = IndexSet::new();
b.insert(&Token(2));
b.insert(&Token(3));

let symmetric_difference: Vec<_> = a.symmetric_difference_indices(&b).collect();
assert_eq!(symmetric_difference, [10, 30]);

Important traits for IntersectionIndices<'a, T>

impl<'a, T> Iterator for IntersectionIndices<'a, T> where
    T: ToIndex,  type Item = T::Index;

pub fn intersection_indices<'a>(     &'a self,     other: &'a IndexSet<T> ) -> IntersectionIndices<'a, T>

Returns an iterator that yields the indices that are in both self and other, in ascending order.

Examples

use index_set::{IndexSet, ToIndex};

struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    fn to_index(&self) -> u32 { self.0 * 10 }
}

let mut a = IndexSet::new();
a.insert(&Token(1));
a.insert(&Token(2));

let mut b = IndexSet::new();
b.insert(&Token(2));
b.insert(&Token(3));

let intersection: Vec<_> = a.intersection_indices(&b).collect();
assert_eq!(intersection, [20]);

Important traits for UnionIndices<'a, T>

impl<'a, T> Iterator for UnionIndices<'a, T> where
    T: ToIndex,  type Item = T::Index;

pub fn union_indices<'a>(     &'a self,     other: &'a IndexSet<T> ) -> UnionIndices<'a, T>

Returns an iterator that yields the indices that are in either self or other, in ascending order.

Examples

use index_set::{IndexSet, ToIndex};

struct Token(u32);

impl ToIndex for Token {
    type Index = u32;

    fn to_index(&self) -> u32 { self.0 * 10 }
}

let mut a = IndexSet::new();
a.insert(&Token(1));
a.insert(&Token(2));

let mut b = IndexSet::new();
b.insert(&Token(2));
b.insert(&Token(3));

let union: Vec<_> = a.union_indices(&b).collect();
assert_eq!(union, [10, 20, 30]);

pub fn is_disjoint(&self, other: &IndexSet<T>) -> bool

Returns true if self and other do not contain any of the same elements.

Examples

use index_set::IndexSet;

let mut a: IndexSet<_> = [1, 2, 3].iter().collect();
let b: IndexSet<_> = [4, 5, 6].iter().collect();

assert!(a.is_disjoint(&b));
a.insert(&4);
assert!(!a.is_disjoint(&b));

pub fn is_subset(&self, other: &IndexSet<T>) -> bool

Returns true if other contains at least all the elements in self.

Examples

use index_set::IndexSet;

let mut a: IndexSet<_> = [1, 2].iter().collect();
let b: IndexSet<_> = [1, 2, 3].iter().collect();

assert!(a.is_subset(&b));
a.insert(&4);
assert!(!a.is_subset(&b));

pub fn is_superset(&self, other: &IndexSet<T>) -> bool

Returns true if self contains at least all the elements in other.

Examples

use index_set::IndexSet;

let mut a: IndexSet<_> = [1, 2].iter().collect();
let b: IndexSet<_> = [1, 2, 3].iter().collect();

assert!(b.is_superset(&a));
a.insert(&4);
assert!(!b.is_superset(&a));

pub fn extend_indices<I>(&mut self, iter: I) where     I: IntoIterator<Item = T::Index>,

Inserts the indices in the iterator into the set.

Panics

This method does not panic, but using it to insert an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic when iterating through the set.

Examples

use index_set::IndexSet;

let mut set = IndexSet::<u32>::new();
set.extend_indices([1, 2].iter().cloned());

assert!(set.contains_index(1));
assert!(set.contains_index(2));
assert!(!set.contains_index(3));

impl<T> IndexSet<T> where     T: FromIndex,

pub fn iter(&self) -> Iter<T>

Returns an iterator that yields the elements in the set, in ascending order.

If T does not implement FromIndex, then you will need to use the indices method instead.

Panics

Iterating through a set that contains an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic.

Examples

use index_set::IndexSet;

let set: IndexSet<_> = [3, 1, 2].iter().collect();

let mut iter = set.iter();
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), None);

pub fn difference<'a>(&'a self, other: &'a IndexSet<T>) -> Difference<'a, T>

Returns an iterator that yields the elements that are in self but not in other, in ascending order.

If T does not implement FromIndex, then you will need to use the difference_indices or sub methods instead.

Panics

Iterating through a set that contains an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 1000, 2000].iter().collect();
let b: IndexSet<_> = [2, 3, 2000, 3000].iter().collect();

let difference: Vec<_> = a.difference(&b).collect();
assert_eq!(difference, [1, 1000]);

pub fn symmetric_difference<'a>(     &'a self,     other: &'a IndexSet<T> ) -> SymmetricDifference<'a, T>

Returns an iterator that yields the elements that are in self or in other but not in both, in asccending order.

If T does not implement FromIndex, then you will need to use the symmetric_difference_indices or bitxor methods instead.

Panics

Iterating through a set that contains an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 1000, 2000].iter().collect();
let b: IndexSet<_> = [2, 3, 2000, 3000].iter().collect();

let symmetric_difference: Vec<_> = a.symmetric_difference(&b).collect();
assert_eq!(symmetric_difference, [1, 3, 1000, 3000]);

pub fn intersection<'a>(&'a self, other: &'a IndexSet<T>) -> Intersection<'a, T>

Returns an iterator that yields the elements that are in both self and other, in asccending order.

If T does not implement FromIndex, then you will need to use the intersection_indices or bitand methods instead.

Panics

Iterating through a set that contains an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 1000, 2000].iter().collect();
let b: IndexSet<_> = [2, 3, 2000, 3000].iter().collect();

let intersection: Vec<_> = a.intersection(&b).collect();
assert_eq!(intersection, [2, 2000]);

pub fn union<'a>(&'a self, other: &'a IndexSet<T>) -> Union<'a, T>

Returns an iterator that yields the elements that are in either self or other, in asccending order.

If T does not implement FromIndex, then you will need to use the union_indices or bitor methods instead.

Panics

Iterating through a set that contains an invalid index (i.e. one for which FromIndex::from_index returns None) will cause a panic.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 1000, 2000].iter().collect();
let b: IndexSet<_> = [2, 3, 2000, 3000].iter().collect();

let union: Vec<_> = a.union(&b).collect();
assert_eq!(union, [1, 2, 3, 1000, 2000, 3000]);

Trait Implementations

impl<T> IntoIterator for IndexSet<T> where     T: FromIndex,

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> where
    T: FromIndex,  type Item = T;

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a IndexSet<T> where     T: FromIndex,

type Item = T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T> Eq for IndexSet<T> where     T: ToIndex,

impl<T> Extend<T> for IndexSet<T> where     T: ToIndex,

fn extend<I>(&mut self, iter: I) where     I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

impl<'a, T> Extend<&'a T> for IndexSet<T> where     T: 'a + ToIndex + Clone,

fn extend<I>(&mut self, iter: I) where     I: IntoIterator<Item = &'a T>,

Extends a collection with the contents of an iterator.

impl<T> PartialOrd<IndexSet<T>> for IndexSet<T> where     T: ToIndex,

fn partial_cmp(&self, other: &IndexSet<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Default for IndexSet<T> where     T: ToIndex,

fn default() -> IndexSet<T>

Creates an empty set.

impl<T> PartialEq<IndexSet<T>> for IndexSet<T> where     T: ToIndex,

fn eq(&self, other: &IndexSet<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: Clone> Clone for IndexSet<T> where     T: ToIndex,     T::Index: Clone,

fn clone(&self) -> IndexSet<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Ord for IndexSet<T> where     T: ToIndex,

fn cmp(&self, other: &IndexSet<T>) -> Ordering

Compares the sets by comparing their indices lexicographically.

Examples

use index_set::IndexSet;

let mut a: IndexSet<_> = [1, 2, 4].iter().collect();
let mut b: IndexSet<_> = [2, 3, 4].iter().collect();

assert!(&a < &b);
b.insert(&1);
assert!(&a > &b);
a.insert(&3);
assert!(&a == &b);

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<T> Debug for IndexSet<T> where     T: ToIndex,

fn fmt(&self, fmt: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T> Hash for IndexSet<T> where     T: ToIndex,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where     H: Hasher,

Feeds a slice of this type into the given [Hasher].

impl<T, '_> Sub<&'_ IndexSet<T>> for &'_ IndexSet<T> where     T: ToIndex,

type Output = IndexSet<T>

The resulting type after applying the - operator.

fn sub(self, rhs: &IndexSet<T>) -> IndexSet<T>

Returns the difference of self and rhs.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 3].iter().collect();
let b: IndexSet<_> = [3, 4, 5].iter().collect();

assert_eq!(&a - &b, [1, 2].iter().collect());

impl<T, '_> BitAnd<&'_ IndexSet<T>> for &'_ IndexSet<T> where     T: ToIndex,

type Output = IndexSet<T>

The resulting type after applying the & operator.

fn bitand(self, rhs: &IndexSet<T>) -> IndexSet<T>

Returns the intersection of self and rhs.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 3].iter().collect();
let b: IndexSet<_> = [3, 4, 5].iter().collect();

assert_eq!(&a & &b, [3].iter().collect());

impl<T, '_> BitOr<&'_ IndexSet<T>> for &'_ IndexSet<T> where     T: ToIndex,

type Output = IndexSet<T>

The resulting type after applying the | operator.

fn bitor(self, rhs: &IndexSet<T>) -> IndexSet<T>

Returns the union of self and rhs.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 3].iter().collect();
let b: IndexSet<_> = [3, 4, 5].iter().collect();

assert_eq!(&a | &b, [1, 2, 3, 4, 5].iter().collect());

impl<T, '_> BitXor<&'_ IndexSet<T>> for &'_ IndexSet<T> where     T: ToIndex,

type Output = IndexSet<T>

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &IndexSet<T>) -> IndexSet<T>

Returns the symmetric difference of self and rhs.

Examples

use index_set::IndexSet;

let a: IndexSet<_> = [1, 2, 3].iter().collect();
let b: IndexSet<_> = [3, 4, 5].iter().collect();

assert_eq!(&a ^ &b, [1, 2, 4, 5].iter().collect());

impl<T> FromIterator<T> for IndexSet<T> where     T: ToIndex,

fn from_iter<I>(iter: I) -> IndexSet<T> where     I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<'a, T> FromIterator<&'a T> for IndexSet<T> where     T: 'a + ToIndex + Clone,

fn from_iter<I>(iter: I) -> IndexSet<T> where     I: IntoIterator<Item = &'a T>,

Creates a value from an iterator.