prtqueue.h

#ifndef __SEAL_PRTQUEUE_H__
#define __SEAL_PRTQUEUE_H__

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

namespace seal
{

template <typename PrtType, typename DataType>
class PriorityQueue : public Collection<DataType>
{
public:

class Iterator : public AbstractIterator<DataType>
{

friend class PriorityQueue<PrtType, DataType>;

public:

    Iterator() : AbstractIterator<DataType>(), _firstPtr(NULL), _currPtr(NULL) {}

    virtual ~Iterator() {}

    virtual bool hasNext(void) { if (_currPtr != NULL) return true; else return false; }

    virtual DataType next(void) throw (OutOfBoundsException);

    virtual void reset(void) { _currPtr = _firstPtr; }

private:

    Iterator(PrtQueueNode<PrtType, DataType> *fPtr) 
        : AbstractIterator<DataType>(), _firstPtr(fPtr), _currPtr(fPtr)
    {}

    PrtQueueNode<PrtType, DataType> *_firstPtr, *_currPtr;
};

public:
    PriorityQueue(void);

    PriorityQueue(const PriorityQueue<PrtType, DataType> &q);

    ~PriorityQueue();

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

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

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

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

    DataType& first(const PrtType &p) throw (MissingPriorityException);

    const DataType& first(const PrtType &p) const throw (MissingPriorityException);

    DataType& last(const PrtType &p) throw (MissingPriorityException);

    const DataType& last(const PrtType &p) const throw (MissingPriorityException);

    bool hasPriority(const PrtType &prt);

    virtual bool isEmpty(void) const { if (*_sizePtr == 0) return true; else return false; }

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

    virtual AbstractIterator<DataType>* iteratorPtr(void) const 
    { 
        return new typename PriorityQueue<PrtType, DataType>::Iterator(_firstNodePtr->data); 
    }

    typename PriorityQueue<PrtType, DataType>::Iterator iterator(void) const 
    { 
        return typename PriorityQueue<PrtType, DataType>::Iterator(_firstNodePtr->data); 
    }

    void enque(const PrtType &prt, const DataType &data);

    inline void deque(void);

    void purge(void);

    void operator=(const PriorityQueue<PrtType, DataType> &map);

private:
    unsigned int *_sizePtr, *_refCountPtr;
    DataPtr< PrtQueueNode<PrtType, DataType> > *_firstNodePtr, *_lastNodePtr;
}; // class PriorityQueue

template <typename PrtType, typename DataType>
PriorityQueue<PrtType, DataType>::PriorityQueue(void)
             : Collection<DataType>()
{
    _sizePtr = new unsigned int; *_sizePtr = 0;
    _refCountPtr =  new unsigned int; *_refCountPtr = 1;
   
    _firstNodePtr = new DataPtr< PrtQueueNode<PrtType, DataType> >();
    _firstNodePtr->data = NULL;

    _lastNodePtr = new DataPtr< PrtQueueNode<PrtType, DataType> >();
    _lastNodePtr->data = NULL;
}

template <typename PrtType, typename DataType>
PriorityQueue<PrtType, DataType>::PriorityQueue(const PriorityQueue<PrtType, DataType> &q)
             : Collection<DataType>(),
               _sizePtr(q._sizePtr), _refCountPtr(q._refCountPtr),
               _firstNodePtr(q._firstNodePtr), _lastNodePtr(q._lastNodePtr)
{
    (*_refCountPtr)++;
}

template <typename PrtType, typename DataType>
PriorityQueue<PrtType, DataType>::~PriorityQueue()
{
    if (*_refCountPtr > 1)
        (*_refCountPtr)--;
    else
    {
        purge();
        delete _sizePtr; delete _refCountPtr;
        delete _firstNodePtr; delete _lastNodePtr;
    }
}

template <typename PrtType, typename DataType>
void PriorityQueue<PrtType, DataType>::operator=(const PriorityQueue<PrtType, DataType> &q)
{
    if (_refCountPtr == q._refCountPtr)
        return;

    if (*_refCountPtr > 1)
        (*_refCountPtr)--;
    else
    {
        purge();
        delete _sizePtr; delete _refCountPtr;
        delete _firstNodePtr; delete _lastNodePtr;
    }

    _sizePtr = q._sizePtr;
    _refCountPtr = q._refCountPtr;
    _firstNodePtr = q._firstNodePtr;
    _lastNodePtr = q._lastNodePtr;

    (*_refCountPtr)++;
}

template <typename PrtType, typename DataType>
DataType& PriorityQueue<PrtType, DataType>::first(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _firstNodePtr->data->data;
}

template <typename PrtType, typename DataType>
DataType& PriorityQueue<PrtType, DataType>::last(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _lastNodePtr->data->data;
}

template <typename PrtType, typename DataType>
const DataType& PriorityQueue<PrtType, DataType>::first(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _firstNodePtr->data->data;
}

template <typename PrtType, typename DataType>
const DataType& PriorityQueue<PrtType, DataType>::last(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _lastNodePtr->data->data;
}

template <typename PrtType, typename DataType>
DataType& PriorityQueue<PrtType, DataType>::first(const PrtType &p) throw (MissingPriorityException)
{
    if (*_sizePtr == 0)
        throw MissingPriorityException();

    PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
    while (nodePtr->prt != p && nodePtr != NULL)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        throw MissingPriorityException();

    return nodePtr->data;
}

template <typename PrtType, typename DataType>
const DataType& PriorityQueue<PrtType, DataType>::first(const PrtType &p) const throw (MissingPriorityException)
{
    if (*_sizePtr == 0)
        throw MissingPriorityException();

    PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
    while (nodePtr->prt != p && nodePtr != NULL)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        throw MissingPriorityException();

    return nodePtr->data;
}

template <typename PrtType, typename DataType>
DataType& PriorityQueue<PrtType, DataType>::last(const PrtType &p) throw (MissingPriorityException)
{
    if (*_sizePtr == 0)
        throw MissingPriorityException();

    PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
    while (nodePtr->prt != p && nodePtr != NULL)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        throw MissingPriorityException();

    while (nodePtr->prt == p && nodePtr != NULL)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        return _lastNodePtr->data->data;
    else
        return nodePtr->prevPtr->data;
}

template <typename PrtType, typename DataType>
const DataType& PriorityQueue<PrtType, DataType>::last(const PrtType &p) const throw (MissingPriorityException)
{
    if (*_sizePtr == 0)
        throw MissingPriorityException();

    PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
    while (nodePtr->prt != p)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        throw MissingPriorityException();

    while (nodePtr->prt == p)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }

