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