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