flower/include/interval.hh

   1 /*
   2   interval.hh -- part of flowerlib
   3
   4   (c) 1996 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_str (T arg);
  27   T center () {
  28     assert (!empty_b ());
  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   bool empty_b () const { return elem (LEFT) > elem (RIGHT); }
  56   bool contains_b (Interval_t<T> const&) const;
  57   Interval_t () {
  58     set_empty ();
  59   }
  60   Interval_t (T m, T M) : Drul_array<T> (m,M)
  61     {
  62     }
  63   Interval_t<T> &operator -= (T r) {
  64     *this += -r;
  65     return *this;
  66   }
  67
  68   Interval_t<T> &operator += (T r) {
  69     elem (LEFT) += r;
  70     elem (RIGHT) +=r;
  71     return *this;
  72   }
  73   Interval_t<T> &operator *= (T r) {
  74     if (!empty_b ())
  75       {
  76         elem (LEFT) *= r;
  77         elem (RIGHT) *= r;
  78         if (r < T (0))
  79           swap();
  80
  81       }
  82     return *this;
  83   }
  84
  85   Real linear_combination (Real x) const {
  86     return ((1.0 - x) * Real (elem (LEFT))  + (x + 1.0) * Real (elem (RIGHT))) * 0.5;
  87   }
  88   String str () const;
  89
  90   bool elem_b (T r);
  91   void negate () {
  92     T r = -elem (LEFT);
  93     T l = -elem (RIGHT);
  94     elem (LEFT) = l;
  95     elem (RIGHT) =r;
  96   }
  97
  98   void swap ()
  99   {
 100     T t = elem (LEFT);
 101     elem (LEFT) = elem (RIGHT);
 102     elem (RIGHT) = t;
 103   }
 104 };
 105
 106
 107 /**
 108   inclusion ordering. Crash if not  comparable.
 109   */
 110 template<class T>
 111 int Interval__compare (const Interval_t<T>&,Interval_t<T> const&);
 112
 113 /**
 114    Inclusion ordering.  return -2 if not comparable
 115  */
 116 template<class T>
 117 int
 118 _Interval__compare (const Interval_t<T>&a,Interval_t<T> const&b);
 119
 120
 121 /*
 122   INLINE
 123  */
 124
 125 #include "compare.hh"
 126
 127 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T>&, Interval__compare, template<class T>);
 128
 129
 130 template<class T>
 131 inline Interval_t<T>
 132 intersection (Interval_t<T> a, Interval_t<T> const&b)
 133 {
 134   a.intersect (b);
 135   return a;
 136
 137 }
 138
 139 template<class T>
 140 inline
 141 Interval_t<T> operator + (T a,Interval_t<T> i)
 142 {
 143   i += a;
 144   return i;
 145 }
 146
 147 template<class T>
 148 inline
 149 Interval_t<T> operator - (Interval_t<T> i, T a)
 150 {
 151   i += -a;
 152   return i;
 153 }
 154
 155 template<class T>
 156 inline
 157 Interval_t<T> operator - (T a,Interval_t<T> i)
 158 {
 159   i.negate ();
 160   i += a;
 161   return i;
 162 }
 163
 164 template<class T>
 165 inline
 166 Interval_t<T> operator + (Interval_t<T> i,T a){
 167   return a+i;
 168 }
 169
 170 template<class T>
 171 inline
 172 Interval_t<T> operator * (T a,Interval_t<T> i)
 173 {
 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   return a*i;
 182 }
 183
 184 // again? see flower-proto.hh
 185 typedef Interval_t<Real> Interval;
 186 typedef Interval_t<int> Slice;  // weird name
 187
 188
 189 #endif // INTERVAL_HH
 190