summaryrefslogtreecommitdiffstats
path: root/CPP/Common/MyVector.h
diff options
context:
space:
mode:
Diffstat (limited to 'CPP/Common/MyVector.h')
-rwxr-xr-xCPP/Common/MyVector.h266
1 files changed, 266 insertions, 0 deletions
diff --git a/CPP/Common/MyVector.h b/CPP/Common/MyVector.h
new file mode 100755
index 0000000..24740dc
--- /dev/null
+++ b/CPP/Common/MyVector.h
@@ -0,0 +1,266 @@
+// 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