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