HashSet<T> structv0.1.0

pub struct HashSet<T> {
    // private fields
}

Move-only: it owns its elements and its storage.

Type parameters

Constructors

HashSet

pub func HashSet(
    allocator: Allocator,
    hash: func(T, uint64, uint64) -> uint64,
    equals: func(T, T) -> bool
) -> HashSet<T>

An empty set that has not allocated anything, with a seed drawn from the operating system.

Returns: an empty collection that has taken no storage yet

Source

Associated functions

WithSeed

pub func WithSeed(
    allocator: Allocator,
    seed: TableSeed,
    hash: func(T, uint64, uint64) -> uint64,
    equals: func(T, T) -> bool
) -> HashSet<T>

An empty set that has not allocated anything, hashing with seed.

Returns: an empty set keyed with that seed

Source

WithCapacity

pub func WithCapacity(
    allocator: Allocator,
    capacity: uint,
    hash: func(T, uint64, uint64) -> uint64,
    equals: func(T, T) -> bool
) -> HashSet<T> ! CollectionError

An empty set with room for capacity elements already taken.

Returns: an empty set with room for that many elements already taken

Source

Methods

Length

pub func Length(self: &HashSet<T>) -> uint

How many elements the set holds.

Returns: how many elements it holds

Source

Capacity

pub func Capacity(self: &HashSet<T>) -> uint

How many slots the table has.

Returns: how many elements fit before the next growth

Source

IsEmpty

pub func IsEmpty(self: &HashSet<T>) -> bool

Whether the set holds no elements.

Returns: whether it holds nothing

Source

Contains

pub func Contains(self: &HashSet<T>, value: T) -> bool

Whether value is in the set. self is borrowed; value is read by value. Runs in constant expected time and allocates nothing.

Returns: whether the value is present

Source

Insert

pub func Insert(
    self: &var HashSet<T>,
    value: T
) -> bool ! CollectionError

Adds value to the set, reporting whether it was not already there. self is borrowed mutably; value is moved in when it is added and destroyed when it was already present -- a set holds one of each, and the one it already had is the one it keeps. A failure leaves the set exactly as it was.

Returns: whether the value was new rather than already present

Source

Remove

pub func Remove(self: &var HashSet<T>, value: T) -> T?

Takes value out of the set and hands it back. self is borrowed mutably. The element is moved out rather than destroyed, so one that owns something leaves intact. Reports none when the set did not have it.

Returns: the value that was stored, or none when it was absent

Source

Reserve

pub func Reserve(
    self: &var HashSet<T>,
    additional: uint
) -> ! CollectionError

Makes room for additional more elements on top of those already present.

Returns: nothing when the operation succeeded, or why it did not

Source

ShrinkToFit

pub func ShrinkToFit(self: &var HashSet<T>) -> ! CollectionError

Releases the capacity the element count does not need.

Returns: nothing when the operation succeeded, or why it did not

Source

Clear

pub func Clear(self: &var HashSet<T>)

Destroys every element, keeping the storage.

Source

TryNext

pub func TryNext(
    self: &HashSet<T>,
    cursor: *var uint,
    value: *var T
) -> bool

Walks to the next occupied slot at or after cursor, reporting the element it holds. self is borrowed; cursor is read and advanced past whatever is reported. The order is the table's, which is the seed's and not the insertion's, and nothing may be inserted or removed while a walk is in progress.

Returns: whether an element was read; false at the end

Source

Iterate

pub func Iterate(self: &HashSet<T>) -> HashSetIterator<T>

An iterator over the elements, by copy. self is borrowed and must outlive the iterator. This is the method a for loop finds. The order is the table's, which is the seed's. Nothing may be inserted or removed while the iterator is alive.

Returns: a cursor over the elements, in an order the seed decides

Source

IntoIterator

pub func IntoIterator(self: HashSet<T>) -> HashSetIntoIterator<T>

Takes the set apart into an iterator over its elements. Consumes the set: it is moved into the iterator, and the storage goes with it. Whatever is not taken is destroyed when the iterator's life ends.

Returns: a cursor that consumes the set as it goes

Source

IsSubsetOf

pub func IsSubsetOf(
    self: &HashSet<T>,
    other: &HashSet<T>
) -> bool

Whether every element of this set is also in other. Both are borrowed. A set is a subset of itself, and the empty set is a subset of everything — there is no element of it to be missing. other is asked about each of this set's elements, so it decides identity: two sets with different hashes for the same values would disagree, which is a caller error rather than something checkable here. Allocates nothing. Runs in time proportional to this set's size.

Returns: whether every element of this set is in other

Source

IsSupersetOf

pub func IsSupersetOf(
    self: &HashSet<T>,
    other: &HashSet<T>
) -> bool

