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>::Array (const_iterator b, const_iterator e)
 108 {
 109   vsize n = e - b;
 110   array_ = new T[n];
 111   max_ = size_ = n;
 112   arrcpy (array_, b, n);
 113 }
 114
 115 template<class T>
 116 void
 117 binary_search_bounds (Array<T> const &table,
 118                       T const &key, int (*compare) (T const &, T const &),
 119                       vsize *lo,
 120                       vsize *hi)
 121 {
 122   int cmp;
 123   int result;
 124
 125   /* binary search */
 126   do
 127     {
 128       cmp = (*lo + *hi) / 2;
 129
 130       result = (*compare) (key, table[cmp]);
 131
 132       if (result < 0)
 133         *hi = cmp;
 134       else
 135         *lo = cmp;
 136     }
 137   while (*hi - *lo > 1);
 138 }
 139
 140 /*
 141   lookup with binsearch, return array index.
 142 */
 143 template<class T>
 144 vsize
 145 binary_search (Array<T> const &table,
 146                T const &key, int (*compare) (T const &, T const &),
 147                vsize lo=0,
 148                vsize hi=VPOS)
 149 {
 150   if (hi == VPOS)
 151     hi = table.size ();
 152
 153   binary_search_bounds (table, key, compare, &lo, &hi);
 154
 155   if (! (*compare) (key, table[lo]))
 156     return lo;
 157
 158   /* not found */
 159   return VPOS;
 160 }