/*
 *  Copyright 2001 Adrian Thurston <thurston@complang.org>
 */
/*  This file is part of Aapl.
 *
 *  Aapl is free software; you can redistribute it and/or modify it under the
 *  terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
 *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
 *  more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
 *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
/* This header is not wrapped in ifndef becuase it is not intended to
 * be included by the user. */
#include "fix_leaks.h"
#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif
#if defined( DOUBLELIST_VALUE )
/**
 * \brief Double list element for DListVal.
 *
 * DListValEl stores the type T of DListVal by value. 
 */
template <class T> struct DListValEl : TmpObject<DListValEl<T>>
{
        /**
         * \brief Construct a DListValEl with a given value.
         *
         * The only constructor available initializes the value element. This
         * enforces that DListVal elements are never created without having their
         * value intialzed by the user. T's copy constructor is used to copy the
         * value in.
         */
        DListValEl( const T &val ) : value(val) { }
        /**
         * \brief Value stored by the list element.
         *
         * Value is always copied into new list elements using the copy
         * constructor.
         */
        T value;
        /**
         * \brief List previous pointer.
         *
         * Points to the previous item in the list. If this is the first item in
         * the list, then prev is NULL. If this element is not in a list then
         * prev is undefined.
         */
        DListValEl<T> *prev;
        /**
         * \brief List next pointer.
         *
         * Points to the next item in the list. If this is the list item in the
         * list, then next is NULL. If this element is not in a list then next is
         * undefined.
         */
        DListValEl<T> *next;
};
#else
#ifndef __AAPL_DOUBLE_LIST_EL
#define __AAPL_DOUBLE_LIST_EL
/**
 * \brief Double list element properties.
 *
 * This class can be inherited to make a class suitable to be a double list
 * element. It simply provides the next and previous pointers. An alternative
 * is to put the next and previous pointers in the class directly.
 */
