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