MyVector.h revision baa3858d3f5d128a5c8466b700098109edcad5f2 
1// Common/Vector.h
2
3#ifndef __COMMON_VECTOR_H
4#define __COMMON_VECTOR_H
5
6#include "Defs.h"
7
8class CBaseRecordVector
9{
10  void MoveItems(int destIndex, int srcIndex);
11protected:
12  int _capacity;
13  int _size;
14  void *_items;
15  size_t _itemSize;
16
17  void ReserveOnePosition();
18  void InsertOneItem(int index);
19  void TestIndexAndCorrectNum(int index, int &num) const
20    { if (index + num > _size) num = _size - index; }
21public:
22  CBaseRecordVector(size_t itemSize): _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
23  virtual ~CBaseRecordVector();
24  void ClearAndFree();
25  int Size() const { return _size; }
26  bool IsEmpty() const { return (_size == 0); }
27  void Reserve(int newCapacity);
28  void ReserveDown();
29  virtual void Delete(int index, int num = 1);
30  void Clear();
31  void DeleteFrom(int index);
32  void DeleteBack();
33};
34
35template <class T>
36class CRecordVector: public CBaseRecordVector
37{
38public:
39  CRecordVector(): CBaseRecordVector(sizeof(T)){};
40  CRecordVector(const CRecordVector &v): CBaseRecordVector(sizeof(T)) { *this = v; }
41  CRecordVector& operator=(const CRecordVector &v)
42  {
43    Clear();
44    return (*this += v);
45  }
46  CRecordVector& operator+=(const CRecordVector &v)
47  {
48    int size = v.Size();
49    Reserve(Size() + size);
50    for (int i = 0; i < size; i++)
51      Add(v[i]);
52    return *this;
53  }
54  int Add(T item)
55  {
56    ReserveOnePosition();
57    ((T *)_items)[_size] = item;
58    return _size++;
59  }
60  void Insert(int index, T item)
61  {
62    InsertOneItem(index);
63    ((T *)_items)[index] = item;
64  }
65  // T* GetPointer() const { return (T*)_items; }
66  // operator const T *() const { return _items; };
67  const T& operator[](int index) const { return ((T *)_items)[index]; }
68  T& operator[](int index) { return ((T *)_items)[index]; }
69  const T& Front() const { return operator[](0); }
70  T& Front() { return operator[](0); }
71  const T& Back() const { return operator[](_size - 1); }
72  T& Back() { return operator[](_size - 1); }
73
74  void Swap(int i, int j)
75  {
76    T temp = operator[](i);
77    operator[](i) = operator[](j);
78    operator[](j) = temp;
79  }
80
81  int FindInSorted(const T& item, int left, int right) const
82  {
83    while (left != right)
84    {
85      int mid = (left + right) / 2;
86      const T& midValue = (*this)[mid];
87      if (item == midValue)
88        return mid;
89      if (item < midValue)
90        right = mid;
91      else
92        left = mid + 1;
93    }
94    return -1;
95  }
96
97  int FindInSorted(const T& item) const
98  {
99    int left = 0, right = Size();
100    while (left != right)
101    {
102      int mid = (left + right) / 2;
103      const T& midValue = (*this)[mid];
104      if (item == midValue)
105        return mid;
106      if (item < midValue)
107        right = mid;
108      else
109        left = mid + 1;
110    }
111    return -1;
112  }
113
114  int AddToUniqueSorted(const T& item)
115  {
116    int left = 0, right = Size();
117    while (left != right)
118    {
119      int mid = (left + right) / 2;
120      const T& midValue = (*this)[mid];
121      if (item == midValue)
122        return mid;
123      if (item < midValue)
124        right = mid;
125      else
126        left = mid + 1;
127    }
128    Insert(right, item);
129    return right;
130  }
131
132  static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param)
133  {
134    T temp = p[k];
135    for (;;)
136    {
137      int s = (k << 1);
138      if (s > size)
139        break;
140      if (s < size && compare(p + s + 1, p + s, param) > 0)
141        s++;
142      if (compare(&temp, p + s, param) >= 0)
143        break;
144      p[k] = p[s];
145      k = s;
146    }
147    p[k] = temp;
148  }
149
150  void Sort(int (*compare)(const T*, const T*, void *), void *param)
151  {
152    int size = _size;
153    if (size <= 1)
154      return;
155    T* p = (&Front()) - 1;
156    {
157      int i = size / 2;
158      do
159        SortRefDown(p, i, size, compare, param);
160      while (--i != 0);
161    }
162    do
163    {
164      T temp = p[size];
165      p[size--] = p[1];
166      p[1] = temp;
167      SortRefDown(p, 1, size, compare, param);
168    }
169    while (size > 1);
170  }
171};
172
173typedef CRecordVector<int> CIntVector;
174typedef CRecordVector<unsigned int> CUIntVector;
175typedef CRecordVector<bool> CBoolVector;
176typedef CRecordVector<unsigned char> CByteVector;
177typedef CRecordVector<void *> CPointerVector;
178
179template <class T>
180class CObjectVector: public CPointerVector
181{
182public:
183  CObjectVector() {};
184  ~CObjectVector() { Clear(); };
185  CObjectVector(const CObjectVector &v): CPointerVector() { *this = v; }
186  CObjectVector& operator=(const CObjectVector &v)
187  {
188    Clear();
189    return (*this += v);
190  }
191  CObjectVector& operator+=(const CObjectVector &v)
192  {
193    int size = v.Size();
194    Reserve(Size() + size);
195    for (int i = 0; i < size; i++)
196      Add(v[i]);
197    return *this;
198  }
199  const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
200  T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
201  T& Front() { return operator[](0); }
202  const T& Front() const { return operator[](0); }
203  T& Back() { return operator[](_size - 1); }
204  const T& Back() const { return operator[](_size - 1); }
205  int Add(const T& item) { return CPointerVector::Add(new T(item)); }
206  void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); }
207  virtual void Delete(int index, int num = 1)
208  {
209    TestIndexAndCorrectNum(index, num);
210    for (int i = 0; i < num; i++)
211      delete (T *)(((void **)_items)[index + i]);
212    CPointerVector::Delete(index, num);
213  }
214  int Find(const T& item) const
215  {
216    for (int i = 0; i < Size(); i++)
217      if (item == (*this)[i])
218        return i;
219    return -1;
220  }
221  int FindInSorted(const T& item) const
222  {
223    int left = 0, right = Size();
224    while (left != right)
225    {
226      int mid = (left + right) / 2;
227      const T& midValue = (*this)[mid];
228      if (item == midValue)
229        return mid;
230      if (item < midValue)
231        right = mid;
232      else
233        left = mid + 1;
234    }
235    return -1;
236  }
237  int AddToSorted(const T& item)
238  {
239    int left = 0, right = Size();
240    while (left != right)
241    {
242      int mid = (left + right) / 2;
243      const T& midValue = (*this)[mid];
244      if (item == midValue)
245      {
246        right = mid + 1;
247        break;
248      }
249      if (item < midValue)
250        right = mid;
251      else
252        left = mid + 1;
253    }
254    Insert(right, item);
255    return right;
256  }
257
258  void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
259    { CPointerVector::Sort(compare, param); }
260
261  static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
262    { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
263  void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
264};
265
266#endif
267