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