Struct immutable_chunkmap::set::Set

pub struct Set<K: Ord + Clone, const SIZE: usize>(_);

This set uses a similar strategy to BTreeSet to ensure cache efficient performance on modern hardware while still providing log(N) get, insert, and remove operations.

Examples

use std::string::String;
use self::immutable_chunkmap::set::SetM;

let m =
   SetM::new()
   .insert(String::from("1")).0
   .insert(String::from("2")).0
   .insert(String::from("3")).0;

assert_eq!(m.contains("1"), true);
assert_eq!(m.contains("2"), true);
assert_eq!(m.contains("3"), true);
assert_eq!(m.contains("4"), false);

for k in &m { println!("{}", k) }

Implementations

impl<K, const SIZE: usize> Set<K, SIZE>where
    K: Ord + Clone,

pub fn new() -> Self

Create a new empty set

Examples found in repository

src/set.rs (line 92)

    fn default() -> Set<K, SIZE> {
        Set::new()
    }
}

impl<K, const SIZE: usize> PartialEq for Set<K, SIZE>
where
    K: Ord + Clone,
{
    fn eq(&self, other: &Set<K, SIZE>) -> bool {
        self.0 == other.0
    }
}

impl<K, const SIZE: usize> Eq for Set<K, SIZE> where K: Eq + Ord + Clone {}

impl<K, const SIZE: usize> PartialOrd for Set<K, SIZE>
where
    K: Ord + Clone,
{
    fn partial_cmp(&self, other: &Set<K, SIZE>) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}

impl<K, const SIZE: usize> Ord for Set<K, SIZE>
where
    K: Ord + Clone,
{
    fn cmp(&self, other: &Set<K, SIZE>) -> Ordering {
        self.0.cmp(&other.0)
    }
}

impl<K, const SIZE: usize> Debug for Set<K, SIZE>
where
    K: Debug + Ord + Clone,
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        f.debug_set().entries(self.into_iter()).finish()
    }
}

impl<K, const SIZE: usize> FromIterator<K> for Set<K, SIZE>
where
    K: Ord + Clone,
{
    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
        Set::new().insert_many(iter)
    }

pub fn downgrade(&self) -> WeakSetRef<K, SIZE>

Create a weak reference to this set

pub fn strong_count(&self) -> usize

Return the number of strong references to this set (see Arc)

pub fn weak_count(&self) -> usize

Return the number of weak references to this set (see Arc)

pub fn insert_many<E: IntoIterator<Item = K>>(&self, elts: E) -> Self

This will insert many elements at once, and is potentially a lot faster than inserting one by one, especially if the data is sorted.

#Examples

 use self::immutable_chunkmap::set::SetM;

 let mut v = vec![1, 10, -12, 44, 50];
 v.sort_unstable();

 let m = SetM::new().insert_many(v.iter().map(|k| *k));

 for k in &v {
   assert_eq!(m.contains(k), true)
 }

Examples found in repository

src/set.rs (line 139)

    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
        Set::new().insert_many(iter)
    }

pub fn remove_many<Q, E>(&self, elts: E) -> Selfwhere
    Q: Ord,
    K: Borrow<Q>,
    E: IntoIterator<Item = Q>,

Remove multiple elements in a single pass. Similar performance to insert_many.

pub fn update_many<Q, E, F>(&self, elts: E, f: F) -> Selfwhere
    Q: Ord,
    K: Borrow<Q>,
    E: IntoIterator<Item = Q>,
    F: FnMut(Q, Option<&K>) -> Option<K>,

This is just slightly wierd, however if you have a bunch of borrowed forms of members of the set, and you want to look at the real entries and possibly add/update/remove them, then this method is for you.

pub fn insert(&self, k: K) -> (Self, bool)

return a new set with k inserted into it. If k already exists in the old set return true, else false. If the element already exists in the set memory will not be allocated.

pub fn insert_cow(&mut self, k: K) -> bool

insert k with copy on write semantics. if self is a unique reference to the set, then k will be inserted in place. Otherwise, only the parts of the set necessary to insert k will be copied, and then the copies will be mutated. self will share all the parts that weren’t modfied with any previous clones.

pub fn contains<'a, Q>(&'a self, k: &Q) -> boolwhere
    Q: ?Sized + Ord,
    K: Borrow<Q>,

return true if the set contains k, else false. Runs in log(N) time and constant space. where N is the size of the set.

Examples found in repository

src/set.rs (line 356)

    pub fn insert(&self, k: K) -> (Self, bool) {
        if self.contains(&k) {
            (self.clone(), true)
        } else {
            (Set(self.0.insert(k, ()).0), false)
        }
    }

pub fn get<'a, Q>(&'a self, k: &Q) -> Option<&K>where
    Q: ?Sized + Ord,
    K: Borrow<Q>,

