00001 #ifndef PACKEDMEMORYARRAY_H
00002 #define PACKEDMEMORYARRAY_H
00003
00004 #include <Structs/Arrays/packedMemoryArrayHelper.h>
00005 #include <set>
00006 #include <deque>
00007 #include <assert.h>
00008 #include <limits>
00009 #include <memory>
00010
00020 template <typename dataType>
00021 class PackedMemoryArray
00022 {
00023 public:
00024 typedef unsigned int SizeType;
00025 typedef PackedMemoryArrayHelper<dataType> Helper;
00026 typedef typename Helper::Node TreeNode;
00027
00028 class Iterator;
00029 class Bucket;
00030 class InlineStream;
00031 class ConstantStream;
00032 class CopyingStream;
00033 class Observer;
00034
00035 PackedMemoryArray(const double& minEmptinessPercentage = 0.4, const double& maxFullnessPercentage = 0.9):
00036 m_minEmptinessPercentage(minEmptinessPercentage),
00037 m_maxFullnessPercentage(maxFullnessPercentage),
00038 m_emptyElement(std::numeric_limits<unsigned int>::max()),
00039 m_numElements(0),
00040 m_poolSize(4)
00041 {
00042
00043
00044
00045 assert( 2*minEmptinessPercentage <= maxFullnessPercentage);
00046 m_bucketSize = 4;
00047 init();
00048 std::fill( m_pool, m_pool + m_poolSize, m_emptyElement);
00049 m_auxIter.reset( this, 0);
00050 m_oldPool = 0;
00051 }
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069 ~PackedMemoryArray()
00070 {
00071 delete[] m_pool;
00072 }
00073
00074 Iterator atAddress( dataType* addr)
00075 {
00076 assert( addr < getPool() + m_poolSize);
00077 return Iterator( this, addr);
00078 }
00079
00080 Iterator atIndex ( const SizeType& poolIndex )
00081 {
00082 assert( poolIndex < m_poolSize);
00083 return Iterator( this, m_pool + poolIndex);
00084 }
00085
00086 Iterator begin ()
00087 {
00088 dataType* ptr = m_pool;
00089 while( (ptr != m_end.m_ptr) && (*ptr == m_emptyElement))
00090 {
00091 ptr += m_bucketSize;
00092 }
00093 return Iterator( this, ptr);
00094 }
00095
00096 SizeType capacity () const
00097 {
00098 return m_poolSize;
00099 }
00100
00101 bool empty () const
00102 {
00103 return ( m_numElements == 0);
00104 }
00105
00106 void clear()
00107 {
00108 m_numElements = 0;
00109 m_poolSize = 4;
00110 m_bucketSize = 4;
00111
00112 delete[] m_pool;
00113
00114 init();
00115 std::fill( m_pool, m_pool + m_poolSize, m_emptyElement);
00116 m_auxIter.reset( this, 0);
00117 m_oldPool = 0;
00118 }
00119
00120 const Iterator& end ()
00121 {
00122 return m_end;
00123 }
00124
00125 void erase( const Iterator& iter)
00126 {
00127 m_auxIter = iter;
00128 assert( m_auxIter.isValid());
00129
00130 resetObservers();
00131 if( !m_helper.affordsErasure())
00132 {
00133 halveArraySize();
00134 }
00135
00136 m_auxNode = m_helper.getNodeOverIndex( m_auxIter.getPoolIndex());
00137
00138 if( !m_helper.affordsElementErasureAt(m_auxNode))
00139 {
00140 TreeNode sparseNode = m_auxNode;
00141 m_auxNode = m_helper.getParentForErasure( m_auxNode);
00142 InlineStream stream( this);
00143 m_helper.rearrangeOver( m_auxNode, sparseNode, stream);
00144 resetObservers();
00145 m_auxIter.reset( this, m_newIteratorIndex);
00146 m_auxNode = m_helper.getNodeOverIndex( m_newIteratorIndex);
00147 }
00148
00149 m_auxBucket.setAt( m_auxIter.getPoolIndex());
00150 m_auxBucket.erase ( m_auxIter);
00151 --m_numElements;
00152
00153 m_helper.decreaseCardinality( m_auxNode);
00154
00155 return;
00156 }
00157
00158
00159 Iterator findBucket( const dataType& data)
00160 {
00161 Iterator it;
00162 TreeNode u, left, right;
00163 u = m_helper.getRoot();
00164 while( !u.isLeaf())
00165 {
00166 left = u;
00167 left.goLeft();
00168 right = u;
00169 right.goRight();
00170
00171 if( !u->m_cardinality)
00172 {
00173 while( !u.isLeaf())
00174 {
00175 u.goRight();
00176 }
00177 break;
00178 }
00179
00180 if( !right->m_cardinality)
00181 {
00182 u = left;
00183 continue;
00184 }
00185
00186 it = atIndex( m_helper.getIndexUnderNode(right) );
00187
00188 if( data < (*it))
00189 {
00190 u = left;
00191 continue;
00192 }
00193 else
00194 {
00195 u = right;
00196 continue;
00197 }
00198 }
00199
00200 return atIndex( m_helper.getIndexUnderNode(u) );
00201 }
00202
00203 Iterator find( const dataType& data)
00204 {
00205 Iterator it = findBucket( data);
00206 Iterator end = Iterator( this, m_pool + it.getPoolIndex() + m_bucketSize);
00207 it.sanitize();
00208 end.sanitize();
00209 while( it != end)
00210 {
00211 if( (*it) == data)
00212 {
00213 return it;
00214 }
00215 ++it;
00216 }
00217 return m_end;
00218 }
00219
00220 Iterator lower_bound( const dataType& data)
00221 {
00222 Iterator it = findBucket( data);
00223 it.sanitize();
00224
00225 while( it != m_end)
00226 {
00227 if( ((*it) > data) || ((*it) == data))
00228 {
00229 return it;
00230 }
00231 ++it;
00232 }
00233 return m_end;
00234 }
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320 inline const SizeType& getBucketSize() const
00321 {
00322 return m_bucketSize;
00323 }
00324
00325 inline const dataType& getEmptyElement() const
00326 {
00327 return m_emptyElement;
00328 }
00329
00330
00331 inline const SizeType& getPoolSize() const
00332 {
00333 return m_poolSize;
00334 }
00335
00336 const Iterator& insert( const Iterator& iter, const dataType& data)
00337 {
00338 m_auxIter = iter;
00339 assert( m_auxIter.isValid() || ( m_auxIter == end()) );
00340
00341 resetObservers();
00342 if( m_auxIter == end())
00343 {
00344 push_back(data);
00345 m_auxIter = end();
00346 return (--m_auxIter);
00347 }
00348
00349
00350 if( !m_helper.affordsInsertion())
00351 {
00352 doubleArraySize();
00353 }
00354
00355
00356 m_auxNode = m_helper.getNodeOverIndex( m_auxIter.getPoolIndex());
00357
00358 if( !m_helper.affordsElementInsertionAt(m_auxNode))
00359 {
00360 TreeNode sparseNode = m_auxNode;
00361 m_auxNode = m_helper.getParentForInsertion( m_auxNode);
00362 InlineStream stream( this);
00363 m_helper.rearrangeOver( m_auxNode, sparseNode, stream);
00364 resetObservers();
00365
00366 m_auxIter.reset( this, m_newIteratorIndex);
00367 m_auxNode = m_helper.getNodeOverIndex( m_newIteratorIndex);
00368 }
00369
00370 m_auxBucket.setAt( m_auxIter.getPoolIndex());
00371 m_auxBucket.insert ( m_auxIter, data);
00372 ++m_numElements;
00373
00374 m_helper.increaseCardinality( m_auxNode);
00375
00376 return m_auxIter;
00377 }
00378
00379
00380 SizeType getMemoryUsage()
00381 {
00382 SizeType poolMem = m_poolSize * sizeof(dataType);
00383 SizeType propertiesMem = 4 * sizeof(SizeType) + sizeof(dataType);
00384 SizeType auxMem = m_auxNode.getMemoryUsage() + m_end.getMemoryUsage() + m_auxBucket.getMemoryUsage() + m_auxNode.getMemoryUsage();
00385 SizeType helperMem = m_helper.getMemoryUsage();
00386 SizeType observersMem = m_observerSet.size() * sizeof( Observer*);
00387
00388 SizeType elements = m_numElements * sizeof(dataType);
00389
00390 std::cout << "\n\tPMA Mem:";
00391 std::cout << "\n\t\telements:\t"<< elements << "(" << double(elements)/1048576 << "Mb)";
00392 std::cout << "\n\t\tpool:\t\t" << poolMem << "(" << double(poolMem)/1048576 << "Mb)";
00393 std::cout << "\n\t\tproperties:\t" << propertiesMem << "(" << double(propertiesMem)/1024 << "Kb)";
00394 std::cout << "\n\t\tauxiliary:\t" << auxMem << "(" << double(auxMem)/1024 << "Kb)";
00395 std::cout << "\n\t\thelper:\t\t" << helperMem << "(" << double(helperMem)/1048576 << "Mb)";
00396 std::cout << "\n\t\tobservers:\t" << observersMem << "(" << double(observersMem)/1048576 << "Mb)";
00397 std::cout << "\n";
00398
00399 return poolMem + propertiesMem + auxMem + helperMem + observersMem;
00400 }
00401
00402
00403
00404
00405 void move( dataType* source, dataType* destination, const dataType& data)
00406 {
00407
00408 assert( destination >= m_pool && ( destination < m_pool + m_poolSize) );
00409
00410 if( m_auxIter.m_ptr == source)
00411 {
00412 m_newIteratorIndex = destination - m_pool;
00413 }
00414
00415 if( source == destination)
00416 {
00417 *destination = data;
00418 return;
00419 }
00420
00421 typename std::set<Observer*>::iterator obs, obsEnd;
00422 for( obs = m_observerSet.begin(), obsEnd = m_observerSet.end(); obs != obsEnd; obs++)
00423 {
00424 (*obs)->move( source, m_oldPool?m_oldPool:m_pool, destination, m_pool, data);
00425 }
00426
00427 *destination = data;
00428 }
00429
00430 dataType& operator[] ( SizeType elementIndex )
00431 {
00432 assert( elementIndex < m_numElements);
00433 return * ( begin() + elementIndex);
00434 }
00435
00436 const dataType& operator[] ( SizeType elementIndex ) const
00437 {
00438 assert( elementIndex < m_numElements);
00439 return *( begin() + elementIndex);
00440 }
00441
00442 Iterator optimalInsert( const dataType& data )
00443 {
00444 m_auxNode = m_helper.findEmptiestNode();
00445 Iterator it = atIndex( m_auxNode.getHorizontalIndex() * m_helper.getCapacity(m_auxNode));
00446 return insert( it, data);
00447 }
00448
00449 void printDot( std::ostream& out, const std::string& name = "", const std::string& next = "")
00450 {
00451
00452 out << "\nsubgraph cluster_" << name << "{\ncolor=blue\n";
00453 m_helper.printDot( out, name);
00454
00455 for( SizeType j = 0; j < m_poolSize; j += m_bucketSize)
00456 {
00457 out << name << "_bucket" << j << "[ shape = \"record\", label = \"";
00458 for( SizeType i = j; i < j + m_bucketSize; ++i)
00459 {
00460 out << "{" << i << "-" << m_pool + i << "|";
00461 if( m_pool[ i] != getEmptyElement())
00462 {
00463 out << m_pool[ i];
00464 }
00465 out << "}|";
00466 }
00467 out << "\"]\n";
00468
00469 m_auxNode = m_helper.getNodeOverIndex( j);
00470 out << name << m_auxNode.getPoolIndex() << " -> " << name << "_bucket" << j << "\n";
00471
00472
00473
00474
00475 }
00476 out << "}\n";
00477
00478 if( !next.empty())
00479 {
00480 for( SizeType j = 0; j < m_poolSize; j += m_bucketSize)
00481 {
00482 out << name << "_bucket" << j <<" -> " << next << "0 [color=white]\n";
00483 }
00484 }
00485
00486 }
00487
00488 void push_back( const dataType& data)
00489 {
00490 resetObservers();
00491 if( !m_helper.affordsInsertion())
00492 {
00493 doubleArraySize();
00494 }
00495
00496 m_auxNode = m_helper.getNodeOverIndex( m_poolSize - 1);
00497
00498 if( !m_helper.affordsElementInsertionAt(m_auxNode))
00499 {
00500 TreeNode sparseNode = m_auxNode;
00501 m_auxNode = m_helper.getParentForInsertion( m_auxNode);
00502 InlineStream stream( this);
00503 m_helper.rearrangeOver( m_auxNode, sparseNode, stream);
00504 resetObservers();
00505 m_auxIter.reset( this, m_newIteratorIndex);
00506 m_auxNode = m_helper.getNodeOverIndex( m_poolSize - 1);
00507 }
00508
00509 m_auxBucket.setAt( m_poolSize - 1);
00510 m_auxBucket.push_back ( data);
00511 ++m_numElements;
00512
00513 m_helper.increaseCardinality( m_auxNode);
00514 }
00515
00516 void registerObserver( Observer* observer)
00517 {
00518 m_observerSet.insert( observer);
00519 }
00520
00521 void unregisterObserver( Observer* observer)
00522 {
00523 typename std::set<Observer*>::iterator pos = m_observerSet.find( observer);
00524 if( pos != m_observerSet.end())
00525 {
00526 m_observerSet.erase(pos);
00527 }
00528 }
00529
00530 void resetObservers()
00531 {
00532 typename std::set<Observer*>::iterator obs, obsEnd;
00533 for( obs = m_observerSet.begin(), obsEnd = m_observerSet.end(); obs != obsEnd; obs++)
00534 {
00535 (*obs)->reset();
00536 }
00537 }
00538
00539 SizeType size() const
00540 {
00541 return m_numElements;
00542 }
00543
00544 dataType* getPool()
00545 {
00546 if( m_oldPool)
00547 {
00548 return m_oldPool;
00549 }
00550 return m_pool;
00551 }
00552
00553 void reserve( SizeType numElements)
00554 {
00555
00556 m_poolSize = nextPowerOf2( numElements);
00557 m_bucketSize = nextPowerOf2( floorLog2( m_poolSize));
00558 m_oldPool = m_pool;
00559
00560 m_maxFullnessPercentage = double( (numElements * 100 / m_poolSize) + 1)/100;
00561
00562
00563 std::cout << "Density:\t" << m_maxFullnessPercentage << "\n";
00564
00565
00566 init();
00567
00568 CopyingStream stream( this, m_oldPool);
00569 m_auxNode = m_helper.getRoot();
00570 m_auxNode->m_cardinality = m_numElements;
00571 m_helper.rearrangeOver( m_auxNode, stream);
00572
00573 resetObservers();
00574 m_auxIter.reset( this, m_newIteratorIndex);
00575 delete[] m_oldPool;
00576 m_oldPool = 0;
00577 }
00578
00579 private:
00580 double m_minEmptinessPercentage;
00581 double m_maxFullnessPercentage;
00582 dataType* m_pool;
00583 dataType m_emptyElement;
00584 SizeType m_numElements;
00585 SizeType m_poolSize;
00586 SizeType m_bucketSize;
00587 Iterator m_auxIter;
00588 Iterator m_end;
00589 Bucket m_auxBucket;
00590 Helper m_helper;
00591 TreeNode m_auxNode;
00592 SizeType m_newIteratorIndex;
00593 std::set<Observer*> m_observerSet;
00594
00595
00596 SizeType m_bucketMask;
00597 dataType* m_oldPool;
00598
00599 void doubleArraySize()
00600 {
00601 m_poolSize <<= 1;
00602 m_bucketSize = nextPowerOf2( floorLog2( m_poolSize));
00603 m_oldPool = m_pool;
00604
00605
00606 init();
00607 CopyingStream stream( this, m_oldPool);
00608 m_helper.rearrangeOver( m_auxNode, stream);
00609 resetObservers();
00610 m_auxIter.reset( this, m_newIteratorIndex);
00611 delete[] m_oldPool;
00612 m_oldPool = 0;
00613 }
00614
00615 void halveArraySize()
00616 {
00617 if( m_poolSize > 2)
00618 {
00619 m_poolSize >>= 1;
00620 m_bucketSize = nextPowerOf2( floorLog2( m_poolSize));
00621 }
00622 else
00623 {
00624 m_poolSize = 1;
00625 m_bucketSize = m_poolSize;
00626 }
00627 m_oldPool = m_pool;
00628
00629
00630 init();
00631 CopyingStream stream( this, m_oldPool);
00632 m_helper.rearrangeOver( m_auxNode, stream);
00633 resetObservers();
00634 m_auxIter.reset( this, m_newIteratorIndex);
00635 delete[] m_oldPool;
00636 m_oldPool = 0;
00637 }
00638
00639 void init()
00640 {
00641 assert( isPowerOf2( m_poolSize));
00642
00643 m_bucketMask = ~(m_bucketSize - 1);
00644 assert( m_bucketSize);
00645 m_pool = new dataType[ m_poolSize];
00646
00647 m_end = Iterator( this, m_pool + m_poolSize);
00648 m_helper.reset( floorLog2(m_poolSize / m_bucketSize) , m_bucketSize, m_numElements, m_minEmptinessPercentage, m_maxFullnessPercentage);
00649 m_auxNode = m_helper.getRoot();
00650 m_auxBucket.setContainer( this);
00651 m_auxBucket.reset();
00652 }
00653 };
00654
00655
00656 template <typename dataType>
00657 class PackedMemoryArray<dataType>::Iterator
00658 {
00659 friend class PackedMemoryArray;
00660
00661 Iterator( PackedMemoryArray* PMA, dataType* ptr) :
00662 m_PMA( PMA),
00663 m_ptr(ptr)
00664 {
00665
00666
00667 }
00668
00669 public:
00670 Iterator():m_PMA(0)
00671 {
00672 }
00673
00674 ~Iterator()
00675 {
00676 }
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696 dataType* getAddress() const
00697 {
00698 return m_ptr;
00699 }
00700
00701 SizeType getElementIndex() const
00702 {
00703
00704 return modulusPow2( m_ptr - m_PMA->m_pool, m_PMA->m_bucketSize) +
00705 m_PMA->m_helper.getAggregateOffsetOver(m_ptr - m_PMA->m_pool);
00706 }
00707
00708 SizeType getPoolIndex() const
00709 {
00710 return m_ptr - m_PMA->m_pool;
00711 }
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726 SizeType getMemoryUsage()
00727 {
00728 return sizeof(dataType*) + sizeof(PackedMemoryArray*);
00729 }
00730
00731 bool isValid() const
00732 {
00733 return (m_ptr >= m_PMA->m_pool) && (m_ptr < m_PMA->m_end.m_ptr);
00734 }
00735
00736 bool isEmpty() const
00737 {
00738 return *m_ptr == m_PMA->m_emptyElement;
00739 }
00740
00741 Iterator& operator=( Iterator const &other) {
00742 m_PMA = other.m_PMA;
00743 m_ptr = other.m_ptr;
00744 return *this;
00745 };
00746
00747 inline bool operator==( const Iterator& other) const
00748 {
00749 return ( other.m_ptr == m_ptr);
00750 }
00751
00752 inline bool operator!=( const Iterator& other) const
00753 {
00754 return !( other.m_ptr == m_ptr);
00755 }
00756
00757 inline bool operator < ( const Iterator& other) const
00758 {
00759 return m_ptr < other.m_ptr;
00760 }
00761
00762 inline bool operator > ( const Iterator& other) const
00763 {
00764 return m_ptr > other.m_ptr;
00765 }
00766
00767 Iterator& operator--()
00768 {
00769 if( m_ptr == m_PMA->m_pool)
00770 {
00771 return *this;
00772 }
00773
00774 --m_ptr;
00775
00776 while( (m_ptr != m_PMA->m_pool) && ( (*m_ptr) == m_PMA->m_emptyElement ) )
00777 {
00778 m_ptr -= 1;
00779 }
00780 return *this;
00781 }
00782
00783
00784 Iterator operator--(int unused)
00785 {
00786 Iterator result = *this;
00787 --(*this);
00788 return result;
00789 }
00790
00791
00792 Iterator& operator++()
00793 {
00794 ++m_ptr;
00795
00796 if( (*this == m_PMA->m_end) || (*m_ptr) != m_PMA->m_emptyElement)
00797 {
00798 return *this;
00799 }
00800
00801 m_ptr = m_PMA->m_pool + m_PMA->m_bucketSize + ( (m_ptr - m_PMA->m_pool) & m_PMA->m_bucketMask);
00802
00803 assert( (*this == m_PMA->m_end) || (*m_ptr) != m_PMA->m_emptyElement);
00804
00805 return *this;
00806
00807
00808
00809
00810
00811
00812
00813
00814
00815
00816
00817
00818 }
00819
00820 Iterator operator++(int unused)
00821 {
00822 Iterator result = *this;
00823 ++(*this);
00824 return result;
00825 }
00826
00827 Iterator operator+( const SizeType& step)
00828 {
00829 if( step)
00830 {
00831 SizeType elementIndex = step + getElementIndex();
00832 assert( elementIndex < m_PMA->m_numElements);
00833 if( elementIndex < m_PMA->m_numElements)
00834 {
00835 return Iterator( m_PMA, m_PMA->m_pool + m_PMA->m_helper.findIndexContainingElement( elementIndex));
00836 }
00837 return m_PMA->m_end;
00838 }
00839 return *this;
00840 }
00841
00842 SizeType operator - ( const Iterator& other)
00843 {
00844 return getElementIndex() - other.getElementIndex();
00845 }
00846
00847 dataType& operator*() const {
00848 assert( (*m_ptr) != m_PMA->m_emptyElement);
00849 return *m_ptr;
00850 }
00851
00852 dataType* operator->() const {
00853
00854 return m_ptr;
00855 }
00856
00857 void reset( PackedMemoryArray* PMA, SizeType poolIndex)
00858 {
00859 m_PMA = PMA;
00860 m_ptr = m_PMA->m_pool + poolIndex;
00861 }
00862
00863 void sanitize()
00864 {
00865 if( *this == m_PMA->m_end) return;
00866 if( (*this != m_PMA->m_end) && ((*m_ptr) == m_PMA->m_emptyElement))
00867 {
00868 m_ptr = m_PMA->m_pool + m_PMA->m_bucketSize + ( (m_ptr - m_PMA->m_pool) & m_PMA->m_bucketMask);
00869 assert( (*this == m_PMA->m_end) || (*m_ptr) != m_PMA->m_emptyElement);
00870 }
00871 }
00872
00873 private:
00874 PackedMemoryArray* m_PMA;
00875 dataType* m_ptr;
00876 };
00877
00878
00879
00880
00881 template <typename dataType>
00882 class PackedMemoryArray<dataType>::Bucket
00883 {
00884 public:
00885 Bucket():m_PMA(0),m_begin(0),m_end(0),m_head(0){}
00886
00887 Bucket( PackedMemoryArray* PMA): m_PMA(PMA),
00888 m_begin( m_PMA->m_pool),
00889 m_end( m_begin + PMA->getBucketSize()),
00890 m_head( m_begin)
00891 {
00892 }
00893
00894 void erase( const Iterator& it)
00895 {
00896 assert(m_PMA);
00897 m_head = m_PMA->m_pool + it.getPoolIndex();
00898 assert( m_head >= m_begin && m_head < m_end);
00899 *m_head = m_PMA->getEmptyElement();
00900 ++m_head;
00901 while( (m_head != m_end) && ( *m_head != m_PMA->getEmptyElement()) )
00902 {
00903 m_PMA->move( m_head, m_head - 1, *m_head);
00904 ++m_head;
00905 }
00906 *(m_head-1) = m_PMA->getEmptyElement();
00907 }
00908
00909 typename PackedMemoryArray<dataType>::Iterator getIterator()
00910 {
00911 return m_PMA->atAddress(m_head);
00912 }
00913
00914 void insert( const Iterator& it, const dataType& data)
00915 {
00916 assert(m_PMA);
00917 dataType temp;
00918 m_head = m_PMA->m_pool + it.getPoolIndex();
00919 assert( m_head >= m_begin && m_head < m_end);
00920
00921
00922 --m_end;
00923 while( *m_end == m_PMA->getEmptyElement() && m_end != m_head)
00924 {
00925 --m_end;
00926 }
00927
00928
00929 while( m_end != m_head)
00930 {
00931 m_PMA->move( m_end, m_end + 1, *m_end);
00932 --m_end;
00933 }
00934
00935 if( *m_end != m_PMA->getEmptyElement())
00936 {
00937 m_PMA->move(m_end, m_end + 1, *m_end);
00938 }
00939 *m_head = data;
00940 m_end = m_begin + m_PMA->getBucketSize();
00941 }
00942
00943 SizeType getMemoryUsage() const
00944 {
00945 return 3 * sizeof(dataType*) + sizeof( PackedMemoryArray*);
00946 }
00947
00948 void push_back( const dataType& data)
00949 {
00950 assert(m_PMA);
00951 m_head = m_end - 1;
00952 while( (m_head != m_begin))
00953 {
00954 if ( *m_head != m_PMA->getEmptyElement())
00955 {
00956 break;
00957 }
00958 --m_head;
00959 }
00960
00961 if( *m_head != m_PMA->getEmptyElement())
00962 {
00963 ++m_head;
00964 }
00965
00966 assert( m_head != m_end);
00967 *m_head = data;
00968 }
00969
00970 void reset( SizeType index = 0)
00971 {
00972 assert(m_PMA);
00973 m_begin = m_PMA->m_pool + index * m_PMA->getBucketSize();
00974 m_end = m_begin + m_PMA->getBucketSize();
00975 m_head = m_begin;
00976 }
00977
00978 void setAt( const SizeType& position)
00979 {
00980 m_begin = m_PMA->m_pool + position - modulusPow2( position, m_PMA->getBucketSize());
00981 m_end = m_begin + m_PMA->getBucketSize();
00982 m_head = m_begin;
00983 }
00984
00985 void setContainer( PackedMemoryArray* PMA)
00986 {
00987 m_PMA = PMA;
00988 }
00989
00990 private:
00991 PackedMemoryArray* m_PMA;
00992 dataType* m_begin;
00993 dataType* m_end;
00994 dataType* m_head;
00995 };
00996
00997
00998
00999
01000
01001 template <typename dataType>
01002 class PackedMemoryArray<dataType>::InlineStream
01003 {
01004 public:
01005 InlineStream( PackedMemoryArray* PMA):m_PMA(PMA)
01006 {
01007 setAt(0);
01008 }
01009
01010 void setAt( const SizeType& writehead)
01011 {
01012 m_readhead = m_PMA->m_pool + writehead;
01013 m_writehead = m_readhead;
01014 m_Q.clear();
01015 }
01016
01017 void emptyOut( PackedMemoryArray<dataType>::SizeType n)
01018 {
01019 while ( n > 0)
01020 {
01021 while( m_readhead <= m_writehead)
01022 {
01023 if( *m_readhead != m_PMA->getEmptyElement())
01024 {
01025 m_Q.push_back( std::pair< dataType, dataType*>( *m_readhead, m_readhead));
01026 *m_readhead = m_PMA->getEmptyElement();
01027 }
01028 ++m_readhead;
01029 }
01030 ++m_writehead;
01031 --n;
01032 }
01033 }
01034
01035 void writeOut( PackedMemoryArray<dataType>::SizeType n)
01036 {
01037 while ( n > 0)
01038 {
01039 while( m_readhead <= m_writehead)
01040 {
01041 assert( m_readhead < m_PMA->m_pool + m_PMA->m_poolSize);
01042 if( *m_readhead != m_PMA->getEmptyElement())
01043 {
01044 m_Q.push_back( std::pair< dataType, dataType*>( *m_readhead, m_readhead));
01045 *m_readhead = m_PMA->getEmptyElement();
01046 }
01047 ++m_readhead;
01048 }
01049 if( m_Q.empty())
01050 {
01051 assert( m_readhead < m_PMA->m_pool + m_PMA->m_poolSize);
01052 while( *m_readhead == m_PMA->getEmptyElement())
01053 {
01054 ++m_readhead;
01055 }
01056 if( m_readhead != m_writehead)
01057 {
01058 m_PMA->move( m_readhead, m_writehead, *m_readhead);
01059 *m_readhead = m_PMA->getEmptyElement();
01060 }
01061 ++m_readhead;
01062 }
01063 else
01064 {
01065 std::pair<dataType,dataType*> p = m_Q.front();
01066 m_PMA->move( p.second, m_writehead, p.first);
01067 m_Q.pop_front();
01068 }
01069 ++m_writehead;
01070 --n;
01071 }
01072 }
01073 private:
01074 std::deque< std::pair< dataType, dataType*> > m_Q;
01075 PackedMemoryArray* m_PMA;
01076 dataType* m_readhead;
01077 dataType* m_writehead;
01078 };
01079
01080
01081 template <typename dataType>
01082 class PackedMemoryArray<dataType>::ConstantStream
01083 {
01084 public:
01085 ConstantStream( PackedMemoryArray* PMA , const dataType& value):m_PMA(PMA),m_constantValue(value)
01086 {
01087 setAt(0);
01088 }
01089
01090 void setAt( const SizeType& writehead)
01091 {
01092 m_writehead = m_PMA->m_pool + writehead;
01093 }
01094
01095 void emptyOut( PackedMemoryArray<dataType>::SizeType n)
01096 {
01097 while ( n > 0)
01098 {
01099 *m_writehead = m_PMA->getEmptyElement();
01100 ++m_writehead;
01101 --n;
01102 }
01103 }
01104
01105 void writeOut( PackedMemoryArray<dataType>::SizeType n)
01106 {
01107 while ( n > 0)
01108 {
01109 *m_writehead = m_constantValue;
01110 ++m_writehead;
01111 --n;
01112 }
01113 }
01114 private:
01115 PackedMemoryArray* m_PMA;
01116 dataType* m_writehead;
01117 dataType m_constantValue;
01118 };
01119
01120
01121
01122
01123 template <typename dataType>
01124 class PackedMemoryArray<dataType>::CopyingStream
01125 {
01126 public:
01127 CopyingStream( PackedMemoryArray* PMA , dataType* source):m_PMA(PMA),m_source(source)
01128 {
01129 setAt(0);
01130 }
01131
01132 void setAt( const SizeType& writehead)
01133 {
01134 m_writehead = m_PMA->m_pool + writehead;
01135 }
01136
01137 void emptyOut( PackedMemoryArray<dataType>::SizeType n)
01138 {
01139 while ( n > 0)
01140 {
01141 assert( m_writehead < m_PMA->m_pool + m_PMA->m_poolSize);
01142 *m_writehead = m_PMA->getEmptyElement();
01143 ++m_writehead;
01144 --n;
01145 }
01146 }
01147
01148 void writeOut( PackedMemoryArray<dataType>::SizeType n)
01149 {
01150 while ( n > 0)
01151 {
01152 while( *m_source == m_PMA->getEmptyElement())
01153 {
01154 ++m_source;
01155 }
01156 m_PMA->move( m_source, m_writehead, *m_source);
01157 ++m_writehead;
01158 ++m_source;
01159 --n;
01160 }
01161 }
01162
01163 private:
01164 PackedMemoryArray* m_PMA;
01165 dataType* m_writehead;
01166 dataType* m_source;
01167 };
01168
01169
01170 template< typename dataType>
01171 class PackedMemoryArray<dataType>::Observer
01172 {
01173 public:
01174 virtual void move( dataType* source, dataType* sourcePool, dataType* destination, dataType* destinationPool, const dataType& data) {}
01175 virtual void remove( PackedMemoryArray::SizeType source) {}
01176 virtual void reset() {}
01177 };
01178
01179
01180
01181
01182 #endif //PACKEDMEMORYARRAY_H