// 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 |