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