flower/include/interval.hh

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