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