Debian Codegraph @

utils/lzma/SRC/Common/Vector.h

raw
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):
23 _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
24 virtual ~CBaseRecordVector();
25 int Size() const { return _size; }
26 bool IsEmpty() const { return (_size == 0); }
27 void Reserve(int newCapacity);
28 virtual void Delete(int index, int num = 1);
29 void Clear();
30 void DeleteFrom(int index);
31 void DeleteBack();
32 };
33
34 template <class T>
35 class CRecordVector: public CBaseRecordVector
36 {
37 public:
38 CRecordVector():CBaseRecordVector(sizeof(T)){};
39 CRecordVector(const CRecordVector &v):
40 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 static int
74 #ifdef _MSC_VER
75 __cdecl
76 #endif
77 CompareRecordItems(const void *a1, const void *a2)
78 { return MyCompare(*((const T *)a1), *((const T *)a2)); }
79 void Sort()
80 { qsort(&Front(), Size(), _itemSize, CompareRecordItems); }
81 };
82
83 typedef CRecordVector<int> CIntVector;
84 typedef CRecordVector<unsigned int> CUIntVector;
85 typedef CRecordVector<bool> CBoolVector;
86 typedef CRecordVector<unsigned char> CByteVector;
87 typedef CRecordVector<void *> CPointerVector;
88
89 template <class T>
90 class CObjectVector: public CPointerVector
91 {
92 public:
93 CObjectVector(){};
94 ~CObjectVector() { Clear(); }
95 CObjectVector(const CObjectVector &objectVector)
96 { *this = objectVector; }
97 CObjectVector& operator=(const CObjectVector &objectVector)
98 {
99 Clear();
100 return (*this += objectVector);
101 }
102 CObjectVector& operator+=(const CObjectVector &objectVector)
103 {
104 int size = objectVector.Size();
105 Reserve(Size() + size);
106 for(int i = 0; i < size; i++)
107 Add(objectVector[i]);
108 return *this;
109 }
110 const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
111 T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
112 T& Front() { return operator[](0); }
113 const T& Front() const { return operator[](0); }
114 T& Back() { return operator[](_size - 1); }
115 const T& Back() const { return operator[](_size - 1); }
116 int Add(const T& item)
117 { return CPointerVector::Add(new T(item)); }
118 void Insert(int index, const T& item)
119 { CPointerVector::Insert(index, new T(item)); }
120 virtual void Delete(int index, int num = 1)
121 {
122 TestIndexAndCorrectNum(index, num);
123 for(int i = 0; i < num; i++)
124 delete (T *)(((void **)_items)[index + i]);
125 CPointerVector::Delete(index, num);
126 }
127 int Find(const T& item) const
128 {
129 for(int i = 0; i < Size(); i++)
130 if (item == (*this)[i])
131 return i;
132 return -1;
133 }
134 int FindInSorted(const T& item) const
135 {
136 int left = 0, right = Size();
137 while (left != right)
138 {
139 int mid = (left + right) / 2;
140 const T& midValue = (*this)[mid];
141 if (item == midValue)
142 return mid;
143 if (item < midValue)
144 right = mid;
145 else
146 left = mid + 1;
147 }
148 return -1;
149 }
150 int AddToSorted(const T& item)
151 {
152 int left = 0, right = Size();
153 while (left != right)
154 {
155 int mid = (left + right) / 2;
156 const T& midValue = (*this)[mid];
157 if (item == midValue)
158 {
159 right = mid + 1;
160 break;
161 }
162 if (item < midValue)
163 right = mid;
164 else
165 left = mid + 1;
166 }
167 Insert(right, item);
168 return right;
169 }
170 static int
171 #ifdef _MSC_VER
172 __cdecl
173 #endif
174 CompareObjectItems(const void *a1, const void *a2)
175 { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
176 void Sort()
177 {
178 CPointerVector &pointerVector = *this;
179 qsort(&pointerVector[0], Size(), sizeof(void *), CompareObjectItems);
180 }
181 };
182
183 #endif