list.h

#ifndef __SEAL_LIST_H__
#define __SEAL_LIST_H__

#include "collection.h"
#include "node.h"
#include "dataptr.h"

namespace seal
{

template <typename T>
class List : public Collection<T>
{
public:

    List(void); 

    virtual void pushBack(const T element) = 0;

    virtual void popBack(void) = 0;

    virtual void pushFront(const T element) = 0;

    virtual void popFront(void) = 0;

    virtual void insert(const T element, unsigned int index) = 0;

    virtual void remove(unsigned int index) = 0;

}; // class List

template <typename T>
List<T>::List(void) : Collection<T>() {}


template <typename T>
class LinkedList : public List<T>
{
public:
class Iterator : public AbstractIterator<T>
{

friend class LinkedList<T>;

public:
    Iterator(void) : AbstractIterator<T>(), _firstNodePtr(NULL), _lastNodePtr(NULL)
    { _currNodePtr = NULL; }

    virtual bool hasNext(void);

    virtual T next(void) throw (OutOfBoundsException);

    virtual void reset(void);

private:
    Iterator(ListNode<T> *fnp, ListNode<T> *lnp) : AbstractIterator<T>(), _firstNodePtr(fnp), _lastNodePtr(lnp)
    { _currNodePtr = _firstNodePtr; }

    ListNode<T> *_currNodePtr;
    ListNode<T> *_firstNodePtr;
    ListNode<T> *_lastNodePtr;
}; // Class ListIterator

public:
    LinkedList(void);

    LinkedList(const LinkedList<T> &l);

    virtual ~LinkedList();

    virtual bool isEmpty(void) const;

    virtual unsigned int size(void) const { return *_sizePtr; }

    virtual AbstractIterator<T>* iteratorPtr(void) const 
    { return new typename LinkedList<T>::Iterator(_firstNodePtr->data, _lastNodePtr->data); }

    virtual typename LinkedList<T>::Iterator iterator(void) const 
    { return typename LinkedList<T>::Iterator(_firstNodePtr->data, _lastNodePtr->data); }

    inline virtual void purge(void);

    virtual void pushBack(const T element);

    virtual void popBack(void);

    virtual void pushFront(const T element);

    virtual void popFront(void);

    virtual void insert(const T element, unsigned int index);   

    virtual void remove(unsigned int index);

    void operator=(const LinkedList<T> &l);

    virtual T& first(void) throw (EmptyCollectionException);

    virtual T& last(void) throw (EmptyCollectionException);

    virtual const T& first(void) const throw (EmptyCollectionException);

    virtual const T& last(void) const throw (EmptyCollectionException);

    bool contains(const T element) const;

    bool removeFirstMatch(const T match);

    bool replace(int i, const T element);

    bool replaceAll(const T match, const T e);

