flower/include/std-vector.hh

   1 /*
   2   std-vector.hh -- declare std::vector
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2006 Jan Nieuwenhuizen <janneke@gnu.org>
   7 */
   8
   9 #ifndef STD_VECTOR_HH
  10 #define STD_VECTOR_HH
  11
  12 #include <algorithm> // reverse, sort
  13
  14 #if !STD_VECTOR
  15 /* Also declare vector, in the wrong way.  */
  16 #include <algorithm>
  17 #include <iostream>
  18 #include <sstream>
  19 #endif
  20
  21
  22 #include "compare.hh"
  23
  24 #if STD_VECTOR
  25
  26 #include <vector>
  27
  28 namespace std {
  29
  30   #ifndef VSIZE
  31   #define VSIZE
  32   typedef size_t vsize;
  33   #define VPOS UINT_MAX
  34   #endif
  35
  36   template<typename T>
  37   T const &
  38   boundary (vector<T> const &v, int dir, vsize i)
  39   {
  40     assert (dir);
  41     return v[dir == 1 ? i : v.size () - 1 - i];
  42   }
  43
  44   template<typename T>
  45   T &
  46   boundary (vector<T> &v, int dir, vsize i)
  47   {
  48     assert (dir);
  49     return v[dir == 1 ? i : v.size () - 1 - i];
  50   }
  51
  52   template<typename T>
  53   T const &
  54   back (vector<T> const &v, vsize i)
  55   {
  56     return v[v.size () - i - 1];
  57   }
  58
  59   template<typename T>
  60   T&
  61   back (vector<T> &v, vsize i)
  62   {
  63     return v[v.size () - i - 1];
  64   }
  65
  66 #if 0
  67   template<typename T>
  68   vsize
  69   //  binary_search (std::vector<T> const &v,
  70   binary_search (vector<T> const &v,
  71                  T const &key, int (*compare) (T const &, T const &),
  72                  vsize b=0, vsize e=VPOS)
  73   {
  74     //(void) compare;
  75     typename vector<T>::const_iterator i = find (v.iter (b), v.iter (e), key);
  76     if (i != v.end ())
  77       return i - v.begin ();
  78     return VPOS;
  79   }
  80 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
  81   template<class T>
  82   void
  83   binary_search_bounds (vector<T> const &table,
  84                         T const &key, int (*compare) (T const &, T const &),
  85                         vsize *lo,
  86                         vsize *hi)
  87   {
  88     int cmp;
  89     int result;
  90
  91     /* binary search */
  92     do
  93       {
  94         cmp = (*lo + *hi) / 2;
  95
  96         result = (*compare) (key, table[cmp]);
  97
  98         if (result < 0)
  99           *hi = cmp;
 100         else
 101           *lo = cmp;
 102       }
 103     while (*hi - *lo > 1);
 104   }
 105
 106   template<class T>
 107   vsize
 108   binary_search (vector<T> const &table,
 109                  T const &key, int (*compare) (T const &, T const &),
 110                  vsize lo=0,
 111                  vsize hi=VPOS)
 112   {
 113     if (hi == VPOS)
 114       hi = table.size ();
 115
 116     binary_search_bounds (table, key, compare, &lo, &hi);
 117
 118     if (! (*compare) (key, table[lo]))
 119       return lo;
 120
 121     /* not found */
 122     return VPOS;
 123   }
 124 #endif
 125
 126
 127 #if 0
 128   /* FIXME: the simple test works, but lily barfs.  */
 129   template<typename T>
 130   void
 131   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 132                vsize lower=VPOS, vsize upper=VPOS)
 133   {
 134     typename vector<T>::iterator b = v.begin ();
 135     typename vector<T>::iterator e = v.begin ();
 136     if (lower == VPOS)
 137       {
 138         lower = 0;
 139         upper = v.size ();
 140       }
 141     ::std::sort (b + lower, e + upper, compare);
 142   }
 143 #else
 144
 145   template<typename T>
 146   void
 147   swap (T *a, T *b)
 148   {
 149     T t = *a;
 150     *a = *b;
 151     *b = t;
 152   }
 153
 154   // ugh, c&p
 155 template<typename T> void
 156 vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 157              vsize lower=VPOS, vsize upper=VPOS)
 158 {
 159   if (lower == VPOS)
 160     {
 161       lower = 0;
 162       upper = v.size () - 1;
 163     }
 164   if (upper == VPOS || lower >= upper)
 165     return;
 166   swap (v[lower], v[(lower + upper) / 2]);
 167   vsize last = lower;
 168   for (vsize i = lower +1; i <= upper; i++)
 169     if (compare (v[i], v[lower]) < 0)
 170       swap (v[++last], v[i]);
 171   swap (v[lower], v[last]);
 172   vector_sort (v, compare, lower, last - 1);
 173   vector_sort (v, compare, last + 1, upper);
 174 }
 175
 176   template<typename T>
 177   void
 178   reverse (vector<T> &v)
 179   {
 180     // CHECKME: for a simple vector, like vector<int>, this should
 181     // expand to memrev.
 182     ::std::reverse (v.begin (), v.end ());
 183   }
 184
 185 #endif
 186
 187 }
 188
 189
 190
 191 #else /* ! STD_VECTOR */
 192
 193 namespace std {
 194
 195 #ifndef Array
 196 #define vector Array
 197 #endif
 198
 199   using namespace std;
 200
 201 #ifndef VSIZE
 202 #define VSIZE
 203   typedef int vsize;
 204 #define VPOS -1
 205 #endif
 206
 207 }
 208
 209
 210 #endif /* STD_VECTOR */
 211
 212 template<typename T>
 213 int default_compare (T const &a, T const &b)
 214 {
 215    if (a < b)
 216      return -1;
 217    else if (a > b)
 218      return 1;
 219    else
 220      return 0;
 221 }
 222
 223
 224 #include "array.hh"
 225
 226 #endif /* STD_VECTOR_HH */