Struct hashbag::HashBag

pub struct HashBag<T, S = RandomState> { /* private fields */ }

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>

pub fn new() -> HashBag<T, RandomState>

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>

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>

pub fn capacity(&self) -> usize

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>

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>

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

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

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

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>

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)

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, 

pub fn with_hasher(hash_builder: S) -> HashBag<T, S>

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 HashBags 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>

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 HashBags 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

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)

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)

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, 

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, 

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

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

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

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, 

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, 

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, 

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, 

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>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for HashBag<T> where
    T: Debug, 

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

Formats the value using the given formatter.

impl<T, S> Default for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher + Default, 

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T, S> Extend<&'a T> for HashBag<T, S> where
    T: 'a + Eq + Hash + Clone,
    S: BuildHasher, 

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T, S> Extend<(&'a T, usize)> for HashBag<T, S> where
    T: 'a + Eq + Hash + Clone,
    S: BuildHasher, 

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, S> Extend<(T, usize)> for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher, 

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, S> Extend<T> for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher, 

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, S> FromIterator<T> for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher + Default, 

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

Creates a value from an iterator.

impl<'a, T, S> IntoIterator for &'a HashBag<T, S>

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>

Creates an iterator from a value.

impl<T, S> IntoIterator for HashBag<T, S>

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>

Creates an iterator from a value.

impl<T, S> PartialEq<HashBag<T, S>> for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher, 

fn eq(&self, other: &Self) -> 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 !=.

impl<T, S> Eq for HashBag<T, S> where
    T: Eq + Hash,
    S: BuildHasher,