1 // Common/Vector.h

     2 

     3 #ifndef __COMMON_VECTOR_H

     4 #define __COMMON_VECTOR_H

     5 

     6 #include "Defs.h"

     7 

     8 class CBaseRecordVector

     9 {

    10   void MoveItems(int destIndex, int srcIndex);

    11 protected:

    12   int _capacity;

    13   int _size;

    14   void *_items;

    15   size_t _itemSize;

    16   

    17   void ReserveOnePosition();

    18   void InsertOneItem(int index);

    19   void TestIndexAndCorrectNum(int index, int &num) const

    20     { if (index + num > _size) num = _size - index; } 

    21 public:

    22   CBaseRecordVector(size_t itemSize):

    23       _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}

    24   virtual ~CBaseRecordVector();

    25   void Free();

    26   int Size() const { return _size; }

    27   bool IsEmpty() const { return (_size == 0); }

    28   void Reserve(int newCapacity);

    29   virtual void Delete(int index, int num = 1);

    30   void Clear();

    31   void DeleteFrom(int index);

    32   void DeleteBack();

    33 };

    34 

    35 template <class T>

    36 class CRecordVector: public CBaseRecordVector

    37 {

    38 public:

    39   CRecordVector():CBaseRecordVector(sizeof(T)){};

    40   CRecordVector(const CRecordVector &v):

    41     CBaseRecordVector(sizeof(T)) { *this = v;}

    42   CRecordVector& operator=(const CRecordVector &v)

    43   {

    44     Clear();

    45     return (*this += v);

    46   }

    47   CRecordVector& operator+=(const CRecordVector &v)

    48   {

    49     int size = v.Size();

    50     Reserve(Size() + size);

    51     for(int i = 0; i < size; i++)

    52       Add(v[i]);

    53     return *this;

    54   }

    55   int Add(T item)

    56   {

    57     ReserveOnePosition();

    58     ((T *)_items)[_size] = item;

    59     return _size++;

    60   }

    61   void Insert(int index, T item)

    62   {

    63     InsertOneItem(index);

    64     ((T *)_items)[index] = item;

    65   }

    66   // T* GetPointer() const { return (T*)_items; }

    67   // operator const T *() const { return _items; };

    68   const T& operator[](int index) const { return ((T *)_items)[index]; }

    69   T& operator[](int index) { return ((T *)_items)[index]; }

    70   const T& Front() const { return operator[](0); }

    71   T& Front()   { return operator[](0); }

    72   const T& Back() const { return operator[](_size - 1); }

    73   T& Back()   { return operator[](_size - 1); }

    74 

    75   void Swap(int i, int j)

    76   {

    77     T temp = operator[](i);

    78     operator[](i) = operator[](j);

    79     operator[](j) = temp;

    80   }

    81 

    82   int FindInSorted(const T& item) const

    83   {

    84     int left = 0, right = Size(); 

    85     while (left != right)

    86     {

    87       int mid = (left + right) / 2;

    88       const T& midValue = (*this)[mid];

    89       if (item == midValue)

    90         return mid;

    91       if (item < midValue)

    92         right = mid;

    93       else

    94         left = mid + 1;

    95     }

    96     return -1;

    97   }

    98 

    99   int AddToUniqueSorted(const T& item)

   100   {

   101     int left = 0, right = Size(); 

   102     while (left != right)

   103     {

   104       int mid = (left + right) / 2;

   105       const T& midValue = (*this)[mid];

   106       if (item == midValue)

   107         return mid;

   108       if (item < midValue)

   109         right = mid;

   110       else

   111         left = mid + 1;

   112     }

   113     Insert(right, item);

   114     return right;

   115   }

   116 

   117   static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param)

   118   { 

   119     T temp = p[k];

   120     for (;;)

   121     {

   122       int s = (k << 1);

   123       if (s > size)

   124         break;

   125       if (s < size && compare(p + s + 1, p + s, param) > 0)

   126         s++;

   127       if (compare(&temp, p + s, param) >= 0)

   128         break;

   129       p[k] = p[s]; 

   130       k = s;

   131     } 

   132     p[k] = temp; 

   133   }

   134 

   135   void Sort(int (*compare)(const T*, const T*, void *), void *param)

   136   {

   137     int size = _size;

   138     if (size <= 1)

   139       return;

   140     T* p = (&Front()) - 1;

   141     {

   142       int i = size / 2;

   143       do

   144         SortRefDown(p, i, size, compare, param);

   145       while(--i != 0);

   146     }

   147     do

   148     {

   149       T temp = p[size];

   150       p[size--] = p[1];

   151       p[1] = temp;

   152       SortRefDown(p, 1, size, compare, param);

   153     }

   154     while (size > 1);

   155   }

   156 };

   157 

   158 typedef CRecordVector<int> CIntVector;

   159 typedef CRecordVector<unsigned int> CUIntVector;

   160 typedef CRecordVector<bool> CBoolVector;

   161 typedef CRecordVector<unsigned char> CByteVector;

   162 typedef CRecordVector<void *> CPointerVector;

   163 

   164 template <class T>

   165 class CObjectVector: public CPointerVector

   166 {

   167 public:

   168   CObjectVector(){};

   169   ~CObjectVector() { Clear(); }

   170   CObjectVector(const CObjectVector &objectVector)

   171     { *this = objectVector; }

   172   CObjectVector& operator=(const CObjectVector &objectVector)

   173   {

   174     Clear();

   175     return (*this += objectVector);

   176   }

   177   CObjectVector& operator+=(const CObjectVector &objectVector)

   178   {

   179     int size = objectVector.Size();

   180     Reserve(Size() + size);

   181     for(int i = 0; i < size; i++)

   182       Add(objectVector[i]);

   183     return *this;

   184   }

   185   const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }

   186   T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }

   187   T& Front() { return operator[](0); }

   188   const T& Front() const { return operator[](0); }

   189   T& Back() { return operator[](_size - 1); }

   190   const T& Back() const { return operator[](_size - 1); }

   191   int Add(const T& item)

   192     { return CPointerVector::Add(new T(item)); }

   193   void Insert(int index, const T& item)

   194     { CPointerVector::Insert(index, new T(item)); }

   195   virtual void Delete(int index, int num = 1)

   196   {

   197     TestIndexAndCorrectNum(index, num);

   198     for(int i = 0; i < num; i++)

   199       delete (T *)(((void **)_items)[index + i]);

   200     CPointerVector::Delete(index, num);

   201   }

   202   int Find(const T& item) const

   203   {

   204     for(int i = 0; i < Size(); i++)

   205       if (item == (*this)[i])

   206         return i;

   207       return -1;

   208   }

   209   int FindInSorted(const T& item) const

   210   {

   211     int left = 0, right = Size(); 

   212     while (left != right)

   213     {

   214       int mid = (left + right) / 2;

   215       const T& midValue = (*this)[mid];

   216       if (item == midValue)

   217         return mid;

   218       if (item < midValue)

   219         right = mid;

   220       else

   221         left = mid + 1;

   222     }

   223     return -1;

   224   }

   225   int AddToSorted(const T& item)

   226   {

   227     int left = 0, right = Size(); 

   228     while (left != right)

   229     {

   230       int mid = (left + right) / 2;

   231       const T& midValue = (*this)[mid];

   232       if (item == midValue)

   233       {

   234         right = mid + 1;

   235         break;

   236       }

   237       if (item < midValue)

   238         right = mid;

   239       else

   240         left = mid + 1;

   241     }

   242     Insert(right, item);

   243     return right;

   244   }

   245 

   246   void Sort(int (*compare)(void *const *, void *const *, void *), void *param) 

   247     { CPointerVector::Sort(compare, param); }

   248 

   249   static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)

   250     { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }

   251   void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }

   252 };

   253 

   254 #endif