/* ullist.h: Unique cons lists */

#ifndef _ULLIST_H_
#define _ULLIST_H_

#include "utils.h"

#define generic template <class T>

generic class ullist;

generic class ullist {

 public:
    ullist (const T& head0, const ullist<T>* tail0)
	: head (head0), rest (tail0) {}

    /* Standard Types */

    typedef T value_type;
    typedef T& reference;
    typedef T const& const_reference;

    /* Iterators */

    class const_iterator {
    public:
	const_iterator () : p (NULL) {}
	const_iterator (const ullist<T>* p0) : p (p0) {}
	const_iterator (void*) : p (NULL) {}
	bool operator== (const const_iterator& x) const { return x.p == p; }
	bool operator!= (const const_iterator& x) const { return !(*this == x); }
	const_iterator& operator++ () { p = p->tail(); return *this; }
	const_iterator operator++ (int) { 
	    const_iterator r = p; p = p->tail(); return r; 
	}
	const_reference operator* () { return p->front(); }
    private:
	const ullist<T>* p;
    };

    const_iterator begin () const { return this; }
    const_iterator end () const { return const_iterator(); }
    

    /* Accessors */

    /* cons(x,y)->front() yields x.  It is not assignable. */
    const_reference front () const { return head; }

    /* cons(x,y)->tail() yields y.  It is not assignable. */
    const ullist<T>* tail () const { return rest; }

    const_reference operator[](size_t i) const {
        const ullist<T>* p;
	for (p = this; i != 0; i -= 1, p = p->rest)
	    ;
	return p->head;
    }

    size_t size () const {
	const ullist<T>* p;
	size_t n;
	for (p = this, n = 0; p != NULL; p = p->rest, n += 1)
	    ;
	return n;
    }
    
 private:
    T head;
    const ullist<T>* rest;
};

/* Assumes nothing about ordering of l. */
generic bool contains(ullist<T> * l, T x)
{
  while (l != NULL)
    if (l->front() == x) return true;
    else l = l->tail();

  return false;
}

/* set ops on ordered lists */

generic bool ocontains(const ullist<T> * l, T x)
{
  while (l != NULL && l->front() <= x)
    if (l->front() == x) return true;
    else l = l->tail();

  return false;
}

/* Is l0 a subset of l1? */
generic bool isSubset(const ullist<T> * l0, const ullist<T> * l1)
{
  while (1) {
    if (l0 == NULL || l0 == l1)
      return true;
    else if (l1 == NULL)
      return false;
    else if (l0->front() < l1->front())
      return false;
    else if (l0->front() > l1->front())
      l1 = l1->tail();
    else {
      l0 = l0->tail();
      l1 = l1->tail();
    }
  }
}

#undef generic

#endif