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

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.

Assignment 5 differs from assignment 4 in that a Set<T> is represented
by a binary tree rather than a map<T, bool>
*/

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

template <class T>
class Set {
private:
  struct Node {          // Node of binary tree
    T data;              // One element of the set
    Node *left, *right;  // Pointers to child nodes, or else 0
    Node(const T& x): data(x), left(0), right(0) {}   // Init data to x
  } *root;               // Root of the tree
  void insert(Node* &p, const T& x);  // Insert x into branch p
  void insert_from(const Node* p);    // Insert from branch p of another tree
  void erase(Node* p);                // Delete all nodes
  void insert_if_in(const Set<T>& s, const Node* p);     // From p if in s
  void insert_if_not_in(const Set<T>& s, const Node* p); // From p if not
  bool in(const T& x, const Node* p) const;              // Is x in branch p?
  int size(const Node* p) const;                         // Nodes at branch p
  void print(std::ostream& out, const Node* p) const;    // Print branch p
public:
  Set(): root(0) {}                            // Create empty set {}
  Set(const T& x): root(0) {insert(root, x);}  // One element set {x}
  Set(const Set<T>& s): root(0) {insert_from(s.root);}  // Copy constructor
  Set<T>& operator = (const Set<T>& s);        // Assignment
  ~Set() {erase(root);}                        // Destructor
  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 in(x, root);}  // x is element?
  int size() const {return size(root);};       // Number of elements
  void print(std::ostream& out) const;         // Print in format {x,y,...}
};

////////// Private member functions:

// Insert x at the branch (subtree) rooted at p (unless already inserted)
template <class T>
void Set<T>::insert(Node* &p, const T& x) {
  if (!p)
    p=new Node(x);
  else if (x < p->data)
    insert(p->left, x);
  else if (p->data < x)
    insert(p->right, x);
}

// Insert a copy of all nodes from branch p from another tree into this tree
template <class T>
void Set<T>::insert_from(const Node* p) {
  if (p) {
    insert(root, p->data);
    insert_from(p->left);
    insert_from(p->right);
  }
}

// Delete all nodes in branch p.  Does NOT set p to 0
template <class T>
void Set<T>::erase(Node* p) {
  if (p) {
    erase(p->left);
    erase(p->right);
    delete p;
  }
}

// Insert copies of nodes of branch p if the values are in s
template <class T>
void Set<T>::insert_if_in(const Set<T>& s, const Node* p) {
  if (p) {
    if (s.in(p->data))
      insert(root, p->data);
    insert_if_in(s, p->left);
    insert_if_in(s, p->right);
  }
}

// Insert copies of nodes of branch p if the values are not in s
template <class T>
void Set<T>::insert_if_not_in(const Set<T>& s, const Node* p) {
  if (p) {
    if (!s.in(p->data))
      insert(root, p->data);
    insert_if_not_in(s, p->left);
    insert_if_not_in(s, p->right);
  }
}

// Is x in branch p?
template <class T>
bool Set<T>::in(const T& x, const Node* p) const {
  if (!p)
    return false;
  else if (x == p->data)
    return true;
  else if (x < p->data)
    return in(x, p->left);
  else
    return in(x, p->right);
}

// Number of nodes in branch p
template <class T>
int Set<T>::size(const Node* p) const {
  if (p)
    return 1 + size(p->left) + size(p->right);
  else
    return 0;
}

// Print branch p to out as a comma separated list, e.g. "a,b,c,d"
template <class T>
void Set<T>::print(std::ostream& out, const Node* p) const {
  if (p) {
    print(out, p->left);
    if (p->left)
      out << ",";
    out << p->data;
    if (p->right)
      out << ",";
    print(out, p->right);
  }
}

////////// Public member functions:

// Assignment
template <class T>
Set<T>& Set<T>::operator = (const Set<T>& s) {
  if (&s != this) {
    erase(root);
    root = 0;
    insert_from(s.root);
  }
  return *this;
}

// Set union
template <class T>
Set<T>& Set<T>::operator += (const Set<T>& b) {
  insert_from(b.root);
  return *this;
}

// Set difference
template <class T>
Set<T>& Set<T>::operator -= (const Set<T>& b) {
  Set<T> r;
  r.insert_if_not_in(b, root);
  *this = r;
  return *this;
}

// Set intersection
template <class T>
Set<T>& Set<T>::operator *= (const Set<T>& b) {
  Set<T> r;
  r.insert_if_in(b, root);
  *this = r;
  return *this;
}

// Print whole set to out as a comma separated list in braces, e.g. "{a,b,c,d}"
template <class T>
void Set<T>::print(std::ostream& out) const {
  out << "{";
  print(out, root);
  out << "}";
}

////////// The following nonmember code is unchaged from assignment 4:

// 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