bintree.h

#ifndef __SEAL_BINTREE_H__
#define __SEAL_BINTREE_H__

#include "list.h"
#include "dataptr.h"
#include "node.h"

namespace seal
{

template <typename T>
class BinTreeBreadthFirstIterator;

template <typename T>
class CompleteBinaryTree : public Collection<T>
{
public:
    CompleteBinaryTree(void);

    CompleteBinaryTree(const CompleteBinaryTree<T> &bt);

    virtual ~CompleteBinaryTree();

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

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

    virtual AbstractIterator<T>* iteratorPtr(void) const 
    { 
        return new BinTreeBreadthFirstIterator<T>(_firstNodePtr->data); 
    }

    BinTreeBreadthFirstIterator<T> breadthFirstIterator(void) const 
    {
        return BinTreeBreadthFirstIterator<T>(_firstNodePtr->data);
    }

    virtual void pushBack(const T element);

    virtual void popBack(void);

    virtual void purge(void);

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

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

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

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

    void operator=(const CompleteBinaryTree<T> &tree);

private:
    unsigned int *_sizePtr, *_refCountPtr;
    DataPtr< BinTreeNode<T> > *_firstNodePtr, *_lastNodePtr;
    LinkedList< BinTreeNode<T> * > _parentList;
}; // class BinaryTree

template <typename T>
CompleteBinaryTree<T>::CompleteBinaryTree(void)
             : Collection<T>(), _parentList(LinkedList< BinTreeNode<T>* >())
{
    _sizePtr = new unsigned int; *_sizePtr = 0;
    _refCountPtr = new unsigned int; *_refCountPtr = 1;

    _firstNodePtr = new DataPtr< BinTreeNode<T> >();
    _lastNodePtr = new DataPtr< BinTreeNode<T> >();

    _firstNodePtr->data = NULL;
    _lastNodePtr->data = NULL;
}

template <typename T>
CompleteBinaryTree<T>::~CompleteBinaryTree(void)
{
    if (*_refCountPtr > 1)
        (*_refCountPtr)--;
    else
    {
        // First destroy all the nodes!
        purge();

        delete _sizePtr;
        delete _refCountPtr;
        delete _firstNodePtr;
        delete _lastNodePtr;
    }
}

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

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

    _sizePtr = t._sizePtr;
    _refCountPtr = t._refCountPtr;
    _firstNodePtr = t._firstNodePtr;
    _lastNodePtr = t._lastNodePtr;
    _parentList = t._parentList;

    (*_refCountPtr)++;
}

template <typename T>
CompleteBinaryTree<T>::CompleteBinaryTree(const CompleteBinaryTree<T> &bt)
             : Collection<T>(),
               _sizePtr(bt._sizePtr),
               _refCountPtr(bt._refCountPtr),
               _firstNodePtr(bt._firstNodePtr),
               _lastNodePtr(bt._lastNodePtr),
               _parentList(bt._parentList)
{
    (*_refCountPtr)++;
}
 
template <typename T>
void CompleteBinaryTree<T>::pushBack(const T element)
{
    BinTreeNode<T> *newNodePtr = new BinTreeNode<T>();
    newNodePtr->data = element;

    if (_lastNodePtr->data == NULL)
    {
        _lastNodePtr->data = newNodePtr;
        _firstNodePtr->data = newNodePtr;
  
        _parentList.pushBack(newNodePtr);
    }
    else
    {
        BinTreeNode<T> *parentPtr = _parentList.first();
        if (parentPtr->lchild == NULL)
        {
            parentPtr->lchild = newNodePtr;
            newNodePtr->parent = parentPtr;
        }
        else
        {
            parentPtr->rchild = newNodePtr;
            newNodePtr->parent = parentPtr;
            _parentList.popFront();
        }
        
        _parentList.pushBack(newNodePtr);
        _lastNodePtr->data = newNodePtr;
    }

    (*_sizePtr)++;
} // BinaryTree::pushBack
 
template <typename T>
void CompleteBinaryTree<T>::popBack(void)
{
    if (*_sizePtr == 0)
        return;

    BinTreeNode<T> *nodePtr = _lastNodePtr->data;
    if (_parentList.size() != 0)
        _parentList.popBack();

    
    if (nodePtr->parent == NULL)
    {
        _lastNodePtr->data = NULL;
        _firstNodePtr->data = NULL;
    }
    else if (nodePtr->parent->lchild == nodePtr)
    {
        nodePtr->parent->lchild = NULL;
        _lastNodePtr->data = _parentList.last();
    }
    else
    { 
        nodePtr->parent->rchild = NULL;
        _parentList.pushFront(nodePtr->parent);
        _lastNodePtr->data = _parentList.last();
    }

    
    delete nodePtr;
    
    (*_sizePtr)--;
} // BinaryTree::popBack

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

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

    return _firstNodePtr->data->data;
}

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

    return _firstNodePtr->data->data;
}

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

    return _lastNodePtr->data->data;
}

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

    return _lastNodePtr->data->data;
}

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

template <typename T>
class BinTreeBreadthFirstIterator : public AbstractIterator<T>
{

friend class CompleteBinaryTree<T>;

public:
    BinTreeBreadthFirstIterator(BinTreeNode<T> *rootNode);

    virtual ~BinTreeBreadthFirstIterator() {}

    virtual bool hasNext(void);

    virtual T next(void) throw(OutOfBoundsException);

    virtual void reset(void);

private:
    BinTreeNode<T> *_rootPtr;
    LinkedList< BinTreeNode<T> * > _nodeQ;
}; // class BinTreeBreadthFirsthIterator

template <typename T>
BinTreeBreadthFirstIterator<T>::BinTreeBreadthFirstIterator(BinTreeNode<T> *node)
                              : _rootPtr(node), _nodeQ(LinkedList< BinTreeNode<T>* >())
{
    if (node != NULL)
        _nodeQ.pushBack(node);
}

template <typename T>
bool BinTreeBreadthFirstIterator<T>::hasNext(void)
{
    if (_nodeQ.size() != 0)
        return true;
    else
        return false;
}

template <typename T>
T BinTreeBreadthFirstIterator<T>::next(void) throw(OutOfBoundsException)
{
    if (_nodeQ.size() == 0)
        throw OutOfBoundsException();

    BinTreeNode<T> *nodePtr = _nodeQ.first();
    if (nodePtr->lchild != NULL)
        _nodeQ.pushBack(nodePtr->lchild);
    if (nodePtr->rchild != NULL)
        _nodeQ.pushBack(nodePtr->rchild);

    _nodeQ.popFront();
    return nodePtr->data;
}

template <typename T>
void BinTreeBreadthFirstIterator<T>::reset(void)
{
    _nodeQ.purge();
    if (_rootPtr != NULL)
        _nodeQ.pushBack(_rootPtr);
}

} // Namespace seal

#endif // __SEAL_BINTREE_H__

---