include/Structs/Trees/completeBinaryTree.h

#ifndef COMPLETEBINARYTREE_H
#define COMPLETEBINARYTREE_H

#include <configuration.h>
#include <Utilities/binaryMath.h>
#include <Structs/Trees/treeStorageSchemes.h>
#include <assert.h>
#include <stack>


template <typename DataType>
class StatisticAnalyser
{
public:
    typedef unsigned int SizeType; 
    StatisticAnalyser() 
    {
        m_out.open( queueStatsFile.c_str(), std::fstream::out | std::fstream::app);
    }
    
    ~StatisticAnalyser()
    {
        m_out.close();
    }
    
    void recordJump(SizeType jump)
    {
        m_out << jump * sizeof(DataType) << "\n";
    }
    
private:
    std::ofstream m_out;
};


template <typename DataType, typename SizeType>
class CopyController
{
public:
    CopyController():bfsIndex(0),height(0),newHeight(0),ptr(0),newPtr(0)
    {   
    }
    
    CopyController( const SizeType& b, const SizeType& h, const SizeType& nh, DataType* p, DataType* np):
                    bfsIndex(b),height(h),newHeight(nh),ptr(p),newPtr(np)
    {   
    }
    
    CopyController operator = ( const CopyController& other)
    {
        if( this != &other)
        {
            bfsIndex = other.bfsIndex;
            height = other.height;
            newHeight = other.newHeight;
            ptr = other.ptr;
            newPtr = other.newPtr;
        }
        return *this;
    }
    
    void print()
    {
    }
    
    void reset( const SizeType& b, const SizeType& h, const SizeType& nh, DataType* p, DataType* np)
    {
        bfsIndex = b;
        height = h;
        newHeight = nh;
        ptr = p;
        newPtr = np;
    }
    
    SizeType bfsIndex;
    SizeType height,newHeight;
    DataType* ptr;
    DataType* newPtr;
    
};



template <typename DataType, template <typename datatype> class StorageStrategy = HeapStorage>
class CompleteBinaryTree
{

public:

    typedef unsigned int SizeType;
    typedef StorageStrategy<DataType> StorageScheme;

    class Node;

    CompleteBinaryTree( const SizeType& height = 0, const DataType& defaultValue = DataType(0)):m_height(height),m_numNodes((1 << (m_height + 1)) - 1),m_defaultValue( defaultValue)
    {
        m_pool = new DataType[ m_numNodes ];
        m_storage = new StorageScheme( m_pool, height);

        for( SizeType i = 0; i < m_numNodes; i++)
        {   
            m_pool[i] = defaultValue;
        }
    }

    ~CompleteBinaryTree()
    {
       delete[] m_pool;
       delete m_storage;
    }
    
    
    void decreaseHeight()
    {
        //std::cout << "Halving\n";
        assert( m_height > 0);
        SizeType newHeight = m_height - 1;
        SizeType newNodes = pow2(newHeight + 1) - 1;
        DataType* newPool = new DataType[ newNodes ];
        StorageScheme* newStorage = new StorageScheme( newPool, newHeight);
        for( SizeType i = 0; i < newNodes; i++)
        {   
            newPool[i] = m_defaultValue;
        }
        
        std::stack< CopyController<DataType,SizeType> > S;
        CopyController<DataType,SizeType> rightCtrl,leftCtrl;
        CopyController<DataType,SizeType> ctrl( 1, m_height, newHeight, m_pool, newPool);
        S.push( ctrl);
        while( !S.empty())
        {
            ctrl = S.top();
            S.pop();
            ctrl.print();
            *(ctrl.newPtr) = *(ctrl.ptr);
            if( (ctrl.bfsIndex << 1) <= newNodes )
            {
                rightCtrl.reset( (ctrl.bfsIndex << 1) + 1, ctrl.height - 1, ctrl.newHeight - 1,
                            m_storage->getRightChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height), 
                            newStorage->getRightChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
                S.push( rightCtrl);      
                 
                leftCtrl.reset( ctrl.bfsIndex << 1, ctrl.height - 1, ctrl.newHeight - 1,
                            m_storage->getLeftChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height), 
                            newStorage->getLeftChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
                S.push( leftCtrl);
            }
        }
        
        --m_height;
        
        m_numNodes = newNodes;
        delete [] m_pool;
        delete m_storage;
        
        m_pool = newPool;
        m_storage = newStorage;
    }

