/* set6.cpp -- Matt Mahoney, mmahoney@cs.fit.edu, assignment 6

This program compares the sets of words in two files specified on
the command line.  For example, if file1 contains "this is a test"
and file2 contains "this is another test", then it runs as follows:

  wcmp file1 file2
  5 word(s) in either file: a another is test this
  3 word(s) in both files: is test this
  1 word(s) in file1 but not file2: a
  1 word(s) in file2 but not file1: another

If there are more than 10 words in any list, only the first 10 are
printed.  If either file cannot be read, an error message is printed.
If there are not exactly two arguments, then a help message is printed.
A word is defined as any sequence of printable characters separated by
white space.  Upper and lower case letters are distinct.

DESIGN

Words are read into two Set<string>, where a Set is defined as in
assignment 5 with the addition of forward iterators (regular and const).
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.

  // New in assignment 6
  a.begin()      // Points to first element
  a.end()        // Points 1 past last element
  Set<T>::iterator        // type of a.begin() or a.end()
  Set<T>::const_iterator  // type if a is const

Both iterator types are read-only forward iterators and are identical
except that conversion is allowed from iterator to const_iteratur but
not the other way.

  Set<T>::iterator p, q=a.begin();   // Declarations
  p==q           // true if p and q point to the same element
  p!=q           // false if p==q
  ++p            // Advance p to next element, return new p
  p++            // Advance p to next element, return original p
  *p             // Element pointed to by p (read-only)
  p->member      // member of struct T pointed to by p (read-only)
  Set<T>::const_iterator c = p;  // Behaves same as p
  p = c;         // Error
*/

#include <iostream>
#include <iterator>  // new

////////// Set from assignment 5, with the addition of iterators, begin/end

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,...}

  ////////// New in assignment 6:
  friend class const_iterator;  // because Node is private
  friend class iterator;
private:
  const Node* first() const { // Find first node in tree (or 0 if empty)
    const Node* p=root;
    while (p && p->left)
      p=p->left;
    return p;
  }
public:

  // const_iterator is a base class to allow conversion from iterator
  class const_iterator {
    friend class Set<T>;
  protected:
    const Node *p;  // Current node, 0 means end
    const Node *root;  // Root node of tree pointed into by p
    const_iterator(const Node* a, const Node* b): p(a), root(b) {}

    // Return first node > x in branch, or 0 if all nodes <= x
    const Node* next(const T& x, const Node* branch) const {
      if (!branch)
        return 0;
      else if (x < branch->data) {
        const Node* q = next(x, branch->left);
        if (q)
          return q;
        else
          return branch;
      }
      else
        return next(x, branch->right);
    }
  public:
    const_iterator(): p(0), root(0) {}
    typedef std::forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
    bool operator==(const const_iterator& q) const {return p==q.p;}
    bool operator!=(const const_iterator& q) const {return p!=q.p;}
    pointer operator->() const {return &p->data;}
    reference operator*() const {return p->data;}
    const_iterator& operator++() {
      p=next(p->data, root);
      return *this;
    }
    const_iterator operator++(int i) { // postfix
      const_iterator t=*this;
      ++*this;
      return t;
    }
  };

  // iterator inherits everything but ++ (return type changes) and constructors
  class iterator: public const_iterator {
    friend class Set<T>;
  private:
    iterator(const Node* a, const Node* b): const_iterator(a, b) {}
  public:
    iterator(): const_iterator() {}
    iterator& operator++() {
      p=next(p->data, root);
      return *this;
    }
    iterator operator++(int i) {
      iterator t=*this;
      ++*this;
      return t;
    }
  };

  // The const versions of begin/end return const_iterator
  const_iterator begin() const {return const_iterator(first(), root);}
  iterator begin() {return iterator(first(), root);}
  const_iterator end() const {return const_iterator();}
  iterator end() {return iterator();}
};

////////// Private member functions, unchanged from assignment 5

// 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, unchanged from assignment 5

// 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 assignments 4 and 5:

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

/////////// Assignment 6 program starts here

#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// print1(s) through print4(s) print up to 10 elements of s, but in
// different ways to test different aspects of Set iterators.

// Print - test const_iterator, !=, postfix ++, *
void print1(const Set<string>& s) {
  int i=0;
  for (Set<string>::const_iterator p=s.begin(); p!=s.end() && ++i<=10; p++)
    cout << " " << *p;
  cout << endl;
}

// Print - test iterator, ==, prefix ++
void print2(Set<string> s) {
  int i=0;
  for (Set<string>::iterator p=s.begin(); !(p==s.end()) && ++i<=10; ++p)
    cout << " " << *p;
  cout << endl;
}

// Print - test conversion from iterator to const_iterator
void print3(Set<string> s) {
  int i=0;
  for (Set<string>::const_iterator p=s.begin(); p!=s.end() && ++i<=10; ++p)
    cout << " " << *p;
  cout << endl;
}

// Print - test copy()
void print4(const Set<string>& s) {
  vector<string> v(s.size());
  copy(s.begin(), s.end(), v.begin());
  for (int i=0; i<int(v.size()) && i<10; ++i)
    cout << " " << v[i];
  cout << endl;
}

int main(int argc, char** argv) {

  // Check for 2 args
  if (argc!=3) {
    cerr << "To compare sets of words in 2 files: wcmp file1 file2\n";
    return 1;
  }

  // Open files
  ifstream f1(argv[1]);
  if (!f1) {
    cerr << "File " << argv[1] << " not found\n";
    return 1;
  }
  ifstream f2(argv[2]);
  if (!f2) {
    cerr << "File " << argv[2] << " not found\n";
    return 1;
  }

  // Read words from file1 and file2 into set1 and set2
  string s;
  Set<string> set1, set2;
  while (f1 >> s)
    set1 += s;
  while (f2 >> s)
    set2 = set2 + s;

  // Print results
  cout << (set1+set2).size() << " word(s) in either file:";
  print1(set1+set2);
  cout << (set1*set2).size() << " word(s) in both files:";
  print2(set1*set2);
  cout << (set1-set2).size() << " word(s) in " << argv[1] << " but not "
    << argv[2] << ":";
  print3(set1-set2);
  cout << (set2-set1).size() << " word(s) in " << argv[2] << " but not "
    << argv[1] << ":";
  print4(set2-set1);
  return 0;
}