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