diff options
Diffstat (limited to '3rdparty/lzma/CPP/Common/MyVector.h')
-rw-r--r-- | 3rdparty/lzma/CPP/Common/MyVector.h | 584 |
1 files changed, 472 insertions, 112 deletions
diff --git a/3rdparty/lzma/CPP/Common/MyVector.h b/3rdparty/lzma/CPP/Common/MyVector.h index 781b648bc87..14f7b11a1a7 100644 --- a/3rdparty/lzma/CPP/Common/MyVector.h +++ b/3rdparty/lzma/CPP/Common/MyVector.h @@ -1,92 +1,256 @@ -// Common/Vector.h +// Common/MyVector.h -#ifndef __COMMON_VECTOR_H -#define __COMMON_VECTOR_H +#ifndef __COMMON_MY_VECTOR_H +#define __COMMON_MY_VECTOR_H -#include "Defs.h" +#include <string.h> -class CBaseRecordVector +template <class T> +class CRecordVector { - void MoveItems(int destIndex, int srcIndex); -protected: - int _capacity; - int _size; - void *_items; - size_t _itemSize; + T *_items; + unsigned _size; + unsigned _capacity; - void ReserveOnePosition(); - void InsertOneItem(int index); - void TestIndexAndCorrectNum(int index, int &num) const - { if (index + num > _size) num = _size - index; } -public: - CBaseRecordVector(size_t itemSize): _capacity(0), _size(0), _items(0), _itemSize(itemSize) {} - virtual ~CBaseRecordVector(); - void ClearAndFree(); - int Size() const { return _size; } - bool IsEmpty() const { return (_size == 0); } - void Reserve(int newCapacity); - void ReserveDown(); - virtual void Delete(int index, int num = 1); - void Clear(); - void DeleteFrom(int index); - void DeleteBack(); -}; + 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 = new T[newCapacity]; + if (_size != 0) + memcpy(p, _items, (size_t)_size * sizeof(T)); + delete []_items; + _items = p; + _capacity = newCapacity; + } + } -template <class T> -class CRecordVector: public CBaseRecordVector -{ public: - CRecordVector(): CBaseRecordVector(sizeof(T)){}; - CRecordVector(const CRecordVector &v): CBaseRecordVector(sizeof(T)) { *this = v; } - CRecordVector& operator=(const CRecordVector &v) + + 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) + { + _items = new T[size]; + _capacity = size; + } + } + + void Reserve(unsigned newCapacity) + { + if (newCapacity > _capacity) + { + T *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(); - return (*this += v); + if (newCapacity > _capacity) + { + delete []_items; + _items = NULL; + _capacity = 0; + _items = new T[newCapacity]; + _capacity = newCapacity; + } + } + + void ClearAndSetSize(unsigned newSize) + { + ClearAndReserve(newSize); + _size = newSize; + } + + void ChangeSize_KeepData(unsigned newSize) + { + if (newSize > _capacity) + { + T *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) { - int size = v.Size(); - Reserve(Size() + size); - for (int i = 0; i < size; i++) - Add(v[i]); + unsigned size = v.Size(); + Reserve(_size + size); + if (size != 0) + memcpy(_items + _size, v._items, (size_t)size * sizeof(T)); + _size += size; return *this; } - int Add(T item) + + unsigned Add(const T item) { ReserveOnePosition(); - ((T *)_items)[_size] = item; + _items[_size] = item; return _size++; } - void Insert(int index, T item) + + void AddInReserved(const T item) { - InsertOneItem(index); - ((T *)_items)[index] = item; + _items[_size++] = item; } - // T* GetPointer() const { return (T*)_items; } - // operator const T *() const { return _items; }; - const T& operator[](int index) const { return ((T *)_items)[index]; } - T& operator[](int index) { return ((T *)_items)[index]; } - const T& Front() const { return operator[](0); } - T& Front() { return operator[](0); } - const T& Back() const { return operator[](_size - 1); } - T& Back() { return operator[](_size - 1); } - void Swap(int i, int j) + void Insert(unsigned index, const T item) { - T temp = operator[](i); - operator[](i) = operator[](j); - operator[](j) = temp; + ReserveOnePosition(); + MoveItems(index + 1, index); + _items[index] = item; + _size++; } - int FindInSorted(const T& item, int left, int right) const + 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 - 1]; } + T& Back() { return _items[_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) { - int mid = (left + right) / 2; - const T& midValue = (*this)[mid]; - if (item == midValue) + unsigned mid = (left + right) / 2; + const T midVal = (*this)[mid]; + if (item == midVal) return mid; - if (item < midValue) + if (item < midVal) right = mid; else left = mid + 1; @@ -94,16 +258,16 @@ public: return -1; } - int FindInSorted(const T& item) const + int FindInSorted2(const T &item, unsigned left, unsigned right) const { - int left = 0, right = Size(); while (left != right) { - int mid = (left + right) / 2; - const T& midValue = (*this)[mid]; - if (item == midValue) + unsigned mid = (left + right) / 2; + const T& midVal = (*this)[mid]; + int comp = item.Compare(midVal); + if (comp == 0) return mid; - if (item < midValue) + if (comp < 0) right = mid; else left = mid + 1; @@ -111,16 +275,26 @@ public: return -1; } - int AddToUniqueSorted(const T& item) + int FindInSorted(const T item) const + { + return FindInSorted(item, 0, _size); + } + + int FindInSorted2(const T &item) const { - int left = 0, right = Size(); + return FindInSorted2(item, 0, _size); + } + + unsigned AddToUniqueSorted(const T item) + { + unsigned left = 0, right = _size; while (left != right) { - int mid = (left + right) / 2; - const T& midValue = (*this)[mid]; - if (item == midValue) + unsigned mid = (left + right) / 2; + const T midVal = (*this)[mid]; + if (item == midVal) return mid; - if (item < midValue) + if (item < midVal) right = mid; else left = mid + 1; @@ -129,12 +303,31 @@ public: return right; } - static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param) + 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 (;;) { - int s = (k << 1); + unsigned s = (k << 1); if (s > size) break; if (s < size && compare(p + s + 1, p + s, param) > 0) @@ -149,12 +342,12 @@ public: void Sort(int (*compare)(const T*, const T*, void *), void *param) { - int size = _size; + unsigned size = _size; if (size <= 1) return; T* p = (&Front()) - 1; { - int i = size / 2; + unsigned i = size >> 1; do SortRefDown(p, i, size, compare, param); while (--i != 0); @@ -168,6 +361,46 @@ public: } 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[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; @@ -177,76 +410,199 @@ typedef CRecordVector<unsigned char> CByteVector; typedef CRecordVector<void *> CPointerVector; template <class T> -class CObjectVector: public CPointerVector +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() { Clear(); }; - CObjectVector(const CObjectVector &v): CPointerVector() { *this = v; } + 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(); - return (*this += v); + 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) { - int size = v.Size(); - Reserve(Size() + size); - for (int i = 0; i < size; i++) - Add(v[i]); + 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[](int index) const { return *((T *)CPointerVector::operator[](index)); } - T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); } - T& Front() { return operator[](0); } + + 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& Back() { return operator[](_size - 1); } - const T& Back() const { return operator[](_size - 1); } - int Add(const T& item) { return CPointerVector::Add(new T(item)); } - void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); } - virtual void Delete(int index, int num = 1) + T& Front() { return operator[](0); } + const T& Back() const { return operator[](_v.Size() - 1); } + T& Back() { return operator[](_v.Size() - 1); } + + 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() { - TestIndexAndCorrectNum(index, num); - for (int i = 0; i < num; i++) - delete (T *)(((void **)_items)[index + i]); - CPointerVector::Delete(index, num); + 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[_v.Size() - 1]; + _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 { - for (int i = 0; i < Size(); i++) + unsigned size = Size(); + for (unsigned i = 0; i < size; i++) if (item == (*this)[i]) return i; return -1; } + */ + int FindInSorted(const T& item) const { - int left = 0, right = Size(); + unsigned left = 0, right = Size(); while (left != right) { - int mid = (left + right) / 2; - const T& midValue = (*this)[mid]; - if (item == midValue) + unsigned mid = (left + right) / 2; + const T& midVal = (*this)[mid]; + int comp = item.Compare(midVal); + if (comp == 0) return mid; - if (item < midValue) + if (comp < 0) right = mid; else left = mid + 1; } return -1; } - int AddToSorted(const T& item) + + 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) { - int left = 0, right = Size(); + unsigned left = 0, right = Size(); while (left != right) { - int mid = (left + right) / 2; - const T& midValue = (*this)[mid]; - if (item == midValue) + unsigned mid = (left + right) / 2; + const T& midVal = (*this)[mid]; + int comp = item.Compare(midVal); + if (comp == 0) { right = mid + 1; break; } - if (item < midValue) + if (comp < 0) right = mid; else left = mid + 1; @@ -254,13 +610,17 @@ public: Insert(right, item); return right; } + */ void Sort(int (*compare)(void *const *, void *const *, void *), void *param) - { CPointerVector::Sort(compare, param); } + { _v.Sort(compare, param); } static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */) - { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); } - void Sort() { CPointerVector::Sort(CompareObjectItems, 0); } + { 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 |