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