/* -*- c++ -*- */
/* llist.h: Functional (Lisp-style) lists				*/

/* Copyright (C) 1996, Paul N. Hilfinger.  All Rights Reserved.		*/

 
#ifndef _LLIST_H_
#define _LLIST_H_

#include "utils.h"
#include "debug_memory.h"

#if defined(__GNUC__) && __GNUC__ == 2 && __GNUC_MINOR__ <= 8
# define CONS_TEMPLATES_INSIDE
#endif

/* An llist<T> is essentially an element of a Lisp-style list whose */
/* head (`car' in Lisp terminology) has type T.  One always */
/* manipulates llist<T>s by pointers; to prevent accidents, the */
/* constructors are private. */

#define generic template <class T>

generic class llist;
generic llist<T>* copylist (const llist<T>* L);
generic llist<T> *cons(T const &, llist<T> *);
generic llist<T> *cons(T const &);

generic class llist {
public:
				/* Constructor */
#ifdef CONS_TEMPLATES_INSIDE
    /* NOTE: Due to a bug in versions of G++ up to 2.7.2 (at least), */
    /* we must put the definition here. */

    /* Constructor for llist<T>.  */
    friend llist<T>* cons(T const& head, llist<T>* tail) {
	return new llist<T> (head, tail);
    }

    /* Same as cons(head, NULL) */
    friend llist<T>* cons(T const& head) {
	return new llist<T> (head, NULL);
    }

#else
    /* Constructor for llist<T>.  */
    friend llist<T>* cons<T>(T const& head, llist<T>* tail);
    /* Same as cons(head, NULL) */
    friend llist<T>* cons<T>(T const& head);
#endif


				/* Standard Types */

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

				/* Iterators */

    class iterator {
    public:
 #if defined(__GNUC__) && __GNUC__ == 2 && __GNUC_MINOR__ == 97
   /* work-around for a buggy g++ release on Tru64 */
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef T difference_type;
    typedef void iterator_category;
 #endif
	iterator () : p (NULL) {}
	iterator (llist<T>* p0) : p (p0) {}
	iterator (void*) : p (NULL) {}
	bool operator== (const iterator& x) const { return x.p == p; }
	bool operator!= (const iterator& x) const { return !(*this == x); }
	iterator& operator++ () { p = p->tail(); return *this; }
	iterator operator++ (int) { iterator r = p; p = p->tail(); return r; }
	reference operator* () { return p->front(); }
	llist<T>* _list_element () const { return p; }
    private:
	llist<T>* p;
    };

    class const_iterator {
    public:
	const_iterator () : p (NULL) {}
	const_iterator (const llist<T>* p0) : p (p0) {}
	const_iterator (void*) : p (NULL) {}
	const_iterator (const iterator& x) : p(x._list_element ()) {}
	bool operator== (const const_iterator& x) const { return x.p == p; }
	bool operator== (const iterator& x) const { 
	    return x._list_element() == p;
	}
	bool operator!= (const const_iterator& x) const { return !(*this == x); }
	bool operator!= (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 llist<T>* p;
    };

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

				/* Accessors */

    /* cons(x,y)->front() yields x.  It is assignable when called on a */
    /* non-const object. */
    reference front () { return head; }
    const_reference front () const { return head; }

    /* cons(x,y)->tail() yields y.  It is assignable when called on a */
    /* non-const object.  */
    llist<T>*& tail () { return rest; }
    const llist<T>* tail () const { return rest; }


    reference last() { return (rest == NULL) ? head : rest->last(); }
    const_reference last() const {
        const_reference q = (rest == NULL) ? head : rest->last();
	return q;
    }

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

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

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

    llist<T> * copy() { return copylist(this); }

				/* Other mutation */

    /* Swap the fronts and the tails of *this and x. */
    void swap (llist<T>& x) { 
	T htmp = head;
	head = x.head; x.head = htmp;
	llist<T>* ttmp = rest;
	rest = x.rest; x.rest = ttmp;
    }
    
				/* Storage management */

    /* Release storage for *this, returning the value of tail. */
    llist<T>* free () { llist<T>* t = rest; delete this; return t; }

    /* Remove (and release storage for) the i'th cons cell from a list.  i counts from 0. */
    llist<T> * excise(int i) {
        if (i == 0)
	    return free();
	else
	    rest = rest->excise(i - 1);
	return this;
    }

    T * to_array() const {
        T * result = new T [size()];
	int j = 0;
	for (const_iterator i = begin(); i != end(); i++, j++)
	    result[j] = *i;
	return result;
    }

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

    T head;
    llist<T>* rest;
};

generic void free_all (llist<T>* x)
{
    while (x != NULL)
	x = x->free ();
}

generic void free_list_and_delete_elements (llist<T>* x)
{
  while (x != NULL) {
    delete x->front();
    x = x->free();
  }
}

/* Result of appending L0 and L1 non-destructively. */
generic llist<T>* append (llist<T>* L0, llist<T>* L1)
{
    if (L0 == NULL)
	return L1;
    else if (L1 == NULL)
	return L0;
    else {
	llist<T>* first = cons (L0->front ());
	llist<T>* last;
	last = first;
	foreach (p, TYPENAME llist<T>, *(L0->tail ())) {
	    last = last->tail () = cons (*p);
	}
	last->tail () = L1;
	return first;
    }
}

generic llist<T>* copylist (const llist<T>* L)
{
  llist<T>* result = NULL;
  foreach_const (p, TYPENAME llist<T>, *L)
    result = cons(*p, result);
  return dreverse(result);
}

/* Result of appending L0 and L1 destructively. */
generic llist<T>* extend (llist<T>* L0, llist<T>* L1)
{
    if (L0 == NULL)
	return L1;
    else if (L1 == NULL)
	return L0;
    else {
	llist<T>* p;
	for (p = L0; p->tail () != NULL; p = p->tail ())
	    ;
	p->tail () = L1;
	return L0;
    }
}
/* Destructively append a single element. */
generic llist<T>* extend (llist<T>* L, T const & x)
{
    return extend(L, cons(x));
}

/* Result of reversing L non-destructively */
generic llist<T>* reverse (const llist<T>* L)
{
    llist<T>* result = NULL;
    if (L == NULL)
	return NULL;
    foreach_const (p, TYPENAME llist<T>, *L)
	result = cons (*p, result);
    return result;
}

generic llist<T>* nthcdr (llist<T>* L, size_t k)
{
  while (k > 0) {
    L = L->tail();
    k--;
  }
  return L;
}

/* Result of reversing L destructively */
generic llist<T>* dreverse (llist<T>* L)
{
    llist<T>* p;
    if (L == NULL)
	return NULL;
    p = NULL;
    while (L->tail () != NULL) {
	llist<T>* next = L->tail ();
	L->tail () = p;
	p = L;
	L = next;
    }
    L->tail () = p;
    return L;
}    

generic llist< llist<T> * > * map_cons(T const & x, llist< llist<T> * > *l)
{
  llist< llist<T> * > * result = NULL;
  while (l != NULL) {
    result = cons(cons(x, l->front()), result);
    l = l->tail();
  }
  return dreverse(result);
}

generic llist< llist<T> * > * powerset(llist<T> *l)
{
  if (l == NULL)
    return cons((llist<T> *) NULL);
  else {
    llist< llist<T> * > * result = powerset(l->tail());
    return extend(map_cons(l->front(), result), result);
  }
}

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

  return NULL;
}

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

  return false;
}

