/* set.h -- Matt Mahoney, mmahoney@cs.fit.edu

set.h defines a Set<T> class.  A Set<T> supports the following
operations:

  Set<T>()       // Empty set, {}
  Set<T>(x)      // Implicit conversion of x (type T) to {x}
  a+b            // Union (elements in either a or b)
  a*b            // Intersection (elements in both a and b)
  a-b            // Difference (elements in a but not b)
  a+=b, a-=b, a*=b  // Equivalent to a=a+b, a=a-b, a=a*b
  a==b           // Set equality
  a<=b           // true if a is a subset of b
  a<b, a>b, a!=b, a>=b  // Equivalent to !(b<=a), b<a, !(a==b), b<=a
  a.in(x)        // true if x is an element of a
  a.size()       // Number of elements in a
  cout << a;     // Prints comma-separated list of elements, e.g. {x,y,z}

A T object x is implicitly converted to a Set<T> containing only x (e.g {x})
in any of the above expressions where a Set<T> is expected.
*/

#include <map>
#include <iostream>
// NO using namespace std;

template <class T>
class Set {
private:
  typedef std::map<T,bool> M;
  typedef M::const_iterator CI;
  M m;  // The elements are the keys of s (ignoring values)
public:
  Set(): m() {}
  Set(const T& x): m() {m[x]=true;}
  Set<T>& operator += (const Set<T>& b);  // Union
  Set<T>& operator -= (const Set<T>& b);  // Difference
  Set<T>& operator *= (const Set<T>& b);  // Intersection
  bool in(const T& x) const {return m.find(x)!=m.end();}  // x is element?
  int size() const {return m.size();}   // Number of elements
  void print(std::ostream& out) const;  // Print in format {x,y,...} to out
};

// Code for members +, -, *
template <class T>
Set<T>& Set<T>::operator += (const Set<T>& b) {  // Union
  for (CI p=b.m.begin(); p!=b.m.end(); ++p)
    m[p->first]=true;
  return *this;
}

template <class T>
Set<T>& Set<T>::operator -= (const Set<T>& b) {  // Difference
  M r;
  for (CI p=m.begin(); p!=m.end(); ++p)
    if (!b.in(p->first))
      r[p->first]=true;
  m=r;
  return *this;
}

template <class T>
Set<T>& Set<T>::operator *= (const Set<T>& b) {  // Intersection
  M r;
  for (CI p=m.begin(); p!=m.end(); ++p)
    if (b.in(p->first))
      r[p->first]=true;
  m=r;
  return *this;
}

// Output helper
template <class T>
void Set<T>::print(std::ostream& out) const {
  out << "{";
  for (CI p=m.begin(); p!=m.end(); ++p) {
    if (p!=m.begin())
      out << ",";
    out << p->first;
  }
  out << "}";
}

// Nonmember binary set operations
template <class T> Set<T> operator+(Set<T> a, const Set<T>& b) {return a+=b;}
template <class T> Set<T> operator-(Set<T> a, const Set<T>& b) {return a-=b;}
template <class T> Set<T> operator*(Set<T> a, const Set<T>& b) {return a*=b;}
template <class T> bool operator<=(const Set<T>& a, const Set<T>& b) {return (a-b).size()==0;}
template <class T> bool operator==(const Set<T>& a, const Set<T>& b) {return a<=b && b<=a;}
template <class T> bool operator!=(const Set<T>& a, const Set<T>& b) {return !(a==b);}
template <class T> bool operator>=(const Set<T>& a, const Set<T>& b) {return b<=a;}
template <class T> bool operator< (const Set<T>& a, const Set<T>& b) {return a<=b && !(b<=a);}
template <class T> bool operator> (const Set<T>& a, const Set<T>& b) {return b<=a && !(a<=b);}

// Output
template <class T>
std::ostream& operator << (std::ostream& out, const Set<T>& st) {
  st.print(out);
  return out;
}

// Define binary operators with implicit conversions on the left or right
#define op(r, x) \
template <class T> r operator x (const T& a, const Set<T>& b) {return Set<T>(a) x b;} \
template <class T> r operator x (const Set<T>& a, const T& b) {return a x Set<T>(b);}

op(Set<T>, +)
op(Set<T>, -)
op(Set<T>, *)
op(bool, <)
op(bool, <=)
op(bool, >)
op(bool, >=)
op(bool, ==)
op(bool, !=)
#undef op