Struct immutable_chunkmap::set::Set

source ·

pub struct Set<K: Ord + Clone>(_);

Expand description

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::Set;

let m =
   Set::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§

source §

impl<K> Set<K>where
K: Ord + Clone,

source

pub fn new() -> Self

Create a new empty set

source

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::Set;

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

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

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

source

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.

source

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.

source

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.

source

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.

source

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.

source

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

source

pub fn union(&self, other: &Set<K>) -> 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::Set;

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

source

pub fn intersect(&self, other: &Set<K>) -> 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::Set;

let s0 = Set::from_iter(0..100); let s1 = Set::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)); } }

source

pub fn len(&self) -> usize

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

source

pub fn range<'a, Q>(
 &'a self,
 lbound: Bound<Q>,
 ubound: Bound<Q>
) -> SetIter<'a, Q, K> ⓘ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