return a reference to the item in the set that is equal to the given value, or None if no such value exists.

pub fn remove<Q: Sized + Ord>(&self, k: &Q) -> (Self, bool)where
    K: Borrow<Q>,

return a new set with k removed. Runs in log(N) time and log(N) space, where N is the size of the set

pub fn remove_cow<Q: Sized + Ord>(&mut self, k: &Q) -> boolwhere
    K: Borrow<Q>,

remove k from the set in place with copy on write semantics (see insert_cow). return true if k was in the set.

pub fn union(&self, other: &Set<K, SIZE>) -> Self

return the union of 2 sets. Runs in O(log(N) + M) time and space, where N is the largest of the two sets, and M is the number of chunks that intersect, which is roughly proportional to the size of the intersection.

Examples

use std::iter::FromIterator;
use self::immutable_chunkmap::set::SetM;

let s0 = SetM::from_iter(0..10);
let s1 = SetM::from_iter(5..15);
let s2 = s0.union(&s1);
for i in 0..15 {
    assert!(s2.contains(&i));
}

pub fn intersect(&self, other: &Set<K, SIZE>) -> Self

return the intersection of 2 sets. Runs in O(log(N) + M) time and space, where N is the smallest of the two sets, and M is the number of intersecting chunks.

Examples

use std::iter::FromIterator; use self::immutable_chunkmap::set::SetM;

let s0 = SetM::from_iter(0..100); let s1 = SetM::from_iter(20..50); let s2 = s0.intersect(&s1);

assert!(s2.len() == 30); for i in 0..100 { if i < 20 || i >= 50 { assert!(!s2.contains(&i)); } else { assert!(s2.contains(&i)); } }

pub fn diff(&self, other: &Set<K, SIZE>) -> Selfwhere
    K: Debug,

Return the difference of two sets. Runs in O(log(N) + M) time and space, where N is the smallest of the two sets, and M is the number of intersecting chunks.

Examples

use std::iter::FromIterator;
use self::immutable_chunkmap::set::SetM;

let s0 = SetM::from_iter(0..100);
let s1 = SetM::from_iter(0..50);
let s2 = s0.diff(&s1);

assert!(s2.len() == 50);
for i in 0..50 {
    assert!(!s2.contains(&i));
}
for i in 50..100 {
    assert!(s2.contains(&i));
}

pub fn len(&self) -> usize

get the number of elements in the map O(1) time and space

pub fn range<'a, Q>(
    &'a self,
    lbound: Bound<Q>,
    ubound: Bound<Q>
) -> SetIter<'a, Q, K, SIZE> where
    Q: Ord,
    K: 'a + Clone + Ord + Borrow<Q>,

return an iterator over the subset of elements in the set that are within the specified range.

The returned iterator runs in O(log(N) + M) time, and constant space. N is the number of elements in the tree, and M is the number of elements you examine.

if lbound >= ubound the returned iterator will be empty

Trait Implementations

impl<K: Clone + Ord + Clone, const SIZE: usize> Clone for Set<K, SIZE>

fn clone(&self) -> Set<K, SIZE>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, const SIZE: usize> Debug for Set<K, SIZE>where
    K: Debug + Ord + Clone,

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

Formats the value using the given formatter.

impl<K, const SIZE: usize> Default for Set<K, SIZE>where
    K: Ord + Clone,

fn default() -> Set<K, SIZE>

Returns the “default value” for a type.

impl<K, const SIZE: usize> FromIterator<K> for Set<K, SIZE>where
    K: Ord + Clone,

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

Creates a value from an iterator.

impl<K, const SIZE: usize> Hash for Set<K, SIZE>where
    K: Hash + Ord + Clone,

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,
    Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<'a, K, const SIZE: usize> IntoIterator for &'a Set<K, SIZE>where
    K: 'a + Ord + Clone,

type Item = &'a K

The type of the elements being iterated over.

type IntoIter = SetIter<'a, K, K, SIZE>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, const SIZE: usize> Ord for Set<K, SIZE>where
    K: Ord + Clone,

fn cmp(&self, other: &Set<K, SIZE>) -> Ordering

This method returns an Ordering between self and other.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl<K, const SIZE: usize> PartialEq<Set<K, SIZE>> for Set<K, SIZE>where
    K: Ord + Clone,

fn eq(&self, other: &Set<K, SIZE>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, const SIZE: usize> PartialOrd<Set<K, SIZE>> for Set<K, SIZE>where
    K: Ord + Clone,

fn partial_cmp(&self, other: &Set<K, SIZE>) -> Option<Ordering>

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

fn lt(&self, other: &Rhs) -> bool

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

fn le(&self, other: &Rhs) -> bool

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

fn gt(&self, other: &Rhs) -> bool

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

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<K, const SIZE: usize> Eq for Set<K, SIZE>where
    K: Eq + Ord + Clone,