[−][src]Struct immutable_chunkmap::set::Set
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
impl<K> Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
pub fn new() -> Self
[src]
Create a new empty set
pub fn downgrade(&self) -> WeakSetRef<K>
[src]
Create a weak reference to this set
pub fn strong_count(&self) -> usize
[src]
Return the number of strong references to this set (see Arc)
pub fn weak_count(&self) -> usize
[src]
Return the number of weak references to this set (see Arc)
pub fn insert_many<E: IntoIterator<Item = K>>(&self, elts: E) -> Self
[src]
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) }
pub fn remove_many<Q, E>(&self, elts: E) -> Self where
Q: Ord,
K: Borrow<Q>,
E: IntoIterator<Item = Q>,
[src]
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) -> Self where
Q: Ord,
K: Borrow<Q>,
E: IntoIterator<Item = Q>,
F: FnMut(Q, Option<&K>) -> Option<K>,
[src]
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)
[src]
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 contains<'a, Q: ?Sized>(&'a self, k: &Q) -> bool where
Q: Ord,
K: Borrow<Q>,
[src]
Q: 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.
pub fn get<'a, Q: ?Sized>(&'a self, k: &Q) -> Option<&K> where
Q: Ord,
K: Borrow<Q>,
[src]
Q: 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>,
[src]
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 union(&self, other: &Set<K>) -> Self
[src]
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)); }
pub fn intersect(&self, other: &Set<K>) -> Self
[src]
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)); } }
pub fn diff(&self, other: &Set<K>) -> Self where
K: Debug,
[src]
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::Set; let s0 = Set::from_iter(0..100); let s1 = Set::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
[src]
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>ⓘ where
Q: Ord,
K: 'a + Clone + Ord + Borrow<Q>,
[src]
&'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
Trait Implementations
impl<K: Clone + Ord> Clone for Set<K>
[src]
impl<K> Debug for Set<K> where
K: Debug + Ord + Clone,
[src]
K: Debug + Ord + Clone,
impl<K> Default for Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
impl<K> Eq for Set<K> where
K: Eq + Ord + Clone,
[src]
K: Eq + Ord + Clone,
impl<K> FromIterator<K> for Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self
[src]
impl<K> Hash for Set<K> where
K: Hash + Ord + Clone,
[src]
K: Hash + Ord + Clone,
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<'a, K> IntoIterator for &'a Set<K> where
K: 'a + Borrow<K> + Ord + Clone,
[src]
K: 'a + Borrow<K> + Ord + Clone,
type Item = &'a K
The type of the elements being iterated over.
type IntoIter = SetIter<'a, K, K>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter
[src]
impl<K> Ord for Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
fn cmp(&self, other: &Set<K>) -> Ordering
[src]
#[must_use]fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn clamp(self, min: Self, max: Self) -> Self
[src]
impl<K> PartialEq<Set<K>> for Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
impl<K> PartialOrd<Set<K>> for Set<K> where
K: Ord + Clone,
[src]
K: Ord + Clone,
Auto Trait Implementations
impl<K> RefUnwindSafe for Set<K> where
K: RefUnwindSafe,
K: RefUnwindSafe,
impl<K> Send for Set<K> where
K: Send + Sync,
K: Send + Sync,
impl<K> Sync for Set<K> where
K: Send + Sync,
K: Send + Sync,
impl<K> Unpin for Set<K>
impl<K> UnwindSafe for Set<K> where
K: RefUnwindSafe,
K: RefUnwindSafe,
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>,