dune-grid
2.2.0
|
00001 #ifndef DUNE_ALBERTAGRID_INDEXSTACK_HH 00002 #define DUNE_ALBERTAGRID_INDEXSTACK_HH 00003 00004 #include <assert.h> 00005 #include <stack> 00006 00007 #include <dune/common/exceptions.hh> 00008 #include <dune/common/reservedvector.hh> 00009 00016 namespace Dune { 00017 00020 template <class T, int length> 00021 class IndexStack 00022 { 00023 class MyFiniteStack : public ReservedVector<T,length> 00024 { 00025 typedef ReservedVector<T,length> BaseType ; 00026 public: 00028 bool full () const { return this->size() >= length; } 00029 00031 void push( const T& t ) { BaseType :: push_back( t ); } 00032 00034 T topAndPop () 00035 { 00036 assert( !this->empty() ); 00037 assert( this->size() <= length ); 00038 // This code is not slower than using the array structure directly. 00039 // The compiler removes the temporary completely. I measured this. 00040 // See the commit message for revision 7837 for more details. 00041 T tmp = this->back(); 00042 this->pop_back(); 00043 return tmp; 00044 } 00045 }; 00046 00047 typedef MyFiniteStack StackType; 00048 typedef typename std::stack < StackType * > StackListType; 00049 00050 StackListType fullStackList_; 00051 StackListType emptyStackList_; 00052 00053 //typedef typename StackListType::Iterator DListIteratorType; 00054 StackType * stack_; 00055 00056 // current maxIndex 00057 int maxIndex_; 00058 public: 00060 inline IndexStack(); 00061 00063 inline ~IndexStack (); 00064 00066 inline void checkAndSetMax(T index) { if(index > maxIndex_) maxIndex_ = index; } 00067 00069 inline void setMaxIndex(T index) { maxIndex_ = index; } 00070 00072 inline int getMaxIndex() const { return maxIndex_; } 00073 00075 inline int size() const { return getMaxIndex(); } 00076 00078 inline T getIndex (); 00079 00081 inline void freeIndex(T index); 00082 00084 inline void test (); 00085 00086 // backup set to out stream 00087 inline void backupIndexSet ( std::ostream & os ); 00088 00089 // restore from in stream 00090 inline void restoreIndexSet ( std::istream & is ); 00091 private: 00092 // no copy constructor allowed 00093 IndexStack( const IndexStack<T,length> & s) : maxIndex_ (0) , stack_(0) {} 00094 00095 // no assignment operator allowed 00096 IndexStack<T,length> & operator = ( const IndexStack<T,length> & s) 00097 { 00098 DUNE_THROW(Exception, "IndexStack::operator = () not allowed!"); 00099 return *this; 00100 } 00101 00102 // clear fullStacks 00103 void clearStack (); 00104 00105 }; // end class IndexStack 00106 00107 //**************************************************************** 00108 // Inline implementation 00109 // *************************************************************** 00110 template <class T, int length> 00111 inline IndexStack<T,length>::IndexStack() 00112 : stack_ ( new StackType () ) , maxIndex_ (0) {} 00113 00114 template <class T, int length> 00115 inline IndexStack<T,length>::~IndexStack () 00116 { 00117 if(stack_) delete stack_; 00118 stack_ = 0; 00119 00120 while( !fullStackList_.empty() ) 00121 { 00122 StackType * st = fullStackList_.top(); 00123 if(st) delete st; 00124 fullStackList_.pop(); 00125 } 00126 while( !emptyStackList_.empty() ) 00127 { 00128 StackType * st = emptyStackList_.top(); 00129 if(st) delete st; 00130 emptyStackList_.pop(); 00131 } 00132 } 00133 00134 template <class T, int length> 00135 inline T IndexStack<T,length>::getIndex () 00136 { 00137 if((*stack_).empty()) 00138 { 00139 if( fullStackList_.size() <= 0) 00140 { 00141 return maxIndex_++; 00142 } 00143 else 00144 { 00145 emptyStackList_.push( stack_ ); 00146 stack_ = fullStackList_.top(); 00147 fullStackList_.pop(); 00148 } 00149 } 00150 return (*stack_).topAndPop(); 00151 } 00152 00153 template <class T, int length> 00154 inline void IndexStack<T,length>::freeIndex ( T index ) 00155 { 00156 if((*stack_).full()) 00157 { 00158 fullStackList_.push( stack_ ); 00159 if(emptyStackList_.size() <= 0) 00160 { 00161 stack_ = new StackType (); 00162 } 00163 else 00164 { 00165 stack_ = emptyStackList_.top(); 00166 emptyStackList_.pop(); 00167 } 00168 } 00169 (*stack_).push(index); 00170 } 00171 00172 template <class T, int length> 00173 inline void IndexStack<T,length>::test () 00174 { 00175 T vec[2*length]; 00176 00177 for(int i=0; i<2*length; i++) 00178 vec[i] = getIndex(); 00179 00180 for(int i=0; i<2*length; i++) 00181 freeIndex(vec[i]); 00182 00183 for(int i=0; i<2*length; i++) 00184 vec[i] = getIndex(); 00185 00186 for(int i=0; i<2*length; i++) 00187 printf(" index [%d] = %d \n",i,vec[i]); 00188 } 00189 00190 template <class T, int length> 00191 inline void IndexStack<T,length>::backupIndexSet ( std::ostream & os ) 00192 { 00193 // holes are not stored at the moment 00194 os.write( ((const char *) &maxIndex_ ), sizeof(int) ) ; 00195 return ; 00196 } 00197 00198 template <class T, int length> 00199 inline void IndexStack<T,length>::restoreIndexSet ( std::istream & is ) 00200 { 00201 is.read ( ((char *) &maxIndex_), sizeof(int) ); 00202 clearStack (); 00203 00204 return ; 00205 } 00206 00207 template <class T, int length> 00208 inline void IndexStack<T,length>::clearStack () 00209 { 00210 if(stack_) 00211 { 00212 delete stack_; 00213 stack_ = new StackType(); 00214 assert(stack_); 00215 } 00216 00217 while( !fullStackList_.empty() ) 00218 { 00219 StackType * st = fullStackList_.top(); 00220 if(st) delete st; 00221 fullStackList_.pop(); 00222 } 00223 return; 00224 } 00225 00226 } // end namespace Dune 00227 #endif