dune-functions  2.6-dev
reserveddeque.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 #ifndef DUNE_FUNCTIONS_COMMON_RESERVEDDEQUE_HH
4 #define DUNE_FUNCTIONS_COMMON_RESERVEDDEQUE_HH
5 
10 #include <algorithm>
11 #include <iostream>
12 #include <cstddef>
13 #include <initializer_list>
14 
15 #include <dune/common/genericiterator.hh>
16 
17 #ifdef CHECK_RESERVEDDEQUE
18 #define CHECKSIZE(X) assert(X)
19 #else
20 #define CHECKSIZE(X) {}
21 #endif
22 
23 namespace Dune {
24 namespace Functions {
25 
43  template<class T, int n>
45  {
46  public:
47 
50  typedef T value_type;
53  typedef T* pointer;
55  typedef T& reference;
57  typedef const T& const_reference;
59  typedef size_t size_type;
61  typedef std::ptrdiff_t difference_type;
63  typedef Dune::GenericIterator<ReservedDeque, value_type> iterator;
65  typedef Dune::GenericIterator<const ReservedDeque, const value_type> const_iterator;
66 
71  ReservedDeque() :
73  size_(0),
74  first_(0)
75  {}
76 
77  ReservedDeque(std::initializer_list<T> const &l)
78  {
79  assert(l.size() <= n);// Actually, this is not needed any more!
80  size_ = l.size();
81  std::copy_n(l.begin(), size_, data_);
82  }
83 
88  void clear()
90  {
91  first_ = 0;
92  size_ = 0;
93  }
94 
96  void resize(size_t s)
97  {
98  CHECKSIZE(s<=n);
99  size_ = s;
100  }
101 
103  void push_back(const T& t)
104  {
105  CHECKSIZE(size_<n);
106  data_[size_++ % n] = t;
107  }
108 
110  void push_front(const T& t)
111  {
112  CHECKSIZE(size_<n);
113  ++size_;
114  first_ = (first_+(n-1)) % n;
115  data_[first_] = t;
116  }
117 
119  void pop_back()
120  {
121  if (! empty())
122  size_--;
123  }
124 
126  void pop_front()
127  {
128  if (! empty())
129  {
130  size_--;
131  first_ = (++first_) % n;
132  }
133  }
134 
137  return iterator(*this, 0);
138  }
139 
142  return const_iterator(*this, 0);
143  }
144 
147  return iterator(*this, size_);
148  }
149 
151  const_iterator end() const {
152  return const_iterator(*this, size_);
153  }
154 
157  {
158  CHECKSIZE(size_>i);
159  return data_[(first_ + i) % n];
160  }
161 
164  {
165  CHECKSIZE(size_>i);
166  return data_[(first_ + i) % n];
167  }
168 
171  {
172  CHECKSIZE(size_>0);
173  return data_[first_];
174  }
175 
178  {
179  CHECKSIZE(size_>0);
180  return data_[first_];
181  }
182 
185  {
186  CHECKSIZE(size_>0);
187  return data_[(first_ + size_-1) % n];
188  }
189 
192  {
193  CHECKSIZE(size_>0);
194  return data_[(first_ + size_-1) % n];
195  }
196 
201  size_type size () const
203  {
204  return size_;
205  }
206 
208  bool empty() const
209  {
210  return size_==0;
211  }
212 
214  static constexpr size_type capacity()
215  {
216  return n;
217  }
218 
220  static constexpr size_type max_size()
221  {
222  return n;
223  }
224 
227  friend std::ostream& operator<< (std::ostream& s, const ReservedDeque& v)
229  {
230  for (size_t i=0; i<v.size(); i++)
231  s << v[i] << " ";
232  return s;
233  }
234 
235  private:
236  T data_[n];
237  size_type first_;
238  size_type size_;
239  };
240 
241 } // end namespace Functions
242 } // end namespace Dune
243 
244 #undef CHECKSIZE
245 
246 #endif // DUNE_FUNCTIONS_COMMON_RESERVEDDEQUE_HH
Dune::Functions::ReservedDeque::size
size_type size() const
Returns number of elements in the vector.
Definition: reserveddeque.hh:202
Dune
Definition: polynomial.hh:7
Dune::Functions::ReservedDeque::pointer
T * pointer
Pointer to T.
Definition: reserveddeque.hh:53
Dune::Functions::ReservedDeque::push_front
void push_front(const T &t)
Prepends an element to the begin of a deque if size<capacity, O(1) time.
Definition: reserveddeque.hh:110
Dune::Functions::ReservedDeque::operator[]
reference operator[](size_type i)
Returns reference to the i'th element.
Definition: reserveddeque.hh:156
Dune::Functions::ReservedDeque::operator<<
friend std::ostream & operator<<(std::ostream &s, const ReservedDeque &v)
Send ReservedVector to an output stream.
Definition: reserveddeque.hh:228
Dune::Functions::ReservedDeque::resize
void resize(size_t s)
Specifies a new size for the vector.
Definition: reserveddeque.hh:96
Dune::Functions::ReservedDeque::iterator
Dune::GenericIterator< ReservedDeque, value_type > iterator
Iterator used to iterate through a vector.
Definition: reserveddeque.hh:63
Dune::Functions::ReservedDeque::value_type
T value_type
The type of object, T, stored in the vector.
Definition: reserveddeque.hh:51
Dune::Functions::ReservedDeque::const_reference
const typedef T & const_reference
Const reference to T.
Definition: reserveddeque.hh:57
Dune::Functions::ReservedDeque
A Vector class with statically reserved memory.
Definition: reserveddeque.hh:44
Dune::Functions::ReservedDeque::back
reference back()
Returns reference to last element of vector.
Definition: reserveddeque.hh:184
Dune::Functions::ReservedDeque::max_size
static constexpr size_type max_size()
Returns the maximum length of the vector.
Definition: reserveddeque.hh:220
Dune::Functions::ReservedDeque::capacity
static constexpr size_type capacity()
Returns current capacity (allocated memory) of the vector.
Definition: reserveddeque.hh:214
Dune::Functions::ReservedDeque::ReservedDeque
ReservedDeque()
Constructor.
Definition: reserveddeque.hh:72
Dune::Functions::ReservedDeque::clear
void clear()
Erases all elements.
Definition: reserveddeque.hh:89
Dune::Functions::ReservedDeque::begin
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition: reserveddeque.hh:136
Dune::Functions::ReservedDeque::difference_type
std::ptrdiff_t difference_type
A signed integral type.
Definition: reserveddeque.hh:61
Dune::Functions::ReservedDeque::push_back
void push_back(const T &t)
Appends an element to the end of a vector, up to the maximum size n, O(1) time.
Definition: reserveddeque.hh:103
Dune::Functions::ReservedDeque::end
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition: reserveddeque.hh:151
Dune::Functions::ReservedDeque::size_type
size_t size_type
An unsigned integral type.
Definition: reserveddeque.hh:59
Dune::Functions::ReservedDeque::reference
T & reference
Reference to T.
Definition: reserveddeque.hh:55
CHECKSIZE
#define CHECKSIZE(X)
Definition: reserveddeque.hh:20
Dune::Functions::ReservedDeque::end
iterator end()
Returns an iterator pointing to the end of the vector.
Definition: reserveddeque.hh:146
Dune::Functions::ReservedDeque::back
const_reference back() const
Returns const reference to last element of vector.
Definition: reserveddeque.hh:191
Dune::Functions::ReservedDeque::front
const_reference front() const
Returns const reference to first element of vector.
Definition: reserveddeque.hh:177
Dune::Functions::ReservedDeque::const_iterator
Dune::GenericIterator< const ReservedDeque, const value_type > const_iterator
Const iterator used to iterate through a vector.
Definition: reserveddeque.hh:65
Dune::Functions::ReservedDeque::front
reference front()
Returns reference to first element of vector.
Definition: reserveddeque.hh:170
Dune::Functions::ReservedDeque::pop_front
void pop_front()
Erases the first element of the vector, O(1) time.
Definition: reserveddeque.hh:126
Dune::Functions::ReservedDeque::empty
bool empty() const
Returns true if vector has no elements.
Definition: reserveddeque.hh:208
Dune::Functions::ReservedDeque::ReservedDeque
ReservedDeque(std::initializer_list< T > const &l)
Definition: reserveddeque.hh:77
Dune::Functions::ReservedDeque::pop_back
void pop_back()
Erases the last element of the vector, O(1) time.
Definition: reserveddeque.hh:119
Dune::Functions::ReservedDeque::begin
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition: reserveddeque.hh:141