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 
30 template <typename Element> class Vector : public Countable<Element>
31 {
32 public:
33  using Comparer = int (*)(const Element& lhs, const Element& rhs);
34 
35  template <bool is_const> class Iterator : public std::iterator<std::random_access_iterator_tag, Element>
36  {
37  public:
38  using V = typename std::conditional<is_const, const Vector, Vector>::type;
39  using E = typename std::conditional<is_const, const Element, Element>::type;
40 
41  Iterator(const Iterator&) = default;
42 
43  Iterator(V& vector, unsigned index) : vector(vector), index(index)
44  {
45  }
46 
48  {
49  ++index;
50  return *this;
51  }
52 
54  {
55  Iterator tmp(*this);
56  ++index;
57  return tmp;
58  }
59 
60  Iterator operator+=(size_t distance)
61  {
62  Iterator tmp(*this);
63  index += distance;
64  return tmp;
65  }
66 
67  bool operator==(const Iterator& rhs) const
68  {
69  return &vector == &rhs.vector && index == rhs.index;
70  }
71 
72  bool operator!=(const Iterator& rhs) const
73  {
74  return !operator==(rhs);
75  }
76 
77  Element& operator*()
78  {
79  return vector[index];
80  }
81 
82  E& operator*() const
83  {
84  return vector[index];
85  }
86 
87  private:
88  V& vector;
89  unsigned index{0};
90  };
91 
92  // constructors
93  Vector(unsigned int initialCapacity = 10, unsigned int capacityIncrement = 10);
94  Vector(const Vector& rhv);
95  ~Vector();
96 
97  // methods
98  unsigned int capacity() const;
99  bool contains(const Element& elem) const;
100  const Element& firstElement() const;
101  int indexOf(const Element& elem) const;
102  bool isEmpty() const;
103  const Element& lastElement() const;
104  int lastIndexOf(const Element& elem) const;
105  unsigned int count() const override
106  {
107  return size();
108  }
109  unsigned int size() const;
110  void copyInto(Element* array) const;
111  bool add(const Element& obj)
112  {
113  return addElement(obj);
114  }
115  bool addElement(const Element& obj);
116  bool addElement(Element* objp);
117  void clear()
118  {
120  }
121  bool ensureCapacity(unsigned int minCapacity);
122  void removeAllElements();
123  bool removeElement(const Element& obj);
124  bool setSize(unsigned int newSize);
125  void trimToSize();
126  const Element& elementAt(unsigned int index) const;
127  bool insertElementAt(const Element& obj, unsigned int index);
128  const void remove(unsigned int index);
129  void removeElementAt(unsigned int index);
130  bool setElementAt(const Element& obj, unsigned int index);
131  const Element& get(unsigned int index) const
132  {
133  return elementAt(index);
134  }
135 
136  const Element& operator[](unsigned int index) const override;
137  Element& operator[](unsigned int index) override;
138 
140  {
141  if(this != &rhv)
142  copyFrom(rhv);
143  return *this;
144  }
145  const Vector<Element>& operator=(const Vector<Element>&& other) noexcept // move assignment
146  {
147  if(_data != nullptr) {
149  delete[] _data; // delete this storage
150  }
151  _data = other._data; // move
152  _size = other._size;
153  _capacity = other._capacity;
154  _increment = other._increment;
155  other._data = nullptr; // leave moved-from in valid state
156  other._size = 0;
157  other._capacity = 0;
158  other._increment = 0;
159  return *this;
160  }
161 
162  void sort(Comparer compareFunction);
163 
164  Iterator<false> begin()
165  {
166  return Iterator<false>(*this, 0);
167  }
168 
169  Iterator<false> end()
170  {
171  return Iterator<false>(*this, count());
172  }
173 
174  Iterator<true> begin() const
175  {
176  return Iterator<true>(*this, 0);
177  }
178 
179  Iterator<true> end() const
180  {
181  return Iterator<true>(*this, count());
182  }
183 
184 protected:
185  void copyFrom(const Vector& rhv);
186 
187 protected:
188  unsigned int _size = 0;
189  unsigned int _capacity = 0;
190  unsigned int _increment;
191  Element** _data = nullptr;
192 };
193 
194 template <class Element> Vector<Element>::Vector(unsigned int initialCapacity, unsigned int capacityIncrement)
195 {
196  _size = 0;
197  _capacity = initialCapacity;
198  _data = new Element*[_capacity];
199  _increment = capacityIncrement;
200  if(_data == nullptr) {
201  _capacity = _increment = 0;
202  }
203 }
204 
205 template <class Element> Vector<Element>::Vector(const Vector<Element>& rhv)
206 {
207  copyFrom(rhv);
208 }
209 
210 template <class Element> void Vector<Element>::copyFrom(const Vector<Element>& rhv)
211 {
212  if(_data != nullptr) {
214  delete[] _data;
215  }
216  _size = rhv._size;
217  _capacity = rhv._capacity;
218  _data = new Element*[_capacity];
219  _increment = rhv._increment;
220  if(_data == nullptr) {
221  _size = _capacity = _increment = 0;
222  }
223 
224  for(unsigned int i = 0; i < _size; i++) {
225  _data[i] = new Element(*(rhv._data[i]));
226  }
227 }
228 
229 template <class Element> Vector<Element>::~Vector()
230 {
232  delete[] _data;
233 }
234 
235 template <class Element> unsigned int Vector<Element>::capacity() const
236 {
237  return _capacity;
238 }
239 
240 template <class Element> bool Vector<Element>::contains(const Element& elem) const
241 {
242  return indexOf(elem) >= 0;
243 }
244 
245 template <class Element> void Vector<Element>::copyInto(Element* array) const
246 {
247  if(array != nullptr) {
248  for(unsigned int i = 0; i < _size; i++) {
249  array[i] = *_data[i];
250  }
251  }
252 }
253 
254 template <class Element> const Element& Vector<Element>::elementAt(unsigned int index) const
255 {
256  if(index >= _size || !_data) {
257  abort();
258  }
259  // add check for valid index
260  return *_data[index];
261 }
262 
263 template <class Element> const Element& Vector<Element>::firstElement() const
264 {
265  if(_size == 0 || !_data) {
266  abort();
267  }
268 
269  return *_data[0];
270 }
271 
272 template <class Element> int Vector<Element>::indexOf(const Element& elem) const
273 {
274  for(unsigned int i = 0; i < _size; i++) {
275  if(*_data[i] == elem) {
276  return i;
277  }
278  }
279 
280  return -1;
281 }
282 
283 template <class Element> bool Vector<Element>::isEmpty() const
284 {
285  return _size == 0;
286 }
287 
288 template <class Element> const Element& Vector<Element>::lastElement() const
289 {
290  if(_size == 0 || !_data) {
291  abort();
292  }
293 
294  return *_data[_size - 1];
295 }
296 
297 template <class Element> int Vector<Element>::lastIndexOf(const Element& elem) const
298 {
299  // check for empty vector
300  if(_size == 0) {
301  return -1;
302  }
303 
304  unsigned int i = _size;
305 
306  do {
307  i--;
308  if(*_data[i] == elem) {
309  return i;
310  }
311  } while(i != 0);
312 
313  return -1;
314 }
315 
316 template <class Element> unsigned int Vector<Element>::size() const
317 {
318  return _size;
319 }
320 
321 template <class Element> bool Vector<Element>::addElement(const Element& obj)
322 {
323  if(!ensureCapacity(_size + 1)) {
324  return false;
325  }
326  _data[_size++] = new Element(obj);
327  return true;
328 }
329 
330 template <class Element> bool Vector<Element>::addElement(Element* objp)
331 {
332  if(!ensureCapacity(_size + 1)) {
333  return false;
334  }
335  _data[_size++] = objp;
336  return true;
337 }
338 
339 template <class Element> bool Vector<Element>::ensureCapacity(unsigned int minCapacity)
340 {
341  if(_capacity >= minCapacity) {
342  return true;
343  }
344 
345  auto newCapacity = std::max(minCapacity, _capacity + _increment);
346  Element** temp = new Element*[newCapacity];
347  // copy all elements
348  if(temp == nullptr) {
349  return false;
350  }
351 
352  _capacity = newCapacity;
353  memcpy(temp, _data, sizeof(Element*) * _size);
354  delete[] _data;
355  _data = temp;
356  return true;
357 }
358 
359 template <class Element> bool Vector<Element>::insertElementAt(const Element& obj, unsigned int index)
360 {
361  if(index == _size) {
362  return addElement(obj);
363  }
364 
365  // need to verify index, right now you must know what you're doing
366  if(index > _size) {
367  return false;
368  }
369  if(!ensureCapacity(_size + 1)) {
370  return false;
371  }
372 
373  Element* newItem = new Element(obj); // pointer to new item
374  if(newItem == nullptr) {
375  return false;
376  }
377 
378  for(unsigned int i = index; i <= _size; i++) {
379  Element* tmp = _data[i];
380  _data[i] = newItem;
381 
382  if(i != _size) {
383  newItem = tmp;
384  } else {
385  break;
386  }
387  }
388  _size++;
389  return true;
390 }
391 
392 template <class Element> const void Vector<Element>::remove(unsigned int index)
393 {
394  removeElementAt(index);
395 }
396 
397 template <class Element> void Vector<Element>::removeAllElements()
398 {
399  // avoid memory leak
400  for(unsigned int i = 0; i < _size; i++) {
401  delete _data[i];
402  }
403 
404  _size = 0;
405 }
406 
407 template <class Element> bool Vector<Element>::removeElement(const Element& obj)
408 {
409  for(unsigned int i = 0; i < _size; i++) {
410  if(*_data[i] == obj) {
411  removeElementAt(i);
412  return true;
413  }
414  }
415  return false;
416 }
417 
418 template <class Element> void Vector<Element>::removeElementAt(unsigned int index)
419 {
420  // check for valid index
421  if(index >= _size) {
422  return;
423  }
424 
425  delete _data[index];
426 
427  unsigned int i;
428  for(i = index + 1; i < _size; i++) {
429  _data[i - 1] = _data[i];
430  }
431 
432  _size--;
433 }
434 
435 template <class Element> bool Vector<Element>::setElementAt(const Element& obj, unsigned int index)
436 {
437  // check for valid index
438  if(index >= _size) {
439  return false;
440  }
441  *_data[index] = obj;
442  return true;
443 }
444 
445 template <class Element> bool Vector<Element>::setSize(unsigned int newSize)
446 {
447  if(!ensureCapacity(newSize)) {
448  return false;
449  }
450 
451  if(newSize < _size) {
452  for(unsigned int i = newSize; i < _size; i++) {
453  delete _data[i];
454  }
455 
456  _size = newSize;
457  }
458 
459  return true;
460 }
461 
462 template <class Element> void Vector<Element>::trimToSize()
463 {
464  if(_size != _capacity) {
465  Element** temp = new Element*[_size];
466  if(temp == nullptr) {
467  return;
468  }
469 
470  for(unsigned int i = 0; i < _size; i++) {
471  temp[i] = _data[i];
472  }
473 
474  delete[] _data;
475 
476  _data = temp;
477  _capacity = _size;
478  }
479 }
480 
481 template <class Element> const Element& Vector<Element>::operator[](unsigned int index) const
482 {
483  return elementAt(index);
484 }
485 
486 template <class Element> Element& Vector<Element>::operator[](unsigned int index)
487 {
488  // check for valid index
489  //static Element dummy_writable_element;
490  if(index >= _size || !_data) {
491  //dummy_writable_element = 0;
492  //return dummy_writable_element;
493  abort();
494  }
495  return *_data[index];
496 }
497 
498 template <class Element> void Vector<Element>::sort(Comparer compareFunction)
499 {
500  for(unsigned j = 1; j < _size; j++) // Start with 1 (not 0)
501  {
502  Element* key = _data[j];
503  int i;
504  for(i = j - 1; (i >= 0) && compareFunction(*_data[i], *key) > 0; i--) // Smaller values move up
505  {
506  _data[i + 1] = _data[i];
507  }
508  _data[i + 1] = key; //Put key into its proper location
509  }
510 }
const Element & lastElement() const
Definition: WVector.h:288
Iterator operator++(int)
Definition: WVector.h:53
int lastIndexOf(const Element &elem) const
Definition: WVector.h:297
E & operator*() const
Definition: WVector.h:82
void trimToSize()
Definition: WVector.h:462
bool contains(const Element &elem) const
Definition: WVector.h:240
unsigned int _increment
Definition: WVector.h:190
int indexOf(const Element &elem) const
Definition: WVector.h:272
Iterator< false > end()
Definition: WVector.h:169
const Element & elementAt(unsigned int index) const
Definition: WVector.h:254
Definition: Countable.h:19
Vector class template.
Definition: WVector.h:30
const Vector< Element > & operator=(const Vector< Element > &rhv)
Definition: WVector.h:139
Element ** _data
Definition: WVector.h:191
unsigned int capacity() const
Definition: WVector.h:235
const void remove(unsigned int index)
Definition: WVector.h:392
bool ensureCapacity(unsigned int minCapacity)
Definition: WVector.h:339
unsigned int _capacity
Definition: WVector.h:189
bool operator!=(const Iterator &rhs) const
Definition: WVector.h:72
bool insertElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:359
Element & operator*()
Definition: WVector.h:77
bool add(const Element &obj)
Definition: WVector.h:111
bool isEmpty() const
Definition: WVector.h:283
void removeElementAt(unsigned int index)
Definition: WVector.h:418
Iterator & operator++()
Definition: WVector.h:47
unsigned int count() const override
Definition: WVector.h:105
const Vector< Element > & operator=(const Vector< Element > &&other) noexcept
Definition: WVector.h:145
bool setSize(unsigned int newSize)
Definition: WVector.h:445
void sort(Comparer compareFunction)
Definition: WVector.h:498
Iterator< false > begin()
Definition: WVector.h:164
typename std::conditional< is_const, const Element, Element >::type E
Definition: WVector.h:39
bool removeElement(const Element &obj)
Definition: WVector.h:407
bool operator==(const Iterator &rhs) const
Definition: WVector.h:67
Iterator< true > end() const
Definition: WVector.h:179
void size_t const void * key
Definition: blake2s.h:33
void copyFrom(const Vector &rhv)
Definition: WVector.h:210
~Vector()
Definition: WVector.h:229
void removeAllElements()
Definition: WVector.h:397
int(*)(const Parameter &lhs, const Parameter &rhs) Comparer
Definition: WVector.h:33
Iterator(const Iterator &)=default
unsigned int _size
Definition: WVector.h:188
bool setElementAt(const Element &obj, unsigned int index)
Definition: WVector.h:435
void clear()
Definition: WVector.h:117
const Element & operator[](unsigned int index) const override
Definition: WVector.h:481
Iterator operator+=(size_t distance)
Definition: WVector.h:60
const Element & firstElement() const
Definition: WVector.h:263
Vector(unsigned int initialCapacity=10, unsigned int capacityIncrement=10)
Definition: WVector.h:194
Iterator< true > begin() const
Definition: WVector.h:174
unsigned int size() const
Definition: WVector.h:316
bool addElement(const Element &obj)
Definition: WVector.h:321
Iterator(V &vector, unsigned index)
Definition: WVector.h:43
typename std::conditional< is_const, const Vector, Vector >::type V
Definition: WVector.h:38
void copyInto(Element *array) const
Definition: WVector.h:245
Definition: WVector.h:35