Whether every element of other is also in this set. Both are borrowed. The mirror of IsSubsetOf, which is what it calls.

Returns: whether every element of other is in this set

Source

IsDisjointFrom

pub func IsDisjointFrom(
    self: &HashSet<T>,
    other: &HashSet<T>
) -> bool

Whether the two sets have no element in common. Both are borrowed. Two empty sets are disjoint, and so is any set with an empty one. Walks the smaller of the two, since an element of either that is in both would be found from whichever side it is looked for. Allocates nothing.

Returns: whether the two share no element

Source

Equals

pub func Equals(
    self: &HashSet<T>,
    other: &HashSet<T>
) -> bool

Whether the two sets hold exactly the same elements. Both are borrowed. Equal sizes and one containment, which together are containment both ways.

Returns: whether both hold exactly the same elements

Source

UnionWith

pub func UnionWith(
    self: &var HashSet<T>,
    other: &HashSet<T>
) -> ! CollectionError

Adds every element of other that this set does not already have. self is borrowed mutably; other is borrowed and left alone. Elements are copied out of other, which is what makes this usable only where copying an element means what it says. Room for the worst case is taken first, so this either adds every element or none: a failure part-way would leave a set that is neither what it was nor the union, and there is nothing useful a caller could do with that. Reserving more than it needs is the price, and it is given back by ShrinkToFit. Runs in time proportional to other.

Returns: nothing when the operation succeeded, or why it did not

Source

IntersectWith

pub func IntersectWith(
    self: &var HashSet<T>,
    other: &HashSet<T>
)

Removes every element this set has that other does not. self is borrowed mutably; other is borrowed and left alone. Whatever leaves is destroyed, since nobody asked for it back. Allocates nothing, so it cannot fail: a set only ever gets smaller here.

Source

Subtract

pub func Subtract(self: &var HashSet<T>, other: &HashSet<T>)

Removes every element this set has that other also has. self is borrowed mutably; other is borrowed and left alone. Whatever leaves is destroyed. Allocates nothing, so it cannot fail.

Source

SymmetricDifferenceWith

pub func SymmetricDifferenceWith(
    self: &var HashSet<T>,
    other: &HashSet<T>
) -> ! CollectionError

Keeps the elements that are in exactly one of the two sets. self is borrowed mutably; other is borrowed and left alone. Elements shared by both leave and are destroyed; elements only other has are copied in. Room for the worst case is taken first, for the same reason UnionWith takes it: a failure part-way would leave a set that is neither operand nor the answer.

Returns: nothing when the operation succeeded, or why it did not

Source

Clone

pub func Clone(self: &HashSet<T>) -> HashSet<T> ! CollectionError

An independent set holding a copy of every element of this one. self is borrowed and left alone. The copy has its own storage from the same allocator and the same seed, so the two lay their elements out alike.

Returns: an independent copy

Source

Related

HashSetIterator<T>

pub struct HashSetIterator<T> {
    // private fields
}

An iterator over the elements of a set, by copy. Borrows the set, so the set must outlive it and must not be inserted into or removed from while it is alive.

Source

Type parameters

Implements Iterator

HashSetIterator<T> conforms to Iterator.

Next

pub func Next(self: &var HashSetIterator<T>) -> T?

The next element, or none once every slot has been looked at. self is borrowed mutably and advanced. The element is a copy; a set of things that own something is walked with TryNext instead.

Returns: the next element, or none at the end

Source

HashSetIntoIterator<T>

pub struct HashSetIntoIterator<T> {
    // private fields
}

An iterator that takes a set apart, yielding each element by value. Move-only: it owns the storage the set owned. Whatever is left when its life ends is destroyed with it.

Source

Type parameters

Implements Iterator

HashSetIntoIterator<T> conforms to Iterator.

Next

pub func Next(self: &var HashSetIntoIterator<T>) -> T?

The next element, moved out, or none once every slot has been looked at. self is borrowed mutably and advanced. The slot is emptied as the element leaves, so what remains for the destructor is exactly what nobody took.

Returns: the next element, or none at the end

Source

WriteHashSetDebug<T>

pub func WriteHashSetDebug<T: Debug>(
    writer: &var TextWriter,
    value: &HashSet<T>,
    spec: FormatSpec
) -> ! FormatError

Writes a borrowed hash set as {first, second, third}. An empty set is {}. The order is the table's and carries the same warning as a hash map's: it follows from the seed and from what the set has been through, so it is not the insertion order and does not hold between runs. TreeSet is the ordered one. Every element is shown through a borrow of it, and spec is handed to each unchanged. Reports whatever the writer or an element's implementation reported, stopping at the first refusal.

Source

Type parameters

Parameters

Returns: success when the whole rendering was accepted