template <class Element> struct DListEl : TmpObject<DListEl<Element>>
{
        /**
         * \brief List previous pointer.
         *
         * Points to the previous item in the list. If this is the first item in
         * the list, then prev is NULL. If this element is not in a list then
         * prev is undefined.
         */
        Element *prev;
        /**
         * \brief List next pointer.
         *
         * Points to the next item in the list. If this is the list item in the
         * list, then next is NULL. If this element is not in a list then next is
         * undefined.
         */
        Element *next;
};
#endif /* __AAPL_DOUBLE_LIST_EL */
#endif
/* Doubly Linked List */
template <DLMEL_TEMPDEF> class DList : public TmpObject<DList<Element>>
{
public:
        /** \brief Initialize an empty list. */
        DList() : head(0), tail(0), listLen(0) {}
        /** 
         * \brief Perform a deep copy of the list.
         * 
         * The elements of the other list are duplicated and put into this list.
         * Elements are copied using the copy constructor.
         */
        DList(const DList &other);
#ifdef DOUBLELIST_VALUE
        /**
         * \brief Clear the double list contents.
         *
         * All elements are deleted.
         */
        ~DList() { empty(); }
        /**
         * \brief Assign another list into this list using a deep copy.
         *
         * The elements of the other list are duplicated and put into this list.
         * Each list item is created using the copy constructor. If this list
         * contains any elements before the copy, they are deleted first.
         *
         * \returns A reference to this.
         */
        DList &operator=(const DList &other);
        /**
         * \brief Transfer the contents of another list into this list.
         *
         * The elements of the other list moved in. The other list will be empty
         * afterwards.  If this list contains any elements before the copy, then
         * they are deleted. 
         */
        void transfer(DList &other);
#else
        /**
         * \brief Abandon all elements in the list. 
         *
         * List elements are not deleted.
         */
        ~DList() {}
        /**
         * \brief Perform a deep copy of the list.
         *
         * The elements of the other list are duplicated and put into this list.
         * Each list item is created using the copy constructor. If this list
         * contains any elements before the copy, they are abandoned.
         *
         * \returns A reference to this.
         */
        DList &operator=(const DList &other);
        /**
         * \brief Transfer the contents of another list into this list.
         *
         * The elements of the other list moved in. The other list will be empty
         * afterwards.  If this list contains any elements before the copy, they
         * are abandoned. 
         */
        void transfer(DList &other);
#endif
#ifdef DOUBLELIST_VALUE
        /**
         * \brief Make a new element and prepend it to the front of the list.
         *
         * The item is copied into the new element using the copy constructor.
         * Equivalent to list.addBefore(list.head, item).
         */
        void prepend(const T &item);
        /**
         * \brief Make a new element and append it to the end of the list.
         *
         * The item is copied into the new element using the copy constructor.
         * Equivalent to list.addAfter(list.tail, item).
         */
        void append(const T &item);
        /**
         * \brief Make a new element and insert it immediately after an element in
         * the list.
         *
         * The item is copied into the new element using the copy constructor. If
         * prev_el is NULL then the new element is prepended to the front of the
         * list. If prev_el is not already in the list then undefined behaviour
         * results.  Equivalent to list.addAfter(prev_el, new DListValEl(item)).
         */
        void addAfter(Element *prev_el, const T &item);
        /**
         * \brief Make a new element and insert it immediately before an element
         * in the list. 
         *
         * The item is copied into the new element using the copy construcotor. If
         * next_el is NULL then the new element is appended to the end of the
         * list.  If next_el is not already in the list then undefined behaviour
         * results.  Equivalent to list.addBefore(next_el, new DListValEl(item)).
         */
        void addBefore(Element *next_el, const T &item);
#endif
        /**
         * \brief Prepend a single element to the front of the list.
         *
         * If new_el is already an element of some list, then undefined behaviour
         * results. Equivalent to list.addBefore(list.head, new_el).
         */
        void prepend(Element *new_el) { addBefore(head, new_el); }
        /**
         * \brief Append a single element to the end of the list.
         *
         * If new_el is alreay an element of some list, then undefined behaviour
         * results.  Equivalent to list.addAfter(list.tail, new_el).
         */
        void append(Element *new_el)  { addAfter(tail, new_el); }
        /**
         * \brief Prepend an entire list to the beginning of this list.
         *
         * All items are moved, not copied. Afterwards, the other list is emtpy.
         * All items are prepended at once, so this is an O(1) operation.
         * Equivalent to list.addBefore(list.head, dl).
         */
        void prepend(DList &dl)       { addBefore(head, dl); }
        /**
         * \brief Append an entire list to the end of the list.
         *
         * All items are moved, not copied. Afterwards, the other list is empty.
         * All items are appened at once, so this is an O(1) operation.
         * Equivalent to list.addAfter(list.tail, dl).
         */
        void append(DList &dl)        { addAfter(tail, dl); }
        void addAfter(Element *prev_el, Element *new_el);
        void addBefore(Element *next_el, Element *new_el);
        void addAfter(Element *prev_el, DList &dl);
        void addBefore(Element *next_el, DList &dl);
        /**
         * \brief Detach the head of the list
         *
         * The element detached is not deleted. If there is no head of the list
         * (the list is empty) then undefined behaviour results.  Equivalent to
         * list.detach(list.head).
         *
         * \returns The element detached.
         */
        Element *detachFirst()        { return detach(head); }
        /**
         * \brief Detach the tail of the list
         *
         * The element detached is not deleted. If there is no tail of the list
         * (the list is empty) then undefined behaviour results.  Equivalent to
         * list.detach(list.tail).
         *
         * \returns The element detached.
         */
        Element *detachLast()         { return detach(tail); }
        /* Detaches an element from the list. Does not free any memory. */
        Element *detach(Element *el);
        /**
         * \brief Detach and delete the first element in the list.
         *
         * If there is no first element (the list is empty) then undefined
         * behaviour results.  Equivalent to delete list.detach(list.head);
         */
        void removeFirst()         { delete detach( head ); }
        /**
         * \brief Detach and delete the last element in the list.
         *
         * If there is no last element (the list is emtpy) then undefined
         * behaviour results.  Equivalent to delete list.detach(list.tail);
         */
        void removeLast()          { delete detach( tail ); }
        /**
         * \brief Detach and delete an element from the list.
         *
         * If the element is not in the list, then undefined behaviour results.
         * Equivalent to delete list.detach(el);
         */
        void remove(Element *el)   { delete detach( el ); }
         
        void empty();
        void abandon();
        /** \brief The number of elements in the list. */
        long length() const { return listLen; }
        /** \brief Head and tail of the linked list. */
        Element *head, *tail;
        /** \brief The number of element in the list. */
        long listLen;
        /* Convenience access. */
        long size() const           { return listLen; }
        /* Forward this so a ref can be used. */
        struct Iter;
        /* Class for setting the iterator. */
        struct IterFirst { IterFirst( const DList &l ) : l(l) { } const DList &l; };
        struct IterLast { IterLast( const DList &l ) : l(l) { } const DList &l; };
        struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
        struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
        /**
         * \brief Double List Iterator. 
         * \ingroup iterators
         */
        struct Iter
        {
                /* Default construct. */
                Iter() : ptr(0) { }
                /* Construct from a double list. */
                Iter( const DList &dl )      : ptr(dl.head) { }
                Iter( Element *el )          : ptr(el) { }
                Iter( const IterFirst &dlf ) : ptr(dlf.l.head) { }
                Iter( const IterLast &dll )  : ptr(dll.l.tail) { }
                Iter( const IterNext &dln )  : ptr(dln.i.ptr->BASE_EL(next)) { }
                Iter( const IterPrev &dlp )  : ptr(dlp.i.ptr->BASE_EL(prev)) { }
                /* Assign from a double list. */
                Iter &operator=( const DList &dl )     { ptr = dl.head; return *this; }
                Iter &operator=( Element *el )         { ptr = el; return *this; }
                Iter &operator=( const IterFirst &af ) { ptr = af.l.head; return *this; }
                Iter &operator=( const IterLast &al )  { ptr = al.l.tail; return *this; }
                Iter &operator=( const IterNext &an )  { ptr = an.i.ptr->BASE_EL(next); return *this; }
                Iter &operator=( const IterPrev &ap )  { ptr = ap.i.ptr->BASE_EL(prev); return *this; }
                /** \brief Less than end? */
                bool lte() const    { return ptr != 0; }
                /** \brief At end? */
                bool end() const    { return ptr == 0; }
                /** \brief Greater than beginning? */
                bool gtb() const { return ptr != 0; }
                /** \brief At beginning? */
                bool beg() const { return ptr == 0; }
                /** \brief At first element? */
                bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }
                /** \brief At last element? */
                bool last() const  { return ptr && ptr->BASE_EL(next) == 0; }
                /** \brief Implicit cast to Element*. */
                operator Element*() const   { return ptr; }
                /** \brief Dereference operator returns Element&. */
                Element &operator *() const { return *ptr; }
                /** \brief Arrow operator returns Element*. */
                Element *operator->() const { return ptr; }
                /** \brief Move to next item. */
                inline Element *operator++()      { return ptr = ptr->BASE_EL(next); }
                /** \brief Move to next item. */
                inline Element *increment()       { return ptr = ptr->BASE_EL(next); }
                /** \brief Move to next item. */
                inline Element *operator++(int);
                /** \brief Move to previous item. */
                inline Element *operator--()      { return ptr = ptr->BASE_EL(prev); }
                /** \brief Move to previous item. */
                inline Element *decrement()       { return ptr = ptr->BASE_EL(prev); }
                /** \brief Move to previous item. */
                inline Element *operator--(int);
                /** \brief Return the next item. Does not modify this. */
                inline IterNext next() const { return IterNext(*this); }
                /** \brief Return the prev item. Does not modify this. */
                inline IterPrev prev() const { return IterPrev(*this); }
                /** \brief The iterator is simply a pointer. */
                Element *ptr;
        };
        /** \brief Return first element. */
        IterFirst first()  { return IterFirst(*this); }
        /** \brief Return last element. */
        IterLast last()    { return IterLast(*this); }
};
/* Copy constructor, does a deep copy of other. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE>::
                DList(const DList<DLMEL_TEMPUSE> &other) :
                        head(0), tail(0), listLen(0)
{
        Element *el = other.head;
        while( el != 0 ) {
                append( new Element(*el) );
                el = el->BASE_EL(next);
        }
}
#ifdef DOUBLELIST_VALUE
/* Assignement operator does deep copy. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
                operator=(const DList &other)
{
        /* Free the old list. The value list assumes items were allocated on the
         * heap by itself. */
        empty();
        Element *el = other.head;
        while( el != 0 ) {
                append( new Element(*el) );
                el = el->BASE_EL(next);
        }
        return *this;
}
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                transfer(DList &other)
{
        /* Free the old list. The value list assumes items were allocated on the
         * heap by itself. */
        empty();
        head = other.head;
        tail = other.tail;
        listLen = other.listLen;
        other.abandon();
}
#else 
/* Assignement operator does deep copy. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
                operator=(const DList &other)
{
        Element *el = other.head;
        while( el != 0 ) {
                append( new Element(*el) );
                el = el->BASE_EL(next);
        }
        return *this;
}
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                transfer(DList &other)
{
        head = other.head;
        tail = other.tail;
        listLen = other.listLen;
        other.abandon();
}
#endif
#ifdef DOUBLELIST_VALUE
/* Prepend a new item. Inlining this bloats the caller with new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                prepend(const T &item)
{
        addBefore(head, new Element(item)); 
}
/* Append a new item. Inlining this bloats the caller with the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                append(const T &item)
{
        addAfter(tail, new Element(item));
}
/* Add a new item after a prev element. Inlining this bloats the caller with
 * the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addAfter(Element *prev_el, const T &item)
{
        addAfter(prev_el, new Element(item));
}
/* Add a new item before a next element. Inlining this bloats the caller with
 * the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addBefore(Element *next_el, const T &item)
{
        addBefore(next_el, new Element(item));
}
#endif
/*
 * The larger iterator operators.
 */
