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 (T m, T M) : Drul_array<T> (m, M)
  74   {
  75   }
  76   Interval_t<T> &operator -= (T r)
  77   {
  78     *this += -r;
  79     return *this;
  80   }
  81
  82   Interval_t<T> &operator += (T r)
  83   {
  84     elem_ref (LEFT) += r;
  85     elem_ref (RIGHT) += r;
  86     return *this;
  87   }
  88   Interval_t<T> &operator *= (T r)
  89   {
  90     if (!is_empty ())
  91       {
  92         elem_ref (LEFT) *= r;
  93         elem_ref (RIGHT) *= r;
  94         if (r < T (0))
  95           swap ();
  96       }
  97     return *this;
  98   }
  99
 100   Real linear_combination (Real x) const
 101   {
 102     Drul_array<Real> da (elem (LEFT), elem (RIGHT));
 103     return ::linear_combination (da, x);
 104   }
 105   String to_string () const;
 106
 107   bool contains (T r);
 108   void negate ()
 109   {
 110     T r = -elem (LEFT);
 111     T l = -elem (RIGHT);
 112     elem_ref (LEFT) = l;
 113     elem_ref (RIGHT) = r;
 114   }
 115
 116   void swap ()
 117   {
 118     T t = elem (LEFT);
 119     elem_ref (LEFT) = elem (RIGHT);
 120     elem_ref (RIGHT) = t;
 121   }
 122
 123   static int left_comparison (Interval_t<T> const &a, Interval_t<T> const &b)
 124   {
 125     return sign (a[LEFT] - b[RIGHT]);
 126   }
 127 };
 128
 129 /**
 130    inclusion ordering. Crash if not  comparable.
 131 */
 132 template<class T>
 133 int Interval__compare (const Interval_t<T> &, Interval_t<T> const &);
 134
 135 /**
 136    Inclusion ordering.  return -2 if not comparable
 137 */
 138 template<class T>
 139 int
 140 _Interval__compare (const Interval_t<T> &a, Interval_t<T> const &b);
 141
 142 /*
 143   INLINE
 144 */
 145
 146 #include "compare.hh"
 147
 148 TEMPLATE_INSTANTIATE_COMPARE (Interval_t<T> &, Interval__compare, template<class T>);
 149
 150 template<class T>
 151 inline Interval_t<T>
 152 intersection (Interval_t<T> a, Interval_t<T> const &b)
 153 {
 154   a.intersect (b);
 155   return a;
 156 }
 157
 158 template<class T>
 159 inline
 160 Interval_t<T> operator + (T a, Interval_t<T> i)
 161 {
 162   i += a;
 163   return i;
 164 }
 165
 166 template<class T>
 167 inline
 168 Interval_t<T> operator - (Interval_t<T> i, T a)
 169 {
 170   i += -a;
 171   return i;
 172 }
 173
 174 template<class T>
 175 inline
 176 Interval_t<T> operator - (T a, Interval_t<T> i)
 177 {
 178   i.negate ();
 179   i += a;
 180   return i;
 181 }
 182
 183 template<class T>
 184 inline
 185 Interval_t<T> operator + (Interval_t<T> i, T a)
 186 {
 187   return a + i;
 188 }
 189
 190 template<class T>
 191 inline
 192 Interval_t<T> operator * (T a, Interval_t<T> i)
 193 {
 194   i *= a;
 195   return i;
 196 }
 197
 198 template<class T>
 199 inline
 200 Interval_t<T> operator * (Interval_t<T> i, T a)
 201 {
 202   return a * i;
 203 }
 204
 205 template<class T>
 206 inline T
 207 Interval_t<T>::center () const
 208 {
 209   assert (!is_empty ());
 210   return (elem (LEFT) + elem (RIGHT)) / T (2);
 211 }
 212
 213 typedef Interval_t<Real> Interval;
 214 typedef Interval_t<int> Slice;  // weird name
 215
 216
 217 #endif // INTERVAL_HH
 218