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