Thea
BoundedSortedArray.hpp
1 //============================================================================
2 //
3 // This file is part of the Thea toolkit.
4 //
5 // This software is distributed under the BSD license, as detailed in the
6 // accompanying LICENSE.txt file. Portions are derived from other works:
7 // their respective licenses and copyright information are reproduced in
8 // LICENSE.txt and/or in the relevant source files.
9 //
10 // Author: Siddhartha Chaudhuri
11 // First version: 2010
12 //
13 //============================================================================
14 
15 #ifndef __Thea_BoundedSortedArray_hpp__
16 #define __Thea_BoundedSortedArray_hpp__
17 
18 #include "Common.hpp"
19 #include "Algorithms/FastCopy.hpp"
20 #include <functional>
21 #include <iterator>
22 
23 namespace Thea {
24 
37 template < typename T, typename Compare = std::less<T> >
39 {
40  private:
41  Compare compare;
42  size_t capacity, num_elems;
43  T * values;
44 
45  public:
46  typedef T const * const_iterator;
47  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
48 
55  BoundedSortedArray(size_t capacity_ = 0, Compare compare_ = Compare())
56  : compare(compare_), capacity(capacity_), num_elems(0), values(nullptr)
57  {
58  alwaysAssertM(capacity >= 0, "BoundedSortedArray: Capacity must be non-negative");
59 
60  if (capacity > 0)
61  values = new T[capacity];
62  }
63 
66  : compare(src.compare), capacity(src.capacity), num_elems(src.num_elems),
67  values(src.capacity > 0 ? new T[src.capacity] : nullptr)
68  {
69  if (src.num_elems > 0)
70  Algorithms::fastCopy(src.values, src.values + src.num_elems, values);
71  }
72 
75  {
76  compare = src.compare;
77  num_elems = src.num_elems;
78 
79  if (capacity != src.capacity)
80  {
81  delete [] values;
82  values = (src.capacity > 0 ? new T[src.capacity] : nullptr);
83  capacity = src.capacity;
84  }
85 
86  if (src.num_elems > 0)
87  Algorithms::fastCopy(src.values, src.values + src.num_elems, values);
88 
89  return *this;
90  }
91 
93  ~BoundedSortedArray() { delete [] values; }
94 
96  void setCapacity(size_t capacity_)
97  {
98  if (capacity != capacity_)
99  {
100  delete [] values;
101  values = (capacity_ > 0 ? new T[capacity_] : nullptr);
102  capacity = capacity_;
103  }
104 
105  num_elems = 0;
106  }
107 
109  size_t getCapacity() const { return capacity; }
110 
112  size_t size() const { return num_elems; }
113 
115  bool empty() const { return num_elems <= 0; }
116 
118  T const * data() const { return values; }
119 
120  const_iterator begin() const noexcept { return values; }
121  const_iterator cbegin() const noexcept { return values; }
122  const_iterator end() const noexcept { return values + num_elems; }
123  const_iterator cend() const noexcept { return values + num_elems; }
126  const_reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); }
129  const_reverse_iterator crbegin() const noexcept { return reverse_iterator(end()); }
132  const_reverse_iterator rend() const noexcept { return reverse_iterator(begin()); }
133 
135  const_reverse_iterator crend() const noexcept { return reverse_iterator(begin()); }
138  T const & first() const
139  {
140  debugAssertM(num_elems > 0, "BoundedSortedArray: Can't get first element of empty array");
141  return values[0];
142  }
145  T const & last() const
146  {
147  debugAssertM(num_elems > 0, "BoundedSortedArray: Can't get last element of empty array");
148  return values[num_elems - 1];
149  }
152  T const & operator[](size_t i) const
153  {
154  debugAssertM(i < num_elems, format("BoundedSortedArray: Index %ld out of bounds [0, %ld)", (long)i, (long)num_elems));
155  return values[i];
156  }
159  bool contains(T const & t) const { return find(t) < capacity; }
160 
165  template <typename EqualityComparatorT> bool contains(T const & t, EqualityComparatorT const & comp) const
166  {
167  for (size_t i = 0; i < num_elems; ++i)
168  if (comp(values[i], t))
169  return true;
170 
171  return false;
172  }
173 
178  size_t find(T const & t) const
179  {
180  size_t lb = lowerBound(t);
181  return (lb < num_elems && !compare(t, values[lb])) ? lb : capacity;
182  }
183 
188  size_t upperBound(T const & t) const
189  {
190  size_t first = 0, mid, step;
191  size_t count = num_elems;
192  while (count > 0)
193  {
194  step = count >> 1;
195  mid = first + step;
196  if (!compare(t, values[mid]))
197  {
198  first = mid + 1;
199  count -= (step + 1);
200  }
201  else
202  count = step;
203  }
204 
205  return first;
206  }
207 
212  size_t lowerBound(T const & t) const
213  {
214  size_t first = 0, mid, step;
215  size_t count = num_elems;
216  while (count > 0)
217  {
218  step = count >> 1;
219  mid = first + step;
220  if (compare(values[mid], t))
221  {
222  first = mid + 1;
223  count -= (step + 1);
224  }
225  else
226  count = step;
227  }
228 
229  return first;
230  }
231 
236  bool isInsertable(T const & t) const
237  {
238  return capacity > 0 && (num_elems < capacity || compare(t, last()));
239  }
240 
246  size_t insert(T const & t)
247  {
248  if (capacity <= 0)
249  return capacity;
250 
251  if (num_elems <= 0)
252  {
253  values[0] = t;
254  ++num_elems;
255  return 0;
256  }
257  else if (isInsertable(t))
258  {
259  size_t ub = upperBound(t);
260  T * end = values + (num_elems < capacity ? num_elems : capacity - 1);
261  Algorithms::fastCopyBackward(values + ub, end, end + 1);
262  values[ub] = t;
263  if (num_elems < capacity) ++num_elems;
264  return ub;
265  }
266 
267  return capacity;
268  }
269 
277  size_t insertUnique(T const & t)
278  {
279  if (contains(t))
280  return capacity;
281 
282  return insert(t);
283  }
286  void erase(size_t i)
287  {
288  if (i < num_elems)
289  {
290  Algorithms::fastCopy(values + i + 1, values + num_elems, values + i);
291  --num_elems;
292  }
293  }
296  void erase(T const & t)
297  {
298  erase(find(t));
299  }
302  void clear()
303  {
304  num_elems = 0;
305  }
306 
307 }; // class BoundedSortedArray
308 
309 } // namespace Thea
310 
311 #endif
T const & first() const
Get the first element in the sorted sequence.
T const * const_iterator
Iterator over immutable elements.
const_iterator begin() const noexcept
Iterator to the beginning of the array.
size_t find(T const &t) const
Get the index of a given value in the array.
const_iterator cbegin() const noexcept
Iterator to the beginning of the array.
bool empty() const
Check if the array is empty or not.
T const * data() const
Get a pointer to the data buffer.
void clear()
Remove all elements from the array.
const_reverse_iterator crbegin() const noexcept
Reverse iterator to the beginning of the array.
Root namespace for the Thea library.
size_t lowerBound(T const &t) const
Get the index of the first element equal to or greater than t, or return the capacity of the array if...
const_reverse_iterator rend() const noexcept
Reverse iterator to the beginning of the array.
I2 fastCopyBackward(I1 first, I1 last, I2 out)
A version of std::copy_backward that calls memmove where appropriate (if the class has a trivial assi...
Definition: FastCopy.hpp:95
bool contains(T const &t) const
Check if the array contains an element with a given value.
std::string format(char const *fmt,...)
Produces a string from arguments in the style of printf.
Definition: StringAlg.cpp:305
T const & last() const
Get the last element in the sorted sequence.
const_iterator cend() const noexcept
Iterator to the end of the array.
std::reverse_iterator< const_iterator > const_reverse_iterator
Reverse iterator over immutable elements.
const_iterator end() const noexcept
Iterator to the end of the array.
BoundedSortedArray & operator=(BoundedSortedArray const &src)
Assignment operator.
BoundedSortedArray(BoundedSortedArray const &src)
Copy constructor.
A sorted array of bounded maximum size, ordered in ascending order according to a comparator...
const_reverse_iterator rbegin() const noexcept
Reverse iterator to the end of the array.
size_t insert(T const &t)
Insert a value into the array.
BoundedSortedArray(size_t capacity_=0, Compare compare_=Compare())
Constructor.
void erase(size_t i)
Remove the element at the given position from the array.
size_t insertUnique(T const &t)
Insert a value into the array only if it does not already exist.
size_t upperBound(T const &t) const
Get the index of the first element strictly greater than t, or return the capacity of the array if no...
size_t size() const
Get the number of elements in the array.
T const & operator[](size_t i) const
Get the element at a given position in the sorted sequence.
void alwaysAssertM(CondT const &test, MessageT const &msg)
Check if a test condition is true, and immediately abort the program with an error code if not...
Definition: Common.hpp:66
void setCapacity(size_t capacity_)
Set the maximum number of elements the array can hold.
I2 fastCopy(I1 first, I1 last, I2 out)
A version of std::copy that calls memcpy where appropriate (if the class has a trivial assignment ope...
Definition: FastCopy.hpp:76
size_t getCapacity() const
Get the maximum number of elements the array can hold.
bool isInsertable(T const &t) const
Check if a value can be inserted in the array.
void debugAssertM(CondT const &test, MessageT const &msg)
Check if a test condition is true, and immediately abort the program with an error code if not...
Definition: Common.hpp:52