judge/manager/array.h

   1 #ifndef ARRAY_H
   2 #define ARRAY_H
   3
   4 typedef long unsigned int LUint;
   5 #include <cassert>
   6
   7 template <class T>
   8 class Array
   9 {
  10         public:
  11                 Array() : start(NULL), size(0), reserved(0) {}
  12                 Array(LUint newSize) : start(new T[newSize]), size(newSize), reserved(newSize) {}
  13                 ~Array() {delete [] start;}
  14
  15                 void Empty() {size = 0;}
  16                 void Add(const T & add);
  17                 void Reserve(LUint reserve);
  18                 void Resize(LUint newSize);
  19                 void RemoveBack();
  20
  21                 LUint Size() const {return size;}
  22                 LUint Capacity() const {return reserved;}
  23
  24                 void operator=(const Array & equ);
  25                 bool operator==(const Array & equ) const;
  26                 bool operator!=(const Array & equ) const {return !operator==(equ);}
  27
  28                 class Iterator
  29                 {
  30                         public:
  31                                 Iterator(const Array & from) : parent(from), index(0) {}
  32                                 Iterator(const Iterator & cpy) : parent(cpy.parent), index(cpy.index) {}
  33                                 ~Iterator() {}
  34
  35                                 bool Good() const {return index < parent.Size();}
  36
  37                                 T & operator*() const {return parent.start[index];}
  38
  39                                 void operator++() {++index;}
  40                                 void operator--() {--index;}
  41                                 void operator++(int) {operator++();}
  42                                 void operator--(int) {operator--();}
  43                                 Iterator & operator+=(int amount) {index += amount;}
  44                                 Iterator & operator-=(int amount) {index -= amount;}
  45                                 Iterator operator+(int amount) {return Iterator(*this) += amount;}
  46                                 Iterator operator-(int amount) {return Iterator(*this) -= amount;}
  47
  48                                 void operator=(const Iterator & set) {index = set.index;}
  49                                 bool operator==(const Iterator & set) {return (&parent == &(set.parent) && index == set.index);}
  50                         private:
  51                                 const Array & parent;
  52                                 LUint index;
  53                 };
  54
  55                 Iterator First() const {return Iterator(*this);}
  56                 Iterator Last() const {return Iterator(*this) -= (size-1);}
  57
  58
  59                 T & operator[](LUint at) const
  60                 {
  61                         #ifdef DEBUGALL
  62                                 printf("        Array<T>::operator[] - called for index %lu/%lu (reserved %lu)\n", at, size, reserved);
  63
  64                         #endif //DEBUG
  65                         assert(at < size); return start[at];
  66                 }
  67
  68                 int Find(const T & find)
  69                 {
  70
  71                         LUint result;
  72                         for (result = 0; result < size; result++)
  73                         {
  74                                 //printf("%p %lu/%lu\n", (void*)(start), result, size);
  75                                 if (start[result] == find)
  76                                         return (int)(result);
  77                         }
  78                         return -1;
  79                 }
  80
  81         private:
  82                 T * start;
  83                 LUint size; LUint reserved;
  84 };
  85
  86 template <class T> void Array<T>::Add(const T & add)
  87 {
  88         if (size >= reserved)
  89         {
  90                 T * old = start;
  91                 reserved *= 2; ++reserved;
  92                 start = new T[reserved];
  93                 for (LUint ii=0; ii < size; ++ii)
  94                         start[ii] = old[ii];
  95                 delete [] old;
  96         }
  97         start[size++] = add;
  98 }
  99
 100 template <class T> void Array<T>::RemoveBack()
 101 {
 102         if (size > 0)
 103                 --size;
 104 }
 105
 106 template <class T> void Array<T>::Resize(LUint newSize)
 107 {
 108         T * old = start;
 109         start = new T[newSize];
 110         for (LUint ii=0; ii < size; ++ii)
 111                 start[ii] = old[ii];
 112         size = newSize; reserved = newSize;
 113         delete [] old;
 114 }
 115
 116 template <class T> void Array<T>::Reserve(LUint newReserve)
 117 {
 118         if (newReserve > reserved)
 119         {
 120                 T * old = start;
 121                 start = new T[newReserve];
 122                 for (LUint ii=0; ii < size; ++ii)
 123                         start[ii] = old[ii];
 124                 reserved = newReserve;
 125         }
 126 }
 127
 128 #endif //ARRAY_H