flower/include/interval.hh

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