/*
 * 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 <iostream>
#include "hashmap.h"
#include "vector.h"

/*
 * Class: HashSet<ValueType>
 * -------------------------
 * 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 <typename ValueType>
class HashSet {

public:

/*
 * Constructor: HashSet
 * Usage: HashSet<ValueType> 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 <typename FunctorType>
   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<ValueType,bool> 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<std::input_iterator_tag,ValueType> {

   private:

      typename HashMap<ValueType,bool>::iterator mapit;

   public:

      iterator() {
         /* Empty */
      }

      iterator(typename HashMap<ValueType,bool>::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 <typename ValueType>
HashSet<ValueType>::HashSet() {
   /* Empty */
}

template <typename ValueType>
HashSet<ValueType>::~HashSet() {
   /* Empty */
}

template <typename ValueType>
int HashSet<ValueType>::size() const {
   return map.size();
}

template <typename ValueType>
bool HashSet<ValueType>::isEmpty() const {
   return map.isEmpty();
}

template <typename ValueType>
void HashSet<ValueType>::add(const ValueType & value) {
   map.put(value, true);
}

template <typename ValueType>
void HashSet<ValueType>::insert(const ValueType & value) {
   map.put(value, true);
}

template <typename ValueType>
void HashSet<ValueType>::remove(const ValueType & value) {
   map.remove(value);
}

template <typename ValueType>
bool HashSet<ValueType>::contains(const ValueType & value) const {
   return map.containsKey(value);
}

template <typename ValueType>
void HashSet<ValueType>::clear() {
   map.clear();
}

template <typename ValueType>
bool HashSet<ValueType>::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 <typename ValueType>
bool HashSet<ValueType>::operator==(const HashSet & set2) const {
   return this->isSubsetOf(set2) && set2.isSubsetOf(*this);
}

template <typename ValueType>
bool HashSet<ValueType>::operator!=(const HashSet & set2) const {
   return !(*this == set2);
}

template <typename ValueType>
HashSet<ValueType> HashSet<ValueType>::operator+(const HashSet & set2) const {
   HashSet<ValueType> set = *this;
   foreach (ValueType value in set2) {
      set.add(value);
   }
   return set;
}

template <typename ValueType>
HashSet<ValueType>
HashSet<ValueType>::operator+(const ValueType & element) const {
   HashSet<ValueType> set = *this;
   set.add(element);
   return set;
}

template <typename ValueType>
HashSet<ValueType> HashSet<ValueType>::operator*(const HashSet & set2) const {
   HashSet<ValueType> set;
   foreach (ValueType value in *this) {
      if (set2.map.containsKey(value)) set.add(value);
   }
   return set;
}

template <typename ValueType>
HashSet<ValueType> HashSet<ValueType>::operator-(const HashSet & set2) const {
   HashSet<ValueType> set;
   foreach (ValueType value in *this) {
      if (!set2.map.containsKey(value)) set.add(value);
   }
   return set;
}

template <typename ValueType>
HashSet<ValueType>
HashSet<ValueType>::operator-(const ValueType & element) const {
   HashSet<ValueType> set = *this;
   set.remove(element);
   return set;
}

template <typename ValueType>
HashSet<ValueType> & HashSet<ValueType>::operator+=(const HashSet & set2) {
   foreach (ValueType value in set2) {
      this->add(value);
   }
   return *this;
}

template <typename ValueType>
HashSet<ValueType> & HashSet<ValueType>::operator+=(const ValueType & value) {
   this->add(value);
   this->removeFlag = false;
   return *this;
}

template <typename ValueType>
HashSet<ValueType> & HashSet<ValueType>::operator*=(const HashSet & set2) {
   Vector<ValueType> 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 <typename ValueType>
HashSet<ValueType> & HashSet<ValueType>::operator-=(const HashSet & set2) {
   Vector<ValueType> 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 <typename ValueType>
HashSet<ValueType> & HashSet<ValueType>::operator-=(const ValueType & value) {
   this->remove(value);
   this->removeFlag = true;
   return *this;
}

template <typename ValueType>
ValueType HashSet<ValueType>::first() const {
   if (isEmpty()) error("first: set is empty");
   return *begin();
}

template <typename ValueType>
std::string HashSet<ValueType>::toString() {
   ostringstream os;
   os << *this;
   return os.str();
}

template <typename ValueType>
void HashSet<ValueType>::mapAll(void (*fn)(ValueType)) const {
   map.mapAll(fn);
}

template <typename ValueType>
void HashSet<ValueType>::mapAll(void (*fn)(const ValueType &)) const {
   map.mapAll(fn);
}

template <typename ValueType>
template <typename FunctorType>
void HashSet<ValueType>::mapAll(FunctorType fn) const {
   map.mapAll(fn);
}

template <typename ValueType>
std::ostream & operator<<(std::ostream & os, const HashSet<ValueType> & set) {
   os << "{";
   bool started = false;
   foreach (ValueType value in set) {
      if (started) os << ", ";
      writeGenericValue(os, value, true);
      started = true;
   }
   os << "}";
   return os;
}

template <typename ValueType>
std::istream & operator>>(std::istream & is, HashSet<ValueType> & 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;
}

#endif