From 0c39051ba80f04b1177833a006f2d442a7170b56 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 3 Dec 2020 17:11:43 +0100 Subject: add initial files l8 --- labb8/lib/StanfordCPPLib/hashset.h | 613 +++++++++++++++++++++++++++++++++++++ 1 file changed, 613 insertions(+) create mode 100755 labb8/lib/StanfordCPPLib/hashset.h (limited to 'labb8/lib/StanfordCPPLib/hashset.h') diff --git a/labb8/lib/StanfordCPPLib/hashset.h b/labb8/lib/StanfordCPPLib/hashset.h new file mode 100755 index 0000000..f7551c5 --- /dev/null +++ b/labb8/lib/StanfordCPPLib/hashset.h @@ -0,0 +1,613 @@ +/* + * File: hashset.h + * --------------- + * This file exports the HashSet class, which + * implements an efficient abstraction for storing sets of values. + */ + +#ifndef _hashset_h +#define _hashset_h + +#include +#include "foreach.h" +#include "hashmap.h" +#include "vector.h" + +/* + * Class: HashSet + * ------------------------- + * 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 iterators return the values in a + * seemingly random order. + */ + +template +class HashSet { + +public: + +/* + * Constructor: HashSet + * Usage: HashSet set; + * ------------------------------ + * Initializes an empty set of the specified element type. + */ + + HashSet(); + +/* + * Destructor: ~HashSet + * -------------------- + * Frees any heap storage associated with this set. + */ + + virtual ~HashSet(); + +/* + * Method: size + * Usage: count = set.size(); + * -------------------------- + * Returns the number of elements in this set. + */ + + int size() const; + +/* + * Method: isEmpty + * Usage: if (set.isEmpty()) ... + * ----------------------------- + * Returns true if this set contains no elements. + */ + + bool isEmpty() const; + +/* + * Method: add + * Usage: set.add(value); + * ---------------------- + * Adds an element to this set, if it was not already there. For + * compatibility with the STL set class, this method + * is also exported as insert. + */ + + void add(const ValueType & value); + void insert(const ValueType & value); + +/* + * Method: remove + * Usage: set.remove(value); + * ------------------------- + * Removes an element from this set. If the value was not + * contained in the set, no error is generated and the set + * remains unchanged. + */ + + void remove(const ValueType & value); + +/* + * Method: contains + * Usage: if (set.contains(value)) ... + * ----------------------------------- + * Returns true if the specified value is in this set. + */ + + bool contains(const ValueType & value) const; + +/* + * Method: isSubsetOf + * Usage: if (set.isSubsetOf(set2)) ... + * ------------------------------------ + * Implements the subset relation on sets. It returns + * true if every element of this set is + * contained in set2. + */ + + bool isSubsetOf(const HashSet & set2) const; + +/* + * Method: clear + * Usage: set.clear(); + * ------------------- + * Removes all elements from this set. + */ + + void clear(); + +/* + * Operator: == + * Usage: set1 == set2 + * ------------------- + * Returns true if set1 and set2 + * contain the same elements. + */ + + bool operator==(const HashSet & set2) const; + +/* + * Operator: != + * Usage: set1 != set2 + * ------------------- + * Returns true if set1 and set2 + * are different. + */ + + bool operator!=(const HashSet & set2) const; + +/* + * Operator: + + * Usage: set1 + set2 + * set1 + element + * --------------------- + * Returns the union of sets set1 and set2, which + * is the set of elements that appear in at least one of the two sets. The + * right hand set can be replaced by an element of the value type, in which + * case the operator returns a new set formed by adding that element. + */ + + HashSet operator+(const HashSet & set2) const; + HashSet operator+(const ValueType & element) const; + +/* + * Operator: * + * Usage: set1 * set2 + * ------------------ + * Returns the intersection of sets set1 and set2, + * which is the set of all elements that appear in both. + */ + + HashSet operator*(const HashSet & set2) const; + +/* + * Operator: - + * Usage: set1 - set2 + * set1 - element + * --------------------- + * Returns the difference of sets set1 and set2, + * which is all of the elements that appear in set1 but + * not set2. The right hand set can be replaced by an + * element of the value type, in which case the operator returns a new + * set formed by removing that element. + */ + + HashSet operator-(const HashSet & set2) const; + HashSet operator-(const ValueType & element) const; + +/* + * Operator: += + * Usage: set1 += set2; + * set1 += value; + * --------------------- + * Adds all of the elements from set2 (or the single + * specified value) to set1. As a convenience, the + * HashSet package also overloads the comma operator so + * that it is possible to initialize a set like this: + * + *
+ *    HashSet<int< digits;
+ *    digits += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
+ *
+ */ + + HashSet & operator+=(const HashSet & set2); + HashSet & operator+=(const ValueType & value); + +/* + * Operator: *= + * Usage: set1 *= set2; + * -------------------- + * Removes any elements from set1 that are not present in + * set2. + */ + + HashSet & operator*=(const HashSet & set2); + +/* + * Operator: -= + * Usage: set1 -= set2; + * set1 -= value; + * --------------------- + * Removes the elements from set2 (or the single + * specified value) from set1. As a convenience, the + * HashSet package also overloads the comma operator so + * that it is possible to remove multiple elements from a set + * like this: + * + *
+ *    digits -= 0, 2, 4, 6, 8;
+ *
+ * + * which removes the values 0, 2, 4, 6, and 8 from the set + * digits. + */ + + HashSet & operator-=(const HashSet & set2); + HashSet & operator-=(const ValueType & value); + +/* + * Method: first + * Usage: ValueType value = set.first(); + * ------------------------------------- + * Returns the first value in the set in the order established by the + * foreach macro. If the set is empty, first + * generates an error. + */ + + ValueType first() const; + +/* + * Method: toString + * Usage: string str = set.toString(); + * ----------------------------------- + * Converts the set to a printable string representation. + */ + + std::string toString(); + +/* + * Method: mapAll + * Usage: set.mapAll(fn); + * ---------------------- + * Iterates through the elements of the set and calls fn(value) + * for each one. The values are processed in ascending order, as defined + * by the comparison function. + */ + + void mapAll(void (*fn)(ValueType)) const; + void mapAll(void (*fn)(const ValueType &)) const; + + template + void mapAll(FunctorType fn) const; + +/* + * Additional HashSet operations + * ----------------------------- + * In addition to the methods listed in this interface, the HashSet + * class supports the following operations: + * + * - Stream I/O using the << and >> operators + * - Deep copying for the copy constructor and assignment operator + * - Iteration using the range-based for statement and STL iterators + * + * The iteration forms process the HashSet in an unspecified order. + */ + +/* Private section */ + +/**********************************************************************/ +/* Note: Everything below this point in the file is logically part */ +/* of the implementation and should not be of interest to clients. */ +/**********************************************************************/ + +private: + + HashMap map; /* Map used to store the element */ + bool removeFlag; /* Flag to differentiate += and -= */ + +public: + +/* + * Hidden features + * --------------- + * The remainder of this file consists of the code required to + * support the comma operator, deep copying, and iteration. + * Including these methods in the public interface would make + * that interface more difficult to understand for the average client. + */ + + HashSet & operator,(const ValueType & value) { + if (this->removeFlag) { + this->remove(value); + } else { + this->add(value); + } + return *this; + } + +/* + * Iterator support + * ---------------- + * The classes in the StanfordCPPLib collection implement input + * iterators so that they work symmetrically with respect to the + * corresponding STL classes. + */ + + class iterator : public std::iterator { + + private: + + typename HashMap::iterator mapit; + + public: + + iterator() { + /* Empty */ + } + + iterator(typename HashMap::iterator it) : mapit(it) { + /* Empty */ + } + + iterator(const iterator & it) { + mapit = it.mapit; + } + + iterator & operator++() { + ++mapit; + return *this; + } + + iterator operator++(int) { + iterator copy(*this); + operator++(); + return copy; + } + + bool operator==(const iterator & rhs) { + return mapit == rhs.mapit; + } + + bool operator!=(const iterator & rhs) { + return !(*this == rhs); + } + + ValueType operator*() { + return *mapit; + } + + ValueType *operator->() { + return mapit; + } + }; + + iterator begin() const { + return iterator(map.begin()); + } + + iterator end() const { + return iterator(map.end()); + } + +}; + +extern void error(std::string msg); + +template +HashSet::HashSet() { + /* Empty */ +} + +template +HashSet::~HashSet() { + /* Empty */ +} + +template +int HashSet::size() const { + return map.size(); +} + +template +bool HashSet::isEmpty() const { + return map.isEmpty(); +} + +template +void HashSet::add(const ValueType & value) { + map.put(value, true); +} + +template +void HashSet::insert(const ValueType & value) { + map.put(value, true); +} + +template +void HashSet::remove(const ValueType & value) { + map.remove(value); +} + +template +bool HashSet::contains(const ValueType & value) const { + return map.containsKey(value); +} + +template +void HashSet::clear() { + map.clear(); +} + +template +bool HashSet::isSubsetOf(const HashSet & set2) const { + iterator it = begin(); + iterator end = this->end(); + while (it != end) { + if (!set2.map.containsKey(*it)) return false; + ++it; + } + return true; +} + +/* + * Implementation notes: set operators + * ----------------------------------- + * The implementations for the set operators use iteration to walk + * over the elements in one or both sets. + */ + +template +bool HashSet::operator==(const HashSet & set2) const { + return this->isSubsetOf(set2) && set2.isSubsetOf(*this); +} + +template +bool HashSet::operator!=(const HashSet & set2) const { + return !(*this == set2); +} + +template +HashSet HashSet::operator+(const HashSet & set2) const { + HashSet set = *this; + foreach (ValueType value in set2) { + set.add(value); + } + return set; +} + +template +HashSet +HashSet::operator+(const ValueType & element) const { + HashSet set = *this; + set.add(element); + return set; +} + +template +HashSet HashSet::operator*(const HashSet & set2) const { + HashSet set; + foreach (ValueType value in *this) { + if (set2.map.containsKey(value)) set.add(value); + } + return set; +} + +template +HashSet HashSet::operator-(const HashSet & set2) const { + HashSet set; + foreach (ValueType value in *this) { + if (!set2.map.containsKey(value)) set.add(value); + } + return set; +} + +template +HashSet +HashSet::operator-(const ValueType & element) const { + HashSet set = *this; + set.remove(element); + return set; +} + +template +HashSet & HashSet::operator+=(const HashSet & set2) { + foreach (ValueType value in set2) { + this->add(value); + } + return *this; +} + +template +HashSet & HashSet::operator+=(const ValueType & value) { + this->add(value); + this->removeFlag = false; + return *this; +} + +template +HashSet & HashSet::operator*=(const HashSet & set2) { + Vector toRemove; + foreach (ValueType value in *this) { + if (!set2.map.containsKey(value)) toRemove.add(value); + } + foreach (ValueType value in toRemove) { + this->remove(value); + } + return *this; +} + +template +HashSet & HashSet::operator-=(const HashSet & set2) { + Vector toRemove; + foreach (ValueType value in *this) { + if (set2.map.containsKey(value)) toRemove.add(value); + } + foreach (ValueType value in toRemove) { + this->remove(value); + } + return *this; +} + +template +HashSet & HashSet::operator-=(const ValueType & value) { + this->remove(value); + this->removeFlag = true; + return *this; +} + +template +ValueType HashSet::first() const { + if (isEmpty()) error("first: set is empty"); + return *begin(); +} + +template +std::string HashSet::toString() { + ostringstream os; + os << *this; + return os.str(); +} + +template +void HashSet::mapAll(void (*fn)(ValueType)) const { + map.mapAll(fn); +} + +template +void HashSet::mapAll(void (*fn)(const ValueType &)) const { + map.mapAll(fn); +} + +template +template +void HashSet::mapAll(FunctorType fn) const { + map.mapAll(fn); +} + +template +std::ostream & operator<<(std::ostream & os, const HashSet & set) { + os << "{"; + bool started = false; + foreach (ValueType value in set) { + if (started) os << ", "; + writeGenericValue(os, value, true); + started = true; + } + os << "}"; + return os; +} + +template +std::istream & operator>>(std::istream & is, HashSet & set) { + char ch; + is >> ch; + if (ch != '{') error("operator >>: Missing {"); + set.clear(); + is >> ch; + if (ch != '}') { + is.unget(); + while (true) { + ValueType value; + readGenericValue(is, value); + set += value; + is >> ch; + if (ch == '}') break; + if (ch != ',') { + error(std::string("operator >>: Unexpected character ") + ch); + } + } + } + return is; +} + +// hashing functions for hash sets; defined in hashmap.cpp +int hashCode(const HashSet& s); +int hashCode(const HashSet& s); +int hashCode(const HashSet& s); +int hashCode(const HashSet& s); +int hashCode(const HashSet& s); + +#endif -- cgit v1.2.1