flower/include/array.hh

   1 /*
   2   (c) Han-Wen Nienhuys 1995,96,97
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #ifndef ARRAY_H
   8 #define ARRAY_H
   9 #include <assert.h>
  10
  11 #ifndef INLINE
  12 #define INLINE inline
  13 #endif
  14
  15 /// copy a bare (C-)array from #src# to #dest# sized  #count#
  16 template<class T> void arrcpy (T*dest, T const*src, int count);
  17
  18 /**
  19   Scaleable array/stack template, for a type T with default constructor.
  20
  21
  22   This template implements a scaleable vector. With (or without) range
  23   checking. The type T should have a default constructor. It is
  24   best suited for simple types, such as int, double or String, it
  25   provides a paranoidly safe replacement for the new T[int] construct.
  26
  27   You should \bf{never} store pointers to objects in an Array (since
  28   the array may be relocated without the pointer knowing it).
  29
  30   It uses stack terminology, (push, pop, top), and  can be used as a stack.
  31
  32
  33   */
  34 template<class T>
  35 class Array
  36 {
  37 protected:
  38   /// maximum length of array.
  39   int max_;
  40
  41   /// the data itself
  42   T *array_;
  43
  44   /// stretch or shrink  array.
  45   void remax (int newmax)
  46     {
  47       T* newarr = new T[newmax];
  48       size_ = (newmax < size_) ? newmax : size_;
  49       arrcpy (newarr, array_, size_);
  50
  51       delete[] array_;
  52       array_ = newarr;
  53       max_ = newmax;
  54     }
  55   int size_;
  56
  57 public:
  58   /// check invariants
  59   void OK () const ;
  60   /** report the size_.
  61       @see
  62       {setsize_}
  63   */
  64
  65   int size () const
  66     {
  67       return size_;
  68     }
  69
  70   /// POST: size () == 0
  71   void clear ()
  72     {
  73       size_ = 0;
  74     }
  75
  76   Array (T *tp, int n)
  77     {
  78       array_ = new T[n];
  79       max_ =size_ = n;
  80       arrcpy (array_, tp, n);
  81     }
  82
  83   Array ()
  84     { array_ = 0; max_ =0; size_ =0; }
  85
  86   // ugh, get around gcc 2.8.1 ice; see bezier.cc
  87   Array (int i)
  88     {
  89       max_ = size_ = i;
  90       array_ = new T[i];
  91     }
  92
  93
  94   /** set the size_ to #s#.
  95       POST: size () == s.
  96       Warning: contents are unspecified */
  97   void set_size (int s)
  98     {
  99       if (s > max_) remax (s);
 100       size_ = s;
 101     }
 102
 103   ~Array ()
 104     { delete[] array_; }
 105
 106   /// return a  "new"ed copy of array
 107   T* copys () const
 108     {
 109       T* Tarray = new T[size_];
 110       arrcpy (Tarray, array_, size_);
 111       return Tarray;
 112     }
 113
 114   T const *accesses () const
 115     {
 116       return array_;
 117     }
 118   void operator= (Array const & src)
 119     {
 120       set_size (src.size_);
 121       arrcpy (array_,src.array_, size_);
 122     }
 123   Array (Array const & src)
 124     {
 125       array_ = src.copys ();
 126       max_ = size_ = src.size_;
 127     }
 128
 129   /// tighten array size_.
 130   void tighten_maxsize ()     {
 131     remax (size_);
 132   }
 133
 134   T * remove_array ();
 135
 136   /// access element
 137   T &operator[] (int i)
 138     {
 139       return elem_ref (i);
 140     }
 141   /// access element
 142   T const & operator[] (int i) const
 143     {
 144       return elem_ref (i);
 145     }
 146   /// access element
 147   T &elem_ref (int i) const
 148     {
 149       assert (i >=0&&i<size_);
 150       return ((T*)array_)[i];
 151     }
 152   /// access element
 153   T elem (int i) const
 154     {
 155       return elem_ref (i);
 156     }
 157
 158   /// add to the end of array
 159   void push (T x)
 160     {
 161       if (size_ == max_)
 162         remax (2*max_ + 1);
 163
 164       // T::operator= (T &) is called here. Safe to use with automatic
 165       // vars
 166       array_[size_++] = x;
 167     }
 168   /// remove and return last entry
 169   T pop ()
 170     {
 171       assert (!empty ());
 172       T l = top (0);
 173       set_size (size ()-1);
 174       return l;
 175     }
 176   /// access last entry
 177   T& top (int j=0)
 178     {
 179       return (*this)[size_-j-1];
 180     }
 181   /// return last entry
 182   T top (int j=0) const
 183     {
 184       return (*this)[size_-j-1];
 185     }
 186
 187
 188
 189   T& boundary (int dir, int idx)
 190     {
 191       assert (dir);
 192       if (dir == 1)
 193         return top (idx);
 194       else
 195         return elem_ref (idx);
 196     }
 197   T boundary (int dir, int idx) const
 198     {
 199       assert (dir);
 200       if (dir == 1)
 201         return top (idx);
 202       else
 203         return elem (idx);
 204     }
 205   void swap (int i,int j)
 206     {
 207       T t ((*this)[i]);
 208  (*this)[i]= (*this)[j];
 209  (*this)[j]=t;
 210     }
 211   bool empty () const
 212     { return !size_; }
 213
 214   void insert (T k, int j);
 215   /**
 216      remove  i-th element, and return it.
 217   */
 218   T get (int i)
 219     {
 220       T t = elem (i);
 221       del (i);
 222       return t;
 223     }
 224   void unordered_del (int i)
 225     {
 226       elem_ref (i) = top ();
 227       set_size (size () -1);
 228     }
 229   void del (int i)
 230     {
 231       assert (i >=0&& i < size_);
 232       arrcpy (array_+i, array_+i+1, size_-i-1);
 233       size_--;
 234     }
 235   // quicksort.
 236   void sort (int (*compare) (T const&,T const&),
 237              int lower = -1, int upper = -1);
 238   void concat (Array<T> const &src)
 239     {
 240       int s = size_;
 241       set_size (size_ + src.size_);
 242       arrcpy (array_+s,src.array_, src.size_);
 243     }
 244   Array<T> slice (int lower, int upper) const;
 245   void reverse ();
 246 };
 247
 248 #include "array.icc"
 249
 250 #endif