#ifndef _UNIQUE_CONS_H_
#define _UNIQUE_CONS_H_

#include "hash_maps.h"
#include "ullist.h"
#include "llist.h"

/* U should be a hashable type large enough to hold a T.
   E.g., if U is a pointer then use intptr_t. */
#define generic template <class T, class U>
#define genericT template <class T>

generic class UniqueCons;

generic class UniqueCons {
  typedef T value_type;
  typedef ullist<T> list_type;
  typedef ullist<T> * list_ref;
  typedef const ullist<T> * const_list_ref;
  /*
  typedef POINTER_HASH_MAP(const_list_ref, const_list_ref) map_list_to_list;
  typedef HASH_MAP(U, map_list_to_list) map_value_list_to_list;
  */
  typedef map<intptr_t, const_list_ref> map_list_to_list;
  typedef map<U, map_list_to_list> map_value_list_to_list;

private:
  // m is a cache of cons cells to memoize cons()
  // for operation cons(v,l), returns the preexisting cons cell if one exists
  // the result is that every list with identical contents created by the
  // UniqueCons object is actually the same list in memory
  map_value_list_to_list m; 
    
  // ma is memoizes the result of adjoin(), which inserts items into a sorted list
  // DOB: because of the above invariant, I don't think this ever saves memory (cons cells)
  //  but it will speed up calls to the adjoin() that insert items already present 
  //  in the given list
  map_value_list_to_list ma;

  // int steps;

public:  
  // cons v onto list l and return the resulting cons cell
  // re-use an existing cons cell if an appropriate one already exists
  const_list_ref cons(value_type v, const_list_ref l) {
    // cout << "UC cons(value_type v, const_list_ref l)" << endl;
    const_list_ref & result = m[v][(intptr_t) l];
    if (result)
      return result;
    else
      return (result = new list_type(v, l));
  }
  const_list_ref cons(value_type v) { return cons(v, NULL); }

  UniqueCons() /* : steps(0) */ {}
  
  ~UniqueCons() {
    for (TYPENAME map_value_list_to_list::const_iterator i = m.begin();
	 i != m.end();
	 i++)
      for (TYPENAME map_list_to_list::const_iterator j = (*i).second.begin();
	   j != (*i).second.end();
	   j++)
	delete (*j).second;
  }

  // non-destructively append L1 onto the end of L0 and return resulting list
  const_list_ref append(const_list_ref L0, const_list_ref L1) {
#if 0
    // recursive implementation causes program stack overflows on deep lists
    if (L0 == NULL)
      return L1;
    else if (L1 == NULL)
      return L0;
    else 
      return cons(L0->front(), append(L0->tail(), L1));
#else
    // DOB: equivalent iterative implementation
    if (L1 == NULL)
      return L0;
    llist<const_list_ref> *stack = NULL;
    while (L0) {
      push(stack, L0);
      L0 = L0->tail();
    }
    const_list_ref result = L1;
    while (stack) {
      result = cons(stack->front()->front(), result);
      stack = stack->free();
    }
    return result;
#endif
  }

  // non-destructively reverse L and return resulting list
  const_list_ref reverse (const_list_ref L)
  {
    const_list_ref result = NULL;
    if (L == NULL)
      return NULL;
    foreach_const (p, TYPENAME list_type, *L)
      result = cons (*p, result);
    return result;
  }

  /* Set operations on ordered lists */
  // T must define the following operators: <,>,==
  // (DOB: this could be reduced to just < with some work)

  // non-destructively insert v into its sorted position in l and return resulting list
  const_list_ref adjoin(value_type v, const_list_ref l)
  {
    // cout << "UC adjoin()" << endl;
#if 0
    // recursive implementation causes program stack overflows on deep lists
    const_list_ref & result = ma[v][l];
    if (result)
      return result;
    else if (l == NULL)
      return (result = cons(v));
    else if (l->front() == v)
      return (result = l);
    else if (l->front() > v)
      return (result = cons(v, l));
    else
      return (result = cons(l->front(), adjoin(v, l->tail())));
#else
    // DOB: equivalent iterative implementation
    map_list_to_list& mav = ma[v];
    const_list_ref & memoizedresult = mav[(intptr_t) l];
    if (memoizedresult) 
      return memoizedresult;
    else if (l == NULL)
      return (memoizedresult = cons(v));

    llist<const_list_ref> *stack = NULL;
    while (l && v > l->front() && mav[(intptr_t) l] == NULL) {
      push(stack, l);
      l = l->tail();
      // ++steps;
    }

    const_list_ref result = NULL;
    if (mav[(intptr_t) l]) result = mav[(intptr_t) l];
    else if (l && l->front() == v) result = l;
    else result = cons(v, l);

    while (stack) {
      const_list_ref ltmp = stack->front();
      result = cons(ltmp->front(), result);
      mav[(intptr_t) ltmp] = result;
      stack = stack->free();
      // ++steps;
    }
    // cout << "in adjoin: " << steps << endl;
    return result;
#endif
  }
  
  // non-destructively merge (union) 2 ordered lists and return resulting list
  const_list_ref merge(const_list_ref l0, const_list_ref l1)
  {
    // cout << "UC merge()" << endl;
#if 0
    // recursive implementation causes program stack overflows on deep lists
    if (l0 == NULL)
      return l1;
    else if (l1 == NULL || l1 == l0)
      return l0;
    else if (l0->front() < l1->front())
      return cons(l0->front(), merge(l0->tail(), l1));
    else if (l0->front() > l1->front())
      return cons(l1->front(), merge(l1->tail(), l0));
    else
      return cons(l0->front(), merge(l1->tail(), l0->tail()));
#else
    // DOB: equivalent iterative implementation
    llist<const_list_ref> *stack = NULL;
    while (l0 && l1 && (l0 != l1)) {
      // ++steps;
      const value_type &l0v = l0->front();
      const value_type &l1v = l1->front();
      if (l0v < l1v) {
        push(stack, l0);
        l0 = l0->tail();
      }
      else if (l0v > l1v) {
        push(stack, l1);
        l1 = l1->tail();
      }
      else {
        push(stack, l0);
        l0 = l0->tail();
        l1 = l1->tail();
      }
    }

    const_list_ref result = NULL;
    if (l0) result = l0;
    else result = l1;

    while (stack) {
      // ++steps;
      const_list_ref ltmp = stack->front();
      result = cons(ltmp->front(), result);
      stack = stack->free();
    }

    // cout << "in merge: " << steps << endl;
    return result;
#endif
  }

  // non-destructively intersect 2 sorted lists and return resulting list
  const_list_ref intersect(const_list_ref l0, const_list_ref l1)
  {
    // cout << "UC intersect()" << endl;
#if 0
    // recursive implementation causes program stack overflows on deep lists
    if (l0 == NULL || l1 == NULL)
      return NULL;
    else if (l0 == l1)
      return l0;
    else if (l0->front() < l1->front())
      return intersect(l0->tail(), l1);
    else if (l0->front() > l1->front())
      return intersect(l1->tail(), l0);
    else
      return cons(l0->front(), intersect(l1->tail(), l0->tail()));
#else
    // DOB: equivalent iterative implementation
    llist<const_list_ref> *stack = NULL;
    while (l0 && l1 && (l0 != l1)) {
      const value_type &l0v = l0->front();
      const value_type &l1v = l1->front();
      if (l0v < l1v) l0 = l0->tail();
      else if (l0v > l1v) l1 = l1->tail();
      else {
        push(stack, l0);
        l0 = l0->tail();
        l1 = l1->tail();
      }
    }

    const_list_ref result = NULL;
    if (l0 == l1) result = l0;

    while (stack) {
      const_list_ref ltmp = stack->front();
      result = cons(ltmp->front(), result);
      stack = stack->free();
    }

    return result;
#endif
  }
  
  size_t size(const_list_ref l0) {
    return l0 ? l0->size() : 0;
  }

};

genericT ullist<T>* find(T x, ullist<T>* l)
{
  while (l)
    if (l->front() == x) return l;
    else l = l->tail();

  return NULL;
}

genericT bool find(bool f(T x), ullist<T> *l)
{
  while (l != NULL)
    if (f(l->front()))
      return true;
    else
      l = l->tail();

  return false;
}

#undef generic

#endif //_UNIQUE_CONS_H_