#ifndef _TI_INTERVAL_SET_H_
#define _TI_INTERVAL_SET_H_

/* IntervalSet is a "factory" for creating sets over a limited universe
   of values (whose type is the IntervalSet template parameter).
   Sets are represented as sorted lists of integer ranges. */

#define DEBUG_INTERVAL DEBUG_PHASE_ENABLED("intervalset", currentFilename)

#include "garbageList.h"
#define EXTERN static
#define INLINE_MODIFIER inline
#define INLINE(x) x
#define ALLOC(T, n) garbageListAlloc<T>(n)
#define FREE(p) garbageListFree((char *) p)

#define bool bool
#define true true
#define false false
#include "../runtime/stoptifu/iseti.h"
#undef bool
#undef true
#undef false

#include <map>
#include <set>

#define generic template <class T>

#define QSET(s) 					\
    (iseti_is_empty(s) ? 				\
     string("{}") : 					\
     (string("{") + int2string(iseti_min(s)) +		\
      (iseti_max(s) == iseti_min(s) ? "}" : ", ...}")))

generic class IntervalSet {
public:
  typedef T value_type;
  typedef T const & const_reference;
  typedef iseti set;
  typedef map< int, value_type > map_int_to_value;
  map_int_to_value mInverse;
  
private:
  typedef map< value_type, int > map_value_to_int;

  int count;
  map_value_to_int m;

 public:
  int R(value_type x)
  {
    int & result = m[x];
    if (result != 0)
      return result;
    else {
      ++count;
      result = -count;
      if (DEBUG_INTERVAL) {
	cout << long2hexstring((long) x) << " is " << result << endl;
      }
      mInverse[result] = x;
      return result;
    }
  }
  
public:  
  IntervalSet<T>() : count (0) {}

  class set_iterator {
  public:
    set_iterator() : F(NULL) {}
    set_iterator(const IntervalSet<T> *F, set p) : p(p), F(F) {
      if (F->isEmpty(p))
	F = NULL;
      else
	next = F->min(p);
    }
    set_iterator(const void *) : F(NULL) {}
    bool operator== (const set_iterator& x) const {
      return x.F == F && (F == NULL || (x.next == next && F->equal(x.p, p)));
    }
    bool operator!= (const set_iterator& x) const {
      return !(*this == x);
    }
    set_iterator& operator++ () {
      if (F != NULL && !iseti_contains(p, ++next)) {
	p = tail_interval(p);
	if (F->isEmpty(p))
	  F = NULL;
	else
	  next = F->min(p);
      }
      return *this;
    }
    set_iterator operator++ (int) { 
      set_iterator r = *this; ++(*this); return r; 
    }
    const_reference operator* () {
      return ((IntervalSet<T> *) F)->mInverse[next];
    }
  private:
    set p;
    int next;
    const IntervalSet<T> *F;
  };

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

  inline void dump(ostream &o, set s) const { o << iseti_to_string(s); }

  inline bool isEmpty(set s) const { return iseti_is_empty(s); }

  inline set empty() const { return iseti_emptyset(); }
  inline int min(set s) const { return iseti_min(s); }
  inline int max(set s) const { return iseti_max(s); }
  inline bool equal(set s, set t) const { return iseti_equal(s, t); }

  inline set singleton(value_type v) { return iseti_singleton(R(v)); }

  /* Non-destructive, but result may share part or all of l's structure. */
  inline set share_adjoin(value_type v, set l)
  {
    if (DEBUG_INTERVAL)
      cout << "share_adjoin(" << int2string(R(v)) << ", " << QSET(l) << ")" << endl;
    return iseti_share_adjoin(R(v), l);
  }
  
  /* Non-destructive, and result will not share any of l's structure. */
  inline set adjoin(value_type v, set l)
  {
    if (DEBUG_INTERVAL)
      cout << "adjoin(" << int2string(R(v)) << ", " << QSET(l) << ")" << endl;
    return iseti_adjoin(R(v), l);
  }
  
  /* Destructive adjoin */
  inline set dadjoin(value_type v, set l)
  {
    return iseti_destructive_adjoin(R(v), l);
  }
  
  /* Non-destructive */
  inline set merge(set l0, set l1)
  {
    if (DEBUG_INTERVAL)
      cout << "merge(" << QSET(l0) << ", " << QSET(l1) << ")" << endl;
    return iseti_union(l0, l1);
  }

  /* Destructive */
  inline set dmerge(set l0, set l1)
  {
    if (DEBUG_INTERVAL)
      cout << "dmerge(" << QSET(l0) << ", " << QSET(l1) << ")" << endl;
    return iseti_destructive_union(l0, l1);
  }

  inline set intersect(set l0, set l1)
  {
    return iseti_intersection(l0, l1);
  }
  
  inline set makeset(llist<value_type> *l) {
    set s = empty();
    foreach_const (i, llist<value_type>, *l)
      s = dadjoin(*i, s);
    return s;
  }

#if 0
  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;
  }
#endif

  inline size_t size(set s) {
    size_t result = 0;
    iinterval_list *l = s.l;
    while (l != NULL) {
      result += head_interval(l)->hi - head_interval(l)->lo + 1;
      l = tail_interval(l);
    }
    return result;
  }
  
  inline bool contains(set l0, value_type v) {
    return iseti_contains(l0, R(v));
  }
};

#undef QSET
#undef generic

#endif /* _TI_INTERVAL_SET_H_ */