| // Common/MyVector.h |
| |
| #ifndef ZIP7_INC_COMMON_MY_VECTOR_H |
| #define ZIP7_INC_COMMON_MY_VECTOR_H |
| |
| #include <string.h> |
| |
| #include "Common.h" |
| |
| const unsigned k_VectorSizeMax = ((unsigned)1 << 31) - 1; |
| |
| 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 ReAllocForNewCapacity(const unsigned newCapacity) |
| { |
| T *p; |
| Z7_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: |
| |
| void ReserveOnePosition() |
| { |
| if (_size != _capacity) |
| return; |
| if (_capacity >= k_VectorSizeMax) |
| throw 2021; |
| const unsigned rem = k_VectorSizeMax - _capacity; |
| unsigned add = (_capacity >> 2) + 1; |
| if (add > rem) |
| add = rem; |
| ReAllocForNewCapacity(_capacity + add); |
| } |
| |
| CRecordVector(): _items(NULL), _size(0), _capacity(0) {} |
| |
| CRecordVector(const CRecordVector &v): _items(NULL), _size(0), _capacity(0) |
| { |
| const unsigned size = v.Size(); |
| if (size != 0) |
| { |
| // Z7_ARRAY_NEW(_items, T, size) |
| _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) |
| { |
| Z7_ARRAY_NEW(_items, T, size) |
| // _items = new T[size]; |
| _capacity = size; |
| } |
| } |
| |
| void Reserve(unsigned newCapacity) |
| { |
| if (newCapacity > _capacity) |
| { |
| if (newCapacity > k_VectorSizeMax) |
| throw 2021; |
| ReAllocForNewCapacity(newCapacity); |
| } |
| } |
| |
| void ChangeSize_KeepData(unsigned newSize) |
| { |
| Reserve(newSize); |
| _size = newSize; |
| } |
| |
| void ClearAndReserve(unsigned newCapacity) |
| { |
| Clear(); |
| if (newCapacity > _capacity) |
| { |
| if (newCapacity > k_VectorSizeMax) |
| throw 2021; |
| delete []_items; |
| _items = NULL; |
| _capacity = 0; |
| Z7_ARRAY_NEW(_items, T, newCapacity) |
| // _items = new T[newCapacity]; |
| _capacity = newCapacity; |
| } |
| } |
| |
| void ClearAndSetSize(unsigned newSize) |
| { |
| ClearAndReserve(newSize); |
| _size = newSize; |
| } |
| |
| void ReserveDown() |
| { |
| if (_size == _capacity) |
| return; |
| T *p = NULL; |
| if (_size != 0) |
| { |
| // Z7_ARRAY_NEW(p, T, _size) |
| 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; |
| const 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) |
| { |
| const unsigned size = v.Size(); |
| if (size != 0) |
| { |
| if (_size >= k_VectorSizeMax || size > k_VectorSizeMax - _size) |
| throw 2021; |
| const unsigned newSize = _size + size; |
| Reserve(newSize); |
| memcpy(_items + _size, v._items, (size_t)size * sizeof(T)); |
| _size = newSize; |
| } |
| return *this; |
| } |
| |
| unsigned Add(const T item) |
| { |
| ReserveOnePosition(); |
| const unsigned size = _size; |
| _size = size + 1; |
| _items[size] = item; |
| return size; |
| } |
| |
| /* |
| unsigned Add2(const T &item) |
| { |
| ReserveOnePosition(); |
| const unsigned size = _size; |
| _size = size + 1; |
| _items[size] = item; |
| return size; |
| } |
| */ |
| |
| unsigned AddInReserved(const T item) |
| { |
| const unsigned size = _size; |
| _size = size + 1; |
| _items[size] = item; |
| return size; |
| } |
| |
| void Insert(unsigned index, const T item) |
| { |
| ReserveOnePosition(); |
| MoveItems(index + 1, index); |
| _items[index] = item; |
| _size++; |
| } |
| |
| void InsertInReserved(unsigned index, const T item) |
| { |
| 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& operator[](int index) const { return _items[(unsigned)index]; } |
| T& operator[](int index) { return _items[(unsigned)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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T midVal = (*this)[mid]; |
| if (item == midVal) |
| return (int)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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T& midVal = (*this)[mid]; |
| const int comp = item.Compare(midVal); |
| if (comp == 0) |
| return (int)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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const 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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T& midVal = (*this)[mid]; |
| const 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) |
| { |
| const unsigned size = v.Size(); |
| _v.ConstructReserve(size); |
| for (unsigned i = 0; i < size; i++) |
| AddInReserved(v[i]); |
| } |
| CObjectVector& operator=(const CObjectVector &v) |
| { |
| if (&v == this) |
| return *this; |
| Clear(); |
| const unsigned size = v.Size(); |
| _v.Reserve(size); |
| for (unsigned i = 0; i < size; i++) |
| AddInReserved(v[i]); |
| return *this; |
| } |
| |
| CObjectVector& operator+=(const CObjectVector &v) |
| { |
| const unsigned addSize = v.Size(); |
| if (addSize != 0) |
| { |
| const unsigned size = Size(); |
| if (size >= k_VectorSizeMax || addSize > k_VectorSizeMax - size) |
| throw 2021; |
| _v.Reserve(size + addSize); |
| for (unsigned i = 0; i < addSize; i++) |
| AddInReserved(v[i]); |
| } |
| return *this; |
| } |
| |
| const T& operator[](unsigned index) const { return *((T *)_v[index]); } |
| T& operator[](unsigned index) { return *((T *)_v[index]); } |
| const T& operator[](int index) const { return *((T *)_v[(unsigned)index]); } |
| T& operator[](int index) { return *((T *)_v[(unsigned)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) |
| { |
| _v.ReserveOnePosition(); |
| return AddInReserved(item); |
| } |
| |
| unsigned AddInReserved(const T& item) |
| { |
| return _v.AddInReserved(new T(item)); |
| } |
| |
| void ReserveOnePosition() |
| { |
| _v.ReserveOnePosition(); |
| } |
| |
| unsigned AddInReserved_Ptr_of_new(T *ptr) |
| { |
| return _v.AddInReserved(ptr); |
| } |
| |
| #define VECTOR_ADD_NEW_OBJECT(v, a) \ |
| (v).ReserveOnePosition(); \ |
| (v).AddInReserved_Ptr_of_new(new a); |
| |
| |
| T& AddNew() |
| { |
| _v.ReserveOnePosition(); |
| T *p = new T; |
| _v.AddInReserved(p); |
| return *p; |
| } |
| |
| T& AddNewInReserved() |
| { |
| T *p = new T; |
| _v.AddInReserved(p); |
| return *p; |
| } |
| |
| void Insert(unsigned index, const T& item) |
| { |
| _v.ReserveOnePosition(); |
| _v.InsertInReserved(index, new T(item)); |
| } |
| |
| T& InsertNew(unsigned index) |
| { |
| _v.ReserveOnePosition(); |
| T *p = new T; |
| _v.InsertInReserved(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) |
| { |
| const 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(int index) { Delete((unsigned)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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T& midVal = (*this)[mid]; |
| const int comp = item.Compare(midVal); |
| if (comp == 0) |
| return (int)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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T& midVal = (*this)[mid]; |
| const 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) |
| { |
| // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); |
| const unsigned mid = (left + right) / 2; |
| const T& midVal = (*this)[mid]; |
| const 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 *const *)a1))).Compare(*(*((const T *const *)a2))); } |
| |
| void Sort() { _v.Sort(CompareObjectItems, NULL); } |
| }; |
| |
| #define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++) |
| |
| #endif |