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