flower/include/interval.hh

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