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     *this += -r;
  78     return *this;
  79   }
  80
  81   Interval_t<T> &operator += (T r) {
  82     elem_ref (LEFT) += r;
  83     elem_ref (RIGHT) +=r;
  84     return *this;
  85   }
  86   Interval_t<T> &operator *= (T r) {
  87     if (!is_empty ())
  88       {
  89         elem_ref (LEFT) *= r;
  90         elem_ref (RIGHT) *= r;
  91         if (r < T (0))
  92           swap();
  93
  94       }
  95     return *this;
  96   }
  97
  98   Real linear_combination (Real x) const
  99   {
 100     Drul_array<Real> da (elem (LEFT), elem (RIGHT));
 101     return ::linear_combination (da, x);
 102   }
 103   String to_string () const;
 104
 105   bool contains (T r);
 106   void negate ()
 107   {
 108     T r = -elem (LEFT);
 109     T l = -elem (RIGHT);
 110     elem_ref (LEFT) = l;
 111     elem_ref (RIGHT) =r;
 112   }
 113
 114   void swap ()
 115   {
 116     T t = elem (LEFT);
 117     elem_ref (LEFT) = elem (RIGHT);
 118     elem_ref (RIGHT) = t;
 119   }
 120 };
 121
 122
 123 /**
 124   inclusion ordering. Crash if not  comparable.
 125   */
 126 template<class T>
 127 int Interval__compare (const Interval_t<T>&,Interval_t<T> const&);
 128
 129 /**
 130    Inclusion ordering.  return -2 if not comparable
 131  */
 132 template<class T>
 133 int
 134 _Interval__compare (const Interval_t<T>&a,Interval_t<T> const&b);
 135
 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
 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   return a+i;
 184 }
 185
 186 template<class T>
 187 inline
 188 Interval_t<T> operator * (T a,Interval_t<T> i)
 189 {
 190   i *= a;
 191   return i;
 192 }
 193
 194 template<class T>
 195 inline
 196 Interval_t<T> operator * (Interval_t<T> i,T a){
 197   return a*i;
 198 }
 199
 200
 201 template<class T>
 202 inline T
 203 Interval_t<T>::center () const
 204 {
 205   assert (!is_empty ());
 206   return (elem (LEFT) + elem (RIGHT)) / T (2);
 207 }
 208
 209 // again? see flower-proto.hh
 210 typedef Interval_t<Real> Interval;
 211 typedef Interval_t<int> Slice;  // weird name
 212
 213
 214 #endif // INTERVAL_HH
 215