Dune Core Modules (2.8.0)

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
16
17#ifdef CHECK_RESERVEDDEQUE
18#define CHECKSIZE(X) assert(X)
19#else
20#define CHECKSIZE(X) {}
21#endif
22
23namespace Dune {
24namespace Functions {
25
43 template<class T, int n>
45 {
46 public:
47
51 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;
66
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
89 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
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
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
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
228 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
A double-ended queue (deque) class with statically reserved memory.
Definition: reserveddeque.hh:45
void pop_front()
Erases the first element of the vector, O(1) time.
Definition: reserveddeque.hh:126
static constexpr size_type capacity()
Returns current capacity (allocated memory) of the vector.
Definition: reserveddeque.hh:214
void clear()
Erases all elements.
Definition: reserveddeque.hh:89
Dune::GenericIterator< ReservedDeque, value_type > iterator
Iterator used to iterate through a vector.
Definition: reserveddeque.hh:63
T value_type
The type of object, T, stored in the vector.
Definition: reserveddeque.hh:51
ReservedDeque()
Constructor.
Definition: reserveddeque.hh:72
bool empty() const
Returns true if vector has no elements.
Definition: reserveddeque.hh:208
const_reference back() const
Returns const reference to last element of vector.
Definition: reserveddeque.hh:191
friend std::ostream & operator<<(std::ostream &s, const ReservedDeque &v)
Send ReservedDeque to an output stream.
Definition: reserveddeque.hh:228
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
reference operator[](size_type i)
Returns reference to the i'th element.
Definition: reserveddeque.hh:156
reference front()
Returns reference to first element of vector.
Definition: reserveddeque.hh:170
T * pointer
Pointer to T.
Definition: reserveddeque.hh:53
const_reference front() const
Returns const reference to first element of vector.
Definition: reserveddeque.hh:177
iterator end()
Returns an iterator pointing to the end of the vector.
Definition: reserveddeque.hh:146
reference back()
Returns reference to last element of vector.
Definition: reserveddeque.hh:184
void pop_back()
Erases the last element of the vector, O(1) time.
Definition: reserveddeque.hh:119
const T & const_reference
Const reference to T.
Definition: reserveddeque.hh:57
static constexpr size_type max_size()
Returns the maximum length of the vector.
Definition: reserveddeque.hh:220
std::ptrdiff_t difference_type
A signed integral type.
Definition: reserveddeque.hh:61
T & reference
Reference to T.
Definition: reserveddeque.hh:55
Dune::GenericIterator< const ReservedDeque, const value_type > const_iterator
Const iterator used to iterate through a vector.
Definition: reserveddeque.hh:65
size_type size() const
Returns number of elements in the vector.
Definition: reserveddeque.hh:202
const_iterator end() const
Returns a const_iterator pointing to the end of the vector.
Definition: reserveddeque.hh:151
void resize(size_t s)
Specifies a new size for the vector.
Definition: reserveddeque.hh:96
iterator begin()
Returns a iterator pointing to the beginning of the vector.
Definition: reserveddeque.hh:136
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the vector.
Definition: reserveddeque.hh:141
size_t size_type
An unsigned integral type.
Definition: reserveddeque.hh:59
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
Generic class for stl-conforming iterators for container classes with operator[].
Definition: genericiterator.hh:151
Implements a generic iterator class for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:11
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 21, 23:30, 2024)