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