aboutsummaryrefslogtreecommitdiff
path: root/CPP/Common/MyVector.h
diff options
context:
space:
mode:
Diffstat (limited to 'CPP/Common/MyVector.h')
-rw-r--r--CPP/Common/MyVector.h634
1 files changed, 634 insertions, 0 deletions
diff --git a/CPP/Common/MyVector.h b/CPP/Common/MyVector.h
new file mode 100644
index 0000000..c851234
--- /dev/null
+++ b/CPP/Common/MyVector.h
@@ -0,0 +1,634 @@
1// Common/MyVector.h
2
3#ifndef __COMMON_MY_VECTOR_H
4#define __COMMON_MY_VECTOR_H
5
6#include <string.h>
7
8template <class T>
9class CRecordVector
10{
11 T *_items;
12 unsigned _size;
13 unsigned _capacity;
14
15 void MoveItems(unsigned destIndex, unsigned srcIndex)
16 {
17 memmove(_items + destIndex, _items + srcIndex, (size_t)(_size - srcIndex) * sizeof(T));
18 }
19
20 void ReserveOnePosition()
21 {
22 if (_size == _capacity)
23 {
24 unsigned newCapacity = _capacity + (_capacity >> 2) + 1;
25 T *p;
26 MY_ARRAY_NEW(p, T, newCapacity);
27 // p = new T[newCapacity];
28 if (_size != 0)
29 memcpy(p, _items, (size_t)_size * sizeof(T));
30 delete []_items;
31 _items = p;
32 _capacity = newCapacity;
33 }
34 }
35
36public:
37
38 CRecordVector(): _items(NULL), _size(0), _capacity(0) {}
39
40 CRecordVector(const CRecordVector &v): _items(0), _size(0), _capacity(0)
41 {
42 unsigned size = v.Size();
43 if (size != 0)
44 {
45 _items = new T[size];
46 _size = size;
47 _capacity = size;
48 memcpy(_items, v._items, (size_t)size * sizeof(T));
49 }
50 }
51
52 unsigned Size() const { return _size; }
53 bool IsEmpty() const { return _size == 0; }
54
55 void ConstructReserve(unsigned size)
56 {
57 if (size != 0)
58 {
59 MY_ARRAY_NEW(_items, T, size)
60 // _items = new T[size];
61 _capacity = size;
62 }
63 }
64
65 void Reserve(unsigned newCapacity)
66 {
67 if (newCapacity > _capacity)
68 {
69 T *p;
70 MY_ARRAY_NEW(p, T, newCapacity);
71 // p = new T[newCapacity];
72 if (_size != 0)
73 memcpy(p, _items, (size_t)_size * sizeof(T));
74 delete []_items;
75 _items = p;
76 _capacity = newCapacity;
77 }
78 }
79
80 void ClearAndReserve(unsigned newCapacity)
81 {
82 Clear();
83 if (newCapacity > _capacity)
84 {
85 delete []_items;
86 _items = NULL;
87 _capacity = 0;
88 MY_ARRAY_NEW(_items, T, newCapacity)
89 // _items = new T[newCapacity];
90 _capacity = newCapacity;
91 }
92 }
93
94 void ClearAndSetSize(unsigned newSize)
95 {
96 ClearAndReserve(newSize);
97 _size = newSize;
98 }
99
100 void ChangeSize_KeepData(unsigned newSize)
101 {
102 if (newSize > _capacity)
103 {
104 T *p;
105 MY_ARRAY_NEW(p, T, newSize)
106 // p = new T[newSize];
107 if (_size != 0)
108 memcpy(p, _items, (size_t)_size * sizeof(T));
109 delete []_items;
110 _items = p;
111 _capacity = newSize;
112 }
113 _size = newSize;
114 }
115
116 void ReserveDown()
117 {
118 if (_size == _capacity)
119 return;
120 T *p = NULL;
121 if (_size != 0)
122 {
123 p = new T[_size];
124 memcpy(p, _items, (size_t)_size * sizeof(T));
125 }
126 delete []_items;
127 _items = p;
128 _capacity = _size;
129 }
130
131 ~CRecordVector() { delete []_items; }
132
133 void ClearAndFree()
134 {
135 delete []_items;
136 _items = NULL;
137 _size = 0;
138 _capacity = 0;
139 }
140
141 void Clear() { _size = 0; }
142
143 void DeleteBack() { _size--; }
144
145 void DeleteFrom(unsigned index)
146 {
147 // if (index <= _size)
148 _size = index;
149 }
150
151 void DeleteFrontal(unsigned num)
152 {
153 if (num != 0)
154 {
155 MoveItems(0, num);
156 _size -= num;
157 }
158 }
159
160 void Delete(unsigned index)
161 {
162 MoveItems(index, index + 1);
163 _size -= 1;
164 }
165
166 /*
167 void Delete(unsigned index, unsigned num)
168 {
169 if (num > 0)
170 {
171 MoveItems(index, index + num);
172 _size -= num;
173 }
174 }
175 */
176
177 CRecordVector& operator=(const CRecordVector &v)
178 {
179 if (&v == this)
180 return *this;
181 unsigned size = v.Size();
182 if (size > _capacity)
183 {
184 delete []_items;
185 _capacity = 0;
186 _size = 0;
187 _items = NULL;
188 _items = new T[size];
189 _capacity = size;
190 }
191 _size = size;
192 if (size != 0)
193 memcpy(_items, v._items, (size_t)size * sizeof(T));
194 return *this;
195 }
196
197 CRecordVector& operator+=(const CRecordVector &v)
198 {
199 unsigned size = v.Size();
200 Reserve(_size + size);
201 if (size != 0)
202 memcpy(_items + _size, v._items, (size_t)size * sizeof(T));
203 _size += size;
204 return *this;
205 }
206
207 unsigned Add(const T item)
208 {
209 ReserveOnePosition();
210 _items[_size] = item;
211 return _size++;
212 }
213
214 void AddInReserved(const T item)
215 {
216 _items[_size++] = item;
217 }
218
219 void Insert(unsigned index, const T item)
220 {
221 ReserveOnePosition();
222 MoveItems(index + 1, index);
223 _items[index] = item;
224 _size++;
225 }
226
227 void MoveToFront(unsigned index)
228 {
229 if (index != 0)
230 {
231 T temp = _items[index];
232 memmove(_items + 1, _items, (size_t)index * sizeof(T));
233 _items[0] = temp;
234 }
235 }
236
237 const T& operator[](unsigned index) const { return _items[index]; }
238 T& operator[](unsigned index) { return _items[index]; }
239 const T& Front() const { return _items[0]; }
240 T& Front() { return _items[0]; }
241 const T& Back() const { return _items[(size_t)_size - 1]; }
242 T& Back() { return _items[(size_t)_size - 1]; }
243
244 /*
245 void Swap(unsigned i, unsigned j)
246 {
247 T temp = _items[i];
248 _items[i] = _items[j];
249 _items[j] = temp;
250 }
251 */
252
253 int FindInSorted(const T item, unsigned left, unsigned right) const
254 {
255 while (left != right)
256 {
257 unsigned mid = (left + right) / 2;
258 const T midVal = (*this)[mid];
259 if (item == midVal)
260 return (int)mid;
261 if (item < midVal)
262 right = mid;
263 else
264 left = mid + 1;
265 }
266 return -1;
267 }
268
269 int FindInSorted2(const T &item, unsigned left, unsigned right) const
270 {
271 while (left != right)
272 {
273 unsigned mid = (left + right) / 2;
274 const T& midVal = (*this)[mid];
275 int comp = item.Compare(midVal);
276 if (comp == 0)
277 return (int)mid;
278 if (comp < 0)
279 right = mid;
280 else
281 left = mid + 1;
282 }
283 return -1;
284 }
285
286 int FindInSorted(const T item) const
287 {
288 return FindInSorted(item, 0, _size);
289 }
290
291 int FindInSorted2(const T &item) const
292 {
293 return FindInSorted2(item, 0, _size);
294 }
295
296 unsigned AddToUniqueSorted(const T item)
297 {
298 unsigned left = 0, right = _size;
299 while (left != right)
300 {
301 unsigned mid = (left + right) / 2;
302 const T midVal = (*this)[mid];
303 if (item == midVal)
304 return mid;
305 if (item < midVal)
306 right = mid;
307 else
308 left = mid + 1;
309 }
310 Insert(right, item);
311 return right;
312 }
313
314 unsigned AddToUniqueSorted2(const T &item)
315 {
316 unsigned left = 0, right = _size;
317 while (left != right)
318 {
319 unsigned mid = (left + right) / 2;
320 const T& midVal = (*this)[mid];
321 int comp = item.Compare(midVal);
322 if (comp == 0)
323 return mid;
324 if (comp < 0)
325 right = mid;
326 else
327 left = mid + 1;
328 }
329 Insert(right, item);
330 return right;
331 }
332
333 static void SortRefDown(T* p, unsigned k, unsigned size, int (*compare)(const T*, const T*, void *), void *param)
334 {
335 T temp = p[k];
336 for (;;)
337 {
338 unsigned s = (k << 1);
339 if (s > size)
340 break;
341 if (s < size && compare(p + s + 1, p + s, param) > 0)
342 s++;
343 if (compare(&temp, p + s, param) >= 0)
344 break;
345 p[k] = p[s];
346 k = s;
347 }
348 p[k] = temp;
349 }
350
351 void Sort(int (*compare)(const T*, const T*, void *), void *param)
352 {
353 unsigned size = _size;
354 if (size <= 1)
355 return;
356 T* p = (&Front()) - 1;
357 {
358 unsigned i = size >> 1;
359 do
360 SortRefDown(p, i, size, compare, param);
361 while (--i != 0);
362 }
363 do
364 {
365 T temp = p[size];
366 p[size--] = p[1];
367 p[1] = temp;
368 SortRefDown(p, 1, size, compare, param);
369 }
370 while (size > 1);
371 }
372
373 static void SortRefDown2(T* p, unsigned k, unsigned size)
374 {
375 T temp = p[k];
376 for (;;)
377 {
378 unsigned s = (k << 1);
379 if (s > size)
380 break;
381 if (s < size && p[(size_t)s + 1].Compare(p[s]) > 0)
382 s++;
383 if (temp.Compare(p[s]) >= 0)
384 break;
385 p[k] = p[s];
386 k = s;
387 }
388 p[k] = temp;
389 }
390
391 void Sort2()
392 {
393 unsigned size = _size;
394 if (size <= 1)
395 return;
396 T* p = (&Front()) - 1;
397 {
398 unsigned i = size >> 1;
399 do
400 SortRefDown2(p, i, size);
401 while (--i != 0);
402 }
403 do
404 {
405 T temp = p[size];
406 p[size--] = p[1];
407 p[1] = temp;
408 SortRefDown2(p, 1, size);
409 }
410 while (size > 1);
411 }
412};
413
414typedef CRecordVector<int> CIntVector;
415typedef CRecordVector<unsigned int> CUIntVector;
416typedef CRecordVector<bool> CBoolVector;
417typedef CRecordVector<unsigned char> CByteVector;
418typedef CRecordVector<void *> CPointerVector;
419
420template <class T>
421class CObjectVector
422{
423 CPointerVector _v;
424public:
425 unsigned Size() const { return _v.Size(); }
426 bool IsEmpty() const { return _v.IsEmpty(); }
427 void ReserveDown() { _v.ReserveDown(); }
428 // void Reserve(unsigned newCapacity) { _v.Reserve(newCapacity); }
429 void ClearAndReserve(unsigned newCapacity) { Clear(); _v.ClearAndReserve(newCapacity); }
430
431 CObjectVector() {}
432 CObjectVector(const CObjectVector &v)
433 {
434 unsigned size = v.Size();
435 _v.ConstructReserve(size);
436 for (unsigned i = 0; i < size; i++)
437 _v.AddInReserved(new T(v[i]));
438 }
439 CObjectVector& operator=(const CObjectVector &v)
440 {
441 if (&v == this)
442 return *this;
443 Clear();
444 unsigned size = v.Size();
445 _v.Reserve(size);
446 for (unsigned i = 0; i < size; i++)
447 _v.AddInReserved(new T(v[i]));
448 return *this;
449 }
450
451 CObjectVector& operator+=(const CObjectVector &v)
452 {
453 unsigned size = v.Size();
454 _v.Reserve(Size() + size);
455 for (unsigned i = 0; i < size; i++)
456 _v.AddInReserved(new T(v[i]));
457 return *this;
458 }
459
460 const T& operator[](unsigned index) const { return *((T *)_v[index]); }
461 T& operator[](unsigned index) { return *((T *)_v[index]); }
462 const T& Front() const { return operator[](0); }
463 T& Front() { return operator[](0); }
464 const T& Back() const { return *(T *)_v.Back(); }
465 T& Back() { return *(T *)_v.Back(); }
466
467 void MoveToFront(unsigned index) { _v.MoveToFront(index); }
468
469 unsigned Add(const T& item) { return _v.Add(new T(item)); }
470
471 void AddInReserved(const T& item) { _v.AddInReserved(new T(item)); }
472
473 T& AddNew()
474 {
475 T *p = new T;
476 _v.Add(p);
477 return *p;
478 }
479
480 T& AddNewInReserved()
481 {
482 T *p = new T;
483 _v.AddInReserved(p);
484 return *p;
485 }
486
487 void Insert(unsigned index, const T& item) { _v.Insert(index, new T(item)); }
488
489 T& InsertNew(unsigned index)
490 {
491 T *p = new T;
492 _v.Insert(index, p);
493 return *p;
494 }
495
496 ~CObjectVector()
497 {
498 for (unsigned i = _v.Size(); i != 0;)
499 delete (T *)_v[--i];
500 }
501
502 void ClearAndFree()
503 {
504 Clear();
505 _v.ClearAndFree();
506 }
507
508 void Clear()
509 {
510 for (unsigned i = _v.Size(); i != 0;)
511 delete (T *)_v[--i];
512 _v.Clear();
513 }
514
515 void DeleteFrom(unsigned index)
516 {
517 unsigned size = _v.Size();
518 for (unsigned i = index; i < size; i++)
519 delete (T *)_v[i];
520 _v.DeleteFrom(index);
521 }
522
523 void DeleteFrontal(unsigned num)
524 {
525 for (unsigned i = 0; i < num; i++)
526 delete (T *)_v[i];
527 _v.DeleteFrontal(num);
528 }
529
530 void DeleteBack()
531 {
532 delete (T *)_v.Back();
533 _v.DeleteBack();
534 }
535
536 void Delete(unsigned index)
537 {
538 delete (T *)_v[index];
539 _v.Delete(index);
540 }
541
542 /*
543 void Delete(unsigned index, unsigned num)
544 {
545 for (unsigned i = 0; i < num; i++)
546 delete (T *)_v[index + i];
547 _v.Delete(index, num);
548 }
549 */
550
551 /*
552 int Find(const T& item) const
553 {
554 unsigned size = Size();
555 for (unsigned i = 0; i < size; i++)
556 if (item == (*this)[i])
557 return i;
558 return -1;
559 }
560 */
561
562 int FindInSorted(const T& item) const
563 {
564 unsigned left = 0, right = Size();
565 while (left != right)
566 {
567 unsigned mid = (left + right) / 2;
568 const T& midVal = (*this)[mid];
569 int comp = item.Compare(midVal);
570 if (comp == 0)
571 return (int)mid;
572 if (comp < 0)
573 right = mid;
574 else
575 left = mid + 1;
576 }
577 return -1;
578 }
579
580 unsigned AddToUniqueSorted(const T& item)
581 {
582 unsigned left = 0, right = Size();
583 while (left != right)
584 {
585 unsigned mid = (left + right) / 2;
586 const T& midVal = (*this)[mid];
587 int comp = item.Compare(midVal);
588 if (comp == 0)
589 return mid;
590 if (comp < 0)
591 right = mid;
592 else
593 left = mid + 1;
594 }
595 Insert(right, item);
596 return right;
597 }
598
599 /*
600 unsigned AddToSorted(const T& item)
601 {
602 unsigned left = 0, right = Size();
603 while (left != right)
604 {
605 unsigned mid = (left + right) / 2;
606 const T& midVal = (*this)[mid];
607 int comp = item.Compare(midVal);
608 if (comp == 0)
609 {
610 right = mid + 1;
611 break;
612 }
613 if (comp < 0)
614 right = mid;
615 else
616 left = mid + 1;
617 }
618 Insert(right, item);
619 return right;
620 }
621 */
622
623 void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
624 { _v.Sort(compare, param); }
625
626 static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
627 { return (*(*((const T *const *)a1))).Compare(*(*((const T *const *)a2))); }
628
629 void Sort() { _v.Sort(CompareObjectItems, NULL); }
630};
631
632#define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++)
633
634#endif