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 
50  Iterator(V& vector, unsigned index) : vector(vector), index(index)
51  {
52  }
53 
55  {
56  ++index;
57  return *this;
58  }
59 
61  {
62  Iterator tmp(*this);
63  ++index;
64  return tmp;
65  }
66 
67  Iterator operator+=(size_t distance)
68  {
69  Iterator tmp(*this);
70  index += distance;
71  return tmp;
72  }
73 
74  bool operator==(const Iterator& rhs) const
75  {
76  return &vector == &rhs.vector && index == rhs.index;
77  }
78 
79  bool operator!=(const Iterator& rhs) const
80  {
81  return !operator==(rhs);
82  }
83 
84  template <typename U = Element> typename std::enable_if<!is_const, U&>::type operator*()
85  {
86  return vector[index];
87  }
88 
89  E& operator*() const
90  {
91  return vector[index];
92  }
93 
94  private:
95  V& vector;
96  unsigned index{0};
97  };
98 
99  // constructors
100  Vector(unsigned int initialCapacity = 10, unsigned int capacityIncrement = 10) : _increment(capacityIncrement)
101  {
102  _data.allocate(initialCapacity);
103  }
104 
105  Vector(const Vector& rhv)
106  {
107  copyFrom(rhv);
108  }
109 
110  // methods
111  unsigned int capacity() const
112  {
113  return _data.size;
114  }
115 
116  bool contains(const Element& elem) const
117  {
118  return indexOf(elem) >= 0;
119  }
120 
121  const Element& firstElement() const
122  {
123  if(_size == 0) {
124  abort();
125  }
126 
127  return _data[0];
128  }
129 
130  int indexOf(const Element& elem) const;
131 
132  bool isEmpty() const
133  {
134  return _size == 0;
135  }
136 
137  const Element& lastElement() const
138  {
139  if(_size == 0) {
140  abort();
141  }
142 
143  return _data[_size - 1];
144  }
145 
146  int lastIndexOf(const Element& elem) const;
147 
148  unsigned int count() const override
149  {
150  return size();
151  }
152 
153  unsigned int size() const
154  {
155  return _size;
156  }
157 
158  void copyInto(Element* array) const;
159 
160  bool add(const Element& obj)
161  {
162  return addElement(obj);
163  }
164 
165  bool addElement(const Element& obj);
166  bool addElement(Element* objp);
167 
168  void clear()
169  {
171  }
172 
173  bool ensureCapacity(unsigned int minCapacity);
174 
176  {
177  _data.clear();
178  _size = 0;
179  }
180 
181  bool removeElement(const Element& obj)
182  {
183  return removeElementAt(indexOf(obj));
184  }
185 
193  bool setSize(unsigned int newSize);
194 
198  void trimToSize()
199  {
200  if(_size < _data.size) {
201  _data.trim(_size, true);
202  }
203  }
204 
205  const Element& elementAt(unsigned int index) const
206  {
207  if(index >= _size) {
208  abort();
209  }
210  return _data[index];
211  }
212 
213  bool insertElementAt(const Element& obj, unsigned int index);
214 
215  bool remove(unsigned int index)
216  {
217  return removeElementAt(index);
218  }
219 
220  bool removeElementAt(unsigned int index);
221  bool setElementAt(const Element& obj, unsigned int index);
222 
223  const Element& get(unsigned int index) const
224  {
225  return elementAt(index);
226  }
227 
228  const Element& operator[](unsigned int index) const override
229  {
230  return elementAt(index);
231  }
232 
233  Element& operator[](unsigned int index) override
234  {
235  if(index >= _size) {
236  abort();
237  }
238  return _data[index];
239  }
240 
242  {
243  if(this != &rhv) {
244  copyFrom(rhv);
245  }
246  return *this;
247  }
248 
249  const Vector<Element>& operator=(Vector<Element>&& other) noexcept // move assignment
250  {
251  clear();
252  _increment = 0;
253  std::swap(_data, other._data);
254  std::swap(_size, other._size);
255  std::swap(_increment, other._increment);
256  return *this;
257  }
258 
259  void sort(Comparer compareFunction);
260 
262  {
263  return Iterator<false>(*this, 0);
264  }
265 
267  {
268  return Iterator<false>(*this, count());
269  }
270 
271  const Iterator<true> begin() const
272  {
273  return Iterator<true>(*this, 0);
274  }
275 
276  const Iterator<true> end() const
277  {
278  return Iterator<true>(*this, count());
279  }
280 
281 protected:
282  void copyFrom(const Vector& rhv);
283 
284 protected:
286 
287  unsigned int _size{0};
288  unsigned int _increment{0};
290 };
291 
292 template <class Element> void Vector<Element>::copyFrom(const Vector<Element>& rhv)
293 {
294  _data.clear();
295  if(!_data.allocate(rhv._data.size)) {
296  _size = _increment = 0;
297  return;
298  }
299 
300  _size = rhv._size;
301  _increment = rhv._increment;
302 
303  for(unsigned int i = 0; i < _size; i++) {
304  _data[i] = rhv._data[i];
305  }
306 }
307 
308 template <class Element> void Vector<Element>::copyInto(Element* array) const
309 {
310  if(array == nullptr) {
311  return;
312  }
313 
314  for(unsigned int i = 0; i < _size; i++) {
315  array[i] = _data[i];
316  }
317 }
318 
319 template <class Element> int Vector<Element>::indexOf(const Element& elem) const
320 {
321  for(unsigned int i = 0; i < _size; i++) {
322  if(_data[i] == elem) {
323  return i;
324  }
325  }
326 
327  return -1;
328 }
329 
330 template <class Element> int Vector<Element>::lastIndexOf(const Element& elem) const
331 {
332  // check for empty vector
333  if(_size == 0) {
334  return -1;
335  }
336 
337  unsigned int i = _size;
338 
339  do {
340  i--;
341  if(_data[i] == elem) {
342  return i;
343  }
344  } while(i != 0);
345 
346  return -1;
347 }
348 
349 template <class Element> bool Vector<Element>::addElement(const Element& obj)
350 {
351  if(!ensureCapacity(_size + 1)) {
352  return false;
353  }
354  _data[_size++] = obj;
355  return true;
356 }
357 
358 template <class Element> bool Vector<Element>::addElement(Element* objp)
359 {
360  if(!ensureCapacity(_size + 1)) {
361  return false;
362  }
363  _data[_size++] = objp;
364  return true;
365 }
366 
367 template <class Element> bool Vector<Element>::ensureCapacity(unsigned int minCapacity)
368 {
369  if(_data.size >= minCapacity) {
370  return true;
371  }
372 
373  auto newCapacity = std::max(minCapacity, _data.size + _increment);
374  return _data.allocate(newCapacity);
375 }
376 
377 template <class Element> bool Vector<Element>::insertElementAt(const Element& obj, unsigned int index)
378 {
379  if(index == _size) {
380  return addElement(obj);
381  }
382 
383  if(index > _size) {
384  return false;
385  }
386  if(!ensureCapacity(_size + 1)) {
387  return false;
388  }
389 
390  if(!_data.insert(index, obj)) {
391  return false;
392  }
393 
394  _size++;
395  return true;
396 }
397 
398 template <class Element> bool Vector<Element>::removeElementAt(unsigned int index)
399 {
400  // check for valid index
401  if(index >= _size) {
402  return false;
403  }
404 
405  _data.remove(index);
406  _size--;
407  return true;
408 }
409 
410 template <class Element> bool Vector<Element>::setElementAt(const Element& obj, unsigned int index)
411 {
412  // check for valid index
413  if(index >= _size) {
414  return false;
415  }
416  _data[index] = obj;
417  return true;
418 }
419 
420 template <class Element> bool Vector<Element>::setSize(unsigned int newSize)
421 {
422  if(!ensureCapacity(newSize)) {
423  return false;
424  }
425 
426  _data.trim(newSize, false);
427  _size = std::min(_size, newSize);
428  return true;
429 }
430 
431 template <class Element> void Vector<Element>::sort(Comparer compareFunction)
432 {
433  // Start with 1 (not 0)
434  for(unsigned j = 1; j < _size; j++) {
435  auto key = _data.values[j];
436  Element& keyRef = _data[j];
437  // Smaller values move up
438  int i;
439  for(i = j - 1; (i >= 0) && compareFunction(_data[i], keyRef) > 0; i--) {
440  _data.values[i + 1] = _data.values[i];
441  }
442  // Put key into its proper location
443  _data.values[i + 1] = key;
444  }
445 }
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:50
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:60
std::random_access_iterator_tag iterator_category
Definition: WVector.h:39
Iterator & operator++()
Definition: WVector.h:54
E & operator*() const
Definition: WVector.h:89
bool operator!=(const Iterator &rhs) const
Definition: WVector.h:79
Iterator operator+=(size_t distance)
Definition: WVector.h:67
std::enable_if<!is_const, U & >::type operator*()
Definition: WVector.h:84
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:74
Vector class template.
Definition: WVector.h:32
bool setElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:410
bool addElement(const Element &obj)
Definition: WVector.h:349
bool setSize(unsigned int newSize)
Reduce or increase number of items.
Definition: WVector.h:420
const Vector< Element > & operator=(const Vector< Element > &rhv)
Definition: WVector.h:241
bool contains(const Element &elem) const
Definition: WVector.h:116
const Iterator< true > begin() const
Definition: WVector.h:271
bool removeElementAt(unsigned int index)
Definition: WVector.h:398
unsigned int count() const override
Definition: WVector.h:148
bool add(const Element &obj)
Definition: WVector.h:160
void clear()
Definition: WVector.h:168
Iterator< false > end()
Definition: WVector.h:266
int(*)(const Element &lhs, const Element &rhs) Comparer
Definition: WVector.h:34
void copyFrom(const Vector &rhv)
Definition: WVector.h:292
bool remove(unsigned int index)
Definition: WVector.h:215
unsigned int capacity() const
Definition: WVector.h:111
bool isEmpty() const
Definition: WVector.h:132
const Vector< Element > & operator=(Vector< Element > &&other) noexcept
Definition: WVector.h:249
void removeAllElements()
Definition: WVector.h:175
const Element & get(unsigned int index) const
Definition: WVector.h:223
Iterator< false > begin()
Definition: WVector.h:261
void trimToSize()
Reduce capacity to match current size.
Definition: WVector.h:198
void sort(Comparer compareFunction)
Definition: WVector.h:431
int indexOf(const Element &elem) const
Definition: WVector.h:319
Element & operator[](unsigned int index) override
Definition: WVector.h:233
unsigned int size() const
Definition: WVector.h:153
Vector(const Vector &rhv)
Definition: WVector.h:105
ElementList _data
Definition: WVector.h:289
unsigned int _size
Definition: WVector.h:287
wiring_private::List< Element > ElementList
Definition: WVector.h:285
bool ensureCapacity(unsigned int minCapacity)
Definition: WVector.h:367
bool removeElement(const Element &obj)
Definition: WVector.h:181
bool insertElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:377
const Element & lastElement() const
Definition: WVector.h:137
const Element & elementAt(unsigned int index) const
Definition: WVector.h:205
const Element & firstElement() const
Definition: WVector.h:121
void copyInto(Element *array) const
Definition: WVector.h:308
const Element & operator[](unsigned int index) const override
Definition: WVector.h:228
Vector(unsigned int initialCapacity=10, unsigned int capacityIncrement=10)
Definition: WVector.h:100
unsigned int _increment
Definition: WVector.h:288
int lastIndexOf(const Element &elem) const
Definition: WVector.h:330
const Iterator< true > end() const
Definition: WVector.h:276
bool addElement(Element *objp)
Definition: WVector.h:358
typename std::conditional< std::is_scalar< T >::value, ScalarList< T >, ObjectList< T > >::type List
Definition: WiringList.h:182