    const SizeType& getHeight() const
    {
        return m_height;
    }
    
    SizeType getMemoryUsage()
    {
        SizeType sum = (m_numNodes + 1) * sizeof( DataType) + m_storage->getMemoryUsage() + 2 * sizeof( SizeType);
        return sum;
    }
    
    const SizeType& getNumNodes() const
    {
        return m_numNodes;
    }
    
    Node getRootNode() 
    {
        return Node(this,m_pool,1);
    }
    
    Node* getRootPointer() const;

    void increaseHeight()
    {
        SizeType newHeight = m_height + 1;
        SizeType newNodes = pow2(newHeight + 1) - 1;
        
        DataType* newPool = new DataType[ newNodes ];
        StorageScheme* newStorage = new StorageScheme( newPool, newHeight);
        for( SizeType i = 0; i < newNodes; i++)
        {   
            newPool[i] = m_defaultValue;
        }
        
        std::stack< CopyController<DataType,SizeType> > S;
        CopyController<DataType,SizeType> rightCtrl,leftCtrl;
        CopyController<DataType,SizeType> ctrl( 1, m_height, newHeight, m_pool, newPool);
        S.push( ctrl);
        while( !S.empty())
        {
            ctrl = S.top();
            S.pop();
            ctrl.print();
            *(ctrl.newPtr) = *(ctrl.ptr);
            if( (ctrl.bfsIndex << 1) <= m_numNodes )
            {
                rightCtrl.reset( (ctrl.bfsIndex << 1) + 1, ctrl.height - 1, ctrl.newHeight - 1,
                            m_storage->getRightChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height), 
                            newStorage->getRightChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
                S.push( rightCtrl);      
                 
                leftCtrl.reset( ctrl.bfsIndex << 1, ctrl.height - 1, ctrl.newHeight - 1,
                            m_storage->getLeftChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height), 
                            newStorage->getLeftChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
                S.push( leftCtrl);
            }
        }
        
        ++m_height;
        m_numNodes = newNodes;
        delete [] m_pool;
        delete m_storage;
        
        m_pool = newPool;
        m_storage = newStorage;
    }
    
    void printGraphviz( std::ostream& out, const std::string& prefix = "")
    {
        if( m_height > 10)
        {
            SizeType size = (1 << m_height);
            std::cout << "The tree is too big to print (>" << size << ")\n";
            return;
        }
        
        out << "digraph BFS {\n\tedge [len=3]\n\tnode  [fontname=\"Arial\"]\n";

        Node m_auxNode( this, m_pool, 1);
                
        std::stack<Node> S;
        S.push(m_auxNode);
        while( !S.empty())
        {
            m_auxNode = S.top();
            S.pop();             
            out << prefix << m_auxNode.getPoolIndex();
            out << "[shape=record,label=\"{";
                    out << prefix << m_auxNode.getBfsIndex() << "|";
            out << prefix << m_auxNode.getPoolIndex();
                out << "}\"]\n";
            out << "\t"; 
            if( !m_auxNode.isLeaf())
            {
                out << prefix << m_auxNode.getPoolIndex();    
                out << " -> ";  
                m_auxNode.goLeft();
                out << prefix << m_auxNode.getPoolIndex();    
                out << "\n"; 
                S.push(m_auxNode);
                m_auxNode.goUp();
                out << "\t";        
                out << prefix << m_auxNode.getPoolIndex(); 
                out << " -> ";     
                m_auxNode.goRight();
                out << prefix << m_auxNode.getPoolIndex();  
                S.push(m_auxNode);
            }
            out << "\n";
        }
        out << "}";
    }

protected:
    DataType* m_pool;

    _QUEUESTATS(StatisticAnalyser<DataType> stats;)

    SizeType m_height;
    
    SizeType m_numNodes;
    
    DataType m_defaultValue;

    StorageScheme* m_storage;
};



template <typename DataType, template <typename datatype> class StorageStrategy>
class CompleteBinaryTree<DataType,StorageStrategy>::Node 
{
public:
    Node(): m_T(0),m_ptr(0),m_bfsIndex(0),m_depth(0)
    {
    }
    
    Node( CompleteBinaryTree<DataType,StorageStrategy>* T, DataType* ptr, const SizeType bfsIndex): m_T(T), m_ptr(ptr), m_bfsIndex( bfsIndex), m_depth( floorLog2( bfsIndex))
    {   
    }
    
    const DataType* getAddress() const
    {
        return m_ptr;
    }
    