generic bool contains(llist<T> *l, T const & x)
{
  return (find(x, l) != NULL);
}

generic bool contains_any(llist<T> *l1, llist<T> *l2)
{
  return l2 != NULL &&
    (contains(l1, l2->front()) || contains_any(l1, l2->tail()));
}

template< class T, class F >
llist<T> * filter( F f, llist<T> *l)
{
  llist<T> *result = 0;
  for ( ; l; l = l->tail())
    if (f(l->front()))
      push(result, l->front());
  
  return result;
}

template< class T, class F >
llist<T> * destructive_filter(F f, llist<T> *l)
{
  llist<T> *orig_l = l;
  while (orig_l && !f(orig_l->front())) orig_l = orig_l->free();
  if (orig_l == NULL) return orig_l;
  l = orig_l;
  while (l->tail()) {
    if (f(l->tail()->front())) l = l->tail();
    else l->tail() = l->tail()->free();
  }
  return orig_l;
}

/* Destructive delete on the first matching element found. Returns -1 
   if the element was not found. */
generic llist<T>* remove(T const & x, llist<T>* l) 
{
  llist<T> *orig_l = l;
  if (l->front() == x)
    return l->free();

  while (l->tail()) {
    if (l->tail()->front() == x) {
      l->tail() = l->tail()->free();
      return orig_l;
    }
    l = l->tail();
  }
  return (llist<T>*)-1;
}

#ifndef CONS_TEMPLATES_INSIDE
generic llist<T>* cons (T const& head, llist<T>* tail)
{
    return new PASS_RETADR llist<T>(head, tail);
}

generic llist<T>* cons(T const& head) {
    return new PASS_RETADR llist<T> (head, NULL);
}
#endif

template< class T, class U > inline
llist<T>* push(llist<T> *& list, const U &element) {
    const T &addend = element;
    list = cons( addend, list );
    return list;
}

generic T* llist_to_array(llist<T> *list)
{
  return list->to_array();
}

/* Hilfinger Standard Iterators */

generic class ListIterator {
public:
    ListIterator () {} 
    ListIterator (llist<T>* L) : p (L) {}

    bool isDone () const { return p == NULL; }
    void next () { p = p->tail (); }
    T& operator* () const { return p->front(); }
    T* operator-> () const { return &p->front(); }
private:
    llist<T>* p;
};

generic ListIterator<T> elements (llist<T>* L)
{
    return L;
}

#undef generic

#endif