flower/include/interval.hh

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