00001 #ifndef PACKEDMEMORYARRAYHELPER_H
00002 #define PACKEDMEMORYARRAYHELPER_H
00003
00004 #include <Structs/Trees/completeBinaryTree.h>
00005 #include <assert.h>
00006
00007
00008 class PmaTreeData{
00009 public:
00010 PmaTreeData( unsigned int cardinality = 0, unsigned int offsetElements = 0):m_cardinality(cardinality), m_offsetElements(offsetElements)
00011 {
00012 }
00013
00014 friend std::ostream& operator << ( std::ostream & os, const PmaTreeData& data)
00015 {
00016 os << "( " << data.m_cardinality << ", " << data.m_offsetElements << ")";
00017 return os;
00018 }
00019
00020 unsigned int m_cardinality;
00021 unsigned int m_offsetElements;
00022 };
00023
00024
00025 template <typename DataType>
00026 class PackedMemoryArrayHelper
00027 {
00028 public:
00029 typedef CompleteBinaryTree<PmaTreeData, ExplicitVebStorage> TreeType;
00030 typedef TreeType::SizeType SizeType;
00031 typedef TreeType::Node Node;
00032
00033
00034 PackedMemoryArrayHelper():m_densityTree(0)
00035 {
00036
00037 }
00038
00039 ~PackedMemoryArrayHelper()
00040 {
00041 assert(m_densityTree);
00042 delete m_densityTree;
00043 delete [] m_maxDensity;
00044 delete [] m_minDensity;
00045 m_densityTree = 0;
00046 m_maxDensity = 0;
00047 m_minDensity = 0;
00048 }
00049
00050 bool affordsElementErasureAt( Node& u)
00051 {
00052 return u->m_cardinality - 1 >= m_minDensity[u.getHeight()] * getCapacity(u);
00053 }
00054
00055 bool affordsElementInsertionAt( Node& u)
00056 {
00057 return u->m_cardinality + 1 <= m_maxDensity[u.getHeight()] * getCapacity(u);
00058 }
00059
00060 bool affordsErasure()
00061 {
00062 assert(m_densityTree);
00063 m_auxNode.setAtRoot();
00064 return affordsElementErasureAt(m_auxNode);
00065 }
00066
00067 bool affordsInsertion()
00068 {
00069 assert(m_densityTree);
00070 m_auxNode.setAtRoot();
00071 return affordsElementInsertionAt(m_auxNode);
00072 }
00073
00074 void decreaseCardinality( const Node& u)
00075 {
00076 assert(m_densityTree);
00077 m_auxNode = u;
00078 bool changedParentOffset = false;
00079 while( !m_auxNode.isRoot())
00080 {
00081 --(m_auxNode->m_cardinality);
00082 if( changedParentOffset)
00083 {
00084 --(m_auxNode->m_offsetElements);
00085 }
00086
00087 changedParentOffset = !m_auxNode.isRightChild();
00088 m_auxNode.goUp();
00089 }
00090 --(m_auxNode->m_cardinality);
00091 if( changedParentOffset)
00092 {
00093 --(m_auxNode->m_offsetElements);
00094 }
00095 }
00096
00097 const Node& findEmptiestNode()
00098 {
00099 assert(m_densityTree);
00100 m_auxNode.setAtRoot();
00101 while( !m_auxNode.isLeaf())
00102 {
00103 if( m_auxNode->m_offsetElements <= (m_auxNode->m_cardinality >> 1))
00104 {
00105 m_auxNode.goLeft();
00106 }
00107 else
00108 {
00109 m_auxNode.goRight();
00110 }
00111 }
00112 return m_auxNode;
00113 }
00114
00115 SizeType findIndexContainingElement( const SizeType& elementIndex)
00116 {
00117 assert(m_densityTree);
00118 m_auxNode.setAtRoot();
00119 SizeType aggregateOffset = 0;
00120 SizeType aggregateCapacity = 0;
00121
00122 while( !m_auxNode.isLeaf())
00123 {
00124 if( elementIndex < aggregateOffset + m_auxNode->m_offsetElements)
00125 {
00126 m_auxNode.goLeft();
00127 }
00128 else
00129 {
00130 aggregateOffset += m_auxNode->m_offsetElements;
00131 aggregateCapacity += (getCapacity(m_auxNode) >> 1);
00132 m_auxNode.goRight();
00133 }
00134 }
00135
00136 return aggregateCapacity + ( elementIndex - aggregateOffset);
00137 }
00138
00139 const Node& findNodeContainingElement( const SizeType& elementIndex)
00140 {
00141 assert(m_densityTree);
00142 m_auxNode.setAtRoot();
00143 SizeType aggregateOffset = 0;
00144
00145 while( !m_auxNode.isLeaf())
00146 {
00147 if( elementIndex < aggregateOffset + m_auxNode->m_offsetElements)
00148 {
00149 m_auxNode.goLeft();
00150 }
00151 else
00152 {
00153 aggregateOffset += m_auxNode->m_offsetElements;
00154 m_auxNode.goRight();
00155 }
00156 }
00157
00158 return m_auxNode;
00159 }
00160
00161 SizeType getAggregateOffsetOver( const SizeType& index)
00162 {
00163 SizeType aggregateOffset = 0;
00164 m_auxNode.setAtPos( 0, index / m_leafSize);
00165 while( !m_auxNode.isRoot())
00166 {
00167 if( m_auxNode.isRightChild())
00168 {
00169 m_auxNode.goUp();
00170 aggregateOffset += m_auxNode->m_offsetElements;
00171 }
00172 else
00173 {
00174 m_auxNode.goUp();
00175 }
00176 }
00177 return aggregateOffset;
00178 }
00179
00180 inline SizeType getCapacity( const Node& u)
00181 {
00182 return m_leafSize << u.getHeight();
00183 }
00184
00185 inline SizeType getCardinality( const Node& u)
00186 {
00187 return u->m_cardinality;
00188 }
00189
00190 SizeType getIndexUnderNode( const Node& u)
00191 {
00192 assert(m_densityTree);
00193 return m_leafSize * u.getHorizontalIndex();
00194 }
00195
00196 SizeType getMemoryUsage()
00197 {
00198 return m_densityTree->getMemoryUsage() + m_auxNode.getMemoryUsage() + sizeof( SizeType);
00199 }
00200
00201 const Node& getNodeOverIndex( const SizeType& index)
00202 {
00203 assert(m_densityTree);
00204 m_auxNode.setAtPos( 0, index / m_leafSize);
00205 return m_auxNode;
00206 }
00207
00208 const Node& getParentForErasure( const Node& u)
00209 {
00210 assert(m_densityTree);
00211 m_auxNode = u;
00212 while( (!u.isRoot()) && (!affordsElementErasureAt(m_auxNode)))
00213 {
00214 m_auxNode.goUp();
00215 }
00216 return m_auxNode;
00217 }
00218
00219 const Node& getParentForInsertion( const Node& u)
00220 {
00221 assert(m_densityTree);
00222 m_auxNode = u;
00223 while( !affordsElementInsertionAt(m_auxNode))
00224 {
00225 m_auxNode.goUp();
00226 }
00227 return m_auxNode;
00228 }
00229
00230 const Node& getRoot()
00231 {
00232 assert(m_densityTree);
00233 m_auxNode.setAtRoot();
00234 return m_auxNode;
00235 }
00236
00237 void increaseCardinality( const Node& u)
00238 {
00239 assert(m_densityTree);
00240 m_auxNode = u;
00241 bool changedParentOffset = false;
00242 while( !m_auxNode.isRoot())
00243 {
00244 ++(m_auxNode->m_cardinality);
00245 if( changedParentOffset)
00246 {
00247 ++(m_auxNode->m_offsetElements);
00248 }
00249
00250 changedParentOffset = !m_auxNode.isRightChild();
00251 m_auxNode.goUp();
00252 }
00253 ++(m_auxNode->m_cardinality);
00254 if( changedParentOffset)
00255 {
00256 ++(m_auxNode->m_offsetElements);
00257 }
00258 }
00259
00260
00261
00262 void printDot( std::ostream& out, const std::string& name = "")
00263 {
00264 if( m_densityTree->getHeight() > 10)
00265 {
00266 SizeType size = (1 << m_densityTree->getHeight());
00267 std::cout << "The tree is too big to print (>" << size << ")\n";
00268 return;
00269 }
00270
00271
00272
00273 m_auxNode.setAtRoot();
00274
00275 std::stack<Node> S;
00276 S.push(m_auxNode);
00277 while( !S.empty())
00278 {
00279 m_auxNode = S.top();
00280 S.pop();
00281 out << name << m_auxNode.getPoolIndex();
00282 out << "[shape=record,label=\"{";
00283 out << name << m_auxNode.getPoolIndex() << "|";
00284
00285 out << m_auxNode->m_cardinality << "/" << getCapacity(m_auxNode) << "|";
00286
00287 out << m_minDensity[m_auxNode.getHeight()] * getCapacity(m_auxNode) << "-" << m_maxDensity[m_auxNode.getHeight()] * getCapacity(m_auxNode);
00288 out << "}\"]\n";
00289 out << "\t";
00290 if( !m_auxNode.isLeaf())
00291 {
00292 out << name << m_auxNode.getPoolIndex();
00293 out << " -> ";
00294 m_auxNode.goLeft();
00295 out << name << m_auxNode.getPoolIndex();
00296 out << "\n";
00297 S.push(m_auxNode);
00298 m_auxNode.goUp();
00299 out << "\t";
00300 out << name << m_auxNode.getPoolIndex();
00301 out << " -> ";
00302 m_auxNode.goRight();
00303 out << name << m_auxNode.getPoolIndex();
00304 S.push(m_auxNode);
00305 }
00306 out << "\n";
00307 }
00308
00309 }
00310
00311 template< typename StreamType>
00312 void rearrangeOver( const Node& u, const Node& sparseNode, StreamType& stream)
00313 {
00314 assert(m_densityTree);
00315 std::stack<Node> S;
00316 SizeType remainder, baseCardinality, leftCardinality;
00317 S.push(u);
00318 stream.setAt( u.getHorizontalIndex() * getCapacity(u) );
00319 while( !S.empty())
00320 {
00321 m_auxNode = S.top();
00322 S.pop();
00323 if( !m_auxNode.isLeaf())
00324 {
00325 remainder = modulusPow2( m_auxNode->m_cardinality, 2);
00326 baseCardinality = m_auxNode->m_cardinality >> 1;
00327
00328 m_auxNode.goRight();
00329
00330 if( sparseNode.isToTheLeftOf( m_auxNode))
00331 {
00332 m_auxNode->m_cardinality = baseCardinality + remainder;
00333 leftCardinality = baseCardinality;
00334 }
00335 else
00336 {
00337 m_auxNode->m_cardinality = baseCardinality;
00338 leftCardinality = baseCardinality + remainder;
00339 }
00340
00341 S.push(m_auxNode);
00342
00343 m_auxNode.goUp();
00344 m_auxNode->m_offsetElements = leftCardinality;
00345
00346 m_auxNode.goLeft();
00347 m_auxNode->m_cardinality = leftCardinality;
00348
00349 S.push(m_auxNode);
00350 }
00351 else
00352 {
00353 m_auxNode->m_offsetElements = 0;
00354
00355 if( m_auxNode->m_cardinality)
00356 {
00357 stream.writeOut( m_auxNode->m_cardinality);
00358 }
00359 stream.emptyOut( getCapacity(m_auxNode) - m_auxNode->m_cardinality);
00360 }
00361 }
00362 }
00363
00364 template< typename StreamType>
00365 void rearrangeOver( const Node& u, StreamType& stream)
00366 {
00367 assert(m_densityTree);
00368 std::stack<Node> S;
00369 SizeType remainder, baseCardinality, leftCardinality;
00370 S.push(u);
00371 stream.setAt( u.getHorizontalIndex() * getCapacity(u) );
00372 while( !S.empty())
00373 {
00374 m_auxNode = S.top();
00375 S.pop();
00376 if( !m_auxNode.isLeaf())
00377 {
00378 remainder = modulusPow2( m_auxNode->m_cardinality, 2);
00379 baseCardinality = m_auxNode->m_cardinality >> 1;
00380
00381 m_auxNode.goRight();
00382
00383 m_auxNode->m_cardinality = baseCardinality;
00384 leftCardinality = baseCardinality + remainder;
00385
00386 S.push(m_auxNode);
00387
00388 m_auxNode.goUp();
00389 m_auxNode->m_offsetElements = leftCardinality;
00390
00391 m_auxNode.goLeft();
00392 m_auxNode->m_cardinality = leftCardinality;
00393
00394 S.push(m_auxNode);
00395 }
00396 else
00397 {
00398 m_auxNode->m_offsetElements = 0;
00399
00400 if( m_auxNode->m_cardinality)
00401 {
00402 stream.writeOut( m_auxNode->m_cardinality);
00403 }
00404 stream.emptyOut( getCapacity(m_auxNode) - m_auxNode->m_cardinality);
00405 }
00406 }
00407 }
00408
00409 void reset( const SizeType& treeHeight, const SizeType& leafSize, const SizeType& cardinality, double minEmptinessPercentage = 0.5, double maxFullnessPercentage = 0.75)
00410 {
00411 if( m_densityTree)
00412 {
00413 delete m_densityTree;
00414 delete [] m_maxDensity;
00415 delete [] m_minDensity;
00416 m_densityTree = 0;
00417 m_maxDensity = 0;
00418 m_minDensity = 0;
00419 }
00420 m_densityTree = new TreeType( treeHeight, leafSize * pow2(treeHeight) );
00421 m_auxNode = m_densityTree->getRootNode();
00422 m_auxNode->m_cardinality = cardinality;
00423 m_leafSize = leafSize;
00424
00425 m_maxDensity = new double[ treeHeight + 1];
00426 m_minDensity = new double[ treeHeight + 1];
00427 m_maxDensity[treeHeight] = maxFullnessPercentage;
00428 m_minDensity[treeHeight] = minEmptinessPercentage;
00429 m_maxDensity[0] = 0.9;
00430 m_minDensity[0] = 0.1;
00431
00432 for( SizeType h = 1; h < treeHeight; h++)
00433 {
00434 m_maxDensity[h] = m_maxDensity[treeHeight] + ( m_maxDensity[0] - m_maxDensity[treeHeight]) * ( treeHeight - h) / treeHeight;
00435 m_minDensity[h] = m_minDensity[treeHeight] - ( m_minDensity[treeHeight] - m_minDensity[0]) * ( treeHeight - h) / treeHeight;
00436 }
00437 }
00438
00439 private:
00440 TreeType* m_densityTree;
00441 Node m_auxNode;
00442 SizeType m_leafSize;
00443 double* m_maxDensity;
00444 double* m_minDensity;
00445
00446 };
00447
00448
00449 #endif //PACKEDMEMORYARRAYHELPER_H