#ifndef _TC_EQUIV_REL_H_
#define _TC_EQUIV_REL_H_

#include "gcset.h"
#include <map>

#define generic template <class T>

generic class EquivalenceRelation {
public:
  typedef gcset<T> * EqClass;

private:
  // If x is the first element of m[x] then m[x] is x's equivalence
  // class.  Otherwise, let f = first element of m[x]; x's equivalence
  // class is the equivalence class of f.
  map<T, EqClass> m;

public:
  EqClass classOf(T x) {
    EqClass &E = m[x];
    if (E == NULL) {
      E = new gcset<T>();
      E->insert(x);
    } else {
      const T first = *(E->begin());
      if (first != x)
	E = classOf(first);
    }
    return E;
  }

  T canonicalElement(T x) { return *(classOf(x)->begin()); }

  EqClass insert(T x, T y) {
    EqClass xc = classOf(x), yc = classOf(y);
    if (xc == yc) 
      return xc;
    EqClass u = new gcset<T>();
    for (TYPENAME set<T>::const_iterator i = yc->begin(); i != yc->end(); i++)
      u->insert(*i);
    for (TYPENAME set<T>::const_iterator i = xc->begin(); i != xc->end(); i++)
      u->insert(*i);
    return m[x] = m[y] = m[*(xc->begin())] = m[*(yc->begin())] = u;
  }

  inline bool contains(T x) const { return (m.find(x) != m.end()); }
  inline bool sameClass(T x, T y) {
    return (contains(x) && contains(y) && classOf(x) == classOf(y));
  }

  class const_iterator {
  public:
    const_iterator(typename map<T, EqClass>::const_iterator i,
		   EquivalenceRelation<T> *rel = NULL) : i(i), rel(rel) {}
    const_iterator& operator++ () { i++; return *this; }
    const_iterator operator++ (int) { const_iterator r(i, rel); i++; return r; }
    bool operator== (const const_iterator& x) const { return x.i == i; }
    bool operator!= (const const_iterator& x) const { return !(*this == x); }
    T operator* () { return (*i).first; }
    EqClass equivalences() { return rel->classOf((*i).first); }
    
  private:
    typename map<T, EqClass>::const_iterator i;
    EquivalenceRelation<T> *rel;
  };
  
  const_iterator begin() { return const_iterator(m.begin(), this); }
  const_iterator end() { return const_iterator(m.end()); }

  void dump(ostream &o) {
    for (const_iterator p = begin(); p != end(); p++) {
      o << *p << " : { ";
      EqClass E = p.equivalences();    
      for (TYPENAME set<T>::iterator q = E->begin(); q != E->end(); q++)
	o << *q << ' ';
      o << "}" << endl;
    }
  }

};

#undef generic

#endif //_TC_EQUIV_REL_H_