flower/include/interval.hh

   1 /*
   2   interval.hh -- part of flowerlib
   3
   4   (c) 1996--2007 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   string to_string () const;
 108
 109   bool contains (T r) const;
 110   void negate ()
 111   {
 112     T r = -at (LEFT);
 113     T l = -at (RIGHT);
 114     at (LEFT) = l;
 115     at (RIGHT) = r;
 116   }
 117
 118   void swap ()
 119   {
 120     T t = at (LEFT);
 121     at (LEFT) = at (RIGHT);
 122     at (RIGHT) = t;
 123   }
 124
 125   static bool left_less (Interval_t<T> const &a, Interval_t<T> const &b)
 126   {
 127     return a[LEFT] < b[RIGHT];
 128   }
 129 };
 130
 131 /**
 132    inclusion ordering. Crash if not  comparable.
 133 */
 134 template<class T>
 135 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 136
 137 /**
 138    Inclusion ordering.  return -2 if not comparable
 139 */
 140 template<class T>
 141 int
 142 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 143
 144 /*
 145   INLINE
 146 */
 147
 148 #include "compare.hh"
 149
 150 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 151
 152 template<class T>
 153 inline Interval_t<T>
 154 intersection (Interval_t<T> a, Interval_t<T> const &b)
 155 {
 156   a.intersect (b);
 157   return a;
 158 }
 159
 160 template<class T>
 161 inline
 162 Interval_t<T> operator + (T a, Interval_t<T> i)
 163 {
 164   i += a;
 165   return i;
 166 }
 167
 168 template<class T>
 169 inline
 170 Interval_t<T> operator - (Interval_t<T> i, T a)
 171 {
 172   i += -a;
 173   return i;
 174 }
 175
 176 template<class T>
 177 inline
 178 Interval_t<T> operator - (T a, Interval_t<T> i)
 179 {
 180   i.negate ();
 181   i += a;
 182   return i;
 183 }
 184
 185 template<class T>
 186 inline
 187 Interval_t<T> operator + (Interval_t<T> i, T a)
 188 {
 189   return a + i;
 190 }
 191
 192 template<class T>
 193 inline
 194 Interval_t<T> operator * (T a, Interval_t<T> i)
 195 {
 196   i *= a;
 197   return i;
 198 }
 199
 200 template<class T>
 201 inline
 202 Interval_t<T> operator * (Interval_t<T> i, T a)
 203 {
 204   return a * i;
 205 }
 206
 207 template<class T>
 208 inline T
 209 Interval_t<T>::center () const
 210 {
 211   assert (!is_empty ());
 212   return (at (LEFT) + at (RIGHT)) / T (2);
 213 }
 214
 215 typedef Interval_t<Real> Interval;
 216 typedef Interval_t<int> Slice;  // weird name
 217
 218
 219 #endif // INTERVAL_HH
 220