flower/include/interval.hh

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