Mercurial > vba-linux

     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): _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}

    23   virtual ~CBaseRecordVector();

    24   void ClearAndFree();

    25   int Size() const { return _size; }

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

    27   void Reserve(int newCapacity);

    28   void ReserveDown();

    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): CBaseRecordVector(sizeof(T)) { *this = v; }

    41   CRecordVector& operator=(const CRecordVector &v)

    42   {

    43     Clear();

    44     return (*this += v);

    45   }

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

    47   {

    48     int size = v.Size();

    49     Reserve(Size() + size);

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

    51       Add(v[i]);

    52     return *this;

    53   }

    54   int Add(T item)

    55   {

    56     ReserveOnePosition();

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

    58     return _size++;

    59   }

    60   void Insert(int index, T item)

    61   {

    62     InsertOneItem(index);

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

    64   }

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

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

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

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

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

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

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

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

    73 

    74   void Swap(int i, int j)

    75   {

    76     T temp = operator[](i);

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

    78     operator[](j) = temp;

    79   }

    80 

    81   int FindInSorted(const T& item) const

    82   {

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

    84     while (left != right)

    85     {

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

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

    88       if (item == midValue)

    89         return mid;

    90       if (item < midValue)

    91         right = mid;

    92       else

    93         left = mid + 1;

    94     }

    95     return -1;

    96   }

    97 

    98   int AddToUniqueSorted(const T& item)

    99   {

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

   101     while (left != right)

   102     {

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

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

   105       if (item == midValue)

   106         return mid;

   107       if (item < midValue)

   108         right = mid;

   109       else

   110         left = mid + 1;

   111     }

   112     Insert(right, item);

   113     return right;

   114   }

   115 

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

   117   {

   118     T temp = p[k];

   119     for (;;)

   120     {

   121       int s = (k << 1);

   122       if (s > size)

   123         break;

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

   125         s++;

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

   127         break;

   128       p[k] = p[s];

   129       k = s;

   130     }

   131     p[k] = temp;

   132   }

   133 

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

   135   {

   136     int size = _size;

   137     if (size <= 1)

   138       return;

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

   140     {

   141       int i = size / 2;

   142       do

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

   144       while (--i != 0);

   145     }

   146     do

   147     {

   148       T temp = p[size];

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

   150       p[1] = temp;

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

   152     }

   153     while (size > 1);

   154   }

   155 };

   156 

   157 typedef CRecordVector<int> CIntVector;

   158 typedef CRecordVector<unsigned int> CUIntVector;

   159 typedef CRecordVector<bool> CBoolVector;

   160 typedef CRecordVector<unsigned char> CByteVector;

   161 typedef CRecordVector<void *> CPointerVector;

   162 

   163 template <class T>

   164 class CObjectVector: public CPointerVector

   165 {

   166 public:

   167   CObjectVector() {};

   168   ~CObjectVector() { Clear(); };

   169   CObjectVector(const CObjectVector &v) { *this = v; }

   170   CObjectVector& operator=(const CObjectVector &v)

   171   {

   172     Clear();

   173     return (*this += v);

   174   }

   175   CObjectVector& operator+=(const CObjectVector &v)

   176   {

   177     int size = v.Size();

   178     Reserve(Size() + size);

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

   180       Add(v[i]);

   181     return *this;

   182   }

   183   const T& operator[](int index) const

   184   {

   185 	  return *((T *)CPointerVector::operator[](index));

   186   }

   187   T& operator[](int index)

   188   {

   189 	  return *((T *)CPointerVector::operator[](index));

   190   }

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

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

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

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

   195   int Add(const T& item) { return CPointerVector::Add(new T(item)); }

   196   void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); }

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

   198   {

   199     TestIndexAndCorrectNum(index, num);

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

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

   202     CPointerVector::Delete(index, num);

   203   }

   204   int Find(const T& item) const

   205   {

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

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

   208         return i;

   209     return -1;

   210   }

   211   int FindInSorted(const T& item) const

   212   {

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

   214     while (left != right)

   215     {

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

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

   218       if (item == midValue)

   219         return mid;

   220       if (item < midValue)

   221         right = mid;

   222       else

   223         left = mid + 1;

   224     }

   225     return -1;

   226   }

   227   int AddToSorted(const T& item)

   228   {

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

   230     while (left != right)

   231     {

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

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

   234       if (item == midValue)

   235       {

   236         right = mid + 1;

   237         break;

   238       }

   239       if (item < midValue)

   240         right = mid;

   241       else

   242         left = mid + 1;

   243     }

   244     Insert(right, item);

   245     return right;

   246   }

   247 

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

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

   250 

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

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

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

   254 };

   255 

   256 #endif
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children