diff options
author | Igor Pavlov <ipavlov@users.sourceforge.net> | 2007-06-26 04:00:00 +0400 |
---|---|---|
committer | Kornel LesiĆski <kornel@geekhood.net> | 2016-05-28 02:15:52 +0300 |
commit | fd8b1d78b496fe38193bf8c5e86af3b43f0b022d (patch) | |
tree | 5b1e3812ed4d8b6037e5035faf3b638849f618e2 /CPP/Common/MyVector.h | |
parent | 0b33f700a66fcf7f55f92b92e0b3e5c7014d769a (diff) |
4.48 beta
Diffstat (limited to 'CPP/Common/MyVector.h')
-rwxr-xr-x | CPP/Common/MyVector.h | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/CPP/Common/MyVector.h b/CPP/Common/MyVector.h new file mode 100755 index 00000000..1bb67a1d --- /dev/null +++ b/CPP/Common/MyVector.h @@ -0,0 +1,237 @@ +// Common/Vector.h + +#ifndef __COMMON_VECTOR_H +#define __COMMON_VECTOR_H + +#include "Defs.h" + +class CBaseRecordVector +{ + void MoveItems(int destIndex, int srcIndex); +protected: + int _capacity; + int _size; + void *_items; + size_t _itemSize; + + 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 Free(); + int Size() const { return _size; } + bool IsEmpty() const { return (_size == 0); } + void Reserve(int newCapacity); + virtual void Delete(int index, int num = 1); + void Clear(); + void DeleteFrom(int index); + void DeleteBack(); +}; + +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) + { + Clear(); + return (*this += v); + } + CRecordVector& operator+=(const CRecordVector &v) + { + int size = v.Size(); + Reserve(Size() + size); + for(int i = 0; i < size; i++) + Add(v[i]); + return *this; + } + int Add(T item) + { + ReserveOnePosition(); + ((T *)_items)[_size] = item; + return _size++; + } + void Insert(int index, T item) + { + InsertOneItem(index); + ((T *)_items)[index] = 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) + { + T temp = operator[](i); + operator[](i) = operator[](j); + operator[](j) = temp; + } + + int FindInSorted(const T& item) const + { + int left = 0, right = Size(); + while (left != right) + { + int mid = (left + right) / 2; + const T& midValue = (*this)[mid]; + if (item == midValue) + return mid; + if (item < midValue) + right = mid; + else + left = mid + 1; + } + return -1; + } + + + static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param) + { + T temp = p[k]; + for (;;) + { + int 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) + { + int size = _size; + if (size <= 1) + return; + T* p = (&Front()) - 1; + { + int i = size / 2; + 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); + } +}; + +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: public CPointerVector +{ +public: + CObjectVector(){}; + ~CObjectVector() { Clear(); } + CObjectVector(const CObjectVector &objectVector) + { *this = objectVector; } + CObjectVector& operator=(const CObjectVector &objectVector) + { + Clear(); + return (*this += objectVector); + } + CObjectVector& operator+=(const CObjectVector &objectVector) + { + int size = objectVector.Size(); + Reserve(Size() + size); + for(int i = 0; i < size; i++) + Add(objectVector[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& 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) + { + TestIndexAndCorrectNum(index, num); + for(int i = 0; i < num; i++) + delete (T *)(((void **)_items)[index + i]); + CPointerVector::Delete(index, num); + } + int Find(const T& item) const + { + for(int i = 0; i < Size(); i++) + if (item == (*this)[i]) + return i; + return -1; + } + int FindInSorted(const T& item) const + { + int left = 0, right = Size(); + while (left != right) + { + int mid = (left + right) / 2; + const T& midValue = (*this)[mid]; + if (item == midValue) + return mid; + if (item < midValue) + right = mid; + else + left = mid + 1; + } + return -1; + } + int AddToSorted(const T& item) + { + int left = 0, right = Size(); + while (left != right) + { + int mid = (left + right) / 2; + const T& midValue = (*this)[mid]; + if (item == midValue) + { + right = mid + 1; + break; + } + if (item < midValue) + right = mid; + else + left = mid + 1; + } + Insert(right, item); + return right; + } + + void Sort(int (*compare)(void *const *, void *const *, void *), void *param) + { CPointerVector::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); } +}; + +#endif |