dune-grid  2.2.0
albertagrid/indexstack.hh
Go to the documentation of this file.
1 #ifndef DUNE_ALBERTAGRID_INDEXSTACK_HH
2 #define DUNE_ALBERTAGRID_INDEXSTACK_HH
3 
4 #include <assert.h>
5 #include <stack>
6 
7 #include <dune/common/exceptions.hh>
8 #include <dune/common/reservedvector.hh>
9 
16 namespace Dune {
17 
20 template <class T, int length>
21 class IndexStack
22 {
23  class MyFiniteStack : public ReservedVector<T,length>
24  {
25  typedef ReservedVector<T,length> BaseType ;
26  public:
28  bool full () const { return this->size() >= length; }
29 
31  void push( const T& t ) { BaseType :: push_back( t ); }
32 
34  T topAndPop ()
35  {
36  assert( !this->empty() );
37  assert( this->size() <= length );
38  // This code is not slower than using the array structure directly.
39  // The compiler removes the temporary completely. I measured this.
40  // See the commit message for revision 7837 for more details.
41  T tmp = this->back();
42  this->pop_back();
43  return tmp;
44  }
45  };
46 
47  typedef MyFiniteStack StackType;
48  typedef typename std::stack < StackType * > StackListType;
49 
50  StackListType fullStackList_;
51  StackListType emptyStackList_;
52 
53  //typedef typename StackListType::Iterator DListIteratorType;
54  StackType * stack_;
55 
56  // current maxIndex
57  int maxIndex_;
58 public:
60  inline IndexStack();
61 
63  inline ~IndexStack ();
64 
66  inline void checkAndSetMax(T index) { if(index > maxIndex_) maxIndex_ = index; }
67 
69  inline void setMaxIndex(T index) { maxIndex_ = index; }
70 
72  inline int getMaxIndex() const { return maxIndex_; }
73 
75  inline int size() const { return getMaxIndex(); }
76 
78  inline T getIndex ();
79 
81  inline void freeIndex(T index);
82 
84  inline void test ();
85 
86  // backup set to out stream
87  inline void backupIndexSet ( std::ostream & os );
88 
89  // restore from in stream
90  inline void restoreIndexSet ( std::istream & is );
91 private:
92  // no copy constructor allowed
93  IndexStack( const IndexStack<T,length> & s) : maxIndex_ (0) , stack_(0) {}
94 
95  // no assignment operator allowed
96  IndexStack<T,length> & operator = ( const IndexStack<T,length> & s)
97  {
98  DUNE_THROW(Exception, "IndexStack::operator = () not allowed!");
99  return *this;
100  }
101 
102  // clear fullStacks
103  void clearStack ();
104 
105 }; // end class IndexStack
106 
107 //****************************************************************
108 // Inline implementation
109 // ***************************************************************
110 template <class T, int length>
112  : stack_ ( new StackType () ) , maxIndex_ (0) {}
113 
114 template <class T, int length>
116 {
117  if(stack_) delete stack_;
118  stack_ = 0;
119 
120  while( !fullStackList_.empty() )
121  {
122  StackType * st = fullStackList_.top();
123  if(st) delete st;
124  fullStackList_.pop();
125  }
126  while( !emptyStackList_.empty() )
127  {
128  StackType * st = emptyStackList_.top();
129  if(st) delete st;
130  emptyStackList_.pop();
131  }
132 }
133 
134 template <class T, int length>
136 {
137  if((*stack_).empty())
138  {
139  if( fullStackList_.size() <= 0)
140  {
141  return maxIndex_++;
142  }
143  else
144  {
145  emptyStackList_.push( stack_ );
146  stack_ = fullStackList_.top();
147  fullStackList_.pop();
148  }
149  }
150  return (*stack_).topAndPop();
151 }
152 
153 template <class T, int length>
154 inline void IndexStack<T,length>::freeIndex ( T index )
155 {
156  if((*stack_).full())
157  {
158  fullStackList_.push( stack_ );
159  if(emptyStackList_.size() <= 0)
160  {
161  stack_ = new StackType ();
162  }
163  else
164  {
165  stack_ = emptyStackList_.top();
166  emptyStackList_.pop();
167  }
168  }
169  (*stack_).push(index);
170 }
171 
172 template <class T, int length>
174 {
175  T vec[2*length];
176 
177  for(int i=0; i<2*length; i++)
178  vec[i] = getIndex();
179 
180  for(int i=0; i<2*length; i++)
181  freeIndex(vec[i]);
182 
183  for(int i=0; i<2*length; i++)
184  vec[i] = getIndex();
185 
186  for(int i=0; i<2*length; i++)
187  printf(" index [%d] = %d \n",i,vec[i]);
188 }
189 
190 template <class T, int length>
191 inline void IndexStack<T,length>::backupIndexSet ( std::ostream & os )
192 {
193  // holes are not stored at the moment
194  os.write( ((const char *) &maxIndex_ ), sizeof(int) ) ;
195  return ;
196 }
197 
198 template <class T, int length>
199 inline void IndexStack<T,length>::restoreIndexSet ( std::istream & is )
200 {
201  is.read ( ((char *) &maxIndex_), sizeof(int) );
202  clearStack ();
203 
204  return ;
205 }
206 
207 template <class T, int length>
208 inline void IndexStack<T,length>::clearStack ()
209 {
210  if(stack_)
211  {
212  delete stack_;
213  stack_ = new StackType();
214  assert(stack_);
215  }
216 
217  while( !fullStackList_.empty() )
218  {
219  StackType * st = fullStackList_.top();
220  if(st) delete st;
221  fullStackList_.pop();
222  }
223  return;
224 }
225 
226 } // end namespace Dune
227 #endif