• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Common/MyVector.h
2 
3 #ifndef __COMMON_MY_VECTOR_H
4 #define __COMMON_MY_VECTOR_H
5 
6 #include <string.h>
7 
8 template <class T>
9 class CRecordVector
10 {
11   T *_items;
12   unsigned _size;
13   unsigned _capacity;
14 
MoveItems(unsigned destIndex,unsigned srcIndex)15   void MoveItems(unsigned destIndex, unsigned srcIndex)
16   {
17     memmove(_items + destIndex, _items + srcIndex, (size_t)(_size - srcIndex) * sizeof(T));
18   }
19 
ReserveOnePosition()20   void ReserveOnePosition()
21   {
22     if (_size == _capacity)
23     {
24       unsigned newCapacity = _capacity + (_capacity >> 2) + 1;
25       T *p = new T[newCapacity];
26       if (_size != 0)
27         memcpy(p, _items, (size_t)_size * sizeof(T));
28       delete []_items;
29       _items = p;
30       _capacity = newCapacity;
31     }
32   }
33 
34 public:
35 
CRecordVector()36   CRecordVector(): _items(0), _size(0), _capacity(0) {}
37 
CRecordVector(const CRecordVector & v)38   CRecordVector(const CRecordVector &v): _items(0), _size(0), _capacity(0)
39   {
40     unsigned size = v.Size();
41     if (size != 0)
42     {
43       _items = new T[size];
44       _size = size;
45       _capacity = size;
46       memcpy(_items, v._items, (size_t)size * sizeof(T));
47     }
48   }
49 
Size()50   unsigned Size() const { return _size; }
IsEmpty()51   bool IsEmpty() const { return _size == 0; }
52 
ConstructReserve(unsigned size)53   void ConstructReserve(unsigned size)
54   {
55     if (size != 0)
56     {
57       _items = new T[size];
58       _capacity = size;
59     }
60   }
61 
Reserve(unsigned newCapacity)62   void Reserve(unsigned newCapacity)
63   {
64     if (newCapacity > _capacity)
65     {
66       T *p = new T[newCapacity];
67       if (_size != 0)
68         memcpy(p, _items, (size_t)_size * sizeof(T));
69       delete []_items;
70       _items = p;
71       _capacity = newCapacity;
72     }
73   }
74 
ClearAndReserve(unsigned newCapacity)75   void ClearAndReserve(unsigned newCapacity)
76   {
77     Clear();
78     if (newCapacity > _capacity)
79     {
80       delete []_items;
81       _items = NULL;
82       _capacity = 0;
83       _items = new T[newCapacity];
84       _capacity = newCapacity;
85     }
86   }
87 
ClearAndSetSize(unsigned newSize)88   void ClearAndSetSize(unsigned newSize)
89   {
90     ClearAndReserve(newSize);
91     _size = newSize;
92   }
93 
ChangeSize_KeepData(unsigned newSize)94   void ChangeSize_KeepData(unsigned newSize)
95   {
96     if (newSize > _capacity)
97     {
98       T *p = new T[newSize];
99       if (_size != 0)
100         memcpy(p, _items, (size_t)_size * sizeof(T));
101       delete []_items;
102       _items = p;
103       _capacity = newSize;
104     }
105     _size = newSize;
106   }
107 
ReserveDown()108   void ReserveDown()
109   {
110     if (_size == _capacity)
111       return;
112     T *p = NULL;
113     if (_size != 0)
114     {
115       p = new T[_size];
116       memcpy(p, _items, (size_t)_size * sizeof(T));
117     }
118     delete []_items;
119     _items = p;
120     _capacity = _size;
121   }
122 
~CRecordVector()123   ~CRecordVector() { delete []_items; }
124 
ClearAndFree()125   void ClearAndFree()
126   {
127     delete []_items;
128     _items = NULL;
129     _size = 0;
130     _capacity = 0;
131   }
132 
Clear()133   void Clear() { _size = 0; }
134 
DeleteBack()135   void DeleteBack() { _size--; }
136 
DeleteFrom(unsigned index)137   void DeleteFrom(unsigned index)
138   {
139     // if (index <= _size)
140       _size = index;
141   }
142 
DeleteFrontal(unsigned num)143   void DeleteFrontal(unsigned num)
144   {
145     if (num != 0)
146     {
147       MoveItems(0, num);
148       _size -= num;
149     }
150   }
151 
Delete(unsigned index)152   void Delete(unsigned index)
153   {
154     MoveItems(index, index + 1);
155     _size -= 1;
156   }
157 
158   /*
159   void Delete(unsigned index, unsigned num)
160   {
161     if (num > 0)
162     {
163       MoveItems(index, index + num);
164       _size -= num;
165     }
166   }
167   */
168 
169   CRecordVector& operator=(const CRecordVector &v)
170   {
171     if (&v == this)
172       return *this;
173     unsigned size = v.Size();
174     if (size > _capacity)
175     {
176       delete []_items;
177       _capacity = 0;
178       _size = 0;
179       _items = NULL;
180       _items = new T[size];
181       _capacity = size;
182     }
183     _size = size;
184     if (size != 0)
185       memcpy(_items, v._items, (size_t)size * sizeof(T));
186     return *this;
187   }
188 
189   CRecordVector& operator+=(const CRecordVector &v)
190   {
191     unsigned size = v.Size();
192     Reserve(_size + size);
193     if (size != 0)
194       memcpy(_items + _size, v._items, (size_t)size * sizeof(T));
195     _size += size;
196     return *this;
197   }
198 
Add(const T item)199   unsigned Add(const T item)
200   {
201     ReserveOnePosition();
202     _items[_size] = item;
203     return _size++;
204   }
205 
AddInReserved(const T item)206   void AddInReserved(const T item)
207   {
208     _items[_size++] = item;
209   }
210 
Insert(unsigned index,const T item)211   void Insert(unsigned index, const T item)
212   {
213     ReserveOnePosition();
214     MoveItems(index + 1, index);
215     _items[index] = item;
216     _size++;
217   }
218 
MoveToFront(unsigned index)219   void MoveToFront(unsigned index)
220   {
221     if (index != 0)
222     {
223       T temp = _items[index];
224       memmove(_items + 1, _items, (size_t)index * sizeof(T));
225       _items[0] = temp;
226     }
227   }
228 
229   const T& operator[](unsigned index) const { return _items[index]; }
230         T& operator[](unsigned index)       { return _items[index]; }
Front()231   const T& Front() const { return _items[0]; }
Front()232         T& Front()       { return _items[0]; }
Back()233   const T& Back() const  { return _items[_size - 1]; }
Back()234         T& Back()        { return _items[_size - 1]; }
235 
236   /*
237   void Swap(unsigned i, unsigned j)
238   {
239     T temp = _items[i];
240     _items[i] = _items[j];
241     _items[j] = temp;
242   }
243   */
244 
FindInSorted(const T item,unsigned left,unsigned right)245   int FindInSorted(const T item, unsigned left, unsigned right) const
246   {
247     while (left != right)
248     {
249       unsigned mid = (left + right) / 2;
250       const T midVal = (*this)[mid];
251       if (item == midVal)
252         return mid;
253       if (item < midVal)
254         right = mid;
255       else
256         left = mid + 1;
257     }
258     return -1;
259   }
260 
FindInSorted2(const T & item,unsigned left,unsigned right)261   int FindInSorted2(const T &item, unsigned left, unsigned right) const
262   {
263     while (left != right)
264     {
265       unsigned mid = (left + right) / 2;
266       const T& midVal = (*this)[mid];
267       int comp = item.Compare(midVal);
268       if (comp == 0)
269         return mid;
270       if (comp < 0)
271         right = mid;
272       else
273         left = mid + 1;
274     }
275     return -1;
276   }
277 
FindInSorted(const T item)278   int FindInSorted(const T item) const
279   {
280     return FindInSorted(item, 0, _size);
281   }
282 
FindInSorted2(const T & item)283   int FindInSorted2(const T &item) const
284   {
285     return FindInSorted2(item, 0, _size);
286   }
287 
AddToUniqueSorted(const T item)288   unsigned AddToUniqueSorted(const T item)
289   {
290     unsigned left = 0, right = _size;
291     while (left != right)
292     {
293       unsigned mid = (left + right) / 2;
294       const T midVal = (*this)[mid];
295       if (item == midVal)
296         return mid;
297       if (item < midVal)
298         right = mid;
299       else
300         left = mid + 1;
301     }
302     Insert(right, item);
303     return right;
304   }
305 
AddToUniqueSorted2(const T & item)306   unsigned AddToUniqueSorted2(const T &item)
307   {
308     unsigned left = 0, right = _size;
309     while (left != right)
310     {
311       unsigned mid = (left + right) / 2;
312       const T& midVal = (*this)[mid];
313       int comp = item.Compare(midVal);
314       if (comp == 0)
315         return mid;
316       if (comp < 0)
317         right = mid;
318       else
319         left = mid + 1;
320     }
321     Insert(right, item);
322     return right;
323   }
324 
SortRefDown(T * p,unsigned k,unsigned size,int (* compare)(const T *,const T *,void *),void * param)325   static void SortRefDown(T* p, unsigned k, unsigned size, int (*compare)(const T*, const T*, void *), void *param)
326   {
327     T temp = p[k];
328     for (;;)
329     {
330       unsigned s = (k << 1);
331       if (s > size)
332         break;
333       if (s < size && compare(p + s + 1, p + s, param) > 0)
334         s++;
335       if (compare(&temp, p + s, param) >= 0)
336         break;
337       p[k] = p[s];
338       k = s;
339     }
340     p[k] = temp;
341   }
342 
Sort(int (* compare)(const T *,const T *,void *),void * param)343   void Sort(int (*compare)(const T*, const T*, void *), void *param)
344   {
345     unsigned size = _size;
346     if (size <= 1)
347       return;
348     T* p = (&Front()) - 1;
349     {
350       unsigned i = size >> 1;
351       do
352         SortRefDown(p, i, size, compare, param);
353       while (--i != 0);
354     }
355     do
356     {
357       T temp = p[size];
358       p[size--] = p[1];
359       p[1] = temp;
360       SortRefDown(p, 1, size, compare, param);
361     }
362     while (size > 1);
363   }
364 
SortRefDown2(T * p,unsigned k,unsigned size)365   static void SortRefDown2(T* p, unsigned k, unsigned size)
366   {
367     T temp = p[k];
368     for (;;)
369     {
370       unsigned s = (k << 1);
371       if (s > size)
372         break;
373       if (s < size && p[s + 1].Compare(p[s]) > 0)
374         s++;
375       if (temp.Compare(p[s]) >= 0)
376         break;
377       p[k] = p[s];
378       k = s;
379     }
380     p[k] = temp;
381   }
382 
Sort2()383   void Sort2()
384   {
385     unsigned size = _size;
386     if (size <= 1)
387       return;
388     T* p = (&Front()) - 1;
389     {
390       unsigned i = size >> 1;
391       do
392         SortRefDown2(p, i, size);
393       while (--i != 0);
394     }
395     do
396     {
397       T temp = p[size];
398       p[size--] = p[1];
399       p[1] = temp;
400       SortRefDown2(p, 1, size);
401     }
402     while (size > 1);
403   }
404 };
405 
406 typedef CRecordVector<int> CIntVector;
407 typedef CRecordVector<unsigned int> CUIntVector;
408 typedef CRecordVector<bool> CBoolVector;
409 typedef CRecordVector<unsigned char> CByteVector;
410 typedef CRecordVector<void *> CPointerVector;
411 
412 template <class T>
413 class CObjectVector
414 {
415   CPointerVector _v;
416 public:
Size()417   unsigned Size() const { return _v.Size(); }
IsEmpty()418   bool IsEmpty() const { return _v.IsEmpty(); }
ReserveDown()419   void ReserveDown() { _v.ReserveDown(); }
420   // void Reserve(unsigned newCapacity) { _v.Reserve(newCapacity); }
ClearAndReserve(unsigned newCapacity)421   void ClearAndReserve(unsigned newCapacity) { Clear(); _v.ClearAndReserve(newCapacity); }
422 
CObjectVector()423   CObjectVector() {};
CObjectVector(const CObjectVector & v)424   CObjectVector(const CObjectVector &v)
425   {
426     unsigned size = v.Size();
427     _v.ConstructReserve(size);
428     for (unsigned i = 0; i < size; i++)
429       _v.AddInReserved(new T(v[i]));
430   }
431   CObjectVector& operator=(const CObjectVector &v)
432   {
433     if (&v == this)
434       return *this;
435     Clear();
436     unsigned size = v.Size();
437     _v.Reserve(size);
438     for (unsigned i = 0; i < size; i++)
439       _v.AddInReserved(new T(v[i]));
440     return *this;
441   }
442 
443   CObjectVector& operator+=(const CObjectVector &v)
444   {
445     unsigned size = v.Size();
446     _v.Reserve(Size() + size);
447     for (unsigned i = 0; i < size; i++)
448       _v.AddInReserved(new T(v[i]));
449     return *this;
450   }
451 
452   const T& operator[](unsigned index) const { return *((T *)_v[index]); }
453         T& operator[](unsigned index)       { return *((T *)_v[index]); }
Front()454   const T& Front() const { return operator[](0); }
Front()455         T& Front()       { return operator[](0); }
Back()456   const T& Back() const  { return operator[](_v.Size() - 1); }
Back()457         T& Back()        { return operator[](_v.Size() - 1); }
458 
MoveToFront(unsigned index)459   void MoveToFront(unsigned index) { _v.MoveToFront(index); }
460 
Add(const T & item)461   unsigned Add(const T& item) { return _v.Add(new T(item)); }
462 
AddInReserved(const T & item)463   void AddInReserved(const T& item) { _v.AddInReserved(new T(item)); }
464 
AddNew()465   T& AddNew()
466   {
467     T *p = new T;
468     _v.Add(p);
469     return *p;
470   }
471 
AddNewInReserved()472   T& AddNewInReserved()
473   {
474     T *p = new T;
475     _v.AddInReserved(p);
476     return *p;
477   }
478 
Insert(unsigned index,const T & item)479   void Insert(unsigned index, const T& item) { _v.Insert(index, new T(item)); }
480 
InsertNew(unsigned index)481   T& InsertNew(unsigned index)
482   {
483     T *p = new T;
484     _v.Insert(index, p);
485     return *p;
486   }
487 
~CObjectVector()488   ~CObjectVector()
489   {
490     for (unsigned i = _v.Size(); i != 0;)
491       delete (T *)_v[--i];
492   }
493 
ClearAndFree()494   void ClearAndFree()
495   {
496     Clear();
497     _v.ClearAndFree();
498   }
499 
Clear()500   void Clear()
501   {
502     for (unsigned i = _v.Size(); i != 0;)
503       delete (T *)_v[--i];
504     _v.Clear();
505   }
506 
DeleteFrom(unsigned index)507   void DeleteFrom(unsigned index)
508   {
509     unsigned size = _v.Size();
510     for (unsigned i = index; i < size; i++)
511       delete (T *)_v[i];
512     _v.DeleteFrom(index);
513   }
514 
DeleteFrontal(unsigned num)515   void DeleteFrontal(unsigned num)
516   {
517     for (unsigned i = 0; i < num; i++)
518       delete (T *)_v[i];
519     _v.DeleteFrontal(num);
520   }
521 
DeleteBack()522   void DeleteBack()
523   {
524     delete (T *)_v[_v.Size() - 1];
525     _v.DeleteBack();
526   }
527 
Delete(unsigned index)528   void Delete(unsigned index)
529   {
530     delete (T *)_v[index];
531     _v.Delete(index);
532   }
533 
534   /*
535   void Delete(unsigned index, unsigned num)
536   {
537     for (unsigned i = 0; i < num; i++)
538       delete (T *)_v[index + i];
539     _v.Delete(index, num);
540   }
541   */
542 
543   /*
544   int Find(const T& item) const
545   {
546     unsigned size = Size();
547     for (unsigned i = 0; i < size; i++)
548       if (item == (*this)[i])
549         return i;
550     return -1;
551   }
552   */
553 
FindInSorted(const T & item)554   int FindInSorted(const T& item) const
555   {
556     unsigned left = 0, right = Size();
557     while (left != right)
558     {
559       unsigned mid = (left + right) / 2;
560       const T& midVal = (*this)[mid];
561       int comp = item.Compare(midVal);
562       if (comp == 0)
563         return mid;
564       if (comp < 0)
565         right = mid;
566       else
567         left = mid + 1;
568     }
569     return -1;
570   }
571 
AddToUniqueSorted(const T & item)572   unsigned AddToUniqueSorted(const T& item)
573   {
574     unsigned left = 0, right = Size();
575     while (left != right)
576     {
577       unsigned mid = (left + right) / 2;
578       const T& midVal = (*this)[mid];
579       int comp = item.Compare(midVal);
580       if (comp == 0)
581         return mid;
582       if (comp < 0)
583         right = mid;
584       else
585         left = mid + 1;
586     }
587     Insert(right, item);
588     return right;
589   }
590 
591   /*
592   unsigned AddToSorted(const T& item)
593   {
594     unsigned left = 0, right = Size();
595     while (left != right)
596     {
597       unsigned mid = (left + right) / 2;
598       const T& midVal = (*this)[mid];
599       int comp = item.Compare(midVal);
600       if (comp == 0)
601       {
602         right = mid + 1;
603         break;
604       }
605       if (comp < 0)
606         right = mid;
607       else
608         left = mid + 1;
609     }
610     Insert(right, item);
611     return right;
612   }
613   */
614 
Sort(int (* compare)(void * const *,void * const *,void *),void * param)615   void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
616     { _v.Sort(compare, param); }
617 
CompareObjectItems(void * const * a1,void * const * a2,void *)618   static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
619     { return (*(*((const T **)a1))).Compare(*(*((const T **)a2))); }
620 
Sort()621   void Sort() { _v.Sort(CompareObjectItems, 0); }
622 };
623 
624 #define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++)
625 
626 #endif
627