#ifndef USET__CLASS #define USET__CLASS #include #include "d_hash.h" // hash class using namespace std; // implements an unordered set template class uset { public: // uset iterators are simply hash iterators typedef typename hash::iterator iterator; typedef typename hash::const_iterator const_iterator; uset(int tableSize = 1237, const HashFunc& hfunc = HashFunc()); // default constructor uset(T *first, T *last, int tableSize = 1237, const HashFunc& hfunc = HashFunc()); // build a set whose data are determined by pointer range // [first, last) bool empty() const; // is the set empty? int size() const; // return the number of elements in the set iterator find (const T& item); // search for item in the set and return an iterator // pointing at it, or end() if it is not found const_iterator find (const T& item) const; // constant version pair insert(const T& item); // if item is not in the set, insert it and return a pair // whose first element is an iterator pointing to the // new element and whose second element is true. // otherwise, return a pair whose first element is an // iterator pointing at the existing element and whose // second element is false // Postcondition: the set size increases by 1 if item is // not in the set int erase(const T& item); // if item is in the set, erase it and return 1; // otherwise, return 0 // Postcondition: the set size decreases by 1 if item is // in the set void erase(iterator pos); // erase the item pointed to by pos. // Precondition: the set is not empty. if the set is empty, // the function throws the underflowError exception. // Postcondition: the set size decreases by 1 void erase(iterator first, iterator last); // erase the elements in the range [first, last) // Precondition: the set is not empty. if the set is empty, // the function throws the underflowError exception. // Postcondition: the tree size decreases by the number // elements in the range iterator begin(); // return an iterator pointing at the first member // in the set const_iterator begin() const; // constant version of begin() iterator end(); // return an iterator pointing just past the last // member in the set const_iterator end() const; // constant version of end() private: hash t; // uset implemented using a hash table }; // default constructor. initialize hash table template uset::uset(int tableSize, const HashFunc& hfunc): t(tableSize, hfunc) {} template uset::uset(T *first, T *last, int tableSize, const HashFunc& hfunc): t(first, last, tableSize, hfunc) {} template bool uset::empty() const { return t.empty(); } template int uset::size() const { return t.size(); } template uset::iterator uset::find (const T& item) { return t.find(item); } template uset::const_iterator uset::find (const T& item) const { return t.find(item); } template pair::iterator,bool> uset::insert(const T& item) { return t.insert(item); } template int uset::erase(const T& item) { return t.erase(item); } template void uset::erase(iterator pos) { if (t.size() == 0) throw underflowError("uset erase(): set is empty"); t.erase(pos); } template void uset::erase(iterator first, iterator last) { if (t.size() == 0) throw underflowError("uset erase(): set is empty"); t.erase(first, last); } template uset::iterator uset::begin() { return t.begin(); } template uset::const_iterator uset::begin() const { return t.begin(); } template uset::iterator uset::end() { return t.end(); } template uset::const_iterator uset::end() const { return t.end(); } // SET FUNCTIONS // determine if sets lhs and rhs have the same size and // are equal element by element template bool operator== (const uset& lhs, const uset& rhs); // return a set containing all elements that are in lhs or rhs template uset operator+ (const uset& lhs, const uset& rhs); // return a set containing all elements that are in goth lhs and rhs template uset operator* (const uset& lhs, const uset& rhs); // return a set containing all elements that are in lhs but not in rhs template uset operator- (const uset& lhs, const uset& rhs); // SET FUNCTION IMPLEMENTATIONS template bool operator== (const uset& lhs, const uset& rhs) { uset::const_iterator myself = lhs.begin(), other = rhs.begin(); // return false if the sets do not have the same size if (lhs.size() == rhs.size()) { // compare until encounter end of the sets or // find two elements that are not equal while (myself != lhs.end() && *myself++ == *other++); // if we left the loop before reaching the end // of the sets, they are not equal if (myself != lhs.end()) return false; else return true; } else return false; } template uset operator+ (const uset& lhs, const uset& rhs) { // construct union. initially, copy in all elements of lhs uset setUnion = lhs; // iterators that traverse the sets uset::const_iterator rhsIter = rhs.begin(); // insert all values from rhs into the union. duplicate // values will be discarded while (rhsIter != rhs.end()) { setUnion.insert(*rhsIter); rhsIter++; } return setUnion; } template uset operator* (const uset& lhs, const uset& rhs) { // construct intersection uset setIntersection; // iterators that traverse the sets uset::const_iterator lhsIter = lhs.begin(); while (lhsIter != lhs.end()) { // insert *lhsIter into the intersection if it is // in rhs if (rhs.find(*lhsIter) != rhs.end()) setIntersection.insert(*lhsIter); lhsIter++; } return setIntersection; } template uset operator- (const uset& lhs, const uset& rhs) { // construct difference uset setDifference; // iterators that traverse the sets uset::const_iterator lhsIter = lhs.begin(), rhsIter = rhs.begin(); while (lhsIter != lhs.end()) { // insert *lhsIter into the difference if it // is not in rhs if (rhs.find(*lhsIter) == rhs.end()) setDifference.insert(*lhsIter); lhsIter++; } return setDifference; } #endif // USET__CLASS