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