    if (nodePtr == NULL)
        return _lastNodePtr->data->data;
    else
        return nodePtr->prevPtr->data;
}

template <typename PrtType, typename DataType>
bool PriorityQueue<PrtType, DataType>::hasPriority(const PrtType &p)
{
    if (*_sizePtr == 0)
        return false;

    PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
    while (nodePtr->prt != p)
    {
        nodePtr = nodePtr->nextPtr;
        if (nodePtr == NULL)
            break;
    }
    
    if (nodePtr == NULL)
        return false;
    else
        return true;    
}

template <typename PrtType, typename DataType>
void PriorityQueue<PrtType, DataType>::deque(void)
{
    if (*_sizePtr == 0)
        return;

    if (*_sizePtr == 1)
    {
        delete _firstNodePtr->data;
        _lastNodePtr->data = _firstNodePtr->data = NULL;
    }
    else
    {
        PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
        _firstNodePtr->data = nodePtr->nextPtr;
        _firstNodePtr->data->prevPtr = NULL;

        delete nodePtr;
    }

    (*_sizePtr)--;
}

template <typename PrtType, typename DataType>
void PriorityQueue<PrtType, DataType>::purge(void)
{
    while (*_sizePtr != 0)
    {
        if (*_sizePtr == 1)
        {
            delete _firstNodePtr->data;
            _lastNodePtr->data = _firstNodePtr->data = NULL;
        }
        else
        {
            PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
            _firstNodePtr->data = nodePtr->nextPtr;
            _firstNodePtr->data->prevPtr = NULL;

            delete nodePtr;
        }

        (*_sizePtr)--;
    }
}

template <typename PrtType, typename DataType>
void PriorityQueue<PrtType, DataType>::enque(const PrtType &prt, const DataType &data)
{
    PrtQueueNode<PrtType, DataType> *newNodePtr = new PrtQueueNode<PrtType, DataType>();
    newNodePtr->data = data;
    newNodePtr->prt = prt;

    if ((*_sizePtr) == 0)
    {
        _firstNodePtr->data = newNodePtr;
        _lastNodePtr->data = newNodePtr;
    }
    else
    {
        PrtQueueNode<PrtType, DataType> *nodePtr = _firstNodePtr->data;
        while (nodePtr != NULL)
        {
            if (nodePtr->prt > prt)
                break;
  
            nodePtr = nodePtr->nextPtr;
        }
        
        if (nodePtr == NULL)
        {
            // Add a node to the end of the queue.
            _lastNodePtr->data->nextPtr = newNodePtr;
            newNodePtr->prevPtr = _lastNodePtr->data;
 
            _lastNodePtr->data = newNodePtr;
        }
        else
        {
            // Add a node before the node pointed to by nodePtr.
            if (nodePtr->prevPtr != NULL)
            {
                // Insert the new node
                newNodePtr->prevPtr = nodePtr->prevPtr;
                newNodePtr->nextPtr = nodePtr;
 
                nodePtr->prevPtr = newNodePtr;
                newNodePtr->prevPtr->nextPtr = newNodePtr;
            }
            else
            {
                // Add a node to the begining of the queue
                _firstNodePtr->data->prevPtr = newNodePtr;
                newNodePtr->nextPtr = _firstNodePtr->data;

                _firstNodePtr->data = newNodePtr;
            }
        }
    }

    (*_sizePtr)++;
}

// *******************************************************************
// *******************************************************************
// *******************************************************************

template <typename PrtType, typename DataType>
DataType PriorityQueue<PrtType, DataType>::Iterator::next(void) throw (OutOfBoundsException)
{
    if (_currPtr == NULL)
        throw OutOfBoundsException();

    PrtQueueNode<PrtType, DataType> *node = _currPtr;
    _currPtr = _currPtr->nextPtr;

    return node->data;
}

} // End of namespace seal

#endif // __SEAL_PRTQUEUE_H__

---