/*
 *  Copyright (C)  2000-2001 Marc Wandschneider <mw@kiltdown.org>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation.
 *
 *  For more information look at the file COPYRIGHT in this package
 *
 */
#include <sanity.h>

/**
 * This is a little list template C++ class.  Very cool, very useful, this 
 * class is a linked list that supports adding (O(1)), removing (O(n)), and
 * iterating (O(1)), using the firstElement() and nextElement() methods.
 */


/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::LinkList
 *=------------------------------------------------------------------------=
 * Our Constructor.  Nulls out a few pointers and that's about it. 
 */
template <class Type>
LinkList<Type>::LinkList()
{
    front = end = last = NULL;
}
  
/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::LinkList [copy constructor
 *=------------------------------------------------------------------------=
 * A copy constructor that will successfully copy over the list given 
 * another list.
 *
 * Parameters:
 *      LinkList &          - [in] source object to copy
 */
template <class Type>
LinkList<Type>::LinkList
(
    LinkList<Type> &source
)
{
    copyList(source);
}

/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::operator=
 *=------------------------------------------------------------------------=
 * implements a full copy operator for the this linked list class.
 *
 * Parameters:
 *      LinkList<Type>  &       - [in] source object to copy
 */
template <class Type>
void LinkList<Type>::operator=
(
    LinkList<Type> &source
)
{
    /**
     * First, clear out the existing list.
     */
    emptyList();

    /**
     * Now copy over the new list
     */
    copyList(source);
}


/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::~LinkList
 *=------------------------------------------------------------------------=
 * Simple destructor that cleans up everything.
 */
template <class Type>
LinkList<Type>::~LinkList()
{
    LLNode<Type> *next;

    /**
     * Loop through the list nuking Nodes, but doing nothing to the data 
     * they hold.
     */
    while (front != NULL) {
        next = front->next;
        delete front;
        front = next;
    }

    // that's all folks!
}

/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::addElement
 *=------------------------------------------------------------------------=
 * We always add to the end of the list.  We can still do this O(1)
 *
 * Parameters:
 *      Type            - [in] element to add to the list.
 *
 * Output:
 *      ERRCODE         - result.
 */
template <class Type>
ERRCODE LinkList<Type>::addElement
(
    Type element
)
{
    LLNode<Type> *nd = new LLNode<Type>;

    if (nd == NULL) return E_OUTOFMEMORY;

    nd->item = element;
    nd->next = NULL;

    if (front == NULL) {
        front = nd;
        end = front;
    } else {
        end->next = nd;
        end = nd;
    }

    return S_OK;
}



/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::copyList
 *=------------------------------------------------------------------------=
 * copies the given list into this list, duplicating the nodes as we go
 * along.
 *
 * Parameters:
 *      LinkList<Type> &            - [in] source list to copy
 */
template <class Type>
void LinkList<Type>::copyList
(
    LinkList<Type> &source
)
{
    LLNode<Type> *node, *iterate, *prev;

    front = last = NULL;

    /**
     * While the source has data, copy it over, and see if this is the
     * last ptr as well!!
     */
    iterate = source.front;
    prev = NULL;
    while (iterate != NULL) {

        /**
         * Create a new node for the data.
         */
        node = new LLNode<Type>();
        if (!node) {
            this->front = this->end = this->last = NULL;
            return;
        }

        /**
         * Set the data and update the chain.
         */
        node->item = iterate->item;
        node->next = NULL;
        if (prev == NULL) {
            this->front = node;
            prev = node;
        } else {
            prev->next = node;
            prev = node;
        }

        if (source.last == iterate)
            this->last = node;
        if (source.end == iterate)
            this->end = node;

        iterate = iterate->next;
    }
}




/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::countElements
 *=------------------------------------------------------------------------=
 * counts the number of elements in this linked list.
 *
 * Output:
 *      int                 - the number of items in this list.
 */
template <class Type>
int LinkList<Type>::countElements()
{
    LLNode<Type> *nd = front;
    int count = 0;

    while (nd) {
        count++;
        nd = nd->next;
    }

    return count;
}


/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::elementAt
 *=------------------------------------------------------------------------=
 * Returns the element at the given index.  This is O(n) on average, of 
 * course.  Use sparingly, and consider firstElement()/nextElement() instead
 * 
 * Parameters:
 *      int             - [in]  index of the element to return.
 *      Type *          - [out] the element to be returned.
 *
 * Output:
 *      ERRCODE
 */
template <class Type>
ERRCODE LinkList<Type>::elementAt
(
    int index,
    Type *pelement
)
{
    LLNode<Type> *node = front;

    if (pelement == NULL)
        return E_PARAM;

    /**
     * Zip through until we've found the element, making sure to stay in the
     * loop
     */
    for (int i = 0; i < index; i++) {
        if (node == NULL) break;
        node = node->next;
    }

    if (node == NULL) return E_PARAM;
    *pelement = node->item;
    return S_OK;
}

/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::emptyList
 *=------------------------------------------------------------------------=
 * clears out the linked list.
 */
template <class Type>
void LinkList<Type>::emptyList()
{
    LLNode<Type> *node = front, *next;

    while (node) {
        next = node->next;
        delete node;
        node = next;
    }

    front = end = last = NULL;
}


/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::firstElement
 *=------------------------------------------------------------------------=
 * Starts an iteration over all the elements in the list.  You then call
 * nextElement successively to see all the elements.  Note that we don't
 * try to guarantee a consistent list, etc ... if you add or remove while
 * iterating, expect wacky stuff.
 *
 * Parameters:
 *      Type *          - [out] The First Element in the LIST.
 *
 * Output:
 *      ERRCODE
 */
template <class Type>
ERRCODE LinkList<Type>::firstElement
(
    Type *pelement
)
{
    if (pelement == NULL) return E_PARAM;

    /**
     * If there are no items in the list, this is easy.
     */
    if (front == NULL) return S_NODATA;

    *pelement = front->item;
    last = front->next;
    return S_OK;
}

/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::nextElement
 *=------------------------------------------------------------------------=
 * continues the iteration over the list.  you continue to call this until
 * you get S_EOF, meaning there is no more data.  Please see the comments
 * for firstElement() regarding consistency.
 *
 * Parameters:
 *      Type *          - [out] next element to be retreived.
 *
 * Output:
 *      ERRCODE
 */
template <class Type>
ERRCODE LinkList<Type>::nextElement
(
    Type *pelement
)
{
    if (pelement == NULL) return E_PARAM;

    if (last != NULL) {
        *pelement = last->item;
        last = last->next;
        return S_OK;
    } else
        return S_NODATA;
}

/**
 *=------------------------------------------------------------------------=
 * LinkList<Type>::removeElement
 *=------------------------------------------------------------------------=
 * Removes the given element from the list.  Not terribly efficient, but
 * we don't really care right now !!
 *
 * Parameters:
 *      Type            - [in] the element to remove.
 *
 * Output:
 *      ERRCODE
 */
template <class Type>
ERRCODE LinkList<Type>::removeElement
(
    Type element
)
{
    LLNode<Type> *nd = front;
    LLNode<Type> *prev = NULL;

    /**
     * loop through looking for this element.
     */
    while (nd != NULL) {

        if (nd->item == element) {

            if (prev) {
                prev->next = nd->next;
                if (nd == end) end = prev;
            } else {
                front = nd->next;
                if (nd == end) end = front;
            }
            delete nd;
            break;
        }
        
        prev = nd;
        nd = nd->next;
    }

    return (nd == NULL) ? S_NOTFOUND : S_OK;
}