flower/include/interval.hh

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