flower/include/interval.hh

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1996--2015 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 "std-string.hh"
  27 #include "drul-array.hh"
  28
  29 /* A T interval.  This represents the closed interval [left,right].
  30    No invariants.  T must be a totally ordered ring (with division, anyway ..)
  31    At instantiation, the function infinity () has to be defined explicitly. */
  32 template<class T>
  33 struct Interval_t : public Drul_array<T>
  34 {
  35   using Drul_array<T>::at;
  36
  37   static T infinity ();
  38   static string T_to_string (T arg);
  39   T center () const;
  40   void translate (T t)
  41   {
  42     at (LEFT) += t;
  43     at (RIGHT) += t;
  44   }
  45   void widen (T t)
  46   {
  47     at (LEFT) -= t;
  48     at (RIGHT) += t;
  49   }
  50
  51   T distance (T t) const
  52   {
  53     if (t > at (RIGHT))
  54       return T (t - at (RIGHT));
  55     else if (t < at (LEFT))
  56       return T (at (LEFT) - t);
  57     else
  58       return T (0);
  59   }
  60   /**
  61      PRE
  62      *this and h are comparable
  63      */
  64   void unite (Interval_t<T> h);
  65   void intersect (Interval_t<T> h);
  66   void add_point (T p)
  67   {
  68     at (LEFT) = min (at (LEFT), p);
  69     at (RIGHT) = max (at (RIGHT), p);
  70   }
  71   T length () const;
  72
  73   // Returns RIGHT - LEFT, even if the interval is empty.
  74   T delta () const;
  75   void set_empty ();
  76   void set_full ();
  77
  78   void unite_disjoint (Interval_t<T> h, T padding, Direction d);
  79   Interval_t<T> union_disjoint (Interval_t<T> h, T padding, Direction d) const;
  80
  81   bool is_empty () const
  82   {
  83     return at (LEFT) > at (RIGHT);
  84   }
  85   bool superset (Interval_t<T> const &) const;
  86   Interval_t ()
  87   {
  88     set_empty ();
  89   }
  90   Interval_t (Drul_array<T> const &src)
  91     : Drul_array<T> (src)
  92   {
  93   }
  94
  95   Interval_t (T m, T M) : Drul_array<T> (m, M)
  96   {
  97   }
  98   Interval_t<T> &operator -= (T r)
  99   {
 100     *this += -r;
 101     return *this;
 102   }
 103
 104   Interval_t<T> &operator += (T r)
 105   {
 106     at (LEFT) += r;
 107     at (RIGHT) += r;
 108     return *this;
 109   }
 110   Interval_t<T> &operator *= (T r)
 111   {
 112     if (!is_empty ())
 113       {
 114         at (LEFT) *= r;
 115         at (RIGHT) *= r;
 116         if (r < T (0))
 117           swap ();
 118       }
 119     return *this;
 120   }
 121
 122   Real linear_combination (Real x) const;
 123   string to_string () const;
 124
 125   bool contains (T r) const;
 126   void negate ()
 127   {
 128     T r = -at (LEFT);
 129     T l = -at (RIGHT);
 130     at (LEFT) = l;
 131     at (RIGHT) = r;
 132   }
 133
 134   void swap ()
 135   {
 136     T t = at (LEFT);
 137     at (LEFT) = at (RIGHT);
 138     at (RIGHT) = t;
 139   }
 140
 141   static bool left_less (Interval_t<T> const &a, Interval_t<T> const &b)
 142   {
 143     return a[LEFT] < b[LEFT];
 144   }
 145 };
 146
 147 /**
 148    inclusion ordering. Crash if not  comparable.
 149 */
 150 template<class T>
 151 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 152
 153 /**
 154    Inclusion ordering.  return -2 if not comparable
 155 */
 156 template<class T>
 157 int
 158 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 159
 160 /*
 161   INLINE
 162 */
 163
 164 #include "compare.hh"
 165
 166 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 167
 168 template<class T>
 169 inline Interval_t<T>
 170 intersection (Interval_t<T> a, Interval_t<T> const &b)
 171 {
 172   a.intersect (b);
 173   return a;
 174 }
 175
 176 template<class T>
 177 inline
 178 Interval_t<T> operator + (T a, Interval_t<T> i)
 179 {
 180   i += a;
 181   return i;
 182 }
 183
 184 template<class T>
 185 inline
 186 Interval_t<T> operator - (Interval_t<T> i, T a)
 187 {
 188   i += -a;
 189   return i;
 190 }
 191
 192 template<class T>
 193 inline
 194 Interval_t<T> operator - (T a, Interval_t<T> i)
 195 {
 196   i.negate ();
 197   i += a;
 198   return i;
 199 }
 200
 201 template<class T>
 202 inline
 203 Interval_t<T> operator + (Interval_t<T> i, T a)
 204 {
 205   return a + i;
 206 }
 207
 208 template<class T>
 209 inline
 210 Interval_t<T> operator * (T a, Interval_t<T> i)
 211 {
 212   i *= a;
 213   return i;
 214 }
 215
 216 template<class T>
 217 inline
 218 Interval_t<T> operator * (Interval_t<T> i, T a)
 219 {
 220   return a * i;
 221 }
 222
 223 template<class T>
 224 inline T
 225 Interval_t<T>::center () const
 226 {
 227   assert (!is_empty ());
 228   return (at (LEFT) + at (RIGHT)) / T (2);
 229 }
 230
 231 typedef Interval_t<Real> Interval;
 232 typedef Interval_t<int> Slice;  // weird name
 233
 234
 235 #endif // INTERVAL_HH
 236