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
  37   /**
  38     PRE
  39     *this and h are comparable
  40     */
  41   void unite (Interval_t<T> h);
  42   void intersect (Interval_t<T> h);
  43
  44   T length () const;
  45   void set_empty () ;
  46   bool empty_b () const { return elem (LEFT) > elem (RIGHT); }
  47   bool contains_b (Interval_t<T> const&) const;
  48   Interval_t () {
  49     set_empty ();
  50   }
  51   Interval_t (T m, T M) : Drul_array<T> (m,M)
  52     {}
  53   Interval_t<T> &operator -= (T r) {
  54     *this += -r;
  55     return *this;
  56   }
  57
  58   Interval_t<T> &operator += (T r) {
  59     elem (LEFT) += r;
  60     elem (RIGHT) +=r;
  61     return *this;
  62   }
  63   Interval_t<T> &operator *= (T r) {
  64     if (!empty_b ())
  65       {
  66         elem (LEFT) *= r;
  67         elem (RIGHT) *= r;
  68         if (r < T (0)) {
  69           T t = elem (LEFT);
  70           elem (LEFT) = elem (RIGHT);
  71           elem (RIGHT) = t;
  72         }
  73       }
  74     return *this;
  75   }
  76
  77   Real linear_combination (Real x) const {
  78     return ((1.0 - x) * Real (elem (LEFT))  + (x + 1.0) * Real (elem (RIGHT))) * 0.5;
  79   }
  80   String str () const;
  81
  82   bool elem_b (T r);
  83   void negate () {
  84     T r = -elem (LEFT);
  85     T l = -elem (RIGHT);
  86     elem (LEFT) = l;
  87     elem (RIGHT) =r;
  88   }
  89 };
  90
  91
  92 /**
  93   inclusion ordering. Crash if not  comparable.
  94   */
  95 template<class T>
  96 int Interval__compare (const Interval_t<T>&,Interval_t<T> const&);
  97
  98 /**
  99    Inclusion ordering.  return -2 if not comparable
 100  */
 101 template<class T>
 102 int
 103 _Interval__compare (const Interval_t<T>&a,Interval_t<T> const&b);
 104
 105
 106 /*
 107   INLINE
 108  */
 109
 110 #include "compare.hh"
 111
 112 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T>&, Interval__compare, template<class T>);
 113
 114
 115 template<class T>
 116 inline Interval_t<T>
 117 intersection (Interval_t<T> a, Interval_t<T> const&b)
 118 {
 119   a.intersect (b);
 120   return a;
 121
 122 }
 123
 124 template<class T>
 125 inline
 126 Interval_t<T> operator + (T a,Interval_t<T> i)
 127 {
 128   i += a;
 129   return i;
 130 }
 131
 132 template<class T>
 133 inline
 134 Interval_t<T> operator - (Interval_t<T> i, T a)
 135 {
 136   i += -a;
 137   return i;
 138 }
 139
 140 template<class T>
 141 inline
 142 Interval_t<T> operator - (T a,Interval_t<T> i)
 143 {
 144   i.negate ();
 145   i += a;
 146   return i;
 147 }
 148
 149 template<class T>
 150 inline
 151 Interval_t<T> operator + (Interval_t<T> i,T a){
 152   return a+i;
 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   return a*i;
 167 }
 168
 169 // again? see flower-proto.hh
 170 typedef Interval_t<Real> Interval;
 171 typedef Interval_t<int> Slice;  // weird name
 172
 173
 174 #endif // INTERVAL_HH
 175