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   void translate (T t)
  27     {
  28       elem_ref (LEFT) += t;
  29       elem_ref (RIGHT) += t;
  30     }
  31   void widen (T t)
  32   {
  33     elem_ref (LEFT) -= t;
  34     elem_ref (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   void add_point (T p)
  44   {
  45     elem_ref(LEFT) = elem (LEFT) <? p;
  46     elem_ref(RIGHT) = elem (RIGHT) >? p;
  47   }
  48   T length () const;
  49   T delta () const;
  50   void set_empty ();
  51   void set_full ();
  52
  53   /*
  54     TODO: strip hungarian suffix.
  55    */
  56   bool is_empty () const
  57   {
  58     return elem (LEFT) > elem (RIGHT);
  59   }
  60   bool superset (Interval_t<T> const&) const;
  61   Interval_t ()
  62   {
  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_ref (LEFT) += r;
  75     elem_ref (RIGHT) +=r;
  76     return *this;
  77   }
  78   Interval_t<T> &operator *= (T r) {
  79     if (!is_empty ())
  80       {
  81         elem_ref (LEFT) *= r;
  82         elem_ref (RIGHT) *= r;
  83         if (r < T (0))
  84           swap();
  85
  86       }
  87     return *this;
  88   }
  89
  90   Real linear_combination (Real x) const
  91   {
  92     Drul_array<Real> da (elem (LEFT), elem (RIGHT));
  93     return ::linear_combination (da, x);
  94   }
  95   String to_string () const;
  96
  97   bool contains (T r);
  98   void negate ()
  99   {
 100     T r = -elem (LEFT);
 101     T l = -elem (RIGHT);
 102     elem_ref (LEFT) = l;
 103     elem_ref (RIGHT) =r;
 104   }
 105
 106   void swap ()
 107   {
 108     T t = elem (LEFT);
 109     elem_ref (LEFT) = elem (RIGHT);
 110     elem_ref (RIGHT) = t;
 111   }
 112 };
 113
 114
 115 /**
 116   inclusion ordering. Crash if not  comparable.
 117   */
 118 template<class T>
 119 int Interval__compare (const Interval_t<T>&,Interval_t<T> const&);
 120
 121 /**
 122    Inclusion ordering.  return -2 if not comparable
 123  */
 124 template<class T>
 125 int
 126 _Interval__compare (const Interval_t<T>&a,Interval_t<T> const&b);
 127
 128
 129 /*
 130   INLINE
 131  */
 132
 133 #include "compare.hh"
 134
 135 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T>&, Interval__compare, template<class T>);
 136
 137
 138 template<class T>
 139 inline Interval_t<T>
 140 intersection (Interval_t<T> a, Interval_t<T> const&b)
 141 {
 142   a.intersect (b);
 143   return a;
 144
 145 }
 146
 147 template<class T>
 148 inline
 149 Interval_t<T> operator + (T a,Interval_t<T> i)
 150 {
 151   i += a;
 152   return i;
 153 }
 154
 155 template<class T>
 156 inline
 157 Interval_t<T> operator - (Interval_t<T> i, T a)
 158 {
 159   i += -a;
 160   return i;
 161 }
 162
 163 template<class T>
 164 inline
 165 Interval_t<T> operator - (T a,Interval_t<T> i)
 166 {
 167   i.negate ();
 168   i += a;
 169   return i;
 170 }
 171
 172 template<class T>
 173 inline
 174 Interval_t<T> operator + (Interval_t<T> i,T a){
 175   return a+i;
 176 }
 177
 178 template<class T>
 179 inline
 180 Interval_t<T> operator * (T a,Interval_t<T> i)
 181 {
 182   i *= a;
 183   return i;
 184 }
 185
 186 template<class T>
 187 inline
 188 Interval_t<T> operator * (Interval_t<T> i,T a){
 189   return a*i;
 190 }
 191
 192
 193 template<class T>
 194 inline T
 195 Interval_t<T>::center () const
 196 {
 197   assert (!is_empty ());
 198   return (elem (LEFT) + elem (RIGHT)) / T (2);
 199 }
 200
 201 // again? see flower-proto.hh
 202 typedef Interval_t<Real> Interval;
 203 typedef Interval_t<int> Slice;  // weird name
 204
 205
 206 #endif // INTERVAL_HH
 207