Annotation of elwix/tools/oldlzma/SRC/Common/Vector.h, revision 1.1.1.1
1.1 misho 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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>