Source code
Revision control
Copy as Markdown
Other Tools
// Common/MyVector.h↩
↩
#ifndef __COMMON_MY_VECTOR_H↩
#define __COMMON_MY_VECTOR_H↩
↩
#include <string.h>↩
↩
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 ReserveOnePosition()↩
{↩
if (_size == _capacity)↩
{↩
unsigned newCapacity = _capacity + (_capacity >> 2) + 1;↩
T *p;↩
MY_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:↩
↩
CRecordVector(): _items(0), _size(0), _capacity(0) {}↩
↩
CRecordVector(const CRecordVector &v): _items(0), _size(0), _capacity(0)↩
{↩
unsigned size = v.Size();↩
if (size != 0)↩
{↩
_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)↩
{↩
MY_ARRAY_NEW(_items, T, size)↩
// _items = new T[size];↩
_capacity = size;↩
}↩
}↩
↩
void Reserve(unsigned newCapacity)↩
{↩
if (newCapacity > _capacity)↩
{↩
T *p;↩
MY_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;↩
}↩
}↩
↩
void ClearAndReserve(unsigned newCapacity)↩
{↩
Clear();↩
if (newCapacity > _capacity)↩
{↩
delete []_items;↩
_items = NULL;↩
_capacity = 0;↩
MY_ARRAY_NEW(_items, T, newCapacity)↩
// _items = new T[newCapacity];↩
_capacity = newCapacity;↩
}↩
}↩
↩
void ClearAndSetSize(unsigned newSize)↩
{↩
ClearAndReserve(newSize);↩
_size = newSize;↩
}↩
↩
void ChangeSize_KeepData(unsigned newSize)↩
{↩
if (newSize > _capacity)↩
{↩
T *p;↩
MY_ARRAY_NEW(p, T, newSize)↩
// p = new T[newSize];↩
if (_size != 0)↩
memcpy(p, _items, (size_t)_size * sizeof(T));↩
delete []_items;↩
_items = p;↩
_capacity = newSize;↩
}↩
_size = newSize;↩
}↩
↩
void ReserveDown()↩
{↩
if (_size == _capacity)↩
return;↩
T *p = NULL;↩
if (_size != 0)↩
{↩
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;↩
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)↩
{↩
unsigned size = v.Size();↩
Reserve(_size + size);↩
if (size != 0)↩
memcpy(_items + _size, v._items, (size_t)size * sizeof(T));↩
_size += size;↩
return *this;↩
}↩
↩
unsigned Add(const T item)↩
{↩
ReserveOnePosition();↩
_items[_size] = item;↩
return _size++;↩
}↩
↩
void AddInReserved(const T item)↩
{↩
_items[_size++] = item;↩
}↩
↩
void Insert(unsigned index, const T item)↩
{↩
ReserveOnePosition();↩
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& 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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T midVal = (*this)[mid];↩
if (item == midVal)↩
return 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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T& midVal = (*this)[mid];↩
int comp = item.Compare(midVal);↩
if (comp == 0)↩
return 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)↩
{↩
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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T& midVal = (*this)[mid];↩
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)↩
{↩
unsigned size = v.Size();↩
_v.ConstructReserve(size);↩
for (unsigned i = 0; i < size; i++)↩
_v.AddInReserved(new T(v[i]));↩
}↩
CObjectVector& operator=(const CObjectVector &v)↩
{↩
if (&v == this)↩
return *this;↩
Clear();↩
unsigned size = v.Size();↩
_v.Reserve(size);↩
for (unsigned i = 0; i < size; i++)↩
_v.AddInReserved(new T(v[i]));↩
return *this;↩
}↩
↩
CObjectVector& operator+=(const CObjectVector &v)↩
{↩
unsigned size = v.Size();↩
_v.Reserve(Size() + size);↩
for (unsigned i = 0; i < size; i++)↩
_v.AddInReserved(new T(v[i]));↩
return *this;↩
}↩
↩
const T& operator[](unsigned index) const { return *((T *)_v[index]); }↩
T& operator[](unsigned index) { return *((T *)_v[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) { return _v.Add(new T(item)); }↩
↩
void AddInReserved(const T& item) { _v.AddInReserved(new T(item)); }↩
↩
T& AddNew()↩
{↩
T *p = new T;↩
_v.Add(p);↩
return *p;↩
}↩
↩
T& AddNewInReserved()↩
{↩
T *p = new T;↩
_v.AddInReserved(p);↩
return *p;↩
}↩
↩
void Insert(unsigned index, const T& item) { _v.Insert(index, new T(item)); }↩
↩
T& InsertNew(unsigned index)↩
{↩
T *p = new T;↩
_v.Insert(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)↩
{↩
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(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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T& midVal = (*this)[mid];↩
int comp = item.Compare(midVal);↩
if (comp == 0)↩
return 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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T& midVal = (*this)[mid];↩
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)↩
{↩
unsigned mid = (left + right) / 2;↩
const T& midVal = (*this)[mid];↩
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 **)a1))).Compare(*(*((const T **)a2))); }↩
↩
void Sort() { _v.Sort(CompareObjectItems, 0); }↩
};↩
↩
#define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++)↩
↩
#endif↩