| // 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 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(); |
| }; |
| |
| 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, int left, int right) const |
| { |
| 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 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 AddToUniqueSorted(const T& item) |
| { |
| 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; |
| } |
| Insert(right, item); |
| return right; |
| } |
| |
| 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 &v): CPointerVector() { *this = v; } |
| CObjectVector& operator=(const CObjectVector &v) |
| { |
| Clear(); |
| return (*this += v); |
| } |
| CObjectVector& operator+=(const CObjectVector &v) |
| { |
| int size = v.Size(); |
| Reserve(Size() + size); |
| for (int i = 0; i < size; i++) |
| Add(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& 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 |