1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/other-licenses/7zstub/src/Common/Vector.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,228 @@
1.4 +// Common/Vector.h
1.5 +
1.6 +#ifndef __COMMON_VECTOR_H
1.7 +#define __COMMON_VECTOR_H
1.8 +
1.9 +#include "Defs.h"
1.10 +
1.11 +class CBaseRecordVector
1.12 +{
1.13 + void MoveItems(int destIndex, int srcIndex);
1.14 +protected:
1.15 + int _capacity;
1.16 + int _size;
1.17 + void *_items;
1.18 + size_t _itemSize;
1.19 +
1.20 + void ReserveOnePosition();
1.21 + void InsertOneItem(int index);
1.22 + void TestIndexAndCorrectNum(int index, int &num) const
1.23 + { if (index + num > _size) num = _size - index; }
1.24 +public:
1.25 + CBaseRecordVector(size_t itemSize):
1.26 + _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
1.27 + virtual ~CBaseRecordVector();
1.28 + int Size() const { return _size; }
1.29 + bool IsEmpty() const { return (_size == 0); }
1.30 + void Reserve(int newCapacity);
1.31 + virtual void Delete(int index, int num = 1);
1.32 + void Clear();
1.33 + void DeleteFrom(int index);
1.34 + void DeleteBack();
1.35 +};
1.36 +
1.37 +template <class T>
1.38 +class CRecordVector: public CBaseRecordVector
1.39 +{
1.40 +public:
1.41 + CRecordVector():CBaseRecordVector(sizeof(T)){};
1.42 + CRecordVector(const CRecordVector &v):
1.43 + CBaseRecordVector(sizeof(T)) { *this = v;}
1.44 + CRecordVector& operator=(const CRecordVector &v)
1.45 + {
1.46 + Clear();
1.47 + return (*this += v);
1.48 + }
1.49 + CRecordVector& operator+=(const CRecordVector &v)
1.50 + {
1.51 + int size = v.Size();
1.52 + Reserve(Size() + size);
1.53 + for(int i = 0; i < size; i++)
1.54 + Add(v[i]);
1.55 + return *this;
1.56 + }
1.57 + int Add(T item)
1.58 + {
1.59 + ReserveOnePosition();
1.60 + ((T *)_items)[_size] = item;
1.61 + return _size++;
1.62 + }
1.63 + void Insert(int index, T item)
1.64 + {
1.65 + InsertOneItem(index);
1.66 + ((T *)_items)[index] = item;
1.67 + }
1.68 + // T* GetPointer() const { return (T*)_items; }
1.69 + // operator const T *() const { return _items; };
1.70 + const T& operator[](int index) const { return ((T *)_items)[index]; }
1.71 + T& operator[](int index) { return ((T *)_items)[index]; }
1.72 + const T& Front() const { return operator[](0); }
1.73 + T& Front() { return operator[](0); }
1.74 + const T& Back() const { return operator[](_size - 1); }
1.75 + T& Back() { return operator[](_size - 1); }
1.76 +
1.77 + void Swap(int i, int j)
1.78 + {
1.79 + T temp = operator[](i);
1.80 + operator[](i) = operator[](j);
1.81 + operator[](j) = temp;
1.82 + }
1.83 +
1.84 + int FindInSorted(const T& item) const
1.85 + {
1.86 + int left = 0, right = Size();
1.87 + while (left != right)
1.88 + {
1.89 + int mid = (left + right) / 2;
1.90 + const T& midValue = (*this)[mid];
1.91 + if (item == midValue)
1.92 + return mid;
1.93 + if (item < midValue)
1.94 + right = mid;
1.95 + else
1.96 + left = mid + 1;
1.97 + }
1.98 + return -1;
1.99 + }
1.100 +
1.101 + void Sort(int left, int right)
1.102 + {
1.103 + if (right - left < 2)
1.104 + return;
1.105 + Swap(left, (left + right) / 2);
1.106 + int last = left;
1.107 + for (int i = left; i < right; i++)
1.108 + if (operator[](i) < operator[](left))
1.109 + Swap(++last, i);
1.110 + Swap(left, last);
1.111 + Sort(left, last);
1.112 + Sort(last + 1, right);
1.113 + }
1.114 + void Sort() { Sort(0, Size()); }
1.115 + void Sort(int left, int right, int (*compare)(const T*, const T*, void *), void *param)
1.116 + {
1.117 + if (right - left < 2)
1.118 + return;
1.119 + Swap(left, (left + right) / 2);
1.120 + int last = left;
1.121 + for (int i = left; i < right; i++)
1.122 + if (compare(&operator[](i), &operator[](left), param) < 0)
1.123 + Swap(++last, i);
1.124 + Swap(left, last);
1.125 + Sort(left, last, compare, param);
1.126 + Sort(last + 1, right, compare, param);
1.127 + }
1.128 +
1.129 + void Sort(int (*compare)(const T*, const T*, void *), void *param)
1.130 + {
1.131 + Sort(0, Size(), compare, param);
1.132 + }
1.133 +};
1.134 +
1.135 +typedef CRecordVector<int> CIntVector;
1.136 +typedef CRecordVector<unsigned int> CUIntVector;
1.137 +typedef CRecordVector<bool> CBoolVector;
1.138 +typedef CRecordVector<unsigned char> CByteVector;
1.139 +typedef CRecordVector<void *> CPointerVector;
1.140 +
1.141 +template <class T>
1.142 +class CObjectVector: public CPointerVector
1.143 +{
1.144 +public:
1.145 + CObjectVector(){};
1.146 + ~CObjectVector() { Clear(); }
1.147 + CObjectVector(const CObjectVector &objectVector)
1.148 + { *this = objectVector; }
1.149 + CObjectVector& operator=(const CObjectVector &objectVector)
1.150 + {
1.151 + Clear();
1.152 + return (*this += objectVector);
1.153 + }
1.154 + CObjectVector& operator+=(const CObjectVector &objectVector)
1.155 + {
1.156 + int size = objectVector.Size();
1.157 + Reserve(Size() + size);
1.158 + for(int i = 0; i < size; i++)
1.159 + Add(objectVector[i]);
1.160 + return *this;
1.161 + }
1.162 + const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
1.163 + T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
1.164 + T& Front() { return operator[](0); }
1.165 + const T& Front() const { return operator[](0); }
1.166 + T& Back() { return operator[](_size - 1); }
1.167 + const T& Back() const { return operator[](_size - 1); }
1.168 + int Add(const T& item)
1.169 + { return CPointerVector::Add(new T(item)); }
1.170 + void Insert(int index, const T& item)
1.171 + { CPointerVector::Insert(index, new T(item)); }
1.172 + virtual void Delete(int index, int num = 1)
1.173 + {
1.174 + TestIndexAndCorrectNum(index, num);
1.175 + for(int i = 0; i < num; i++)
1.176 + delete (T *)(((void **)_items)[index + i]);
1.177 + CPointerVector::Delete(index, num);
1.178 + }
1.179 + int Find(const T& item) const
1.180 + {
1.181 + for(int i = 0; i < Size(); i++)
1.182 + if (item == (*this)[i])
1.183 + return i;
1.184 + return -1;
1.185 + }
1.186 + int FindInSorted(const T& item) const
1.187 + {
1.188 + int left = 0, right = Size();
1.189 + while (left != right)
1.190 + {
1.191 + int mid = (left + right) / 2;
1.192 + const T& midValue = (*this)[mid];
1.193 + if (item == midValue)
1.194 + return mid;
1.195 + if (item < midValue)
1.196 + right = mid;
1.197 + else
1.198 + left = mid + 1;
1.199 + }
1.200 + return -1;
1.201 + }
1.202 + int AddToSorted(const T& item)
1.203 + {
1.204 + int left = 0, right = Size();
1.205 + while (left != right)
1.206 + {
1.207 + int mid = (left + right) / 2;
1.208 + const T& midValue = (*this)[mid];
1.209 + if (item == midValue)
1.210 + {
1.211 + right = mid + 1;
1.212 + break;
1.213 + }
1.214 + if (item < midValue)
1.215 + right = mid;
1.216 + else
1.217 + left = mid + 1;
1.218 + }
1.219 + Insert(right, item);
1.220 + return right;
1.221 + }
1.222 +
1.223 + void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
1.224 + { CPointerVector::Sort(compare, param); }
1.225 +
1.226 + static int CompareObjectItems(void *const *a1, void *const *a2, void *param)
1.227 + { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
1.228 + void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
1.229 +};
1.230 +
1.231 +#endif
