#include "hashset.h"

`class HashSet<ValueType>`

This class stores a collection of distinct elements. This class implements an efficient abstraction for storing sets of distinct elements. This class is identical to the Set class except for the fact that it uses a hash table as its underlying representation. The advantage of the HashSet class is that it operates in constant time, as opposed to the O(log N) time for the Set class. The disadvantage of HashSet is that range-based for loops and other iteration patterns will access the elements in an unpredictable and seemingly random order. The HashSet operations to add/access/remove an element run in O(1) time.

Constructor
HashSet()	O(1)	Initializes a new HashSet of the specified element type.
Methods
add(`value`)	O(1)	Adds an element to this HashSet, if it was not already there.
clear()	O(N)	Removes all elements from this HashSet.
contains(`value`)	O(1)	Returns `true` if the specified value is in this HashSet.
difference(`otherSet`)	O(N)	Subtracts `otherSet` from this HashSet. The difference removes those elements that appear in `otherSet`.
equals(`set`)	O(N)	Returns `true` if the two sets contain the same elements.
first()	O(1)	Returns the first value in this HashSet in the order established by a for-each loop.
intersect(`otherSet`)	O(N)	Intersects `otherSet` with this HashSet. The intersection retains only those elements also contained in `otherSet`.
isEmpty()	O(1)	Returns `true` if this HashSet contains no elements.
isSubsetOf(`otherSet`)	O(N)	Returns `true` if this HashSet is a subset of `otherSet`.
isSupersetOf(`otherSet`)	O(N)	Returns `true` if this HashSet is a superset of `otherSet`.
last()	O(1)	Returns the last value in this HashSet in the order established by a for-each loop.
mapAll(`fn`)	O(N)	Calls `fn(value)` for each element of this HashSet.
remove(`value`)	O(1)	Removes an element from this HashSet.
size()	O(1)	Returns the number of elements in this HashSet.
toString()	O(N)	Returns a printable string representation of this set.
unionWith(`otherSet`)	O(N)	Unions `otherSet` with this HashSet. The union adds all elements from `otherSet`.
Operators
for (ValueType elem : set)	O(N)	Iterates through the elements in a set.
`set1` == `set2`	O(N)	Evaluates to `true` if `set1` and `set2` contain the same elements.
`set1` != `set2`	O(N)	Evaluates to `true` if `set1` and `set2` are different.
`set1` + `set2`	O(N)	Creates a new set which is the union of `set1` with `set2`.
`set` + `value`	O(N)	Creates a new set which is the union of `set` with the single `value`.
`set1` += `set2`	O(N)	Adds all of the elements from `set2` to `set1`.
`set` += `value`	O(1)	Adds the single `value` to `set`.
`set1` - `set2`	O(N)	Creates a new set which is the difference of `set1` minus `set2`.
`set` - `value`	O(N)	Creates a new set which is the difference of `set` minus the single `value`.
`set1` -= `set2`	O(N)	Removes the elements of `set2` from `set1`.
`set` -= `value`	O(1)	Removes the single `value` from `set`.
`set1` * `set2`	O(N)	Creates a new set which is the intersection of `set1` and `set2`.
`set1` *= `set2`	O(N)	Removes any elements from `set1` that are not present in `set2`.
`ostream` << `set`	O(N)	Outputs the contents of `set` to the given output stream.
`istream` >> `set`	O(N)	Reads the contents of the given input stream into `set`.

Constructor detail

HashSet();

Creates an empty HashSet of the specified element type. You may also optionally provide an initializer list of values. The newly created set will contain those values.

Usage:

HashSet<ValueType> set;
HashSet<ValueType> set = { value1, value2, value3 };

Method detail

void add(const ValueType& value);

Adds an element to this HashSet, if it was not already there.

Usage:

set.add(value);

void clear();

Removes all elements from this HashSet.

Usage:

set.clear();

bool contains(const ValueType& value) const;

Returns true if the specified value is in this HashSet.

Usage:

if (set.contains(value)) ...

HashSet& difference(const HashSet& set2);

Removes from this HashSet all elements that are present in set2. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 - set2 instead.

Usage:

