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 (*compare) (T const &, T const &), vsize b=0, int e=VPOS)
 167     {
 168       ::std::sort (iter (b), iter(e), compare);
 169     }
 170
 171     void swap (vsize i, vsize j)
 172     {
 173       T t ((*this)[i]);
 174       (*this)[i] = (*this)[j];
 175       (*this)[j] = t;
 176     }
 177
 178     T const &
 179     top (vsize i) const
 180     {
 181       return (*this)[this->size () - i - 1];
 182     }
 183
 184     T&
 185     top (vsize i)
 186     {
 187       return (*this)[this->size () - i - 1];
 188     }
 189   };
 190
 191 #if 0
 192   template<typename T>
 193   vsize
 194   //  binary_search (std::vector<T> const &v,
 195   binary_search (vector<T> const &v,
 196                  T const &key, int (*compare) (T const &, T const &),
 197                  vsize b=0, vsize e=VPOS)
 198   {
 199     //(void) compare;
 200     typename vector<T>::const_iterator i = find (v.iter (b), v.iter (e), key);
 201     if (i != v.end ())
 202       return i - v.begin ();
 203     return VPOS;
 204   }
 205 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 206   template<class T>
 207   void
 208   binary_search_bounds (vector<T> const &table,
 209                         T const &key, int (*compare) (T const &, T const &),
 210                         vsize *lo,
 211                         vsize *hi)
 212   {
 213     int cmp;
 214     int result;
 215
 216     /* binary search */
 217     do
 218       {
 219         cmp = (*lo + *hi) / 2;
 220
 221         result = (*compare) (key, table[cmp]);
 222
 223         if (result < 0)
 224           *hi = cmp;
 225         else
 226           *lo = cmp;
 227       }
 228     while (*hi - *lo > 1);
 229   }
 230
 231   template<class T>
 232   vsize
 233   binary_search (vector<T> const &table,
 234                  T const &key, int (*compare) (T const &, T const &),
 235                  vsize lo=0,
 236                  vsize hi=VPOS)
 237   {
 238     if (hi == VPOS)
 239       hi = table.size ();
 240
 241     binary_search_bounds (table, key, compare, &lo, &hi);
 242
 243     if (! (*compare) (key, table[lo]))
 244       return lo;
 245
 246     /* not found */
 247     return VPOS;
 248   }
 249 #endif
 250
 251 }
 252
 253
 254
 255 #else /* ! STD_VECTOR */
 256
 257 namespace std {
 258
 259 #ifndef Array
 260 #define vector Array
 261 #endif
 262
 263   using namespace std;
 264
 265 #ifndef VSIZE
 266 #define VSIZE
 267   typedef int vsize;
 268 #define VPOS -1
 269 #endif
 270
 271 }
 272
 273
 274 #endif /* STD_VECTOR */
 275
 276 #include "array.hh"
 277
 278 #endif /* STD_VECTOR_HH */