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 "std-vector.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, vsize count)
  22 {
  23   for (vsize 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, vsize j)
  42 {
  43 #if !STD_VECTOR
  44     assert (j >= 0 && j <= size_);
  45 #else
  46     assert (j <= size_);
  47 #endif
  48   resize (size_ + 1);
  49   for (vsize i = size_ - 1; i > j; i--)
  50     array_[i] = array_[i - 1];
  51   array_[j] = k;
  52 }
  53
  54 template<class T> INLINE void
  55 Array<T>::sort (int (*compare) (T const &, T const &), vsize lower, vsize upper)
  56 {
  57   if (lower < 0)
  58     {
  59       lower = 0;
  60       upper = size () - 1;
  61     }
  62   if (lower >= upper)
  63     return;
  64   swap (lower, (lower + upper) / 2);
  65   vsize last = lower;
  66   for (vsize i = lower +1; i <= upper; i++)
  67     if (compare (array_[i], array_[lower]) < 0)
  68       swap (++last, i);
  69   swap (lower, last);
  70   sort (compare, lower, last - 1);
  71   sort (compare, last + 1, upper);
  72 }
  73
  74 template<class T> INLINE void
  75 Array<T>::reverse ()
  76 {
  77   vsize h = size_ / 2;
  78   for (vsize i = 0, j = size_ - 1; i < h; i++, j--)
  79     swap (i, j);
  80 }
  81
  82 template<class T> INLINE
  83 void
  84 Array<T>::OK () const
  85 {
  86 #if !STD_VECTOR
  87   assert (max_ >= size_ && size_ >= 0);
  88 #else
  89   assert (max_ >= size_);
  90 #endif
  91   if (max_)
  92     assert (array_);
  93 }
  94
  95 template<class T> INLINE
  96 T *
  97 Array<T>::remove_array ()
  98 {
  99   T *p = array_;
 100   size_ = 0;
 101   max_ = 0;
 102   array_ = 0;
 103   return p;
 104 }
 105
 106 template<class T> INLINE
 107 Array<T>
 108 Array<T>::slice (vsize lower, vsize upper) const
 109 {
 110 #if !STD_VECTOR
 111   assert (lower >= 0 && lower <= upper && upper <= size_);
 112 #else
 113   assert (lower <= upper && upper <= size_);
 114 #endif
 115   Array<T> r;
 116   vsize s = upper - lower;
 117   r.resize (s);
 118   arrcpy (r.array_, array_ + lower, s);
 119   return r;
 120 }
 121
 122 template<class T>
 123 void
 124 binary_search_bounds (Array<T> const &table,
 125                       T const &key, int (*compare) (T const &, T const &),
 126                       vsize *lo,
 127                       vsize *hi)
 128 {
 129   int cmp;
 130   int result;
 131
 132   /* binary search */
 133   do
 134     {
 135       cmp = (*lo + *hi) / 2;
 136
 137       result = (*compare) (key, table[cmp]);
 138
 139       if (result < 0)
 140         *hi = cmp;
 141       else
 142         *lo = cmp;
 143     }
 144   while (*hi - *lo > 1);
 145 }
 146
 147 /*
 148   lookup with binsearch, return array index.
 149 */
 150 template<class T>
 151 vsize
 152 binary_search (Array<T> const &table,
 153                T const &key, int (*compare) (T const &, T const &),
 154                vsize lo=0,
 155                vsize hi=VPOS)
 156 {
 157   if (hi == VPOS)
 158     hi = table.size ();
 159
 160   binary_search_bounds (table, key, compare, &lo, &hi);
 161
 162   if (! (*compare) (key, table[lo]))
 163     return lo;
 164
 165   /* not found */
 166   return VPOS;
 167 }