flower/include/interval.hh

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1996--2010 Han-Wen Nienhuys
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #ifndef INTERVAL_HH
  21 #define INTERVAL_HH
  22
  23 #include <math.h>
  24
  25 #include "flower-proto.hh"
  26 #include "drul-array.hh"
  27
  28 /* A T interval.  This represents the closed interval [left,right].
  29    No invariants.  T must be a totally ordered ring (with division, anyway ..)
  30    At instantiation, the function infinity () has to be defined explicitly. */
  31 template<class T>
  32 struct Interval_t : public Drul_array<T>
  33 {
  34   Drul_array<T>::at;
  35
  36   static T infinity ();
  37   static string T_to_string (T arg);
  38   T center () const;
  39   void translate (T t)
  40   {
  41     at (LEFT) += t;
  42     at (RIGHT) += t;
  43   }
  44   void widen (T t)
  45   {
  46     at (LEFT) -= t;
  47     at (RIGHT) += t;
  48   }
  49
  50   T distance (T t) const
  51   {
  52     if (t > at (RIGHT))
  53       return T (t - at (RIGHT));
  54     else if (t < at (LEFT))
  55       return T (at (LEFT) - t);
  56     else
  57       return T (0);
  58   }
  59   /**
  60      PRE
  61      *this and h are comparable
  62      */
  63   void unite (Interval_t<T> h);
  64   void intersect (Interval_t<T> h);
  65   void add_point (T p)
  66   {
  67     at (LEFT) = min (at (LEFT), p);
  68     at (RIGHT) = max (at (RIGHT), p);
  69   }
  70   T length () const;
  71   T delta () const;
  72   void set_empty ();
  73   void set_full ();
  74
  75   bool is_empty () const
  76   {
  77     return at (LEFT) > at (RIGHT);
  78   }
  79   bool superset (Interval_t<T> const &) const;
  80   Interval_t ()
  81   {
  82     set_empty ();
  83   }
  84   Interval_t (Drul_array<T> const &src)
  85     : Drul_array<T> (src)
  86   {
  87   }
  88
  89   Interval_t (T m, T M) : Drul_array<T> (m, M)
  90   {
  91   }
  92   Interval_t<T> &operator -= (T r)
  93   {
  94     *this += -r;
  95     return *this;
  96   }
  97
  98   Interval_t<T> &operator += (T r)
  99   {
 100     at (LEFT) += r;
 101     at (RIGHT) += r;
 102     return *this;
 103   }
 104   Interval_t<T> &operator *= (T r)
 105   {
 106     if (!is_empty ())
 107       {
 108         at (LEFT) *= r;
 109         at (RIGHT) *= r;
 110         if (r < T (0))
 111           swap ();
 112       }
 113     return *this;
 114   }
 115
 116   Real linear_combination (Real x) const;
 117   string to_string () const;
 118
 119   bool contains (T r) const;
 120   void negate ()
 121   {
 122     T r = -at (LEFT);
 123     T l = -at (RIGHT);
 124     at (LEFT) = l;
 125     at (RIGHT) = r;
 126   }
 127
 128   void swap ()
 129   {
 130     T t = at (LEFT);
 131     at (LEFT) = at (RIGHT);
 132     at (RIGHT) = t;
 133   }
 134
 135   static bool left_less (Interval_t<T> const &a, Interval_t<T> const &b)
 136   {
 137     return a[LEFT] < b[LEFT];
 138   }
 139 };
 140
 141 /**
 142    inclusion ordering. Crash if not  comparable.
 143 */
 144 template<class T>
 145 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 146
 147 /**
 148    Inclusion ordering.  return -2 if not comparable
 149 */
 150 template<class T>
 151 int
 152 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 153
 154 /*
 155   INLINE
 156 */
 157
 158 #include "compare.hh"
 159
 160 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 161
 162 template<class T>
 163 inline Interval_t<T>
 164 intersection (Interval_t<T> a, Interval_t<T> const &b)
 165 {
 166   a.intersect (b);
 167   return a;
 168 }
 169
 170 template<class T>
 171 inline
 172 Interval_t<T> operator + (T a, Interval_t<T> i)
 173 {
 174   i += a;
 175   return i;
 176 }
 177
 178 template<class T>
 179 inline
 180 Interval_t<T> operator - (Interval_t<T> i, T a)
 181 {
 182   i += -a;
 183   return i;
 184 }
 185
 186 template<class T>
 187 inline
 188 Interval_t<T> operator - (T a, Interval_t<T> i)
 189 {
 190   i.negate ();
 191   i += a;
 192   return i;
 193 }
 194
 195 template<class T>
 196 inline
 197 Interval_t<T> operator + (Interval_t<T> i, T a)
 198 {
 199   return a + i;
 200 }
 201
 202 template<class T>
 203 inline
 204 Interval_t<T> operator * (T a, Interval_t<T> i)
 205 {
 206   i *= a;
 207   return i;
 208 }
 209
 210 template<class T>
 211 inline
 212 Interval_t<T> operator * (Interval_t<T> i, T a)
 213 {
 214   return a * i;
 215 }
 216
 217 template<class T>
 218 inline T
 219 Interval_t<T>::center () const
 220 {
 221   assert (!is_empty ());
 222   return (at (LEFT) + at (RIGHT)) / T (2);
 223 }
 224
 225 typedef Interval_t<Real> Interval;
 226 typedef Interval_t<int> Slice;  // weird name
 227
 228
 229 #endif // INTERVAL_HH
 230