Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/Common/MyVector.h @ 1:f9f4f1b99eed

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