diff options
Diffstat (limited to 'other-licenses/7zstub/src/CPP/Common/MyVector.h')
| -rw-r--r-- | other-licenses/7zstub/src/CPP/Common/MyVector.h | 634 |
1 files changed, 634 insertions, 0 deletions
diff --git a/other-licenses/7zstub/src/CPP/Common/MyVector.h b/other-licenses/7zstub/src/CPP/Common/MyVector.h new file mode 100644 index 000000000..21125fa7d --- /dev/null +++ b/other-licenses/7zstub/src/CPP/Common/MyVector.h @@ -0,0 +1,634 @@ +// Common/MyVector.h
+
+#ifndef __COMMON_MY_VECTOR_H
+#define __COMMON_MY_VECTOR_H
+
+#include <string.h>
+
+template <class T>
+class CRecordVector
+{
+ T *_items;
+ unsigned _size;
+ unsigned _capacity;
+
+ void MoveItems(unsigned destIndex, unsigned srcIndex)
+ {
+ memmove(_items + destIndex, _items + srcIndex, (size_t)(_size - srcIndex) * sizeof(T));
+ }
+
+ void ReserveOnePosition()
+ {
+ if (_size == _capacity)
+ {
+ unsigned newCapacity = _capacity + (_capacity >> 2) + 1;
+ T *p;
+ MY_ARRAY_NEW(p, T, newCapacity);
+ // p = new T[newCapacity];
+ if (_size != 0)
+ memcpy(p, _items, (size_t)_size * sizeof(T));
+ delete []_items;
+ _items = p;
+ _capacity = newCapacity;
+ }
+ }
+
+public:
+
+ CRecordVector(): _items(0), _size(0), _capacity(0) {}
+
+ CRecordVector(const CRecordVector &v): _items(0), _size(0), _capacity(0)
+ {
+ unsigned size = v.Size();
+ if (size != 0)
+ {
+ _items = new T[size];
+ _size = size;
+ _capacity = size;
+ memcpy(_items, v._items, (size_t)size * sizeof(T));
+ }
+ }
+
+ unsigned Size() const { return _size; }
+ bool IsEmpty() const { return _size == 0; }
+
+ void ConstructReserve(unsigned size)
+ {
+ if (size != 0)
+ {
+ MY_ARRAY_NEW(_items, T, size)
+ // _items = new T[size];
+ _capacity = size;
+ }
+ }
+
+ void Reserve(unsigned newCapacity)
+ {
+ if (newCapacity > _capacity)
+ {
+ T *p;
+ MY_ARRAY_NEW(p, T, newCapacity);
+ // p = new T[newCapacity];
+ if (_size != 0)
+ memcpy(p, _items, (size_t)_size * sizeof(T));
+ delete []_items;
+ _items = p;
+ _capacity = newCapacity;
+ }
+ }
+
+ void ClearAndReserve(unsigned newCapacity)
+ {
+ Clear();
+ if (newCapacity > _capacity)
+ {
+ delete []_items;
+ _items = NULL;
+ _capacity = 0;
+ MY_ARRAY_NEW(_items, T, newCapacity)
+ // _items = new T[newCapacity];
+ _capacity = newCapacity;
+ }
+ }
+
+ void ClearAndSetSize(unsigned newSize)
+ {
+ ClearAndReserve(newSize);
+ _size = newSize;
+ }
+
+ void ChangeSize_KeepData(unsigned newSize)
+ {
+ if (newSize > _capacity)
+ {
+ T *p;
+ MY_ARRAY_NEW(p, T, newSize)
+ // p = new T[newSize];
+ if (_size != 0)
+ memcpy(p, _items, (size_t)_size * sizeof(T));
+ delete []_items;
+ _items = p;
+ _capacity = newSize;
+ }
+ _size = newSize;
+ }
+
+ void ReserveDown()
+ {
+ if (_size == _capacity)
+ return;
+ T *p = NULL;
+ if (_size != 0)
+ {
+ p = new T[_size];
+ memcpy(p, _items, (size_t)_size * sizeof(T));
+ }
+ delete []_items;
+ _items = p;
+ _capacity = _size;
+ }
+
+ ~CRecordVector() { delete []_items; }
+
+ void ClearAndFree()
+ {
+ delete []_items;
+ _items = NULL;
+ _size = 0;
+ _capacity = 0;
+ }
+
+ void Clear() { _size = 0; }
+
+ void DeleteBack() { _size--; }
+
+ void DeleteFrom(unsigned index)
+ {
+ // if (index <= _size)
+ _size = index;
+ }
+
+ void DeleteFrontal(unsigned num)
+ {
+ if (num != 0)
+ {
+ MoveItems(0, num);
+ _size -= num;
+ }
+ }
+
+ void Delete(unsigned index)
+ {
+ MoveItems(index, index + 1);
+ _size -= 1;
+ }
+
+ /*
+ void Delete(unsigned index, unsigned num)
+ {
+ if (num > 0)
+ {
+ MoveItems(index, index + num);
+ _size -= num;
+ }
+ }
+ */
+
+ CRecordVector& operator=(const CRecordVector &v)
+ {
+ if (&v == this)
+ return *this;
+ unsigned size = v.Size();
+ if (size > _capacity)
+ {
+ delete []_items;
+ _capacity = 0;
+ _size = 0;
+ _items = NULL;
+ _items = new T[size];
+ _capacity = size;
+ }
+ _size = size;
+ if (size != 0)
+ memcpy(_items, v._items, (size_t)size * sizeof(T));
+ return *this;
+ }
+
+ CRecordVector& operator+=(const CRecordVector &v)
+ {
+ unsigned size = v.Size();
+ Reserve(_size + size);
+ if (size != 0)
+ memcpy(_items + _size, v._items, (size_t)size * sizeof(T));
+ _size += size;
+ return *this;
+ }
+
+ unsigned Add(const T item)
+ {
+ ReserveOnePosition();
+ _items[_size] = item;
+ return _size++;
+ }
+
+ void AddInReserved(const T item)
+ {
+ _items[_size++] = item;
+ }
+
+ void Insert(unsigned index, const T item)
+ {
+ ReserveOnePosition();
+ MoveItems(index + 1, index);
+ _items[index] = item;
+ _size++;
+ }
+
+ void MoveToFront(unsigned index)
+ {
+ if (index != 0)
+ {
+ T temp = _items[index];
+ memmove(_items + 1, _items, (size_t)index * sizeof(T));
+ _items[0] = temp;
+ }
+ }
+
+ const T& operator[](unsigned index) const { return _items[index]; }
+ T& operator[](unsigned index) { return _items[index]; }
+ const T& Front() const { return _items[0]; }
+ T& Front() { return _items[0]; }
+ const T& Back() const { return _items[(size_t)_size - 1]; }
+ T& Back() { return _items[(size_t)_size - 1]; }
+
+ /*
+ void Swap(unsigned i, unsigned j)
+ {
+ T temp = _items[i];
+ _items[i] = _items[j];
+ _items[j] = temp;
+ }
+ */
+
+ int FindInSorted(const T item, unsigned left, unsigned right) const
+ {
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T midVal = (*this)[mid];
+ if (item == midVal)
+ return mid;
+ if (item < midVal)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ return -1;
+ }
+
+ int FindInSorted2(const T &item, unsigned left, unsigned right) const
+ {
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T& midVal = (*this)[mid];
+ int comp = item.Compare(midVal);
+ if (comp == 0)
+ return mid;
+ if (comp < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ return -1;
+ }
+
+ int FindInSorted(const T item) const
+ {
+ return FindInSorted(item, 0, _size);
+ }
+
+ int FindInSorted2(const T &item) const
+ {
+ return FindInSorted2(item, 0, _size);
+ }
+
+ unsigned AddToUniqueSorted(const T item)
+ {
+ unsigned left = 0, right = _size;
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T midVal = (*this)[mid];
+ if (item == midVal)
+ return mid;
+ if (item < midVal)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ Insert(right, item);
+ return right;
+ }
+
+ unsigned AddToUniqueSorted2(const T &item)
+ {
+ unsigned left = 0, right = _size;
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T& midVal = (*this)[mid];
+ int comp = item.Compare(midVal);
+ if (comp == 0)
+ return mid;
+ if (comp < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ Insert(right, item);
+ return right;
+ }
+
+ static void SortRefDown(T* p, unsigned k, unsigned size, int (*compare)(const T*, const T*, void *), void *param)
+ {
+ T temp = p[k];
+ for (;;)
+ {
+ unsigned s = (k << 1);
+ if (s > size)
+ break;
+ if (s < size && compare(p + s + 1, p + s, param) > 0)
+ s++;
+ if (compare(&temp, p + s, param) >= 0)
+ break;
+ p[k] = p[s];
+ k = s;
+ }
+ p[k] = temp;
+ }
+
+ void Sort(int (*compare)(const T*, const T*, void *), void *param)
+ {
+ unsigned size = _size;
+ if (size <= 1)
+ return;
+ T* p = (&Front()) - 1;
+ {
+ unsigned i = size >> 1;
+ do
+ SortRefDown(p, i, size, compare, param);
+ while (--i != 0);
+ }
+ do
+ {
+ T temp = p[size];
+ p[size--] = p[1];
+ p[1] = temp;
+ SortRefDown(p, 1, size, compare, param);
+ }
+ while (size > 1);
+ }
+
+ static void SortRefDown2(T* p, unsigned k, unsigned size)
+ {
+ T temp = p[k];
+ for (;;)
+ {
+ unsigned s = (k << 1);
+ if (s > size)
+ break;
+ if (s < size && p[(size_t)s + 1].Compare(p[s]) > 0)
+ s++;
+ if (temp.Compare(p[s]) >= 0)
+ break;
+ p[k] = p[s];
+ k = s;
+ }
+ p[k] = temp;
+ }
+
+ void Sort2()
+ {
+ unsigned size = _size;
+ if (size <= 1)
+ return;
+ T* p = (&Front()) - 1;
+ {
+ unsigned i = size >> 1;
+ do
+ SortRefDown2(p, i, size);
+ while (--i != 0);
+ }
+ do
+ {
+ T temp = p[size];
+ p[size--] = p[1];
+ p[1] = temp;
+ SortRefDown2(p, 1, size);
+ }
+ while (size > 1);
+ }
+};
+
+typedef CRecordVector<int> CIntVector;
+typedef CRecordVector<unsigned int> CUIntVector;
+typedef CRecordVector<bool> CBoolVector;
+typedef CRecordVector<unsigned char> CByteVector;
+typedef CRecordVector<void *> CPointerVector;
+
+template <class T>
+class CObjectVector
+{
+ CPointerVector _v;
+public:
+ unsigned Size() const { return _v.Size(); }
+ bool IsEmpty() const { return _v.IsEmpty(); }
+ void ReserveDown() { _v.ReserveDown(); }
+ // void Reserve(unsigned newCapacity) { _v.Reserve(newCapacity); }
+ void ClearAndReserve(unsigned newCapacity) { Clear(); _v.ClearAndReserve(newCapacity); }
+
+ CObjectVector() {};
+ CObjectVector(const CObjectVector &v)
+ {
+ unsigned size = v.Size();
+ _v.ConstructReserve(size);
+ for (unsigned i = 0; i < size; i++)
+ _v.AddInReserved(new T(v[i]));
+ }
+ CObjectVector& operator=(const CObjectVector &v)
+ {
+ if (&v == this)
+ return *this;
+ Clear();
+ unsigned size = v.Size();
+ _v.Reserve(size);
+ for (unsigned i = 0; i < size; i++)
+ _v.AddInReserved(new T(v[i]));
+ return *this;
+ }
+
+ CObjectVector& operator+=(const CObjectVector &v)
+ {
+ unsigned size = v.Size();
+ _v.Reserve(Size() + size);
+ for (unsigned i = 0; i < size; i++)
+ _v.AddInReserved(new T(v[i]));
+ return *this;
+ }
+
+ const T& operator[](unsigned index) const { return *((T *)_v[index]); }
+ T& operator[](unsigned index) { return *((T *)_v[index]); }
+ const T& Front() const { return operator[](0); }
+ T& Front() { return operator[](0); }
+ const T& Back() const { return *(T *)_v.Back(); }
+ T& Back() { return *(T *)_v.Back(); }
+
+ void MoveToFront(unsigned index) { _v.MoveToFront(index); }
+
+ unsigned Add(const T& item) { return _v.Add(new T(item)); }
+
+ void AddInReserved(const T& item) { _v.AddInReserved(new T(item)); }
+
+ T& AddNew()
+ {
+ T *p = new T;
+ _v.Add(p);
+ return *p;
+ }
+
+ T& AddNewInReserved()
+ {
+ T *p = new T;
+ _v.AddInReserved(p);
+ return *p;
+ }
+
+ void Insert(unsigned index, const T& item) { _v.Insert(index, new T(item)); }
+
+ T& InsertNew(unsigned index)
+ {
+ T *p = new T;
+ _v.Insert(index, p);
+ return *p;
+ }
+
+ ~CObjectVector()
+ {
+ for (unsigned i = _v.Size(); i != 0;)
+ delete (T *)_v[--i];
+ }
+
+ void ClearAndFree()
+ {
+ Clear();
+ _v.ClearAndFree();
+ }
+
+ void Clear()
+ {
+ for (unsigned i = _v.Size(); i != 0;)
+ delete (T *)_v[--i];
+ _v.Clear();
+ }
+
+ void DeleteFrom(unsigned index)
+ {
+ unsigned size = _v.Size();
+ for (unsigned i = index; i < size; i++)
+ delete (T *)_v[i];
+ _v.DeleteFrom(index);
+ }
+
+ void DeleteFrontal(unsigned num)
+ {
+ for (unsigned i = 0; i < num; i++)
+ delete (T *)_v[i];
+ _v.DeleteFrontal(num);
+ }
+
+ void DeleteBack()
+ {
+ delete (T *)_v.Back();
+ _v.DeleteBack();
+ }
+
+ void Delete(unsigned index)
+ {
+ delete (T *)_v[index];
+ _v.Delete(index);
+ }
+
+ /*
+ void Delete(unsigned index, unsigned num)
+ {
+ for (unsigned i = 0; i < num; i++)
+ delete (T *)_v[index + i];
+ _v.Delete(index, num);
+ }
+ */
+
+ /*
+ int Find(const T& item) const
+ {
+ unsigned size = Size();
+ for (unsigned i = 0; i < size; i++)
+ if (item == (*this)[i])
+ return i;
+ return -1;
+ }
+ */
+
+ int FindInSorted(const T& item) const
+ {
+ unsigned left = 0, right = Size();
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T& midVal = (*this)[mid];
+ int comp = item.Compare(midVal);
+ if (comp == 0)
+ return mid;
+ if (comp < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ return -1;
+ }
+
+ unsigned AddToUniqueSorted(const T& item)
+ {
+ unsigned left = 0, right = Size();
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T& midVal = (*this)[mid];
+ int comp = item.Compare(midVal);
+ if (comp == 0)
+ return mid;
+ if (comp < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ Insert(right, item);
+ return right;
+ }
+
+ /*
+ unsigned AddToSorted(const T& item)
+ {
+ unsigned left = 0, right = Size();
+ while (left != right)
+ {
+ unsigned mid = (left + right) / 2;
+ const T& midVal = (*this)[mid];
+ int comp = item.Compare(midVal);
+ if (comp == 0)
+ {
+ right = mid + 1;
+ break;
+ }
+ if (comp < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ Insert(right, item);
+ return right;
+ }
+ */
+
+ void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
+ { _v.Sort(compare, param); }
+
+ static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
+ { return (*(*((const T **)a1))).Compare(*(*((const T **)a2))); }
+
+ void Sort() { _v.Sort(CompareObjectItems, 0); }
+};
+
+#define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++)
+
+#endif
|