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.Collect): IContainer!(V);

Hash table implementation of a Set

        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)
        uint remove (IContainer!(V) e)
        bool replace (V oldElement, V newElement)

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

        uint buckets ()
        void buckets (uint cap)
        float threshold ()
        void threshold (float desired)

this(float f = Container.defaultLoadFactor);

Construct a HashSet instance

Alloc allocator ();

Return the configured allocator

Iterator iterator ();

Return a generic iterator for contained elements

int opApply (int delegate(ref V value) dg);

uint size ();

Return the number of elements contained

bool add (V element);

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);

Does this set contain the given element?

Time complexity: O(1) average; O(n) worst

HashSet dup ();

Make an independent copy of the container. Does not clone elements

Time complexity: O(n)

uint remove (V element, bool all);

Remove the provided element. Returns true if found, false otherwise

Time complexity: O(1) average; O(n) worst

bool remove (V element);

Remove the provided element. Returns true if found, false otherwise

Time complexity: O(1) average; O(n) worst

uint replace (V oldElement, V newElement, bool all);

Replace the first instance of oldElement with newElement. Returns true if oldElement was found and replaced, false otherwise.

bool replace (V oldElement, V newElement);

Replace the first instance of oldElement with newElement. Returns true if oldElement was found and replaced, false otherwise.

bool take (ref V element);

Remove and expose the first element. Returns false when no more elements are contained

Time complexity: O(n)

void add (IContainer!(V) e);

uint remove (IContainer!(V) e);

HashSet clear ();

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 ();

Reset the HashSet contents and optionally configure a new heap manager. This releases more memory than clear() does

Time complexity: O(1)

uint buckets ();

Return the number of buckets

Time complexity: O(1)

void buckets (uint cap);

Set the number of buckets and resize as required

Time complexity: O(n)

float threshold ();

Return the resize threshold

Time complexity: O(1)

void threshold (float desired);

Set the resize threshold , and resize as required

Time complexity: O(n)

V[] toArray (V[] dst = null);

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 ();

Is this container empty?

Time complexity: O(1)

HashSet check ();

Sanity check

Ref allocate ();

Allocate a node instance. This is used as the default allocator

void checkLoad ();

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 (uint newCap);

resize table to new capacity, rehashing all elements

bool remove (Ref node, uint row);

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);

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 ();

new element was added

void decrement (Ref p);

element was removed

void mutate ();

set was changed

struct Iterator ;

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

anchorFromTitle('tango.util.container.HashSet', 'source/', 'html');