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