repo sync | baa3858 | 2013-07-26 17:53:31 -0700 | [diff] [blame] | 1 | // Common/Vector.h
|
| 2 |
|
| 3 | #ifndef __COMMON_VECTOR_H
|
| 4 | #define __COMMON_VECTOR_H
|
| 5 |
|
| 6 | #include "Defs.h"
|
| 7 |
|
| 8 | class CBaseRecordVector
|
| 9 | {
|
| 10 | void MoveItems(int destIndex, int srcIndex);
|
| 11 | protected:
|
| 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; }
|
| 21 | public:
|
| 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 |
|
| 35 | template <class T>
|
| 36 | class CRecordVector: public CBaseRecordVector
|
| 37 | {
|
| 38 | public:
|
| 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 |
|
| 173 | typedef CRecordVector<int> CIntVector;
|
| 174 | typedef CRecordVector<unsigned int> CUIntVector;
|
| 175 | typedef CRecordVector<bool> CBoolVector;
|
| 176 | typedef CRecordVector<unsigned char> CByteVector;
|
| 177 | typedef CRecordVector<void *> CPointerVector;
|
| 178 |
|
| 179 | template <class T>
|
| 180 | class CObjectVector: public CPointerVector
|
| 181 | {
|
| 182 | public:
|
| 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
|