#ifndef _ORDERLY_SET_H_
#define _ORDERLY_SET_H_

#include <map>
#include <set>
#include "UniqueCons.h"
#include "llist.h"
#include "code-util.h"
#include "code.h"
#include "using-std.h"

#define TRY_HASHING 1

#if TRY_HASHING
#include "hash_maps.h"
#endif

#define DEBUG_ORDERLY DEBUG_PHASE_ENABLED("ord", currentFilename)

#include <string>
#define QSET(s) 				\
    ((s) == NULL ? 				\
     string("{}") : 				\
     (string("{") + int2string(s->front()) + 	\
      (s->tail() == NULL ? "}" : ", ...}")))

#define generic template <class T>

generic class OrderlySet;

// OrderlySet is a "factory" for creating sets over a limited universe
//  of values (whose type is the OrderlySet template parameter)
// Implemented in such a way that the sets with similar contents 
//  created by the same factory object will share some of their 
//  substructure when possible, for memory efficiency
// The sets (OrderlySet<T>::set) are immutable, and are created using
//  empty(), makeset() or other OrderlySet methods that return a set
// Note that factory methods which take set parameters should ONLY be 
//  used on sets created by this _same_ OrderlySet factory object

generic class OrderlySet {
public:
  typedef T value_type;
  typedef T const & const_reference;
  typedef const ullist<int> * set;
#if TRY_HASHING
  typedef HASH_MAP(int, value_type) map_int_to_value;
#else
  typedef map< int, value_type > map_int_to_value;
#endif
  map_int_to_value mInverse;
  
private:
#if TRY_HASHING
  typedef HASH_MAP(intptr_t, int) map_value_to_int;
#define MAP(x) m[(intptr_t) (x)]
#else
  typedef map< value_type, int > map_value_to_int;
#define MAP(x) m[x]
#endif

  UniqueCons<int> U;
  int count;
  map_value_to_int m;

 public: // temporarily public
  int R(value_type x)
  {
    int & result = MAP(x);
    if (result != 0)
      return result;
    else {
      ++count;
      result = -count;
      if (DEBUG_ORDERLY) {
	cout << long2hexstring((long) x) << " is " << result << endl;
      }
      mInverse[result] = x;
      return result;
    }
  }
 private:
  inline set _adjoin(int v, set l)
  {
    if (DEBUG_ORDERLY)
      cout << "_adjoin(" << int2string(v) << ", " << QSET(l) << ")" << endl;
    return U.adjoin(v, l);
  }
  
public:  
  OrderlySet<T> () : count (0) {}

  class set_iterator {
  public:
    set_iterator (const OrderlySet<T> *F0, set p0) : p (p0), F (F0) {}
    set_iterator (const void *) : p (NULL), F (NULL) {}
    bool operator== (const set_iterator& x) const {
      return x.p == p && x.F == F;
    }
    bool operator!= (const set_iterator& x) const {
      return !(*this == x);
    }
    set_iterator& operator++ () { p = p->tail(); return *this; }
    set_iterator operator++ (int) { 
      set_iterator r = p; p = p->tail(); return r; 
    }
    const_reference operator* () {
      return ((OrderlySet<T> *) F)->mInverse[p->front()];
    }
  private:
    set p;
    const OrderlySet<T> *F;
  };

  inline set_iterator begin (set s) const {
    return set_iterator(this, s);
  }
  inline set_iterator end (set s) const {
    return set_iterator(this, NULL);
  }

  inline void dump(ostream &o, set s) const {
    o << "{";
    while (s != NULL) {
      o << ' ' << s->front();
      s = s->tail();
    }
    o << " }";
  }

  inline value_type head(set s) { return mInverse[s->front()]; }
  inline set tail(set s) { return s->tail(); }

  inline bool isEmpty(set s) { return s == NULL; }

  inline set empty() { return NULL; }

  inline set singleton(value_type v) { return adjoin(v, NULL); }

  inline set adjoin(value_type v, set l)
  {
    // cout << "O adjoin(value_type v, set l)" << endl;
    if (DEBUG_ORDERLY)
      cout << "adjoin(" << int2string(R(v)) << ", " << QSET(l) << ")" << endl;
    return U.adjoin(R(v), l);
  }
  
  // Same order as the "old way."  Apply R() in LIFO order.
  class lazyset {
  public:
    lazyset() : l(NULL) {}
    ~lazyset() { free_all(l); }
    inline void adjoin(value_type v) { l = cons(v, l); }
    inline llist<value_type> *as_list() { return l; }
  private:
    llist<value_type> *l;
  };

  // Reversed order from the "old way."  Apply R() in FIFO order.
  class reverse_lazyset {
  public:
    ::set<int> s;
  };

  inline void adjoin(value_type v, reverse_lazyset &s) { s.s.insert(R(v)); }

  set makeset(reverse_lazyset &s) {
    // cout << "O makeset(reverse_lazyset &s)" << endl;
    set result = empty();
    for (::set<int>::reverse_iterator e = s.s.rbegin(); e != s.s.rend(); e++)
      result = _adjoin(*e, result);
    return result;
  }

  set makeset(const llist<value_type> *l)
  {
    // cout << "O makeset(const llist<value_type> *l)" << endl;
    reverse_lazyset s;
    foreach_const (i, TYPENAME llist<value_type>, *l)
      adjoin(*i, s);
    return makeset(s);
  }

  inline set makeset(lazyset &s) {
    // cout << "O makeset(lazyset &s)" << endl;
    const llist<value_type> *l = s.as_list();
    return makeset(l);
  }

  inline set merge(set l0, set l1)
  {
    // cout << "O merge()" << endl;
    if (DEBUG_ORDERLY)
      cout << "merge(" << QSET(l0) << ", " << QSET(l1) << ")" << endl;
    return U.merge(l0, l1);
  }

  inline set intersect(set l0, set l1)
  {
    return U.intersect(l0, l1);
  }
  
  set filter(bool f(value_type), set s)
  {
    set result = empty();
    for (set_iterator i = begin(s); i != end(s); i++)
      if (f(mInverse[*i]))
	result = adjoin(*i, result);
    return result;
  }

  inline size_t size(set l0) {
    return l0 ? l0->size() : 0;
  }
  
  inline bool contains(set l0, value_type v) {
    return ocontains(l0, R(v));
  }
};

#undef QSET
#undef generic
#undef MAP

#endif // _ORDERLY_SET_H_