flower/include/array.icc

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