flower/include/array.icc

   1 /*
   2   (c) 1995--2006  Han-Wen Nienhuys  <hanwen@xs4all.nl>
   3
   4   Distributed under GNU GPL
   5 */
   6
   7 #if 0
   8 #include "array.hh"
   9 #ifdef INLINE
  10 #undef INLINE
  11 #endif
  12
  13 #define INLINE
  14 #endif
  15
  16 /*
  17   functions with loops don't inline
  18 */
  19
  20 template<class T> INLINE void
  21 arrcpy (T *dest, T const *src, int count)
  22 {
  23   for (int i_shadows_local = 0; i_shadows_local < count; i_shadows_local++)
  24 #ifdef __powerpc__
  25     {
  26       /*
  27         urg: wierd egcs-1.1.2-12c (stock LinuxPPC R5) bug on ppc
  28         bug report filed
  29         fixed in egcs-1.1.2-12f
  30         ftp://dev.linuxppc.org/users/fsirl/R5/RPMS/ppc/
  31       */
  32       *dest = *src;
  33       dest++, src++;
  34     }
  35 #else
  36   *dest++ = *src++;
  37 #endif
  38 }
  39
  40 template<class T> INLINE void
  41 Array<T>::insert (T k, int j)
  42 {
  43   assert (j >= 0 && j <= size_);
  44   set_size (size_ + 1);
  45   for (int i = size_ - 1; i > j; i--)
  46     array_[i] = array_[i - 1];
  47   array_[j] = k;
  48 }
  49
  50 template<class T> INLINE void
  51 Array<T>::sort (int (*compare) (T const &, T const &), int lower, int upper)
  52 {
  53   if (lower < 0)
  54     {
  55       lower = 0;
  56       upper = size () - 1;
  57     }
  58   if (lower >= upper)
  59     return;
  60   swap (lower, (lower + upper) / 2);
  61   int last = lower;
  62   for (int i = lower +1; i <= upper; i++)
  63     if (compare (array_[i], array_[lower]) < 0)
  64       swap (++last, i);
  65   swap (lower, last);
  66   sort (compare, lower, last - 1);
  67   sort (compare, last + 1, upper);
  68 }
  69
  70 template<class T> INLINE void
  71 Array<T>::reverse ()
  72 {
  73   int h = size_ / 2;
  74   for (int i = 0, j = size_ - 1; i < h; i++, j--)
  75     swap (i, j);
  76 }
  77
  78 template<class T> INLINE
  79 void
  80 Array<T>::OK () const
  81 {
  82   assert (max_ >= size_ && size_ >= 0);
  83   if (max_)
  84     assert (array_);
  85 }
  86
  87 template<class T> INLINE
  88 T *
  89 Array<T>::remove_array ()
  90 {
  91   T *p = array_;
  92   size_ = 0;
  93   max_ = 0;
  94   array_ = 0;
  95   return p;
  96 }
  97
  98 template<class T> INLINE
  99 Array<T>
 100 Array<T>::slice (int lower, int upper) const
 101 {
 102   assert (lower >= 0 && lower <= upper && upper <= size_);
 103   Array<T> r;
 104   int s = upper - lower;
 105   r.set_size (s);
 106   arrcpy (r.array_, array_ + lower, s);
 107   return r;
 108 }
 109
 110 template<class T>
 111 void
 112 binary_search_bounds (Array<T> const &table,
 113                       T const &key, int (*compare) (T const &, T const &),
 114                       int *lo,
 115                       int *hi)
 116 {
 117   int cmp;
 118   int result;
 119
 120   /* binary search */
 121   do
 122     {
 123       cmp = (*lo + *hi) / 2;
 124
 125       result = (*compare) (key, table[cmp]);
 126
 127       if (result < 0)
 128         *hi = cmp;
 129       else
 130         *lo = cmp;
 131     }
 132   while (*hi - *lo > 1);
 133 }
 134
 135 /*
 136   lookup with binsearch, return array index.
 137 */
 138 template<class T>
 139 int
 140 binary_search (Array<T> const &table,
 141                T const &key, int (*compare) (T const &, T const &),
 142                int lo = 0,
 143                int hi = -1)
 144 {
 145   if (hi < 0)
 146     hi = table.size ();
 147
 148   binary_search_bounds (table, key, compare, &lo, &hi);
 149
 150   if (! (*compare) (key, table[lo]))
 151     return lo;
 152   else
 153     return -1;              /* not found */
 154 }