KSS Utility
C++ general utilities
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends
circular_array.hpp
Go to the documentation of this file.
1 // \file circular_array.hpp
2 // \author Steven W. Klassen (klassens@acm.org)
3 // \date Sat Sep 20 2003
4 // \brief Circular array container.
5 //
6 // This file is Copyright (c) 2003 by Klassen Software Solutions. All rights reserved.
7 // Licensing follows the MIT License.
8 //
9 
10 #ifndef kssutil_circular_array_hpp
11 #define kssutil_circular_array_hpp
12 
13 #include <algorithm>
14 #include <cassert>
15 #include <initializer_list>
16 #include <iterator>
17 #include <memory>
18 #include <stdexcept>
19 #include <utility>
20 
21 #include <kss/util/algorithm.hpp>
22 #include <kss/util/iterator.hpp>
23 #include <kss/util/memory.hpp>
24 
30 namespace kss { namespace util { namespace containers {
31 
65  template <class T, class A = std::allocator<T>>
66  class CircularArray : public kss::util::AddRelOps<CircularArray<T, A>> {
67  public:
68  using value_type = T;
69  using allocator_type = A;
70  using size_type = typename A::size_type;
71  using difference_type = typename A::difference_type;
74  using reverse_iterator = std::reverse_iterator<iterator>;
75  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
76  using pointer = typename A::pointer;
77  using const_pointer = typename A::const_pointer;
78  using reference = typename A::reference;
79  using const_reference = typename A::const_reference;
80 
86  explicit CircularArray(size_type cap = size_type(10), const A& allocator = A())
87  : _allocator(allocator)
88  {
89  init(cap);
90 
91  // postconditions
92  assert(_array != nullptr);
93  assert(_capacity == cap);
94  assert(_size == 0);
95  assert(_first == 0);
96  assert(_last == _size);
97  }
98 
100  const value_type& val,
101  size_type cap = size_type(10),
102  const A& allocator = A())
103  : _allocator(allocator)
104  {
105  init(std::max(n, cap));
106  assign(n, val);
107 
108  // postconditions
109  assert(_array != nullptr);
110  assert(_capacity == std::max(n, cap));
111  assert(_size == n);
112  assert(_first == 0);
113  assert((_last == _size) || (_last == 0 && _size == _capacity));
114  }
115 
116  template <class InputIterator>
117  CircularArray(InputIterator first,
118  InputIterator last,
119  size_type cap = size_type(10),
120  const A& allocator = A())
121  : _allocator(allocator)
122  {
123  init(cap);
124  assign(first, last);
125 
126  // postconditions
127  assert(_array != nullptr);
128  assert(_capacity >= cap);
129  assert(_capacity >= _size);
130  assert(_first == 0);
131  assert((_last == _size) || (_last == 0 && _size == _capacity));
132  }
133 
135  size_type cap = size_type(10),
136  const A& allocator = A())
137  : _allocator(allocator)
138  {
139  init(std::max(ca.size(), cap));
140  assign(ca.begin(), ca.end());
141 
142  // postconditions
143  assert(_array != nullptr);
144  assert(_capacity == std::max(ca.size(), cap));
145  assert(_size == ca.size());
146  assert(_first == 0);
147  assert((_last == _size) || (_last == 0 && _size == _capacity));
148  assert(*this == ca);
149  }
150 
152  _array = ca._array;
153  _capacity = ca._capacity;
154  _first = ca._first;
155  _last = ca._last;
156  _size = ca._size;
157  _allocator = ca._allocator;
158 
159  ca._array = nullptr;
160  ca._capacity = ca._first = ca._last = ca._size = 0;
161 
162  // postconditions
163  assert(_array != nullptr);
164  assert(_capacity >= _size);
165  assert(_capacity > 0);
166  assert(ca._array == nullptr);
167  assert(ca._size == 0);
168  assert(ca._capacity == 0);
169  }
170 
171  CircularArray(std::initializer_list<value_type> il,
172  size_type cap = size_type(10),
173  const A& allocator = A())
174  : _allocator(allocator)
175  {
176  init(std::max(il.size(), cap));
177  assign(il);
178 
179  // postconditions
180  assert(_array != nullptr);
181  assert(_capacity == std::max(il.size(), cap));
182  assert(_size == il.size());
183  assert(_first == 0);
184  assert((_last == _size) || (_last == 0 && _size == _capacity));
185  }
186 
187  ~CircularArray() noexcept {
188  teardown();
189  }
190 
197  if (&ca != this) {
198  teardown();
199  init(ca.capacity());
200  for (const value_type& v : ca) {
201  push_back(v);
202  }
203  }
204 
205  // postconditions
206  assert(_array != nullptr);
207  assert(_capacity >= ca._capacity);
208  assert(*this == ca);
209  return *this;
210  }
211 
213  if (&ca != this) {
214  teardown();
215  _array = ca._array;
216  _capacity = ca._capacity;
217  _first = ca._first;
218  _last = ca._last;
219  _size = ca._size;
220  _allocator = ca._allocator;
221  ca.teardown();
222  }
223 
224  // postconditions
225  assert(_array != nullptr);
226  assert(_capacity >= _size);
227  assert(_capacity > 0);
228  assert(ca._array == nullptr);
229  assert(ca._capacity == 0);
230  assert(ca._size == 0);
231  return *this;
232  }
233 
234  template <class InputIterator>
235  void assign(InputIterator first, InputIterator last) {
236  clear();
237  for (InputIterator it = first; it != last; ++it) {
238  ensure_room_for_one_more();
239  push_back(*it);
240  }
241 
242  // postconditions
243  assert(_array != nullptr);
244  assert(_capacity > 0);
245  assert(_capacity >= _size);
246  }
247 
248  void assign(size_type n, const value_type& val) {
249  clear();
250  reserve(n);
251  for (size_type i = 0; i < n; ++i) {
252  push_back(val);
253  }
254 
255  // postconditions
256  assert(_array != nullptr);
257  assert(_capacity >= _size);
258  assert(_size == n);
259  }
260 
261  void assign(std::initializer_list<value_type> il) {
262  clear();
263  reserve(il.size());
264  assign(il.begin(), il.end());
265 
266  // postconditions
267  assert(_array != nullptr);
268  assert(_capacity >= _size);
269  assert(_size == il.size());
270  }
271 
275  iterator begin() { return iterator(*this); }
276  iterator end() { return iterator(*this, true); }
277  const_iterator begin() const { return const_iterator(*this); }
278  const_iterator end() const { return const_iterator(*this, true); }
279  const_iterator cbegin() const { return const_iterator(*this); }
280  const_iterator cend() const { return const_iterator(*this, true); }
281  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
282  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
283  const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
284  const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
287 
295  size_type size() const noexcept { return _size; }
296  size_type max_size() const noexcept { return _allocator.max_size(); }
297  size_type capacity() const noexcept { return _capacity; }
298  bool empty() const noexcept { return (_size == 0); }
299 
300  void resize(size_type n, const value_type& val = value_type()) {
301  while (size() > n) {
302  pop_back();
303  }
304  if (size() < n) {
305  reserve(n);
306  do { push_back(val); } while (size() < n);
307  }
308 
309  // postconditions
310  assert(_array != nullptr);
311  assert(_size == n);
312  assert(_capacity >= n);
313  }
314 
315  void reserve(size_type cap) {
316  if (cap <= _capacity) {
317  return;
318  }
319 
320  CircularArray ca(*this, cap, _allocator);
321  swap(ca);
322 
323  // postconditions
324  assert(_array != nullptr);
325  assert(_capacity >= cap);
326  assert(_capacity >= _size);
327  }
328 
329  void shrink_to_fit() {
330  if (capacity() > size()) {
331  CircularArray tmp(*this, size(), _allocator);
332  swap(tmp);
333  }
334 
335  // postconditions
336  assert(_capacity == _size);
337  }
338 
345  // preconditions
346  assert(_array != nullptr);
347  assert(_size > n);
348 
349  size_type pos = _first + n;
350  if (pos >= _capacity) {
351  pos -= _capacity;
352  }
353 
354  // postconditions
355  assert((pos >= _first && pos < _capacity)
356  || (pos < _last && _first > _last)
357  || (pos >= _first && pos < _last));
358  return _array[pos];
359  }
360 
362  // preconditions
363  assert(_array != nullptr);
364  assert(_size > n);
365 
366  size_type pos = _first + n;
367  if (pos >= _capacity) {
368  pos -= _capacity;
369  }
370 
371  // postconditions
372  assert((pos >= _first && pos < _capacity)
373  || (pos < _last && _first > _last)
374  || (pos >= _first && pos < _last));
375  return _array[pos];
376  }
377 
379  // preconditions
380  assert(_array != nullptr);
381 
382  if (n >= _size) {
383  throw std::out_of_range("n is out of range of this circular_array");
384  }
385  size_type pos = _first + n;
386  if (pos >= _capacity) {
387  pos -= _capacity;
388  }
389 
390  // postconditions
391  assert((pos >= _first && pos < _capacity)
392  || (pos < _last && _first > _last)
393  || (pos >= _first && pos < _last));
394  return _array[pos];
395  }
396 
398  // preconditions
399  assert(_array != nullptr);
400 
401  if (n >= _size) {
402  throw std::out_of_range("n is out of range of this circular_array");
403  }
404  size_type pos = _first + n;
405  if (pos >= _capacity) {
406  pos -= _capacity;
407  }
408 
409  // postconditions
410  assert((pos >= _first && pos < _capacity)
411  || (pos < _last && _first > _last)
412  || (pos >= _first && pos < _last));
413  return _array[pos];
414  }
415 
416  reference front() noexcept {
417  // precondijtions
418  assert(_array != nullptr);
419  assert(_size > 0);
420 
421  return _array[_first];
422  }
423 
424  const_reference front() const noexcept {
425  // precondijtions
426  assert(_array != nullptr);
427  assert(_size > 0);
428 
429  return _array[_first];
430  }
431 
432  reference back() noexcept {
433  // preconditions
434  assert(_array != nullptr);
435  assert(_size > 0);
436 
437  if (_last == 0) {
438  return _array[_capacity-1];
439  }
440  else {
441  return _array[_last - 1];
442  }
443  }
444 
445  const_reference back() const noexcept {
446  // preconditions
447  assert(_array != nullptr);
448  assert(_size > 0);
449 
450  if (_last == 0) {
451  return _array[_capacity-1];
452  }
453  else {
454  return _array[_last - 1];
455  }
456  }
457 
462  void push_back(const value_type& val) {
463  value_type v(val);
464  push_back(std::move(v));
465 
466  // postconditions
467  assert(back() == val);
468  }
469 
470  void push_back(value_type&& val) {
471  check_room_for_one_more();
472  _allocator.construct(_array+_last, val);
473  ++_last;
474  ++_size;
475  if (_last >= _capacity) {
476  _last = 0;
477  }
478 
479  // postconditions
480  assert(_array != nullptr);
481  assert(_size > 0);
482  assert(_capacity >= _size);
483  }
484 
485  void pop_back() noexcept {
486  // preconditions
487  assert(_array != nullptr);
488  assert(_size > 0);
489 
490  _last = (_last == 0 ? _capacity - 1 : _last - 1);
491  --_size;
492  _allocator.destroy(_array+_last);
493 
494  // postconditions
495  assert(_array != nullptr);
496  assert(_capacity > 0);
497  }
498 
499  void push_front(const value_type& val) {
500  value_type v(val);
501  push_front(std::move(v));
502 
503  // postconditions
504  assert(front() == val);
505  }
506 
507  void push_front(value_type&& val) {
508  check_room_for_one_more();
509  _first = (_first == 0 ? _capacity - 1 : _first - 1);
510  ++_size;
511  _allocator.construct(_array+_first, val);
512 
513  // postconditions
514  assert(_array != nullptr);
515  assert(_size > 0);
516  assert(_capacity >= _size);
517  }
518 
519  void pop_front() noexcept {
520  // preconditions
521  assert(_array != nullptr);
522  assert(_size > 0);
523 
524  _allocator.destroy(_array+_first);
525  ++_first;
526  --_size;
527  if (_first >= _capacity) {
528  _first = 0;
529  }
530 
531  // postconditions
532  assert(_array != nullptr);
533  assert(_capacity > 0);
534  }
535 
536  void swap(CircularArray& ca) noexcept {
537  if (&ca != this) {
538  std::swap(_array, ca._array);
539  std::swap(_capacity, ca._capacity);
540  std::swap(_first, ca._first);
541  std::swap(_last, ca._last);
542  std::swap(_size, ca._size);
543  std::swap(_allocator, ca._allocator);
544  }
545  }
546 
547  void clear() noexcept {
549  if (_first < _last) {
550  destroy(_array+_first, _array+_last, _allocator);
551  }
552  else if (_last < _first) {
553  destroy(_array+_first, _array+_capacity, _allocator);
554  destroy(_array, _array+_last, _allocator);
555  }
556  _first = _last = _size = 0;
557 
558  // postconditions
559  assert(_size == 0);
560  assert(_first == 0);
561  assert(_last == 0);
562  }
563 
567  allocator_type get_allocator() const noexcept { return _allocator; }
568 
573  bool operator==(const CircularArray& rhs) const noexcept {
574  if (&rhs == this) {
575  return true;
576  }
577  if (_size != rhs._size) {
578  return false;
579  }
580  return !kss::util::notEqual(begin(), end(), rhs.begin());
581  }
582 
583  bool operator<(const CircularArray& rhs) const noexcept {
584  if (&rhs == this) {
585  return false;
586  }
587  return std::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end());
588  }
589 
590  private:
591  void init(size_type cap) {
592  _array = _allocator.allocate(cap);
593  _capacity = cap;
594  _first = _last = _size = 0;
595  }
596 
597  void teardown() {
598  if (_array) {
600  if (_first < _last) {
601  destroy(_array+_first, _array+_last, _allocator);
602  }
603  else if (_last < _first) {
604  destroy(_array+_first, _array+_capacity, _allocator);
605  destroy(_array, _array+_last, _allocator);
606  }
607  _allocator.deallocate(_array, _capacity);
608  _array = nullptr;
609  }
610  }
611 
612  void ensure_room_for_one_more() {
613  if (size() == capacity()) {
614  size_type growth = std::max(size_type(10), capacity() / 4);
615  reserve(capacity() + growth);
616  }
617  assert(size() < capacity());
618  }
619 
620  void check_room_for_one_more() {
621  if (size() == capacity()) {
622  throw std::length_error("This circular_array is full.");
623  }
624  assert(size() < capacity());
625  }
626 
627  pointer _array;
628  size_type _capacity;
629  size_type _first;
630  size_type _last; // one past last element
631  size_type _size;
632  allocator_type _allocator;
633  };
634 
638  template <class T, class A>
640  x.swap(y);
641  }
642 }}}
643 
644 
645 #endif
kss::util::iterators::ConstRandomAccessIterator< CircularArray > const_iterator
void assign(std::initializer_list< value_type > il)
CircularArray(size_type n, const value_type &val, size_type cap=size_type(10), const A &allocator=A())
reference operator[](size_type n) noexcept
void swap(kss::util::iterators::ForwardIterator< Container, T > &a, kss::util::iterators::ForwardIterator< Container, T > &b)
Definition: iterator.hpp:530
Almost contiguous array referenced in a circular manner.
const_reference back() const noexcept
const_reverse_iterator rbegin() const noexcept
allocator_type get_allocator() const noexcept
void resize(size_type n, const value_type &val=value_type())
const_reverse_iterator crbegin() const noexcept
const_reference front() const noexcept
CircularArray(const CircularArray &ca, size_type cap=size_type(10), const A &allocator=A())
void swap(CircularArray< T, A > &x, CircularArray< T, A > &y)
void destroy(Iterator start, Iterator finish, Allocator &allocator)
Definition: memory.hpp:38
typename A::const_pointer const_pointer
typename A::const_reference const_reference
const_reference at(size_type n) const
size_type size() const noexcept
Base implementation of a const version of a random access iterator.
Definition: iterator.hpp:305
bool notEqual(InputIterator first, InputIterator last, InputIterator2 first2, BinaryPredicate bp)
Definition: algorithm.hpp:53
CircularArray & operator=(CircularArray &&ca)
void push_front(const value_type &val)
bool operator==(const CircularArray &rhs) const noexcept
const_reverse_iterator rend() const noexcept
void assign(size_type n, const value_type &val)
CircularArray(InputIterator first, InputIterator last, size_type cap=size_type(10), const A &allocator=A())
CircularArray & operator=(const CircularArray &ca)
std::reverse_iterator< iterator > reverse_iterator
size_type max_size() const noexcept
Base implementation of a random access iterator.
Definition: iterator.hpp:201
void swap(CircularArray &ca) noexcept
typename A::difference_type difference_type
CircularArray(std::initializer_list< value_type > il, size_type cap=size_type(10), const A &allocator=A())
void push_back(const value_type &val)
void assign(InputIterator first, InputIterator last)
std::reverse_iterator< const_iterator > const_reverse_iterator
const_reverse_iterator crend() const noexcept
kss::util::iterators::RandomAccessIterator< CircularArray > iterator
reverse_iterator rend() noexcept
size_type capacity() const noexcept
bool operator<(const CircularArray &rhs) const noexcept
CircularArray(size_type cap=size_type(10), const A &allocator=A())
const_reference operator[](size_type n) const noexcept
Add the operators !=, &lt;=, &gt; and &gt;= assuming the existance of == and &lt;.
Definition: add_rel_ops.hpp:31
reverse_iterator rbegin() noexcept