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   void unite_disjoint (Interval_t<T> h, T padding, Direction d);
  76   Interval_t<T> union_disjoint (Interval_t<T> h, T padding, Direction d) const;
  77
  78   bool is_empty () const
  79   {
  80     return at (LEFT) > at (RIGHT);
  81   }
  82   bool superset (Interval_t<T> const &) const;
  83   Interval_t ()
  84   {
  85     set_empty ();
  86   }
  87   Interval_t (Drul_array<T> const &src)
  88     : Drul_array<T> (src)
  89   {
  90   }
  91
  92   Interval_t (T m, T M) : Drul_array<T> (m, M)
  93   {
  94   }
  95   Interval_t<T> &operator -= (T r)
  96   {
  97     *this += -r;
  98     return *this;
  99   }
 100
 101   Interval_t<T> &operator += (T r)
 102   {
 103     at (LEFT) += r;
 104     at (RIGHT) += r;
 105     return *this;
 106   }
 107   Interval_t<T> &operator *= (T r)
 108   {
 109     if (!is_empty ())
 110       {
 111         at (LEFT) *= r;
 112         at (RIGHT) *= r;
 113         if (r < T (0))
 114           swap ();
 115       }
 116     return *this;
 117   }
 118
 119   Real linear_combination (Real x) const;
 120   string to_string () const;
 121
 122   bool contains (T r) const;
 123   void negate ()
 124   {
 125     T r = -at (LEFT);
 126     T l = -at (RIGHT);
 127     at (LEFT) = l;
 128     at (RIGHT) = r;
 129   }
 130
 131   void swap ()
 132   {
 133     T t = at (LEFT);
 134     at (LEFT) = at (RIGHT);
 135     at (RIGHT) = t;
 136   }
 137
 138   static bool left_less (Interval_t<T> const &a, Interval_t<T> const &b)
 139   {
 140     return a[LEFT] < b[LEFT];
 141   }
 142 };
 143
 144 /**
 145    inclusion ordering. Crash if not  comparable.
 146 */
 147 template<class T>
 148 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 149
 150 /**
 151    Inclusion ordering.  return -2 if not comparable
 152 */
 153 template<class T>
 154 int
 155 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 156
 157 /*
 158   INLINE
 159 */
 160
 161 #include "compare.hh"
 162
 163 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 164
 165 template<class T>
 166 inline Interval_t<T>
 167 intersection (Interval_t<T> a, Interval_t<T> const &b)
 168 {
 169   a.intersect (b);
 170   return a;
 171 }
 172
 173 template<class T>
 174 inline
 175 Interval_t<T> operator + (T a, Interval_t<T> i)
 176 {
 177   i += a;
 178   return i;
 179 }
 180
 181 template<class T>
 182 inline
 183 Interval_t<T> operator - (Interval_t<T> i, T a)
 184 {
 185   i += -a;
 186   return i;
 187 }
 188
 189 template<class T>
 190 inline
 191 Interval_t<T> operator - (T a, Interval_t<T> i)
 192 {
 193   i.negate ();
 194   i += a;
 195   return i;
 196 }
 197
 198 template<class T>
 199 inline
 200 Interval_t<T> operator + (Interval_t<T> i, T a)
 201 {
 202   return a + i;
 203 }
 204
 205 template<class T>
 206 inline
 207 Interval_t<T> operator * (T a, Interval_t<T> i)
 208 {
 209   i *= a;
 210   return i;
 211 }
 212
 213 template<class T>
 214 inline
 215 Interval_t<T> operator * (Interval_t<T> i, T a)
 216 {
 217   return a * i;
 218 }
 219
 220 template<class T>
 221 inline T
 222 Interval_t<T>::center () const
 223 {
 224   assert (!is_empty ());
 225   return (at (LEFT) + at (RIGHT)) / T (2);
 226 }
 227
 228 typedef Interval_t<Real> Interval;
 229 typedef Interval_t<int> Slice;  // weird name
 230
 231
 232 #endif // INTERVAL_HH
 233