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 #define vector __vector
  27 #include <vector>
  28 #undef vector
  29
  30 namespace std {
  31
  32   #ifndef VSIZE
  33   #define VSIZE
  34   typedef size_t vsize;
  35   #define VPOS UINT_MAX
  36   #endif
  37
  38   /* Interface without pointer arithmetic (iterator) semantics.  */
  39   template<typename T>
  40   class vector : public __vector<T>
  41   {
  42   public:
  43     typedef typename __vector<T>::iterator iterator;
  44     typedef typename __vector<T>::const_iterator const_iterator;
  45
  46     vector<T> () : __vector<T> ()
  47     {
  48     }
  49
  50     vector<T> (const_iterator b, const_iterator e) : __vector<T> (b, e)
  51     {
  52     }
  53
  54     /* Flower-Array compatibility.  */
  55     T const &
  56     boundary (int dir, vsize i) const
  57     {
  58       assert (dir);
  59       if (dir == 1)
  60         return this->top (i);
  61       else
  62         return this->at (i);
  63     }
  64
  65     T &
  66     boundary (int dir, vsize i)
  67     {
  68       assert (dir);
  69       if (dir == 1)
  70         return this->top (i);
  71       else
  72         return this->at (i);
  73     }
  74
  75     T *
  76     remove_array ()
  77     {
  78       T *p = &(*this)[0];
  79       /* FIXME: forget array? */
  80       /* this->resize (0); */
  81       return p;
  82     }
  83
  84     void
  85     reverse ()
  86     {
  87       // CHECKME: for a simple vector, like vector<int>, this should
  88       // expand to memrev.
  89       ::std::reverse (this->begin (), this->end ());
  90     }
  91
  92     void swap (vsize i, vsize j)
  93     {
  94       T t ((*this)[i]);
  95       (*this)[i] = (*this)[j];
  96       (*this)[j] = t;
  97     }
  98
  99     T const &
 100     top (vsize i) const
 101     {
 102       return (*this)[this->size () - i - 1];
 103     }
 104
 105     T&
 106     top (vsize i)
 107     {
 108       return (*this)[this->size () - i - 1];
 109     }
 110   };
 111
 112 #if 0
 113   template<typename T>
 114   vsize
 115   //  binary_search (std::vector<T> const &v,
 116   binary_search (vector<T> const &v,
 117                  T const &key, int (*compare) (T const &, T const &),
 118                  vsize b=0, vsize e=VPOS)
 119   {
 120     //(void) compare;
 121     typename vector<T>::const_iterator i = find (v.iter (b), v.iter (e), key);
 122     if (i != v.end ())
 123       return i - v.begin ();
 124     return VPOS;
 125   }
 126 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 127   template<class T>
 128   void
 129   binary_search_bounds (vector<T> const &table,
 130                         T const &key, int (*compare) (T const &, T const &),
 131                         vsize *lo,
 132                         vsize *hi)
 133   {
 134     int cmp;
 135     int result;
 136
 137     /* binary search */
 138     do
 139       {
 140         cmp = (*lo + *hi) / 2;
 141
 142         result = (*compare) (key, table[cmp]);
 143
 144         if (result < 0)
 145           *hi = cmp;
 146         else
 147           *lo = cmp;
 148       }
 149     while (*hi - *lo > 1);
 150   }
 151
 152   template<class T>
 153   vsize
 154   binary_search (vector<T> const &table,
 155                  T const &key, int (*compare) (T const &, T const &),
 156                  vsize lo=0,
 157                  vsize hi=VPOS)
 158   {
 159     if (hi == VPOS)
 160       hi = table.size ();
 161
 162     binary_search_bounds (table, key, compare, &lo, &hi);
 163
 164     if (! (*compare) (key, table[lo]))
 165       return lo;
 166
 167     /* not found */
 168     return VPOS;
 169   }
 170 #endif
 171
 172
 173 #if 0
 174   /* FIXME: the simple test works, but lily barfs.  */
 175   template<typename T>
 176   void
 177   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 178                vsize lower=VPOS, vsize upper=VPOS)
 179   {
 180     typename vector<T>::iterator b = v.begin ();
 181     typename vector<T>::iterator e = v.begin ();
 182     if (lower == VPOS)
 183       {
 184         lower = 0;
 185         upper = v.size ();
 186       }
 187     ::std::sort (b + lower, e + upper, compare);
 188   }
 189 #else
 190   // ugh, c&p
 191 template<typename T> void
 192 vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 193              vsize lower=VPOS, vsize upper=VPOS)
 194 {
 195   if (lower == VPOS)
 196     {
 197       lower = 0;
 198       upper = v.size () - 1;
 199     }
 200   if (upper == VPOS || lower >= upper)
 201     return;
 202   v.swap (lower, (lower + upper) / 2);
 203   vsize last = lower;
 204   for (vsize i = lower +1; i <= upper; i++)
 205     if (compare (v[i], v[lower]) < 0)
 206       v.swap (++last, i);
 207   v.swap (lower, last);
 208   vector_sort (v, compare, lower, last - 1);
 209   vector_sort (v, compare, last + 1, upper);
 210 }
 211
 212 #endif
 213
 214 }
 215
 216
 217
 218 #else /* ! STD_VECTOR */
 219
 220 namespace std {
 221
 222 #ifndef Array
 223 #define vector Array
 224 #endif
 225
 226   using namespace std;
 227
 228 #ifndef VSIZE
 229 #define VSIZE
 230   typedef int vsize;
 231 #define VPOS -1
 232 #endif
 233
 234 }
 235
 236
 237 #endif /* STD_VECTOR */
 238
 239 template<typename T>
 240 int default_compare (T const &a, T const &b)
 241 {
 242    if (a < b)
 243      return -1;
 244    else if (a > b)
 245      return 1;
 246    else
 247      return 0;
 248 }
 249
 250
 251 #include "array.hh"
 252
 253 #endif /* STD_VECTOR_HH */