release/src-rt/linux/linux-2.6/scripts/squashfs/lzma/C/Common/Vector.h

   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   int Size() const { return _size; }
  26         bool IsEmpty() const { return (_size == 0); }
  27         void Reserve(int newCapacity);
  28         virtual void Delete(int index, int num = 1);
  29         void Clear();
  30   void DeleteFrom(int index);
  31   void DeleteBack();
  32 };
  33
  34 template <class T>
  35 class CRecordVector: public CBaseRecordVector
  36 {
  37 public:
  38   CRecordVector():CBaseRecordVector(sizeof(T)){};
  39   CRecordVector(const CRecordVector &v):
  40     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   void Sort(int left, int right)
  82   {
  83     if (right - left < 2)
  84       return;
  85     Swap(left, (left + right) / 2);
  86     int last = left;
  87     for (int i = left; i < right; i++)
  88       if (operator[](i) < operator[](left))
  89         Swap(++last, i);
  90     Swap(left, last);
  91     Sort(left, last);
  92     Sort(last + 1, right);
  93   }
  94   void Sort() { Sort(0, Size());  }
  95   void Sort(int left, int right, int (*compare)(const T*, const T*, void *), void *param)
  96   {
  97     if (right - left < 2)
  98       return;
  99     Swap(left, (left + right) / 2);
 100     int last = left;
 101     for (int i = left; i < right; i++)
 102       if (compare(&operator[](i), &operator[](left), param) < 0)
 103         Swap(++last, i);
 104     Swap(left, last);
 105     Sort(left, last, compare, param);
 106     Sort(last + 1, right, compare, param);
 107   }
 108
 109   void Sort(int (*compare)(const T*, const T*, void *), void *param)
 110   {
 111     Sort(0, Size(), compare, param);
 112   }
 113 };
 114
 115 typedef CRecordVector<int> CIntVector;
 116 typedef CRecordVector<unsigned int> CUIntVector;
 117 typedef CRecordVector<bool> CBoolVector;
 118 typedef CRecordVector<unsigned char> CByteVector;
 119 typedef CRecordVector<void *> CPointerVector;
 120
 121 template <class T>
 122 class CObjectVector: public CPointerVector
 123 {
 124 public:
 125   CObjectVector(){};
 126   ~CObjectVector() { Clear(); }
 127   CObjectVector(const CObjectVector &objectVector)
 128     { *this = objectVector; }
 129         CObjectVector& operator=(const CObjectVector &objectVector)
 130   {
 131     Clear();
 132     return (*this += objectVector);
 133   }
 134         CObjectVector& operator+=(const CObjectVector &objectVector)
 135   {
 136     int size = objectVector.Size();
 137     Reserve(Size() + size);
 138     for(int i = 0; i < size; i++)
 139       Add(objectVector[i]);
 140     return *this;
 141   }
 142         const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
 143         T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
 144         T& Front() { return operator[](0); }
 145         const T& Front() const { return operator[](0); }
 146         T& Back() { return operator[](_size - 1); }
 147         const T& Back() const { return operator[](_size - 1); }
 148         int Add(const T& item)
 149     { return CPointerVector::Add(new T(item)); }
 150         void Insert(int index, const T& item)
 151     { CPointerVector::Insert(index, new T(item)); }
 152         virtual void Delete(int index, int num = 1)
 153   {
 154     TestIndexAndCorrectNum(index, num);
 155     for(int i = 0; i < num; i++)
 156       delete (T *)(((void **)_items)[index + i]);
 157     CPointerVector::Delete(index, num);
 158   }
 159   int Find(const T& item) const
 160   {
 161     for(int i = 0; i < Size(); i++)
 162       if (item == (*this)[i])
 163         return i;
 164       return -1;
 165   }
 166   int FindInSorted(const T& item) const
 167   {
 168     int left = 0, right = Size();
 169     while (left != right)
 170     {
 171       int mid = (left + right) / 2;
 172       const T& midValue = (*this)[mid];
 173       if (item == midValue)
 174         return mid;
 175       if (item < midValue)
 176         right = mid;
 177       else
 178         left = mid + 1;
 179     }
 180     return -1;
 181   }
 182   int AddToSorted(const T& item)
 183   {
 184     int left = 0, right = Size();
 185     while (left != right)
 186     {
 187       int mid = (left + right) / 2;
 188       const T& midValue = (*this)[mid];
 189       if (item == midValue)
 190       {
 191         right = mid + 1;
 192         break;
 193       }
 194       if (item < midValue)
 195         right = mid;
 196       else
 197         left = mid + 1;
 198     }
 199     Insert(right, item);
 200     return right;
 201   }
 202
 203   void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
 204     { CPointerVector::Sort(compare, param); }
 205
 206   static int CompareObjectItems(void *const *a1, void *const *a2, void *param)
 207     { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
 208   void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
 209 };
 210
 211 #endif