    const SizeType& getBfsIndex() const
    {
        return m_bfsIndex;
    }
        
    const SizeType& getDepth() const
    {
        return m_depth;
    }

    SizeType getHeight() const
    {
        return m_T->m_height - m_depth;
    }
    
    SizeType getHorizontalIndex() const
    {
       return m_bfsIndex - pow2( getDepth());
    }
    
    SizeType getMemoryUsage()
    {
        return 2*sizeof(SizeType) + sizeof(DataType*) + sizeof(CompleteBinaryTree<DataType,StorageStrategy>*);
    }
        
    SizeType getPoolIndex() const
    {
        return m_ptr - m_T->m_pool;
    }    
    
    void goLeft()
    {
        _QUEUESTATS( m_T->stats.recordJump( m_T->m_storage->getLeftChildAddress( m_ptr, m_bfsIndex, getHeight() ) - m_ptr);)
        m_ptr = m_T->m_storage->getLeftChildAddress( m_ptr, m_bfsIndex, getHeight() );
        m_bfsIndex = m_bfsIndex << 1;
        m_depth++;
    }
    
    void goRight()
    {
        _QUEUESTATS( m_T->stats.recordJump( m_T->m_storage->getRightChildAddress( m_ptr, m_bfsIndex, getHeight() ) - m_ptr);)
        m_ptr = m_T->m_storage->getRightChildAddress( m_ptr, m_bfsIndex, getHeight() );
        m_bfsIndex = (m_bfsIndex << 1) + 1;
        m_depth++;
    }
    
    void goUp()
    {
        _QUEUESTATS(m_T->stats.recordJump( m_ptr - m_T->m_storage->getParentAddress( m_ptr, m_bfsIndex, getHeight() ));)
        m_ptr = m_T->m_storage->getParentAddress( m_ptr, m_bfsIndex, getHeight() );
        m_bfsIndex = m_bfsIndex >> 1;
            m_depth--;  
    }
        
    bool isLeaf() const
    {
        return m_depth == m_T->m_height;
    }

    bool isRightChild() const
    {
        return ( (m_bfsIndex & 1) == 1);
    }
    
    bool isToTheLeftOf( const Node& other) const
    {
        assert( this->isLeaf());
        return ( (m_bfsIndex >> other.getHeight()) < other.m_bfsIndex);
    }
        
    bool isRoot() const
    {
        return !m_depth;
    }

    Node& operator=(const Node& other)
    {
        if( this != &other)
        {       
            this->m_T = other.m_T;
            this->m_ptr = other.m_ptr;
            this->m_bfsIndex = other.m_bfsIndex;
            this->m_depth = other.m_depth;
        }
        return *this;
    }
    
    
    DataType& operator * ()
    {
        return *m_ptr;
    }

    DataType* operator -> ()
    {
        return m_ptr;
    }

    bool operator == ( const Node& other) const
    {
        return (m_T == other.m_T) && (m_ptr == other.m_ptr);
    }
    
    bool operator != ( const Node& other) const
    {
        return !(*this == other);
    }

    void setAtBfsIndex( const SizeType& bfsIndex)
    {
        m_ptr = m_T->m_storage->getBfsIndexAddress( bfsIndex);
        m_bfsIndex = bfsIndex;
        m_depth = floorLog2( bfsIndex);
    }

        void setAtPos( const SizeType& height, const SizeType& horizontalPosition)
        {
        setAtBfsIndex( (1<<(m_T->m_height - height)) + horizontalPosition);
        return;
            /*SizeType numLeaves = pow2( m_T->getHeight());
            m_ptr = m_T->m_storage->getRootAddr();      
            m_bfsIndex = 1;
            m_depth = 0;
        unsigned int mask = numLeaves >> 1;
            horizontalPosition <<= height;
            while( getHeight() > height)
            {
                    if( mask & horizontalPosition)
                    {
                            goRight();
                    }   
                    else
                    {
                            goLeft();
                    }
                    mask >>= 1;
            }*/
    }

    void setAtRoot() 
    {
        m_bfsIndex = 1;
        m_depth = 0;
        m_ptr = m_T->m_storage->getRootAddr();
    }

protected:
    CompleteBinaryTree<DataType,StorageStrategy>* m_T;  
    
    DataType* m_ptr;

    SizeType m_bfsIndex;

    SizeType m_depth;
};




#endif //COMPLETEBINARYTREE_H

---