/* Postfix ++ */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
                operator++(int)       
{
        Element *rtn = ptr; 
        ptr = ptr->BASE_EL(next);
        return rtn;
}
/* Postfix -- */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
                operator--(int)       
{
        Element *rtn = ptr;
        ptr = ptr->BASE_EL(prev);
        return rtn;
}
/**
 * \brief Insert an element immediately after an element in the list.
 *
 * If prev_el is NULL then new_el is prepended to the front of the list. If
 * prev_el is not in the list or if new_el is already in a list, then
 * undefined behaviour results.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addAfter(Element *prev_el, Element *new_el)
{
        /* Set the previous pointer of new_el to prev_el. We do
         * this regardless of the state of the list. */
        new_el->BASE_EL(prev) = prev_el; 
        /* Set forward pointers. */
        if (prev_el == 0) {
                /* There was no prev_el, we are inserting at the head. */
                new_el->BASE_EL(next) = head;
                head = new_el;
        } 
        else {
                /* There was a prev_el, we can access previous next. */
                new_el->BASE_EL(next) = prev_el->BASE_EL(next);
                prev_el->BASE_EL(next) = new_el;
        } 
        /* Set reverse pointers. */
        if (new_el->BASE_EL(next) == 0) {
                /* There is no next element. Set the tail pointer. */
                tail = new_el;
        }
        else {
                /* There is a next element. Set it's prev pointer. */
                new_el->BASE_EL(next)->BASE_EL(prev) = new_el;
        }
        /* Update list length. */
        listLen++;
}
/**
 * \brief Insert an element immediatly before an element in the list.
 *
 * If next_el is NULL then new_el is appended to the end of the list. If
 * next_el is not in the list or if new_el is already in a list, then
 * undefined behaviour results.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addBefore(Element *next_el, Element *new_el)
{
        /* Set the next pointer of the new element to next_el. We do
         * this regardless of the state of the list. */
        new_el->BASE_EL(next) = next_el; 
        /* Set reverse pointers. */
        if (next_el == 0) {
                /* There is no next elememnt. We are inserting at the tail. */
                new_el->BASE_EL(prev) = tail;
                tail = new_el;
        } 
        else {
                /* There is a next element and we can access next's previous. */
                new_el->BASE_EL(prev) = next_el->BASE_EL(prev);
                next_el->BASE_EL(prev) = new_el;
        } 
        /* Set forward pointers. */
        if (new_el->BASE_EL(prev) == 0) {
                /* There is no previous element. Set the head pointer.*/
                head = new_el;
        }
        else {
                /* There is a previous element, set it's next pointer to new_el. */
                new_el->BASE_EL(prev)->BASE_EL(next) = new_el;
        }
        /* Update list length. */
        listLen++;
}
/**
 * \brief Insert an entire list immediatly after an element in this list.
 *
 * Elements are moved, not copied. Afterwards, the other list is empty. If
 * prev_el is NULL then the elements are prepended to the front of the list.
 * If prev_el is not in the list then undefined behaviour results. All
 * elements are inserted into the list at once, so this is an O(1) operation.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addAfter( Element *prev_el, DList<DLMEL_TEMPUSE> &dl )
{
        /* Do not bother if dl has no elements. */
        if ( dl.listLen == 0 )
                return;
        /* Set the previous pointer of dl.head to prev_el. We do
         * this regardless of the state of the list. */
        dl.head->BASE_EL(prev) = prev_el; 
        /* Set forward pointers. */
        if (prev_el == 0) {
                /* There was no prev_el, we are inserting at the head. */
                dl.tail->BASE_EL(next) = head;
                head = dl.head;
        } 
        else {
                /* There was a prev_el, we can access previous next. */
                dl.tail->BASE_EL(next) = prev_el->BASE_EL(next);
                prev_el->BASE_EL(next) = dl.head;
        } 
        /* Set reverse pointers. */
        if (dl.tail->BASE_EL(next) == 0) {
                /* There is no next element. Set the tail pointer. */
                tail = dl.tail;
        }
        else {
                /* There is a next element. Set it's prev pointer. */
                dl.tail->BASE_EL(next)->BASE_EL(prev) = dl.tail;
        }
        /* Update the list length. */
        listLen += dl.listLen;
        /* Empty out dl. */
        dl.head = dl.tail = 0;
        dl.listLen = 0;
}
/**
 * \brief Insert an entire list immediately before an element in this list.
 *
 * Elements are moved, not copied. Afterwards, the other list is empty. If
 * next_el is NULL then the elements are appended to the end of the list. If
 * next_el is not in the list then undefined behaviour results. All elements
 * are inserted at once, so this is an O(1) operation.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
                addBefore( Element *next_el, DList<DLMEL_TEMPUSE> &dl )
{
        /* Do not bother if dl has no elements. */
        if ( dl.listLen == 0 )
                return;
        /* Set the next pointer of dl.tail to next_el. We do
         * this regardless of the state of the list. */
        dl.tail->BASE_EL(next) = next_el; 
        /* Set reverse pointers. */
        if (next_el == 0) {
                /* There is no next elememnt. We are inserting at the tail. */
                dl.head->BASE_EL(prev) = tail;
                tail = dl.tail;
        } 
        else {
                /* There is a next element and we can access next's previous. */
                dl.head->BASE_EL(prev) = next_el->BASE_EL(prev);
                next_el->BASE_EL(prev) = dl.tail;
        } 
        /* Set forward pointers. */
        if (dl.head->BASE_EL(prev) == 0) {
                /* There is no previous element. Set the head pointer.*/
                head = dl.head;
        }
        else {
                /* There is a previous element, set it's next pointer to new_el. */
                dl.head->BASE_EL(prev)->BASE_EL(next) = dl.head;
        }
        /* Update list length. */
        listLen += dl.listLen;
        /* Empty out dl. */
        dl.head = dl.tail = 0;
        dl.listLen = 0;
}
/**
 * \brief Detach an element from the list.
 *
 * The element is not deleted. If the element is not in the list, then
 * undefined behaviour results.
 *
 * \returns The element detached.
 */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::
                detach(Element *el)
{
        /* Set forward pointers to skip over el. */
        if (el->BASE_EL(prev) == 0) 
                head = el->BASE_EL(next); 
        else {
                el->BASE_EL(prev)->BASE_EL(next) =
                                el->BASE_EL(next); 
        }
        /* Set reverse pointers to skip over el. */
        if (el->BASE_EL(next) == 0) 
                tail = el->BASE_EL(prev); 
        else {
                el->BASE_EL(next)->BASE_EL(prev) =
                                el->BASE_EL(prev); 
        }
        /* Update List length and return element we detached. */
        listLen--;
        return el;
}
/**
 * \brief Clear the list by deleting all elements.
 *
 * Each item in the list is deleted. The list is reset to its initial state.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::empty()
{
        Element *nextToGo = 0, *cur = head;
         
        while (cur != 0)
        {
                nextToGo = cur->BASE_EL(next);
                delete cur;
                cur = nextToGo;
        }
        head = tail = 0;
        listLen = 0;
}
/**
 * \brief Clear the list by forgetting all elements.
 *
 * All elements are abandoned, not deleted. The list is reset to it's initial
 * state.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::abandon()
{
        head = tail = 0;
        listLen = 0;
}
#ifdef AAPL_NAMESPACE
}
#endif