dune-functions  2.9.0
overflowarray.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_OVERFLOWARRAY_HH
4 #define DUNE_FUNCTIONS_COMMON_OVERFLOWARRAY_HH
5 
6 #include <algorithm>
7 #include <iostream>
8 #include <cstddef>
9 #include <array>
10 #include <initializer_list>
11 
12 #include <dune/common/genericiterator.hh>
13 
14 
15 
16 namespace Dune::Functions {
17 
18 
42 template<class BA, std::size_t maxSize = std::tuple_size_v<BA>>
44  public BA
45 {
46  static constexpr std::size_t baseSize = std::tuple_size_v<BA>;
47 
48 public:
49  using BaseArray = BA;
50 
51  using value_type = typename BaseArray::value_type;
53  using const_reference = const value_type&;
54  using pointer = value_type*;
55  using difference_type = std::ptrdiff_t;
56  using size_type = std::size_t;
57  using iterator = Dune::GenericIterator<OverflowArray, value_type>;
58  using const_iterator = Dune::GenericIterator<const OverflowArray, const value_type>;
59 
60 private:
61  using OverflowBuffer = std::array<value_type, maxSize-baseSize>;
62 
63 public:
64 
65  OverflowArray() = default;
66 
67  OverflowArray(const std::initializer_list<value_type>& l) {
68  assert(l.size() <= capacity());
69  size_ = l.size();
70  std::copy_n(l.begin(), size_, begin());
71  }
72 
73  bool operator == (const OverflowArray& other) const {
74  if (size() != other.size())
75  return false;
76  for (size_type i=0; i<size(); ++i)
77  if ((*this)[i] != other[i])
78  return false;
79  return true;
80  }
81 
83  void clear() {
84  size_ = 0;
85  }
86 
93  void resize(size_type n) {
94  assert(n <= capacity());
95  size_ = n;
96  }
97 
104  void push_back(const value_type& t) {
105  assert(size() < capacity());
106  (*this)[size_++] = t;
107  }
108 
110  void pop_back() {
111  assert(size() > 0);
112  if (! empty())
113  size_--;
114  }
115 
122  void push_front(const value_type& t) {
123  assert(size() < capacity());
124  for (size_type i=0; i<size(); i++)
125  (*this)[i+1] = (*this)[i];
126  (*this)[0] = t;
127  }
128 
131  return iterator(*this, 0);
132  }
133 
136  return const_iterator(*this, 0);
137  }
138 
141  return iterator(*this, size());
142  }
143 
145  const_iterator end() const {
146  return const_iterator(*this, size());
147  }
148 
151  assert(i < size());
152  // If there's no padding between the base class and the overflow_ member,
153  // the compiler should be able to optimize this to
154  // return *(&BaseArray::operator[](0) + i);
155  if (i<baseSize)
156  return BaseArray::operator[](i);
157  return overflow_[i-baseSize];
158  }
159 
162  assert(i < size());
163  // If there's no padding between the base class and the overflow_ member,
164  // the compiler should be able to optimize this to
165  // return *(&BaseArray::operator[](0) + i);
166  if (i<baseSize)
167  return BaseArray::operator[](i);
168  return overflow_[i-baseSize];
169  }
170 
173  assert(size() > 0);
174  return (*this)[0];
175  }
176 
179  assert(size() > 0);
180  return (*this)[0];
181  }
182 
185  assert(size() > 0);
186  return (*this)[size()-1];
187  }
188 
191  assert(size() > 0);
192  return (*this)[size()-1];
193  }
194 
196  size_type size () const {
197  return size_;
198  }
199 
201  bool empty() const {
202  return size() == 0;
203  }
204 
206  static constexpr size_type capacity() {
207  return maxSize;
208  }
209 
211  static constexpr size_type max_size() {
212  return maxSize;
213  }
214 
216  inline friend std::size_t hash_value(const OverflowArray& v) noexcept {
217  return hash_range(v.begin(), v.end());
218  }
219 
221  friend std::ostream& operator<< (std::ostream& s, const OverflowArray& c) {
222  for (const auto& ci : c)
223  s << ci << " ";
224  return s;
225  }
226 
227 private:
228  OverflowBuffer overflow_;
229  size_type size_ = 0;
230 };
231 
232 
233 
234 } // namespace Dune::Functions
235 
236 
237 
238 #endif // DUNE_FUNCTIONS_COMMON_OVERFLOWARRAY_HH
Definition: polynomial.hh:11
A dynamically sized array-like class with overflow.
Definition: overflowarray.hh:45
const value_type & const_reference
Definition: overflowarray.hh:53
value_type & reference
Definition: overflowarray.hh:52
const_iterator end() const
Returns a const_iterator pointing to the end of the OverflowArray.
Definition: overflowarray.hh:145
bool operator==(const OverflowArray &other) const
Definition: overflowarray.hh:73
friend std::ostream & operator<<(std::ostream &s, const OverflowArray &c)
Write container to an output stream.
Definition: overflowarray.hh:221
friend std::size_t hash_value(const OverflowArray &v) noexcept
Compute hash value.
Definition: overflowarray.hh:216
void push_back(const value_type &t)
Appends an element to the end of the OverflowArray,.
Definition: overflowarray.hh:104
iterator begin()
Returns a iterator pointing to the beginning of the OverflowArray.
Definition: overflowarray.hh:130
bool empty() const
Returns true if OverflowArray has no elements.
Definition: overflowarray.hh:201
size_type size() const
Returns number of elements in the OverflowArray.
Definition: overflowarray.hh:196
typename BaseArray::value_type value_type
Definition: overflowarray.hh:51
void pop_back()
Erases the last element of the OverflowArray, O(1) time.
Definition: overflowarray.hh:110
Dune::GenericIterator< OverflowArray, value_type > iterator
Definition: overflowarray.hh:57
const_iterator begin() const
Returns a const_iterator pointing to the beginning of the OverflowArray.
Definition: overflowarray.hh:135
std::ptrdiff_t difference_type
Definition: overflowarray.hh:55
BA BaseArray
Definition: overflowarray.hh:49
static constexpr size_type capacity()
Returns the capacity of the OverflowArray.
Definition: overflowarray.hh:206
static constexpr size_type max_size()
Returns the maximum length of the OverflowArray.
Definition: overflowarray.hh:211
const_reference front() const
Returns const reference to first element of OverflowArray.
Definition: overflowarray.hh:178
void clear()
Erases all elements.
Definition: overflowarray.hh:83
iterator end()
Returns an iterator pointing to the end of the OverflowArray.
Definition: overflowarray.hh:140
std::size_t size_type
Definition: overflowarray.hh:56
void resize(size_type n)
Specifies a new size for the OverflowArray.
Definition: overflowarray.hh:93
value_type * pointer
Definition: overflowarray.hh:54
Dune::GenericIterator< const OverflowArray, const value_type > const_iterator
Definition: overflowarray.hh:58
const_reference back() const
Returns const reference to last element of OverflowArray.
Definition: overflowarray.hh:190
OverflowArray(const std::initializer_list< value_type > &l)
Definition: overflowarray.hh:67
reference back()
Returns reference to last element of OverflowArray.
Definition: overflowarray.hh:184
void push_front(const value_type &t)
Inserts an element to the begin of the OverflowArray,.
Definition: overflowarray.hh:122
reference front()
Returns reference to first element of OverflowArray.
Definition: overflowarray.hh:172
reference operator[](size_type i)
Returns reference to the i'th element.
Definition: overflowarray.hh:150