flower/include/interval.hh

   1 /*
   2   interval.hh -- part of flowerlib
   3
   4   (c) 1996--2005 Han-Wen Nienhuys
   5 */
   6
   7 #ifndef INTERVAL_HH
   8 #define INTERVAL_HH
   9
  10 #include "flower-proto.hh"
  11 #include "drul-array.hh"
  12
  13 /* A T interval.  This represents the closed interval [left,right].
  14    No invariants.  T must be a totally ordered ring (with division, anyway ..)
  15    At instantiation, the function infinity () has to be defined explicitely. */
  16 template<class T>
  17 struct Interval_t : public Drul_array<T>
  18 {
  19   Drul_array<T>::elem;
  20   Drul_array<T>::elem_ref;
  21
  22   static T infinity ();
  23   static String T_to_string (T arg);
  24   T center () const;
  25   void translate (T t)
  26   {
  27     elem_ref (LEFT) += t;
  28     elem_ref (RIGHT) += t;
  29   }
  30   void widen (T t)
  31   {
  32     elem_ref (LEFT) -= t;
  33     elem_ref (RIGHT) += t;
  34   }
  35
  36   T distance (T t) const
  37   {
  38     if (t > elem (RIGHT))
  39       return T (t - elem (RIGHT));
  40     else if (t < elem (LEFT))
  41       return T (elem (LEFT) - t);
  42     else
  43       return T (0);
  44   }
  45   /**
  46      PRE
  47      *this and h are comparable
  48      */
  49   void unite (Interval_t<T> h);
  50   void intersect (Interval_t<T> h);
  51   void add_point (T p)
  52   {
  53     elem_ref (LEFT) = min (elem (LEFT), p);
  54     elem_ref (RIGHT) = max (elem (RIGHT), p);
  55   }
  56   T length () const;
  57   T delta () const;
  58   void set_empty ();
  59   void set_full ();
  60
  61   /*
  62     TODO: strip hungarian suffix.
  63   */
  64   bool is_empty () const
  65   {
  66     return elem (LEFT) > elem (RIGHT);
  67   }
  68   bool superset (Interval_t<T> const &) const;
  69   Interval_t ()
  70   {
  71     set_empty ();
  72   }
  73   Interval_t (Drul_array<T> const &src)
  74     : Drul_array<T> (src)
  75   {
  76   }
  77
  78   Interval_t (T m, T M) : Drul_array<T> (m, M)
  79   {
  80   }
  81   Interval_t<T> &operator -= (T r)
  82   {
  83     *this += -r;
  84     return *this;
  85   }
  86
  87   Interval_t<T> &operator += (T r)
  88   {
  89     elem_ref (LEFT) += r;
  90     elem_ref (RIGHT) += r;
  91     return *this;
  92   }
  93   Interval_t<T> &operator *= (T r)
  94   {
  95     if (!is_empty ())
  96       {
  97         elem_ref (LEFT) *= r;
  98         elem_ref (RIGHT) *= r;
  99         if (r < T (0))
 100           swap ();
 101       }
 102     return *this;
 103   }
 104
 105   Real linear_combination (Real x) const
 106   {
 107     Drul_array<Real> da (elem (LEFT), elem (RIGHT));
 108     return ::linear_combination (da, x);
 109   }
 110   String to_string () const;
 111
 112   bool contains (T r) const;
 113   void negate ()
 114   {
 115     T r = -elem (LEFT);
 116     T l = -elem (RIGHT);
 117     elem_ref (LEFT) = l;
 118     elem_ref (RIGHT) = r;
 119   }
 120
 121   void swap ()
 122   {
 123     T t = elem (LEFT);
 124     elem_ref (LEFT) = elem (RIGHT);
 125     elem_ref (RIGHT) = t;
 126   }
 127
 128   static int left_comparison (Interval_t<T> const &a, Interval_t<T> const &b)
 129   {
 130     return sign (a[LEFT] - b[RIGHT]);
 131   }
 132 };
 133
 134 /**
 135    inclusion ordering. Crash if not  comparable.
 136 */
 137 template<class T>
 138 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 139
 140 /**
 141    Inclusion ordering.  return -2 if not comparable
 142 */
 143 template<class T>
 144 int
 145 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 146
 147 /*
 148   INLINE
 149 */
 150
 151 #include "compare.hh"
 152
 153 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 154
 155 template<class T>
 156 inline Interval_t<T>
 157 intersection (Interval_t<T> a, Interval_t<T> const &b)
 158 {
 159   a.intersect (b);
 160   return a;
 161 }
 162
 163 template<class T>
 164 inline
 165 Interval_t<T> operator + (T a, Interval_t<T> i)
 166 {
 167   i += a;
 168   return i;
 169 }
 170
 171 template<class T>
 172 inline
 173 Interval_t<T> operator - (Interval_t<T> i, T a)
 174 {
 175   i += -a;
 176   return i;
 177 }
 178
 179 template<class T>
 180 inline
 181 Interval_t<T> operator - (T a, Interval_t<T> i)
 182 {
 183   i.negate ();
 184   i += a;
 185   return i;
 186 }
 187
 188 template<class T>
 189 inline
 190 Interval_t<T> operator + (Interval_t<T> i, T a)
 191 {
 192   return a + i;
 193 }
 194
 195 template<class T>
 196 inline
 197 Interval_t<T> operator * (T a, Interval_t<T> i)
 198 {
 199   i *= a;
 200   return i;
 201 }
 202
 203 template<class T>
 204 inline
 205 Interval_t<T> operator * (Interval_t<T> i, T a)
 206 {
 207   return a * i;
 208 }
 209
 210 template<class T>
 211 inline T
 212 Interval_t<T>::center () const
 213 {
 214   assert (!is_empty ());
 215   return (elem (LEFT) + elem (RIGHT)) / T (2);
 216 }
 217
 218 typedef Interval_t<Real> Interval;
 219 typedef Interval_t<int> Slice;  // weird name
 220
 221
 222 #endif // INTERVAL_HH
 223