00001 #ifndef COMPLETEBINARYTREE_H
00002 #define COMPLETEBINARYTREE_H
00003
00004 #include <configuration.h>
00005 #include <Utilities/binaryMath.h>
00006 #include <Structs/Trees/treeStorageSchemes.h>
00007 #include <assert.h>
00008 #include <stack>
00009
00010
00011 template <typename DataType>
00012 class StatisticAnalyser
00013 {
00014 public:
00015 typedef unsigned int SizeType;
00016 StatisticAnalyser()
00017 {
00018 m_out.open( queueStatsFile.c_str(), std::fstream::out | std::fstream::app);
00019 }
00020
00021 ~StatisticAnalyser()
00022 {
00023 m_out.close();
00024 }
00025
00026 void recordJump(SizeType jump)
00027 {
00028 m_out << jump * sizeof(DataType) << "\n";
00029 }
00030
00031 private:
00032 std::ofstream m_out;
00033 };
00034
00035
00036 template <typename DataType, typename SizeType>
00037 class CopyController
00038 {
00039 public:
00040 CopyController():bfsIndex(0),height(0),newHeight(0),ptr(0),newPtr(0)
00041 {
00042 }
00043
00044 CopyController( const SizeType& b, const SizeType& h, const SizeType& nh, DataType* p, DataType* np):
00045 bfsIndex(b),height(h),newHeight(nh),ptr(p),newPtr(np)
00046 {
00047 }
00048
00049 CopyController operator = ( const CopyController& other)
00050 {
00051 if( this != &other)
00052 {
00053 bfsIndex = other.bfsIndex;
00054 height = other.height;
00055 newHeight = other.newHeight;
00056 ptr = other.ptr;
00057 newPtr = other.newPtr;
00058 }
00059 return *this;
00060 }
00061
00062 void print()
00063 {
00065 }
00066
00067 void reset( const SizeType& b, const SizeType& h, const SizeType& nh, DataType* p, DataType* np)
00068 {
00069 bfsIndex = b;
00070 height = h;
00071 newHeight = nh;
00072 ptr = p;
00073 newPtr = np;
00074 }
00075
00076 SizeType bfsIndex;
00077 SizeType height,newHeight;
00078 DataType* ptr;
00079 DataType* newPtr;
00080
00081 };
00082
00083
00084
00096 template <typename DataType, template <typename datatype> class StorageStrategy = HeapStorage>
00097 class CompleteBinaryTree
00098 {
00099
00100 public:
00101
00102 typedef unsigned int SizeType;
00103 typedef StorageStrategy<DataType> StorageScheme;
00104
00105 class Node;
00106
00113 CompleteBinaryTree( const SizeType& height = 0, const DataType& defaultValue = DataType(0)):m_height(height),m_numNodes((1 << (m_height + 1)) - 1),m_defaultValue( defaultValue)
00114 {
00115 m_pool = new DataType[ m_numNodes ];
00116 m_storage = new StorageScheme( m_pool, height);
00117
00118 for( SizeType i = 0; i < m_numNodes; i++)
00119 {
00120 m_pool[i] = defaultValue;
00121 }
00122 }
00123
00127 ~CompleteBinaryTree()
00128 {
00129 delete[] m_pool;
00130 delete m_storage;
00131 }
00132
00133
00137 void decreaseHeight()
00138 {
00139
00140 assert( m_height > 0);
00141 SizeType newHeight = m_height - 1;
00142 SizeType newNodes = pow2(newHeight + 1) - 1;
00144 DataType* newPool = new DataType[ newNodes ];
00145 StorageScheme* newStorage = new StorageScheme( newPool, newHeight);
00146 for( SizeType i = 0; i < newNodes; i++)
00147 {
00148 newPool[i] = m_defaultValue;
00149 }
00150
00151 std::stack< CopyController<DataType,SizeType> > S;
00152 CopyController<DataType,SizeType> rightCtrl,leftCtrl;
00153 CopyController<DataType,SizeType> ctrl( 1, m_height, newHeight, m_pool, newPool);
00154 S.push( ctrl);
00155 while( !S.empty())
00156 {
00157 ctrl = S.top();
00158 S.pop();
00159 ctrl.print();
00160 *(ctrl.newPtr) = *(ctrl.ptr);
00161 if( (ctrl.bfsIndex << 1) <= newNodes )
00162 {
00163 rightCtrl.reset( (ctrl.bfsIndex << 1) + 1, ctrl.height - 1, ctrl.newHeight - 1,
00164 m_storage->getRightChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height),
00165 newStorage->getRightChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
00166 S.push( rightCtrl);
00167
00168 leftCtrl.reset( ctrl.bfsIndex << 1, ctrl.height - 1, ctrl.newHeight - 1,
00169 m_storage->getLeftChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height),
00170 newStorage->getLeftChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
00171 S.push( leftCtrl);
00172 }
00173 }
00174
00175 --m_height;
00176
00178 m_numNodes = newNodes;
00179 delete [] m_pool;
00180 delete m_storage;
00181
00182 m_pool = newPool;
00183 m_storage = newStorage;
00184 }
00185
00190 const SizeType& getHeight() const
00191 {
00192 return m_height;
00193 }
00194
00195 SizeType getMemoryUsage()
00196 {
00197 SizeType sum = (m_numNodes + 1) * sizeof( DataType) + m_storage->getMemoryUsage() + 2 * sizeof( SizeType);
00198 return sum;
00199 }
00200
00205 const SizeType& getNumNodes() const
00206 {
00207 return m_numNodes;
00208 }
00209
00214 Node getRootNode()
00215 {
00216 return Node(this,m_pool,1);
00217 }
00218
00223 Node* getRootPointer() const;
00224
00228 void increaseHeight()
00229 {
00230 SizeType newHeight = m_height + 1;
00231 SizeType newNodes = pow2(newHeight + 1) - 1;
00232
00234 DataType* newPool = new DataType[ newNodes ];
00235 StorageScheme* newStorage = new StorageScheme( newPool, newHeight);
00236 for( SizeType i = 0; i < newNodes; i++)
00237 {
00238 newPool[i] = m_defaultValue;
00239 }
00240
00241 std::stack< CopyController<DataType,SizeType> > S;
00242 CopyController<DataType,SizeType> rightCtrl,leftCtrl;
00243 CopyController<DataType,SizeType> ctrl( 1, m_height, newHeight, m_pool, newPool);
00244 S.push( ctrl);
00245 while( !S.empty())
00246 {
00247 ctrl = S.top();
00248 S.pop();
00249 ctrl.print();
00250 *(ctrl.newPtr) = *(ctrl.ptr);
00251 if( (ctrl.bfsIndex << 1) <= m_numNodes )
00252 {
00253 rightCtrl.reset( (ctrl.bfsIndex << 1) + 1, ctrl.height - 1, ctrl.newHeight - 1,
00254 m_storage->getRightChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height),
00255 newStorage->getRightChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
00256 S.push( rightCtrl);
00257
00258 leftCtrl.reset( ctrl.bfsIndex << 1, ctrl.height - 1, ctrl.newHeight - 1,
00259 m_storage->getLeftChildAddress( ctrl.ptr, ctrl.bfsIndex, ctrl.height),
00260 newStorage->getLeftChildAddress( ctrl.newPtr, ctrl.bfsIndex, ctrl.newHeight));
00261 S.push( leftCtrl);
00262 }
00263 }
00264
00265 ++m_height;
00267 m_numNodes = newNodes;
00268 delete [] m_pool;
00269 delete m_storage;
00270
00271 m_pool = newPool;
00272 m_storage = newStorage;
00273 }
00274
00281 void printGraphviz( std::ostream& out, const std::string& prefix = "")
00282 {
00283 if( m_height > 10)
00284 {
00285 SizeType size = (1 << m_height);
00286 std::cout << "The tree is too big to print (>" << size << ")\n";
00287 return;
00288 }
00289
00290 out << "digraph BFS {\n\tedge [len=3]\n\tnode [fontname=\"Arial\"]\n";
00291
00292 Node m_auxNode( this, m_pool, 1);
00293
00294 std::stack<Node> S;
00295 S.push(m_auxNode);
00296 while( !S.empty())
00297 {
00298 m_auxNode = S.top();
00299 S.pop();
00300 out << prefix << m_auxNode.getPoolIndex();
00301 out << "[shape=record,label=\"{";
00302 out << prefix << m_auxNode.getBfsIndex() << "|";
00303 out << prefix << m_auxNode.getPoolIndex();
00304 out << "}\"]\n";
00305 out << "\t";
00306 if( !m_auxNode.isLeaf())
00307 {
00308 out << prefix << m_auxNode.getPoolIndex();
00309 out << " -> ";
00310 m_auxNode.goLeft();
00311 out << prefix << m_auxNode.getPoolIndex();
00312 out << "\n";
00313 S.push(m_auxNode);
00314 m_auxNode.goUp();
00315 out << "\t";
00316 out << prefix << m_auxNode.getPoolIndex();
00317 out << " -> ";
00318 m_auxNode.goRight();
00319 out << prefix << m_auxNode.getPoolIndex();
00320 S.push(m_auxNode);
00321 }
00322 out << "\n";
00323 }
00324 out << "}";
00325 }
00326
00327 protected:
00331 DataType* m_pool;
00332
00336 _QUEUESTATS(StatisticAnalyser<DataType> stats;)
00337
00341 SizeType m_height;
00342
00346 SizeType m_numNodes;
00347
00351 DataType m_defaultValue;
00352
00356 StorageScheme* m_storage;
00357 };
00358
00359
00360
00371 template <typename DataType, template <typename datatype> class StorageStrategy>
00372 class CompleteBinaryTree<DataType,StorageStrategy>::Node
00373 {
00374 public:
00378 Node(): m_T(0),m_ptr(0),m_bfsIndex(0),m_depth(0)
00379 {
00380 }
00381
00389 Node( CompleteBinaryTree<DataType,StorageStrategy>* T, DataType* ptr, const SizeType bfsIndex): m_T(T), m_ptr(ptr), m_bfsIndex( bfsIndex), m_depth( floorLog2( bfsIndex))
00390 {
00391 }
00392
00397 const DataType* getAddress() const
00398 {
00399 return m_ptr;
00400 }
00401
00406 const SizeType& getBfsIndex() const
00407 {
00408 return m_bfsIndex;
00409 }
00410
00415 const SizeType& getDepth() const
00416 {
00417 return m_depth;
00418 }
00419
00424 SizeType getHeight() const
00425 {
00426 return m_T->m_height - m_depth;
00427 }
00428
00433 SizeType getHorizontalIndex() const
00434 {
00435 return m_bfsIndex - pow2( getDepth());
00436 }
00437
00442 SizeType getMemoryUsage()
00443 {
00444 return 2*sizeof(SizeType) + sizeof(DataType*) + sizeof(CompleteBinaryTree<DataType,StorageStrategy>*);
00445 }
00446
00451 SizeType getPoolIndex() const
00452 {
00453 return m_ptr - m_T->m_pool;
00454 }
00455
00460 void goLeft()
00461 {
00462 _QUEUESTATS( m_T->stats.recordJump( m_T->m_storage->getLeftChildAddress( m_ptr, m_bfsIndex, getHeight() ) - m_ptr);)
00463 m_ptr = m_T->m_storage->getLeftChildAddress( m_ptr, m_bfsIndex, getHeight() );
00464 m_bfsIndex = m_bfsIndex << 1;
00465 m_depth++;
00466 }
00467
00472 void goRight()
00473 {
00474 _QUEUESTATS( m_T->stats.recordJump( m_T->m_storage->getRightChildAddress( m_ptr, m_bfsIndex, getHeight() ) - m_ptr);)
00475 m_ptr = m_T->m_storage->getRightChildAddress( m_ptr, m_bfsIndex, getHeight() );
00476 m_bfsIndex = (m_bfsIndex << 1) + 1;
00477 m_depth++;
00478 }
00479
00484 void goUp()
00485 {
00486 _QUEUESTATS(m_T->stats.recordJump( m_ptr - m_T->m_storage->getParentAddress( m_ptr, m_bfsIndex, getHeight() ));)
00487 m_ptr = m_T->m_storage->getParentAddress( m_ptr, m_bfsIndex, getHeight() );
00488 m_bfsIndex = m_bfsIndex >> 1;
00489 m_depth--;
00490 }
00491
00496 bool isLeaf() const
00497 {
00498 return m_depth == m_T->m_height;
00499 }
00500
00505 bool isRightChild() const
00506 {
00507 return ( (m_bfsIndex & 1) == 1);
00508 }
00509
00515 bool isToTheLeftOf( const Node& other) const
00516 {
00517 assert( this->isLeaf());
00518 return ( (m_bfsIndex >> other.getHeight()) < other.m_bfsIndex);
00519 }
00520
00525 bool isRoot() const
00526 {
00527 return !m_depth;
00528 }
00529
00535 Node& operator=(const Node& other)
00536 {
00537 if( this != &other)
00538 {
00539 this->m_T = other.m_T;
00540 this->m_ptr = other.m_ptr;
00541 this->m_bfsIndex = other.m_bfsIndex;
00542 this->m_depth = other.m_depth;
00543 }
00544 return *this;
00545 }
00546
00547
00548 DataType& operator * ()
00549 {
00550 return *m_ptr;
00551 }
00552
00553 DataType* operator -> ()
00554 {
00555 return m_ptr;
00556 }
00557
00563 bool operator == ( const Node& other) const
00564 {
00565 return (m_T == other.m_T) && (m_ptr == other.m_ptr);
00566 }
00567
00573 bool operator != ( const Node& other) const
00574 {
00575 return !(*this == other);
00576 }
00577
00582 void setAtBfsIndex( const SizeType& bfsIndex)
00583 {
00584 m_ptr = m_T->m_storage->getBfsIndexAddress( bfsIndex);
00585 m_bfsIndex = bfsIndex;
00586 m_depth = floorLog2( bfsIndex);
00587 }
00588
00594 void setAtPos( const SizeType& height, const SizeType& horizontalPosition)
00595 {
00596 setAtBfsIndex( (1<<(m_T->m_height - height)) + horizontalPosition);
00597 return;
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616 }
00617
00621 void setAtRoot()
00622 {
00623 m_bfsIndex = 1;
00624 m_depth = 0;
00625 m_ptr = m_T->m_storage->getRootAddr();
00626 }
00627
00628 protected:
00632 CompleteBinaryTree<DataType,StorageStrategy>* m_T;
00633
00637 DataType* m_ptr;
00638
00643 SizeType m_bfsIndex;
00644
00648 SizeType m_depth;
00649 };
00650
00651
00652
00653
00654 #endif //COMPLETEBINARYTREE_H