Mercurial > vba-linux

comparison 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
comparison
equal deleted inserted replaced
0:8ced16adf2e1 1:f9f4f1b99eed
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) const
82 {
83 int left = 0, right = Size();
84 while (left != right)
85 {
86 int mid = (left + right) / 2;
87 const T& midValue = (*this)[mid];
88 if (item == midValue)
89 return mid;
90 if (item < midValue)
91 right = mid;
92 else
93 left = mid + 1;
94 }
95 return -1;
96 }
97
98 int AddToUniqueSorted(const T& item)
99 {
100 int left = 0, right = Size();
101 while (left != right)
102 {
103 int mid = (left + right) / 2;
104 const T& midValue = (*this)[mid];
105 if (item == midValue)
106 return mid;
107 if (item < midValue)
108 right = mid;
109 else
110 left = mid + 1;
111 }
112 Insert(right, item);
113 return right;
114 }
115
116 static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param)
117 {
118 T temp = p[k];
119 for (;;)
120 {
121 int s = (k << 1);
122 if (s > size)
123 break;
124 if (s < size && compare(p + s + 1, p + s, param) > 0)
125 s++;
126 if (compare(&temp, p + s, param) >= 0)
127 break;
128 p[k] = p[s];
129 k = s;
130 }
131 p[k] = temp;
132 }
133
134 void Sort(int (*compare)(const T*, const T*, void *), void *param)
135 {
136 int size = _size;
137 if (size <= 1)
138 return;
139 T* p = (&Front()) - 1;
140 {
141 int i = size / 2;
142 do
143 SortRefDown(p, i, size, compare, param);
144 while (--i != 0);
145 }
146 do
147 {
148 T temp = p[size];
149 p[size--] = p[1];
150 p[1] = temp;
151 SortRefDown(p, 1, size, compare, param);
152 }
153 while (size > 1);
154 }
155 };
156
157 typedef CRecordVector<int> CIntVector;
158 typedef CRecordVector<unsigned int> CUIntVector;
159 typedef CRecordVector<bool> CBoolVector;
160 typedef CRecordVector<unsigned char> CByteVector;
161 typedef CRecordVector<void *> CPointerVector;
162
163 template <class T>
164 class CObjectVector: public CPointerVector
165 {
166 public:
167 CObjectVector() {};
168 ~CObjectVector() { Clear(); };
169 CObjectVector(const CObjectVector &v) { *this = v; }
170 CObjectVector& operator=(const CObjectVector &v)
171 {
172 Clear();
173 return (*this += v);
174 }
175 CObjectVector& operator+=(const CObjectVector &v)
176 {
177 int size = v.Size();
178 Reserve(Size() + size);
179 for (int i = 0; i < size; i++)
180 Add(v[i]);
181 return *this;
182 }
183 const T& operator[](int index) const
184 {
185 return *((T *)CPointerVector::operator[](index));
186 }
187 T& operator[](int index)
188 {
189 return *((T *)CPointerVector::operator[](index));
190 }
191 T& Front() { return operator[](0); }
192 const T& Front() const { return operator[](0); }
193 T& Back() { return operator[](_size - 1); }
194 const T& Back() const { return operator[](_size - 1); }
195 int Add(const T& item) { return CPointerVector::Add(new T(item)); }
196 void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); }
197 virtual void Delete(int index, int num = 1)
198 {
199 TestIndexAndCorrectNum(index, num);
200 for (int i = 0; i < num; i++)
201 delete (T *)(((void **)_items)[index + i]);
202 CPointerVector::Delete(index, num);
203 }
204 int Find(const T& item) const
205 {
206 for (int i = 0; i < Size(); i++)
207 if (item == (*this)[i])
208 return i;
209 return -1;
210 }
211 int FindInSorted(const T& item) const
212 {
213 int left = 0, right = Size();
214 while (left != right)
215 {
216 int mid = (left + right) / 2;
217 const T& midValue = (*this)[mid];
218 if (item == midValue)
219 return mid;
220 if (item < midValue)
221 right = mid;
222 else
223 left = mid + 1;
224 }
225 return -1;
226 }
227 int AddToSorted(const T& item)
228 {
229 int left = 0, right = Size();
230 while (left != right)
231 {
232 int mid = (left + right) / 2;
233 const T& midValue = (*this)[mid];
234 if (item == midValue)
235 {
236 right = mid + 1;
237 break;
238 }
239 if (item < midValue)
240 right = mid;
241 else
242 left = mid + 1;
243 }
244 Insert(right, item);
245 return right;
246 }
247
248 void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
249 { CPointerVector::Sort(compare, param); }
250
251 static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
252 { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
253 void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
254 };
255
256 #endif