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

}

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