dune-grid  2.2.0
albertagrid/indexstack.hh
Go to the documentation of this file.
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