    bool replaceFirst(const T match, const T e);
    
private:
    unsigned int *_sizePtr, *_refCountPtr;
    DataPtr< ListNode<T> > *_firstNodePtr;
    DataPtr< ListNode<T> > *_lastNodePtr;
}; // class LinkedList

// Implementation of LinkedList

template <typename T>
LinkedList<T>::LinkedList(void)
             : List<T>()
{
    _sizePtr = new unsigned int; *_sizePtr = 0;
    _refCountPtr = new unsigned int; *_refCountPtr = 1;
    
    _firstNodePtr = new DataPtr< ListNode<T> >();
    _firstNodePtr->data = NULL;
    
    _lastNodePtr = new DataPtr< ListNode<T> >();
    _lastNodePtr->data = NULL;
} // LinkedList::LinkedList

template <typename T>
LinkedList<T>::LinkedList(const LinkedList<T> &l)
             : List<T>(),
               _sizePtr(l._sizePtr),
               _refCountPtr(l._refCountPtr),
               _firstNodePtr(l._firstNodePtr),
               _lastNodePtr(l._lastNodePtr)
{
    (*_refCountPtr)++;
} // LinkedList::LinkedList

template <typename T>
LinkedList<T>::~LinkedList()
{
    if (*_refCountPtr <= 1)
    {
        delete _sizePtr;
        delete _refCountPtr;
        delete _firstNodePtr;
        delete _lastNodePtr;
    }
    else
        (*_refCountPtr)--;
} // LinkedList::~LinkedList

template <typename T>
bool LinkedList<T>::isEmpty() const 
{
    if (*_sizePtr == 0)
        return true;
    else
        return false;
} // LinkedList::isEmpty

template <typename T>
void LinkedList<T>::purge(void)
{
    while (*_sizePtr != 0)
        popBack();
} // LinkedList::purge

template <typename T>
void LinkedList<T>::pushBack(const T element)
{
    // Create the new node first.
    ListNode<T> *newNodePtr = new ListNode<T>();
    newNodePtr->data = element;

    if (*_sizePtr == 0)
    {
        // If the size is 0, then firstNodePtr and 
        // the lastNodePtr should both point to the 
        // new node.
        _firstNodePtr->data = newNodePtr;
        _lastNodePtr->data = newNodePtr;
    }
    else
    {
        // The current last node should have the new node 
        // as the next node.
        _lastNodePtr->data->nextPtr = newNodePtr;

        // The new node should have the current last node 
        // as the previous node.
        newNodePtr->prevPtr = _lastNodePtr->data;

        // The last node pointer should point to the new 
        // node.
        _lastNodePtr->data = newNodePtr;
    }
    
    // The size HAS to be incremented after a push 
    // operation.
    (*_sizePtr)++;
} // LinkedList::pushBack

template <typename T>
void LinkedList<T>::popBack()
{
    if (*_sizePtr == 0)
        return;

    if (*_sizePtr == 1)
    {
        delete _lastNodePtr->data;
        _lastNodePtr->data = NULL;
        _firstNodePtr->data = NULL;
    }
    else
    {
        _lastNodePtr->data = _lastNodePtr->data->prevPtr;
        delete _lastNodePtr->data->nextPtr;
        _lastNodePtr->data->nextPtr = NULL;
    }
    
    // Size HAS to be decremented in case of pop 
    // operation.
    (*_sizePtr)--;
} // LinkedList::popBack

template <typename T>
void LinkedList<T>::pushFront(const T element)
{
    // Create the new node first.
    ListNode<T> *newNodePtr = new ListNode<T>();
    newNodePtr->data = element;

    if (*_sizePtr == 0)
    {
        // If the size is 0, then firstNodePtr and 
        // the lastNodePtr should both point to the 
        // new node.
        _firstNodePtr->data = newNodePtr;
        _lastNodePtr->data = newNodePtr;
    }
    else
    {
        // The current first node should have the new node 
        // as the previous node.
        _firstNodePtr->data->prevPtr = newNodePtr;

        // The new node should have the current first node 
        // as the next node.
        newNodePtr->nextPtr = _firstNodePtr->data;

        // The first node pointer should point to the new 
        // node.
        _firstNodePtr->data = newNodePtr;
    }
    
    // The size HAS to be incremented after a push 
    // operation.
    (*_sizePtr)++;
} // LinkedList::pushFront

template <typename T>
void LinkedList<T>::popFront()
{
    if (*_sizePtr == 0)
        return;

    if (*_sizePtr == 1)
    {
        delete _firstNodePtr->data;
        _lastNodePtr->data = NULL;
        _firstNodePtr->data = NULL;
    }
    else
    {
        _firstNodePtr->data = _firstNodePtr->data->nextPtr;
        delete _firstNodePtr->data->prevPtr;
        _firstNodePtr->data->prevPtr = NULL;
    }
    
    // Size HAS to be decremented in case of pop 
    // operation.
    (*_sizePtr)--;
} // LinkedList::popFront

template <typename T>
void LinkedList<T>::insert(const T element, unsigned int index)
{
    if (index == 0)
        pushFront(element);
    else if (index >= *_sizePtr)
        pushBack(element);
    else
    {
        ListNode<T> *nextNodePtr = _firstNodePtr->data;
        for (int i = 0; i < index; i++)
            nextNodePtr = nextNodePtr->nextPtr;

        ListNode<T> *newNodePtr = new ListNode<T>();
        newNodePtr->data = element;

        newNodePtr->nextPtr = nextNodePtr;
        newNodePtr->prevPtr = nextNodePtr->prevPtr;
        newNodePtr->prevPtr->nextPtr = newNodePtr;
        newNodePtr->nextPtr->prevPtr = newNodePtr;

        (*_sizePtr)++;
    }
} // LinkedList::insert

template <typename T>
void LinkedList<T>::remove(unsigned int index)
{
    if (index >= *_sizePtr)
        return;
    else if (index == 0)
        popFront();
    else if (index == (*_sizePtr)-1)
        popBack();
    else
    {
        ListNode<T> *listNodePtr = _firstNodePtr->data;
        for (int i = 0; i < index; i++)
            listNodePtr = listNodePtr->nextPtr;

        // Redirect the pointers.
        listNodePtr->prevPtr->nextPtr = listNodePtr->nextPtr;
        listNodePtr->nextPtr->prevPtr = listNodePtr->prevPtr;

        delete listNodePtr;

        (*_sizePtr)--;
    }
} // LinkedList::remove

template <typename T>
void LinkedList<T>::operator=(const LinkedList<T> &rhs)
{
    if (_refCountPtr == rhs._refCountPtr)
        return;

    if (rhs._sizePtr == _sizePtr)
        return;

    if (*_refCountPtr > 1)
    {
        (*_refCountPtr)--;
        
        _refCountPtr = rhs._refCountPtr;
        _sizePtr = rhs._sizePtr;
        _firstNodePtr = rhs._firstNodePtr;
        _lastNodePtr = rhs._lastNodePtr;

        (*_refCountPtr)++;
    }
    else
    {
        delete _refCountPtr;
        delete _sizePtr;
        delete _firstNodePtr;
        delete _lastNodePtr;

        _refCountPtr = rhs._refCountPtr;
        _sizePtr = rhs._sizePtr;
        _firstNodePtr = rhs._firstNodePtr;
        _lastNodePtr = rhs._lastNodePtr;

        (*_refCountPtr)++;
    }
} // LinkedList::operator=

template <typename T>
const T& LinkedList<T>::first(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _firstNodePtr->data->data;
}

template <typename T>
const T& LinkedList<T>::last(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _lastNodePtr->data->data;
}

template <typename T>
T& LinkedList<T>::first(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _firstNodePtr->data->data;
}

template <typename T>
T& LinkedList<T>::last(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _lastNodePtr->data->data;
}

template <typename T>
bool LinkedList<T>::contains (const T e) const
{
    ListNode<T> *nodePtr = _firstNodePtr->data;
    while (nodePtr != NULL)
    {
        if (nodePtr->data == e)
            break;
       
        nodePtr = nodePtr->nextPtr;
    }

    if (nodePtr == NULL)
        return false;
    else
        return true;
}

template <typename T>
bool LinkedList<T>::removeFirstMatch(const T e)
{
    ListNode<T> *nodePtr = _firstNodePtr->data;
    while (nodePtr != NULL)
    {
        if (nodePtr->data == e)
            break;
       
        nodePtr = nodePtr->nextPtr;
    }

    if (nodePtr == NULL)
        return false;
    else
    {
        if (nodePtr->prevPtr == NULL)
            popFront();
        else if (nodePtr->nextPtr == NULL)
            popBack();
        else
        {
            // Redirect the pointers.
            nodePtr->prevPtr->nextPtr = nodePtr->nextPtr;
            nodePtr->nextPtr->prevPtr = nodePtr->prevPtr;

            delete nodePtr;

            (*_sizePtr)--;       
        }

        return true;
    }
}

template <typename T>
bool LinkedList<T>::replace(int i, const T element)
{
    if (i < 0 || i >= *_sizePtr)
        return false;

    ListNode<T> *nodePtr = _firstNodePtr->data;
    for (int l = 0; l < i; l++)
        nodePtr = nodePtr->nextPtr;

    nodePtr->data = element;
    return true;
}

template <typename T>
bool LinkedList<T>::replaceAll(const T element, const T match)
{
    int matchCount = 0;
    ListNode<T> *nodePtr = _firstNodePtr->data;

    while (nodePtr != NULL)
    {
        if (nodePtr->data == element)
        {
            nodePtr->data = match;
            matchCount++;
        }
  
        nodePtr = nodePtr->nextPtr;
    }

    if (matchCount > 0)
        return true;
    else
        return false;
}

template <typename T>
bool LinkedList<T>::replaceFirst(const T element, const T match)
{
    ListNode<T> *nodePtr = _firstNodePtr->data;

    while (nodePtr != NULL)
    {
        if (nodePtr->data == element)
        {
            nodePtr->data = match;
            return true;
        }
    
        nodePtr = nodePtr->nextPtr;
    }

    return false;
}

// Implementation of ListIterator

template <typename T>
bool LinkedList<T>::Iterator::hasNext(void)
{
    if (_currNodePtr != NULL)
        return true;
    else
        return false;
}

template <typename T>
T LinkedList<T>::Iterator::next(void) throw (OutOfBoundsException)
{
    if (_currNodePtr == NULL)
        throw OutOfBoundsException();
    else
    {
        T data = _currNodePtr->data;
        _currNodePtr = _currNodePtr->nextPtr;

        return data;
    }
}

template <typename T>
void LinkedList<T>::Iterator::reset(void)
{
    _currNodePtr = _firstNodePtr;
}

} // End of namespace seal.

#endif // __SEAL_LIST_H__

---