diff options
Diffstat (limited to 'CPP/Common/MyVector.h')
-rw-r--r-- | CPP/Common/MyVector.h | 634 |
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 | |||
8 | template <class T> | ||
9 | class 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 | |||
36 | public: | ||
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 | |||
414 | typedef CRecordVector<int> CIntVector; | ||
415 | typedef CRecordVector<unsigned int> CUIntVector; | ||
416 | typedef CRecordVector<bool> CBoolVector; | ||
417 | typedef CRecordVector<unsigned char> CByteVector; | ||
418 | typedef CRecordVector<void *> CPointerVector; | ||
419 | |||
420 | template <class T> | ||
421 | class CObjectVector | ||
422 | { | ||
423 | CPointerVector _v; | ||
424 | public: | ||
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 | ||