set1.difference(set2);

bool equals(const HashSet& set2) const;

Returns true if the two HashSets contain exactly the same element values. Identical in behavior to the == operator.

Usage:

if (set1.equals(set2)) ...

ValueType first() const;

Returns the first value in the HashSet in the order established by a for-each loop. If the HashSet is empty, first signals an error.

Usage:

ValueType value = set.first();

HashSet& intersect(const HashSet& set2);

Removes from this HashSet all elements that are not present in set2. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 * set2 instead.

Usage:

set1.intersect(set2);

bool isEmpty() const;

Returns true if this HashSet contains no elements.

Usage:

if (set.isEmpty()) ...

bool isSubsetOf(const HashSet& set2) const;

Returns true if every element of this HashSet is contained in set2.

Usage:

if (set1.isSubsetOf(set2)) ...

bool isSupersetOf(const HashSet& set2) const;

Returns true if every element of set2 is contained in this HashSet.

Usage:

if (set1.isSupersetOf(set2)) ...

ValueType last() const;

Returns the last value in the HashSet in the order established by a for-each loop. If HashSet is empty, last signals an error.

Usage:

ValueType value = set.last();

void mapAll(std::function<void (const ValueType&)> fn) const;

Iterates through the elements of the HashSet and calls fn(value) for each one. The elements are processed in unpredictable order.

Usage:

set.mapAll(fn);

void remove(const ValueType& value);

Removes an element from this HashSet. If the value was not contained in the HashSet, there is no error and the HashSet remains unchanged.

Usage:

set.remove(value);

int size() const;

Returns the number of elements in this HashSet.

Usage:

count = set.size();

string toString() const;

Returns a printable string representation of this HashSet, such as "{value1, value2, value3}". The values are listed in unpredictable order.

Usage:

string str = set.toString();

HashSet& unionWith(const HashSet& set2);

Adds to this HashSet all elements from set2. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 + set2 instead.

Usage:

set1.unionWith(set2);

Operator detail

for (ValueType elem : set)

The range-based for loop can be used to iterate through the elements in a collection. The elements in a HashSet are accessed in unpredictable order. An error is signaled if you attempt to add/remove elements from a collection while iterating over it.

Usage:

for (ValueType elem : set) {
	cout << elem << endl;
}

bool operator==(const HashSet& set2) const;

Returns true if set1 and set2 contain the same elements.

Usage:

set1 == set2

bool operator!=(const HashSet& set2) const;

Returns true if set1 and set2 are different.

Usage:

set1 != set2

HashSet operator+(const HashSet& set2) const;
HashSet operator+(const ValueType& element) const;

Creates a new HashSet which is the union of set1 with set2 (or with the single value).

Usage:

set1 + set2
set1 + value

HashSet operator*(const HashSet& set2) const;

Creates a new HashSet which is the intersection of set1 and set2.

Usage:

set1 * set2

HashSet operator-(const HashSet& set2) const;
HashSet operator-(const ValueType& element) const;

Creates a new HashSet which is the difference of set1 minus set2 (or minus the single value).

Usage:

set1 - set2
set1 - value

HashSet& operator+=(const HashSet& set2);
HashSet& operator+=(const ValueType& value);

Adds all of the elements from set2 (or the single value) to set1.

Usage:

set1 += set2;
set1 += value;

HashSet& operator*=(const HashSet& set2);

Removes any elements from set1 that are not present in set2.

Usage:

set1 *= set2;

HashSet& operator-=(const HashSet& set2);
HashSet& operator-=(const ValueType& value);

Removes the elements from set2 (or the single value) from set1.

Usage:

set1 -= set2;
set1 -= value;

ostream& operator<<(const HashSet& set);

Outputs the contents of set to the given output stream. The output is in the form {value1, value2, value3} where elements are listed in unpredictable order.

Usage:

cout << set << endl;

istream& operator>>(HashSet& set);

Reads the contents of the given input stream into set. Any previous contents of the set are replaced. The input is expected to be in the form {value1, value2, value3}. If unable to read a proper set from the stream, the operation results in a stream fail state.

Usage:

if (infile >> set) ...