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*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_p_;
  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_p_, size_);
  50
  51       delete[] array_p_;
  52       array_p_ = 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_p_ = new T[n];
  79       max_ =size_ = n;
  80       arrcpy (array_p_, tp, n);
  81     }
  82
  83   Array()
  84     { array_p_ = 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_p_ = 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_p_; }
 105
 106   /// return a  "new"ed copy of array
 107   T* copy_array() const
 108     {
 109       T* Tarray = new T[size_];
 110       arrcpy (Tarray, array_p_, size_);
 111       return Tarray;
 112     }
 113
 114   void operator=(Array const & src)
 115     {
 116       set_size (src.size_);
 117       arrcpy (array_p_,src.array_p_, size_);
 118     }
 119   Array (Array const & src)
 120     {
 121       array_p_ = src.copy_array();
 122       max_ = size_ = src.size_;
 123     }
 124
 125   /// tighten array size_.
 126   void tighten_maxsize()     {
 127     remax (size_);
 128   }
 129
 130   T * remove_array_p ();
 131
 132   /// access element
 133   T &operator[] (int i)
 134     {
 135       return elem_ref (i);
 136     }
 137   /// access element
 138   T const & operator[] (int i) const
 139     {
 140       return elem_ref (i);
 141     }
 142   /// access element
 143   T &elem_ref (int i) const
 144     {
 145       assert (i >=0&&i<size_);
 146       return ((T*)array_p_)[i];
 147     }
 148   /// access element
 149   T elem (int i) const
 150     {
 151       return elem_ref (i);
 152     }
 153
 154   /// add to the end of array
 155   void push (T x)
 156     {
 157       if (size_ == max_)
 158         remax (2*max_ + 1);
 159
 160       // T::operator=(T &) is called here. Safe to use with automatic
 161       // vars
 162       array_p_[size_++] = x;
 163     }
 164   /// remove and return last entry
 165   T pop()
 166     {
 167       assert (!empty());
 168       T l = top (0);
 169       set_size (size()-1);
 170       return l;
 171     }
 172   /// access last entry
 173   T& top (int j=0)
 174     {
 175       return (*this)[size_-j-1];
 176     }
 177   /// return last entry
 178   T top (int j=0) const
 179     {
 180       return (*this)[size_-j-1];
 181     }
 182
 183
 184   void swap (int i,int j)
 185     {
 186       T t ((*this)[i]);
 187       (*this)[i]=(*this)[j];
 188       (*this)[j]=t;
 189     }
 190   bool empty () const
 191     { return !size_; }
 192
 193   void insert (T k, int j);
 194   /**
 195      remove  i-th element, and return it.
 196   */
 197   T get (int i)
 198     {
 199       T t = elem (i);
 200       del (i);
 201       return t;
 202     }
 203   void unordered_del (int i)
 204     {
 205       elem_ref (i) = top();
 206       set_size (size() -1);
 207     }
 208   void del (int i)
 209     {
 210       assert (i >=0&& i < size_);
 211       arrcpy (array_p_+i, array_p_+i+1, size_-i-1);
 212       size_--;
 213     }
 214   // quicksort.
 215   void sort (int (*compare)(T const&,T const&),
 216              int lower = -1, int upper = -1);
 217   void concat (Array<T> const &src)
 218     {
 219       int s = size_;
 220       set_size (size_ + src.size_);
 221       arrcpy (array_p_+s,src.array_p_, src.size_);
 222     }
 223   Array<T> slice (int lower, int upper) ;
 224   void reverse();
 225 };
 226
 227 #include "array.icc"
 228
 229 #endif