[−][src]Struct hashbag::HashBag
A hash bag implemented as a HashMap
where the value is usize
.
A bag, unlike a set, allows duplicate values, and keeps track of how many duplicates each value holds. This type of collection is often referred to as an unordered multiset.
As with the HashMap
type, a HashBag
requires that the elements
implement the Eq
and Hash
traits. This can frequently be achieved by
using #[derive(PartialEq, Eq, Hash)]
. If you implement these yourself,
it is important that the following property holds:
k1 == k2 -> hash(k1) == hash(k2)
In other words, if two keys are equal, their hashes must be equal.
It is a logic error for an item to be modified in such a way that the
item's hash, as determined by the Hash
trait, or its equality, as
determined by the Eq
trait, changes while it is in the bag.
Examples
use hashbag::HashBag; // Type inference lets us omit an explicit type signature (which // would be `HashBag<String>` in this example). let mut books = HashBag::new(); // Add some books. // Since we are a library, we have many copies. books.insert("A Dance With Dragons".to_string()); books.insert("To Kill a Mockingbird".to_string()); books.insert("To Kill a Mockingbird".to_string()); books.insert("The Odyssey".to_string()); books.insert("The Odyssey".to_string()); books.insert("The Odyssey".to_string()); books.insert("The Great Gatsby".to_string()); books.insert("The Great Gatsby".to_string()); books.insert("The Great Gatsby".to_string()); books.insert("The Great Gatsby".to_string()); // When we count the number of books, duplicates are included. assert_eq!(books.len(), 10); // Check for a specific one. if books.contains("The Winds of Winter") == 0 { println!("We have {} books, but The Winds of Winter ain't one.", books.len()); } // Remove a book. let had_copies = books.remove("The Odyssey"); // Remove returns how many copies of that book we had. assert_eq!(had_copies, 3); // Iterate over everything. // Duplicates will be listed multiple times. for book in &books { println!("{}", book); } // Iterate over each distinct book. for (book, copies) in books.set_iter() { println!("{} ({} copies)", book, copies); } // Extract the books and their counts. for (book, copies) in books { println!("{} ({} copies)", book, copies); }
The easiest way to use HashBag
with a custom type is to derive
Eq
and Hash
. We must also derive PartialEq
, this will in the
future be implied by Eq
.
use hashbag::HashBag; #[derive(Hash, Eq, PartialEq, Debug, Clone)] struct Viking { name: String, power: usize, } let mut vikings = HashBag::new(); vikings.insert(Viking { name: "Einar".to_string(), power: 9 }); vikings.insert(Viking { name: "Einar".to_string(), power: 9 }); vikings.insert(Viking { name: "Olaf".to_string(), power: 4 }); vikings.insert(Viking { name: "Olaf".to_string(), power: 5 }); vikings.insert(Viking { name: "Harald".to_string(), power: 8 }); // Use derived implementation to print the vikings. // Notice that all duplicates are printed. for v in &vikings { println!("{:?}", v); } // Since the derived implementation compares all the fields, // vikings that share a name but not a power are not duplicates. for (v, n) in vikings.set_iter() { println!("{:?} ({} of them!)", v, n); } // HashBags themselves can also be compared for equality, // and will do so by considering both the values and their counts. let mut vikings2 = vikings.clone(); assert_eq!(vikings, vikings2); let fallen = vikings.iter().next().unwrap(); vikings2.remove(fallen); assert_ne!(vikings, vikings2); vikings2.insert(Viking { name: "Snorre".to_string(), power: 1 }); assert_ne!(vikings, vikings2);
A HashBag
with fixed list of elements can be initialized from an array:
use hashbag::HashBag; let mut viking_names: HashBag<&'static str> = [ "Einar", "Olaf", "Harald" ].iter().cloned().collect(); // use the values stored in the bag
You can also extend the bag easily:
use hashbag::HashBag; let mut vikings: HashBag<String> = HashBag::new(); vikings.extend(std::iter::once("Snorre".to_string())); assert_eq!(vikings.contains("Snorre"), 1); // You can extend with many instances at once: vikings.extend(std::iter::once(("Snorre".to_string(), 4))); assert_eq!(vikings.contains("Snorre"), 5); // Extension also works with reference iterators if the type is Clone: let einar = String::from("Einar"); vikings.extend(std::iter::once(&einar)); assert_eq!(vikings.contains(&einar), 1); // And extend with many instances at once: vikings.extend(std::iter::once((&einar, 4))); assert_eq!(vikings.contains(&einar), 5);
Implementations
impl<T: Hash + Eq> HashBag<T, RandomState>
[src]
pub fn new() -> HashBag<T, RandomState>
[src]
Creates an empty HashBag
.
The hash bag is initially created with a capacity of 0, so it will not allocate until it is first inserted into.
Examples
use hashbag::HashBag; let bag: HashBag<i32> = HashBag::new();
pub fn with_capacity(capacity: usize) -> HashBag<T, RandomState>
[src]
Creates an empty HashBag
with the specified capacity.
The hash bag will be able to hold at least capacity
distinct values without
reallocating. If capacity
is 0, the hash bag will not allocate.
Examples
use hashbag::HashBag; let bag: HashBag<i32> = HashBag::with_capacity(10); assert!(bag.capacity() >= 10);
impl<T, S> HashBag<T, S>
[src]
pub fn capacity(&self) -> usize
[src]
Returns the number of distinct values the bag can hold without reallocating.
Examples
use hashbag::HashBag; let bag: HashBag<i32> = HashBag::with_capacity(100); assert!(bag.capacity() >= 100);
pub fn iter(&self) -> Iter<T>ⓘ
[src]
An iterator visiting all elements in arbitrary order.
The iterator element type is &'a T
.
Duplicates are yielded as many times as they appear in the bag.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert("a"); bag.insert("b"); bag.insert("b"); // Will print in an arbitrary order. // b will be printed twice. for x in bag.iter() { println!("{}", x); }
pub fn set_iter(&self) -> SetIter<T>ⓘ
[src]
An iterator visiting all distinct elements in arbitrary order.
The iterator element type is (&'a T, usize)
.
Duplicated values are yielded once along with a count of the number of occurrences.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert("a"); bag.insert("b"); bag.insert("b"); // Will print in an arbitrary order. for (x, n) in bag.set_iter() { println!("{} {}", x, n); }
pub fn len(&self) -> usize
[src]
Returns the number of elements in the bag.
Duplicates are counted.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); assert_eq!(bag.len(), 0); bag.insert(1); assert_eq!(bag.len(), 1); bag.insert(1); assert_eq!(bag.len(), 2);
pub fn set_len(&self) -> usize
[src]
Returns the number of elements in the bag.
Duplicates are not counted.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); assert_eq!(bag.set_len(), 0); bag.insert(1); assert_eq!(bag.set_len(), 1); bag.insert(1); assert_eq!(bag.set_len(), 1);
pub fn is_empty(&self) -> bool
[src]
Returns true
if the bag contains no elements.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); assert!(bag.is_empty()); bag.insert(1); assert!(!bag.is_empty());
pub fn drain(&mut self) -> Drain<T>ⓘ
[src]
Clears the bag, returning all elements in an iterator.
Duplicates appear only in the count yielded for each element.
Examples
use hashbag::HashBag; let mut bag: HashBag<_> = [1, 2, 3, 3].iter().cloned().collect(); assert!(!bag.is_empty()); // prints // 1 1 // 2 1 // 3 2 // in an arbitrary order for (i, n) in bag.drain() { println!("{} {}", i, n); } assert!(bag.is_empty());
pub fn clear(&mut self)
[src]
Clears the bag, removing all values.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert(1); bag.clear(); assert!(bag.is_empty());
impl<T, S> HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher,
[src]
T: Eq + Hash,
S: BuildHasher,
pub fn with_hasher(hash_builder: S) -> HashBag<T, S>
[src]
Creates a new empty hash bag which will use the given hasher to hash keys.
The hash bag is also created with the default initial capacity.
Warning: hasher
is normally randomly generated, and
is designed to allow HashBag
s to be resistant to attacks that
cause many collisions and very poor performance. Setting it
manually using this function can expose a DoS attack vector.
Examples
use hashbag::HashBag; use std::collections::hash_map::RandomState; let s = RandomState::new(); let mut bag = HashBag::with_hasher(s); bag.insert(2);
pub fn with_capacity_and_hasher(
capacity: usize,
hash_builder: S
) -> HashBag<T, S>
[src]
capacity: usize,
hash_builder: S
) -> HashBag<T, S>
Creates an empty HashBag
with the specified capacity, using
hasher
to hash the keys.
The hash bag will be able to hold at least capacity
distinct values
without reallocating. If capacity
is 0, the hash bag will not allocate.
Warning: hasher
is normally randomly generated, and
is designed to allow HashBag
s to be resistant to attacks that
cause many collisions and very poor performance. Setting it
manually using this function can expose a DoS attack vector.
Examples
use hashbag::HashBag; use std::collections::hash_map::RandomState; let s = RandomState::new(); let mut bag = HashBag::with_capacity_and_hasher(10, s); bag.insert(1);
pub fn hasher(&self) -> &S
[src]
Returns a reference to the bag's BuildHasher
.
Examples
use hashbag::HashBag; use std::collections::hash_map::RandomState; let hasher = RandomState::new(); let bag: HashBag<i32> = HashBag::with_hasher(hasher); let hasher: &RandomState = bag.hasher();
pub fn reserve(&mut self, additional: usize)
[src]
Reserves capacity for at least additional
more distinct values
to be inserted in the HashBag
. The collection may reserve more
space to avoid frequent reallocations.
Panics
Panics if the new allocation size overflows usize
.
Examples
use hashbag::HashBag; let mut bag: HashBag<i32> = HashBag::new(); bag.reserve(10); assert!(bag.capacity() >= 10);
pub fn shrink_to_fit(&mut self)
[src]
Shrinks the capacity of the ba as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.
Examples
use hashbag::HashBag; let mut bag = HashBag::with_capacity(100); bag.insert(1); bag.insert(2); assert!(bag.capacity() >= 100); bag.shrink_to_fit(); assert!(bag.capacity() >= 2);
pub fn contains<Q: ?Sized>(&self, value: &Q) -> usize where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Returns the number of instances of value
in the bag.
The value may be any borrowed form of the bag's value type, but
Hash
and Eq
on the borrowed form must match those for
the value type.
Examples
use hashbag::HashBag; let bag: HashBag<_> = [1, 2, 3, 3].iter().cloned().collect(); assert_eq!(bag.contains(&1), 1); assert_eq!(bag.contains(&3), 2); assert_eq!(bag.contains(&4), 0);
pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<(&T, usize)> where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Returns a reference to the value in the bag, if any, that is equal to the given value, along with its number of occurrences.
The value may be any borrowed form of the bag's value type, but
Hash
and Eq
on the borrowed form must match those for
the value type.
Examples
use hashbag::HashBag; let bag: HashBag<_> = [1, 2, 3, 3].iter().cloned().collect(); assert_eq!(bag.get(&2), Some((&2, 1))); assert_eq!(bag.get(&3), Some((&3, 2))); assert_eq!(bag.get(&4), None);
pub fn insert(&mut self, value: T) -> usize
[src]
Adds a value to the bag.
The number of occurrences of the value previously in the bag is returned.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); assert_eq!(bag.insert(2), 0); assert_eq!(bag.insert(2), 1); assert_eq!(bag.insert(2), 2); assert_eq!(bag.set_len(), 1); assert_eq!(bag.len(), 3);
pub fn insert_many(&mut self, value: T, count: usize) -> usize
[src]
Adds multiple occurrences of a value to the bag.
The number of occurrences of the value previously in the bag is returned.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); assert_eq!(bag.insert_many(2, 1), 0); assert_eq!(bag.insert_many(2, 2), 1); assert_eq!(bag.insert_many(2, 4), 3); assert_eq!(bag.set_len(), 1); assert_eq!(bag.len(), 7);
pub fn replace(&mut self, value: T) -> usize
[src]
Adds a value to the bag, replacing all existing occurrences, if any, that equal the given one.
The number of occurrences of the value previously in the bag is returned.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert(Vec::<i32>::new()); bag.insert(Vec::<i32>::new()); assert_eq!(bag.contains(&[][..]), 2); assert_eq!(bag.get(&[][..]).unwrap().0.capacity(), 0); bag.replace(Vec::with_capacity(10)); assert_eq!(bag.contains(&[][..]), 1); assert_eq!(bag.get(&[][..]).unwrap().0.capacity(), 10);
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> usize where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Removes a value from the bag.
The number of occurrences of the value previously in the bag is returned.
The value may be any borrowed form of the bag's value type, but
Hash
and Eq
on the borrowed form must match those for
the value type.
Examples
use hashbag::HashBag; let mut bag = HashBag::new(); bag.insert_many('x', 2); assert_eq!(bag.contains(&'x'), 2); assert_eq!(bag.remove(&'x'), 2); assert_eq!(bag.contains(&'x'), 1); assert_eq!(bag.remove(&'x'), 1); assert_eq!(bag.contains(&'x'), 0); assert_eq!(bag.remove(&'x'), 0);
pub fn try_take<Q: ?Sized>(
&mut self,
value: &Q
) -> Result<T, Option<(&T, usize)>> where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
&mut self,
value: &Q
) -> Result<T, Option<(&T, usize)>> where
T: Borrow<Q>,
Q: Hash + Eq,
Removes a value that is equal to the given one, and returns it if it was the last.
If the matching value is not the last, a reference to the remainder is given, along with the number of occurrences prior to the removal.
The value may be any borrowed form of the bag's value type, but
Hash
and Eq
on the borrowed form must match those for
the value type.
Examples
use hashbag::HashBag; let mut bag: HashBag<_> = [1, 2, 3, 3].iter().cloned().collect(); assert_eq!(bag.try_take(&2), Ok(2)); assert_eq!(bag.try_take(&3), Err(Some((&3, 2)))); assert_eq!(bag.try_take(&3), Ok(3)); assert_eq!(bag.try_take(&4), Err(None));
pub fn take_all<Q: ?Sized>(&mut self, value: &Q) -> Option<(T, usize)> where
T: Borrow<Q>,
Q: Hash + Eq,
[src]
T: Borrow<Q>,
Q: Hash + Eq,
Removes and returns all occurrences of the value, if any, that is equal to the given one.
The value may be any borrowed form of the bag's value type, but
Hash
and Eq
on the borrowed form must match those for
the value type.
Examples
use hashbag::HashBag; let mut bag: HashBag<_> = [1, 2, 3, 3].iter().cloned().collect(); assert_eq!(bag.take_all(&2), Some((2, 1))); assert_eq!(bag.take_all(&3), Some((3, 2))); assert_eq!(bag.take_all(&2), None); assert_eq!(bag.take_all(&3), None);
pub fn retain<F>(&mut self, f: F) where
F: FnMut(&T, usize) -> usize,
[src]
F: FnMut(&T, usize) -> usize,
Retains only the values specified by the predicate.
In other words, for each value v
retain only f(&v)
occurrences.
Examples
use hashbag::HashBag; let xs = [0,0,0,0,0,1,1,1,1,2,2,2,3,3,4]; let mut bag: HashBag<i32> = xs.iter().cloned().collect(); bag.retain(|&k, _| k as usize); assert_eq!(bag.set_len(), 4); // >= 1 of all but value 0 assert_eq!(bag.len(), 6); assert_eq!(bag.contains(&0), 0); assert_eq!(bag.contains(&1), 1); assert_eq!(bag.contains(&2), 2); assert_eq!(bag.contains(&3), 2); assert_eq!(bag.contains(&4), 1);
Trait Implementations
impl<T: Clone + Hash, S: Clone + BuildHasher> Clone for HashBag<T, S>
[src]
fn clone(&self) -> Self
[src]
fn clone_from(&mut self, source: &Self)
[src]
impl<T> Debug for HashBag<T> where
T: Debug,
[src]
T: Debug,
impl<T, S> Default for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher + Default,
[src]
T: Eq + Hash,
S: BuildHasher + Default,
impl<T, S> Eq for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher,
[src]
T: Eq + Hash,
S: BuildHasher,
impl<'a, T, S> Extend<&'a T> for HashBag<T, S> where
T: 'a + Eq + Hash + Clone,
S: BuildHasher,
[src]
T: 'a + Eq + Hash + Clone,
S: BuildHasher,
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)
[src]
fn extend_one(&mut self, item: A)
[src]
fn extend_reserve(&mut self, additional: usize)
[src]
impl<'a, T, S> Extend<(&'a T, usize)> for HashBag<T, S> where
T: 'a + Eq + Hash + Clone,
S: BuildHasher,
[src]
T: 'a + Eq + Hash + Clone,
S: BuildHasher,
fn extend<I: IntoIterator<Item = (&'a T, usize)>>(&mut self, iter: I)
[src]
fn extend_one(&mut self, item: A)
[src]
fn extend_reserve(&mut self, additional: usize)
[src]
impl<T, S> Extend<(T, usize)> for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher,
[src]
T: Eq + Hash,
S: BuildHasher,
fn extend<I: IntoIterator<Item = (T, usize)>>(&mut self, iter: I)
[src]
fn extend_one(&mut self, item: A)
[src]
fn extend_reserve(&mut self, additional: usize)
[src]
impl<T, S> Extend<T> for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher,
[src]
T: Eq + Hash,
S: BuildHasher,
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
[src]
fn extend_one(&mut self, item: A)
[src]
fn extend_reserve(&mut self, additional: usize)
[src]
impl<T, S> FromIterator<T> for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher + Default,
[src]
T: Eq + Hash,
S: BuildHasher + Default,
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
impl<'a, T, S> IntoIterator for &'a HashBag<T, S>
[src]
type Item = &'a 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>ⓘ
[src]
impl<T, S> IntoIterator for HashBag<T, S>
[src]
type Item = (T, usize)
The type of the elements being iterated over.
type IntoIter = IntoIter<T>
Which kind of iterator are we turning this into?
fn into_iter(self) -> IntoIter<T>ⓘ
[src]
impl<T, S> PartialEq<HashBag<T, S>> for HashBag<T, S> where
T: Eq + Hash,
S: BuildHasher,
[src]
T: Eq + Hash,
S: BuildHasher,
Auto Trait Implementations
impl<T, S> RefUnwindSafe for HashBag<T, S> where
S: RefUnwindSafe,
T: RefUnwindSafe,
S: RefUnwindSafe,
T: RefUnwindSafe,
impl<T, S> Send for HashBag<T, S> where
S: Send,
T: Send,
S: Send,
T: Send,
impl<T, S> Sync for HashBag<T, S> where
S: Sync,
T: Sync,
S: Sync,
T: Sync,
impl<T, S> Unpin for HashBag<T, S> where
S: Unpin,
T: Unpin,
S: Unpin,
T: Unpin,
impl<T, S> UnwindSafe for HashBag<T, S> where
S: UnwindSafe,
T: UnwindSafe,
S: UnwindSafe,
T: UnwindSafe,
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,
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<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
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.
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>,