michael@0: // Common/Vector.h
michael@0: 
michael@0: #ifndef __COMMON_VECTOR_H
michael@0: #define __COMMON_VECTOR_H
michael@0: 
michael@0: #include "Defs.h"
michael@0: 
michael@0: class CBaseRecordVector
michael@0: {
michael@0:   void MoveItems(int destIndex, int srcIndex);
michael@0: protected:
michael@0: 	int _capacity;
michael@0:   int _size;
michael@0: 	void *_items;
michael@0:   size_t _itemSize;
michael@0: 
michael@0: 	void ReserveOnePosition();
michael@0:   void InsertOneItem(int index);
michael@0:   void TestIndexAndCorrectNum(int index, int &num) const
michael@0:     { if (index + num > _size) num = _size - index; } 
michael@0: public:
michael@0:   CBaseRecordVector(size_t itemSize):
michael@0:       _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
michael@0: 	virtual ~CBaseRecordVector();
michael@0:   int Size() const { return _size; }
michael@0: 	bool IsEmpty() const { return (_size == 0); }
michael@0: 	void Reserve(int newCapacity);
michael@0: 	virtual void Delete(int index, int num = 1);
michael@0: 	void Clear();
michael@0:   void DeleteFrom(int index);
michael@0:   void DeleteBack();
michael@0: };
michael@0: 
michael@0: template <class T>
michael@0: class CRecordVector: public CBaseRecordVector
michael@0: {
michael@0: public:
michael@0:   CRecordVector():CBaseRecordVector(sizeof(T)){};
michael@0:   CRecordVector(const CRecordVector &v):
michael@0:     CBaseRecordVector(sizeof(T)) { *this = v;}
michael@0: 	CRecordVector& operator=(const CRecordVector &v)
michael@0:   {
michael@0:     Clear();
michael@0:     return (*this += v);
michael@0:   }
michael@0:   CRecordVector& operator+=(const CRecordVector &v)
michael@0:   {
michael@0:     int size = v.Size();
michael@0:     Reserve(Size() + size);
michael@0:     for(int i = 0; i < size; i++)
michael@0:       Add(v[i]);
michael@0:     return *this;
michael@0:   }
michael@0: 	int Add(T item)
michael@0:   {
michael@0:     ReserveOnePosition();
michael@0:     ((T *)_items)[_size] = item;
michael@0:     return _size++;
michael@0:   }
michael@0: 	void Insert(int index, T item)
michael@0:   {
michael@0:     InsertOneItem(index);
michael@0:     ((T *)_items)[index] = item;
michael@0:   }
michael@0:   // T* GetPointer() const { return (T*)_items; }
michael@0:   // operator const T *() const { return _items; };
michael@0:   const T& operator[](int index) const { return ((T *)_items)[index]; }
michael@0: 	T& operator[](int index) { return ((T *)_items)[index]; }
michael@0: 	const T& Front() const { return operator[](0); }
michael@0:   T& Front()   { return operator[](0); }
michael@0: 	const T& Back() const { return operator[](_size - 1); }
michael@0:   T& Back()   { return operator[](_size - 1); }
michael@0: 
michael@0:   void Swap(int i, int j)
michael@0:   {
michael@0:     T temp = operator[](i);
michael@0:     operator[](i) = operator[](j);
michael@0:     operator[](j) = temp;
michael@0:   }
michael@0: 
michael@0:   int FindInSorted(const T& item) const
michael@0:   {
michael@0:     int left = 0, right = Size(); 
michael@0:     while (left != right)
michael@0:     {
michael@0:       int mid = (left + right) / 2;
michael@0:       const T& midValue = (*this)[mid];
michael@0:       if (item == midValue)
michael@0:         return mid;
michael@0:       if (item < midValue)
michael@0:         right = mid;
michael@0:       else
michael@0:         left = mid + 1;
michael@0:     }
michael@0:     return -1;
michael@0:   }
michael@0: 
michael@0:   void Sort(int left, int right)
michael@0:   { 
michael@0:     if (right - left < 2)
michael@0:       return;
michael@0:     Swap(left, (left + right) / 2);
michael@0:     int last = left;
michael@0:     for (int i = left; i < right; i++)
michael@0:       if (operator[](i) < operator[](left))
michael@0:         Swap(++last, i);
michael@0:     Swap(left, last);
michael@0:     Sort(left, last);
michael@0:     Sort(last + 1, right);
michael@0:   }
michael@0:   void Sort() { Sort(0, Size());  }
michael@0:   void Sort(int left, int right, int (*compare)(const T*, const T*, void *), void *param)
michael@0:   { 
michael@0:     if (right - left < 2)
michael@0:       return;
michael@0:     Swap(left, (left + right) / 2);
michael@0:     int last = left;
michael@0:     for (int i = left; i < right; i++)
michael@0:       if (compare(&operator[](i), &operator[](left), param) < 0)
michael@0:         Swap(++last, i);
michael@0:     Swap(left, last);
michael@0:     Sort(left, last, compare, param);
michael@0:     Sort(last + 1, right, compare, param);
michael@0:   }
michael@0: 
michael@0:   void Sort(int (*compare)(const T*, const T*, void *), void *param) 
michael@0:   {  
michael@0:     Sort(0, Size(), compare, param);  
michael@0:   }
michael@0: };
michael@0: 
michael@0: typedef CRecordVector<int> CIntVector;
michael@0: typedef CRecordVector<unsigned int> CUIntVector;
michael@0: typedef CRecordVector<bool> CBoolVector;
michael@0: typedef CRecordVector<unsigned char> CByteVector;
michael@0: typedef CRecordVector<void *> CPointerVector;
michael@0: 
michael@0: template <class T>
michael@0: class CObjectVector: public CPointerVector
michael@0: {
michael@0: public:
michael@0:   CObjectVector(){};
michael@0:   ~CObjectVector() { Clear(); }
michael@0:   CObjectVector(const CObjectVector &objectVector)
michael@0:     { *this = objectVector; }
michael@0: 	CObjectVector& operator=(const CObjectVector &objectVector)
michael@0:   {
michael@0:     Clear();
michael@0:     return (*this += objectVector);
michael@0:   }
michael@0: 	CObjectVector& operator+=(const CObjectVector &objectVector)
michael@0:   {
michael@0:     int size = objectVector.Size();
michael@0:     Reserve(Size() + size);
michael@0:     for(int i = 0; i < size; i++)
michael@0:       Add(objectVector[i]);
michael@0:     return *this;
michael@0:   }
michael@0: 	const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
michael@0: 	T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
michael@0: 	T& Front() { return operator[](0); }
michael@0: 	const T& Front() const { return operator[](0); }
michael@0: 	T& Back() { return operator[](_size - 1); }
michael@0: 	const T& Back() const { return operator[](_size - 1); }
michael@0: 	int Add(const T& item)
michael@0:     { return CPointerVector::Add(new T(item)); }
michael@0: 	void Insert(int index, const T& item)
michael@0:     { CPointerVector::Insert(index, new T(item)); }
michael@0: 	virtual void Delete(int index, int num = 1)
michael@0:   {
michael@0:     TestIndexAndCorrectNum(index, num);
michael@0:     for(int i = 0; i < num; i++)
michael@0:       delete (T *)(((void **)_items)[index + i]);
michael@0:     CPointerVector::Delete(index, num);
michael@0:   }
michael@0:   int Find(const T& item) const
michael@0:   {
michael@0:     for(int i = 0; i < Size(); i++)
michael@0:       if (item == (*this)[i])
michael@0:         return i;
michael@0:       return -1;
michael@0:   }
michael@0:   int FindInSorted(const T& item) const
michael@0:   {
michael@0:     int left = 0, right = Size(); 
michael@0:     while (left != right)
michael@0:     {
michael@0:       int mid = (left + right) / 2;
michael@0:       const T& midValue = (*this)[mid];
michael@0:       if (item == midValue)
michael@0:         return mid;
michael@0:       if (item < midValue)
michael@0:         right = mid;
michael@0:       else
michael@0:         left = mid + 1;
michael@0:     }
michael@0:     return -1;
michael@0:   }
michael@0:   int AddToSorted(const T& item)
michael@0:   {
michael@0:     int left = 0, right = Size(); 
michael@0:     while (left != right)
michael@0:     {
michael@0:       int mid = (left + right) / 2;
michael@0:       const T& midValue = (*this)[mid];
michael@0:       if (item == midValue)
michael@0:       {
michael@0:         right = mid + 1;
michael@0:         break;
michael@0:       }
michael@0:       if (item < midValue)
michael@0:         right = mid;
michael@0:       else
michael@0:         left = mid + 1;
michael@0:     }
michael@0:     Insert(right, item);
michael@0:     return right;
michael@0:   }
michael@0: 
michael@0:   void Sort(int (*compare)(void *const *, void *const *, void *), void *param) 
michael@0:     { CPointerVector::Sort(compare, param); }
michael@0: 
michael@0:   static int CompareObjectItems(void *const *a1, void *const *a2, void *param)
michael@0:     { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
michael@0:   void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
michael@0: };
michael@0: 
michael@0: #endif