tango.util.container.HashSet

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release

Authors:

Kris

Since:

0.99.7

Based upon Doug Lea's Java collection package

class HashSet(V, alias Hash = Container.hash, alias Reap = Container.reap, alias Heap = Container.DefaultCollect) : IContainer!(V) #
Hash table implementation of a Set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Iterator iterator ()
int opApply (int delegate(ref V value) dg)

bool add (V element)
bool contains (V element)
bool take (ref V element)
bool remove (V element)
size_t remove (IContainer!(V) e)
bool replace (V oldElement, V newElement)

size_t size ()
bool isEmpty ()
V[] toArray (V[] dst)
HashSet dup ()
HashSet clear ()
HashSet reset ()

size_t buckets ()
void buckets (size_t cap)
float threshold ()
void threshold (float desired)
this(float f = Container.defaultLoadFactor) #
Construct a HashSet instance
~this() #
Clean up when deleted
Alloc allocator() [final] #
Return the configured allocator
Iterator iterator() [final] #
Return a generic iterator for contained elements
int opApply(int delegate(ref V value) dg) [final] #
size_t size() [final] #
Return the number of elements contained
bool add(V element) [final] #
Add a new element to the set. Does not add if there is an equivalent already present. Returns true where an element is added, false where it already exists Time complexity: O(1) average; O(n) worst.
bool contains(V element) [final] #
Does this set contain the given element? Time complexity: O(1) average; O(n) worst
HashSet dup() [final] #
Make an independent copy of the container. Does not clone elements Time complexity: O(n)
size_t remove(V element, bool all) [final] #
Remove the provided element. Returns true if found, false otherwise Time complexity: O(1) average; O(n) worst
bool remove(V element) [final] #
Remove the provided element. Returns true if found, false otherwise Time complexity: O(1) average; O(n) worst
size_t replace(V oldElement, V newElement, bool all) [final] #
Replace the first instance of oldElement with newElement. Returns true if oldElement was found and replaced, false otherwise.
bool replace(V oldElement, V newElement) [final] #
Replace the first instance of oldElement with newElement. Returns true if oldElement was found and replaced, false otherwise.
bool take(ref V element) [final] #
Remove and expose the first element. Returns false when no more elements are contained Time complexity: O(n)
void add(IContainer!(V) e) [public] #
size_t remove(IContainer!(V) e) [public] #
HashSet clear() [final] #
Clears the HashMap contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.
Time complexity: O(n)
HashSet reset() [final] #
Reset the HashSet contents and optionally configure a new heap manager. This releases more memory than clear() does
Time complexity: O(1)
size_t buckets() [final] #
Return the number of buckets
Time complexity: O(1)
void buckets(size_t cap) [final] #
Set the number of buckets and resize as required Time complexity: O(n)
float threshold() [final] #
Return the resize threshold Time complexity: O(1)
void threshold(float desired) [final] #
Set the resize threshold, and resize as required Time complexity: O(n)
V[] toArray(V[] dst = null) [final] #
Copy and return the contained set of values in an array, using the optional dst as a recipient (which is resized as necessary).
Returns a slice of dst representing the container values. Time complexity: O(n)
bool isEmpty() [final] #
Is this container empty? Time complexity: O(1)
HashSet check() [final] #
Sanity check
Ref allocate() [private] #
Allocate a node instance. This is used as the default allocator
void checkLoad() [private] #
Check to see if we are past load factor threshold. If so, resize so that we are at half of the desired threshold.
void resize(size_t newCap) [private] #
resize table to new capacity, rehashing all elements
bool remove(Ref node, size_t row) [private] #
Remove the indicated node. We need to traverse buckets for this, since we're singly-linked only. Better to save the per-node memory than to gain a little on each remove
Used by iterators only
HashSet clear(bool all) [private] #
Clears the HashSet contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.
Time complexity: O(n)
void increment() [private] #
new element was added
void decrement(Ref p) [private] #
element was removed
void mutate() [private] #
set was changed
struct Iterator [private] #
Iterator with no filtering
bool valid() #
Did the container change underneath us?
bool next(ref V v) #
Accesses the next value, and returns false when there are no further values to traverse
V* next() #
Return a pointer to the next value, or null when there are no further values to traverse
int opApply(int delegate(ref V value) dg) #
Foreach support
bool remove() #
Remove value at the current iterator location