WVector.h
Go to the documentation of this file.
1 /* $Id: WVector.h 1156 2011-06-07 04:01:16Z bhagman $
2 ||
3 || @author Hernando Barragan <b@wiring.org.co>
4 || @url http://wiring.org.co/
5 || @contribution Brett Hagman <bhagman@wiring.org.co>
6 || @contribution Alexander Brevig <abrevig@wiring.org.co>
7 ||
8 || @description
9 || | Vector data structure.
10 || |
11 || | Wiring Common API
12 || #
13 ||
14 || @license Please see cores/Common/License.txt.
15 ||
16 */
17 
18 #pragma once
19 
20 #include "Countable.h"
21 #include <cstdlib>
22 #include <cstring>
23 #include <algorithm>
24 #include <iterator>
25 #include "WiringList.h"
26 
31 template <typename Element> class Vector : public Countable<Element>
32 {
33 public:
34  using Comparer = int (*)(const Element& lhs, const Element& rhs);
35 
36  template <bool is_const> class Iterator
37  {
38  public:
39  using iterator_category = std::random_access_iterator_tag;
40  using value_type = Element;
41  using difference_type = std::ptrdiff_t;
42  using pointer = Element*;
43  using reference = Element&;
44 
45  using V = typename std::conditional<is_const, const Vector, Vector>::type;
46  using E = typename std::conditional<is_const, const Element, Element>::type;
47 
48  Iterator(const Iterator&) = default;
49  Iterator(Iterator&&) = default;
50  Iterator& operator=(const Iterator&) = default;
51  Iterator& operator=(Iterator&&) = default;
52 
53  Iterator(V& vector, unsigned index) : vector(vector), index(index)
54  {
55  }
56 
58  {
59  }
60 
62  {
63  ++index;
64  return *this;
65  }
66 
68  {
69  Iterator tmp(*this);
70  ++index;
71  return tmp;
72  }
73 
74  Iterator operator+=(size_t distance)
75  {
76  Iterator tmp(*this);
77  index += distance;
78  return tmp;
79  }
80 
81  bool operator==(const Iterator& rhs) const
82  {
83  return &vector == &rhs.vector && index == rhs.index;
84  }
85 
86  bool operator!=(const Iterator& rhs) const
87  {
88  return !operator==(rhs);
89  }
90 
91  template <typename U = Element> typename std::enable_if<!is_const, U&>::type operator*()
92  {
93  return vector[index];
94  }
95 
96  E& operator*() const
97  {
98  return vector[index];
99  }
100 
101  private:
102  V& vector;
103  unsigned index{0};
104  };
105 
106  Vector(unsigned int initialCapacity = 10, unsigned int capacityIncrement = 10) : _increment(capacityIncrement)
107  {
108  _data.allocate(initialCapacity);
109  }
110 
111  Vector(const Vector& rhv)
112  {
113  copyFrom(rhv);
114  }
115 
116  Vector(Vector&&) = delete;
117 
119  {
120  }
121 
122  // methods
123  unsigned int capacity() const
124  {
125  return _data.size;
126  }
127 
128  template <typename T> bool contains(const T& elem) const
129  {
130  return indexOf(elem) >= 0;
131  }
132 
133  const Element& firstElement() const
134  {
135  if(_size == 0) {
136  abort();
137  }
138 
139  return _data[0];
140  }
141 
142  template <typename T> int indexOf(const T& elem) const;
143 
144  bool isEmpty() const
145  {
146  return _size == 0;
147  }
148 
149  const Element& lastElement() const
150  {
151  if(_size == 0) {
152  abort();
153  }
154 
155  return _data[_size - 1];
156  }
157 
158  template <typename T> int lastIndexOf(const T& elem) const;
159 
160  unsigned int count() const override
161  {
162  return size();
163  }
164 
165  unsigned int size() const
166  {
167  return _size;
168  }
169 
170  void copyInto(Element* array) const;
171 
172  bool add(const Element& obj)
173  {
174  return addElement(obj);
175  }
176 
177  bool addElement(const Element& obj);
178  bool addElement(Element* objp);
179 
180  void clear()
181  {
183  }
184 
185  bool ensureCapacity(unsigned int minCapacity);
186 
188  {
189  _data.clear();
190  _size = 0;
191  }
192 
193  template <typename T> bool removeElement(const T& elem)
194  {
195  return removeElementAt(indexOf(elem));
196  }
197 
205  bool setSize(unsigned int newSize);
206 
210  void trimToSize()
211  {
212  if(_size < _data.size) {
213  _data.trim(_size, true);
214  }
215  }
216 
217  const Element& elementAt(unsigned int index) const
218  {
219  if(index >= _size) {
220  abort();
221  }
222  return _data[index];
223  }
224 
225  bool insertElementAt(const Element& obj, unsigned int index);
226 
227  bool remove(unsigned int index)
228  {
229  return removeElementAt(index);
230  }
231 
232  bool removeElementAt(unsigned int index);
233  bool setElementAt(const Element& obj, unsigned int index);
234 
235  const Element& get(unsigned int index) const
236  {
237  return elementAt(index);
238  }
239 
240  const Element& operator[](unsigned int index) const override
241  {
242  return elementAt(index);
243  }
244 
245  Element& operator[](unsigned int index) override
246  {
247  if(index >= _size) {
248  abort();
249  }
250  return _data[index];
251  }
252 
254  {
255  if(this != &rhv) {
256  copyFrom(rhv);
257  }
258  return *this;
259  }
260 
261  Vector<Element>& operator=(Vector<Element>&& other) noexcept // move assignment
262  {
263  clear();
264  _increment = 0;
265  std::swap(_data, other._data);
266  std::swap(_size, other._size);
267  std::swap(_increment, other._increment);
268  return *this;
269  }
270 
271  void sort(Comparer compareFunction);
272 
274  {
275  return Iterator<false>(*this, 0);
276  }
277 
279  {
280  return Iterator<false>(*this, count());
281  }
282 
283  const Iterator<true> begin() const
284  {
285  return Iterator<true>(*this, 0);
286  }
287 
288  const Iterator<true> end() const
289  {
290  return Iterator<true>(*this, count());
291  }
292 
293 protected:
294  void copyFrom(const Vector& rhv);
295 
296 protected:
298 
299  unsigned int _size{0};
300  unsigned int _increment{0};
302 };
303 
304 template <class Element> void Vector<Element>::copyFrom(const Vector<Element>& rhv)
305 {
306  _data.clear();
307  if(!_data.allocate(rhv._data.size)) {
308  _size = _increment = 0;
309  return;
310  }
311 
312  _size = rhv._size;
313  _increment = rhv._increment;
314 
315  for(unsigned int i = 0; i < _size; i++) {
316  _data[i] = rhv._data[i];
317  }
318 }
319 
320 template <class Element> void Vector<Element>::copyInto(Element* array) const
321 {
322  if(array == nullptr) {
323  return;
324  }
325 
326  for(unsigned int i = 0; i < _size; i++) {
327  array[i] = _data[i];
328  }
329 }
330 
331 template <class Element> template <typename T> int Vector<Element>::indexOf(const T& elem) const
332 {
333  for(unsigned int i = 0; i < _size; i++) {
334  if(_data[i] == elem) {
335  return int(i);
336  }
337  }
338 
339  return -1;
340 }
341 
342 template <class Element> template <typename T> int Vector<Element>::lastIndexOf(const T& elem) const
343 {
344  // check for empty vector
345  if(_size == 0) {
346  return -1;
347  }
348 
349  unsigned int i = _size;
350 
351  do {
352  i--;
353  if(_data[i] == elem) {
354  return int(i);
355  }
356  } while(i != 0);
357 
358  return -1;
359 }
360 
361 template <class Element> bool Vector<Element>::addElement(const Element& obj)
362 {
363  if(!ensureCapacity(_size + 1)) {
364  return false;
365  }
366  _data[_size++] = obj;
367  return true;
368 }
369 
370 template <class Element> bool Vector<Element>::addElement(Element* objp)
371 {
372  if(!ensureCapacity(_size + 1)) {
373  return false;
374  }
375  _data[_size++] = objp;
376  return true;
377 }
378 
379 template <class Element> bool Vector<Element>::ensureCapacity(unsigned int minCapacity)
380 {
381  if(_data.size >= minCapacity) {
382  return true;
383  }
384 
385  auto newCapacity = std::max(minCapacity, _data.size + _increment);
386  return _data.allocate(newCapacity);
387 }
388 
389 template <class Element> bool Vector<Element>::insertElementAt(const Element& obj, unsigned int index)
390 {
391  if(index == _size) {
392  return addElement(obj);
393  }
394 
395  if(index > _size) {
396  return false;
397  }
398  if(!ensureCapacity(_size + 1)) {
399  return false;
400  }
401 
402  if(!_data.insert(index, obj)) {
403  return false;
404  }
405 
406  _size++;
407  return true;
408 }
409 
410 template <class Element> bool Vector<Element>::removeElementAt(unsigned int index)
411 {
412  // check for valid index
413  if(index >= _size) {
414  return false;
415  }
416 
417  _data.remove(index);
418  _size--;
419  return true;
420 }
421 
422 template <class Element> bool Vector<Element>::setElementAt(const Element& obj, unsigned int index)
423 {
424  // check for valid index
425  if(index >= _size) {
426  return false;
427  }
428  _data[index] = obj;
429  return true;
430 }
431 
432 template <class Element> bool Vector<Element>::setSize(unsigned int newSize)
433 {
434  if(!ensureCapacity(newSize)) {
435  return false;
436  }
437 
438  _data.trim(newSize, false);
439  _size = std::min(_size, newSize);
440  return true;
441 }
442 
443 template <class Element> void Vector<Element>::sort(Comparer compareFunction)
444 {
445  // Start with 1 (not 0)
446  for(unsigned j = 1; j < _size; j++) {
447  auto key = _data.values[j];
448  Element& keyRef = _data[j];
449  // Smaller values move up
450  int i;
451  for(i = int(j) - 1; (i >= 0) && compareFunction(_data[i], keyRef) > 0; i--) {
452  _data.values[i + 1] = _data.values[i];
453  }
454  // Put key into its proper location
455  _data.values[i + 1] = key;
456  }
457 }
void size_t const void * key
Definition: blake2s.h:33
Definition: Countable.h:20
Definition: WVector.h:37
Iterator(V &vector, unsigned index)
Definition: WVector.h:53
typename std::conditional< is_const, const Element, Element >::type E
Definition: WVector.h:46
Element value_type
Definition: WVector.h:40
Element * pointer
Definition: WVector.h:42
typename std::conditional< is_const, const Vector, Vector >::type V
Definition: WVector.h:45
Iterator operator++(int)
Definition: WVector.h:67
std::random_access_iterator_tag iterator_category
Definition: WVector.h:39
Iterator & operator=(const Iterator &)=default
~Iterator()
Definition: WVector.h:57
Iterator & operator=(Iterator &&)=default
Iterator & operator++()
Definition: WVector.h:61
E & operator*() const
Definition: WVector.h:96
bool operator!=(const Iterator &rhs) const
Definition: WVector.h:86
Iterator operator+=(size_t distance)
Definition: WVector.h:74
std::enable_if<!is_const, U & >::type operator*()
Definition: WVector.h:91
std::ptrdiff_t difference_type
Definition: WVector.h:41
Iterator(const Iterator &)=default
Element & reference
Definition: WVector.h:43
bool operator==(const Iterator &rhs) const
Definition: WVector.h:81
Iterator(Iterator &&)=default
Vector class template.
Definition: WVector.h:32
bool setElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:422
~Vector()
Definition: WVector.h:118
bool addElement(const Element &obj)
Definition: WVector.h:361
bool setSize(unsigned int newSize)
Reduce or increase number of items.
Definition: WVector.h:432
const Iterator< true > begin() const
Definition: WVector.h:283
bool contains(const T &elem) const
Definition: WVector.h:128
bool removeElementAt(unsigned int index)
Definition: WVector.h:410
Vector(Vector &&)=delete
unsigned int count() const override
Definition: WVector.h:160
bool add(const Element &obj)
Definition: WVector.h:172
Vector< Element > & operator=(Vector< Element > &&other) noexcept
Definition: WVector.h:261
void clear()
Definition: WVector.h:180
Iterator< false > end()
Definition: WVector.h:278
int(*)(const Element &lhs, const Element &rhs) Comparer
Definition: WVector.h:34
void copyFrom(const Vector &rhv)
Definition: WVector.h:304
bool remove(unsigned int index)
Definition: WVector.h:227
unsigned int capacity() const
Definition: WVector.h:123
bool isEmpty() const
Definition: WVector.h:144
void removeAllElements()
Definition: WVector.h:187
const Element & get(unsigned int index) const
Definition: WVector.h:235
Iterator< false > begin()
Definition: WVector.h:273
void trimToSize()
Reduce capacity to match current size.
Definition: WVector.h:210
void sort(Comparer compareFunction)
Definition: WVector.h:443
Element & operator[](unsigned int index) override
Definition: WVector.h:245
unsigned int size() const
Definition: WVector.h:165
Vector(const Vector &rhv)
Definition: WVector.h:111
int lastIndexOf(const T &elem) const
Definition: WVector.h:342
ElementList _data
Definition: WVector.h:301
unsigned int _size
Definition: WVector.h:299
Vector< Element > & operator=(const Vector< Element > &rhv)
Definition: WVector.h:253
wiring_private::List< Element > ElementList
Definition: WVector.h:297
bool removeElement(const T &elem)
Definition: WVector.h:193
bool ensureCapacity(unsigned int minCapacity)
Definition: WVector.h:379
int indexOf(const T &elem) const
Definition: WVector.h:331
bool insertElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:389
const Element & lastElement() const
Definition: WVector.h:149
const Element & elementAt(unsigned int index) const
Definition: WVector.h:217
const Element & firstElement() const
Definition: WVector.h:133
void copyInto(Element *array) const
Definition: WVector.h:320
const Element & operator[](unsigned int index) const override
Definition: WVector.h:240
Vector(unsigned int initialCapacity=10, unsigned int capacityIncrement=10)
Definition: WVector.h:106
unsigned int _increment
Definition: WVector.h:300
const Iterator< true > end() const
Definition: WVector.h:288
bool addElement(Element *objp)
Definition: WVector.h:370
typename std::conditional< std::is_scalar< T >::value, ScalarList< T >, ObjectList< T > >::type List
Definition: WiringList.h:197