Update 2Geom to pull in integer rectangle class

(bzr r10347.1.1)

1 files changed, 42 insertions, 238 deletions

diff --git a/src/2geom/interval.h b/src/2geom/interval.h
index a790a6c3b..ee6d674d2 100644
--- a/src/2geom/interval.h
+++ b/src/2geom/interval.h
@@ -37,19 +37,24 @@
 #ifndef LIB2GEOM_SEEN_INTERVAL_H
 #define LIB2GEOM_SEEN_INTERVAL_H
 
-#include <assert.h>
 #include <boost/none.hpp>
 #include <boost/optional.hpp>
 #include <boost/operators.hpp>
 #include <2geom/coord.h>
-#include <2geom/isnan.h>
+#include <2geom/math-utils.h>
+#include <2geom/generic-interval.h>
+#include <2geom/int-interval.h>
 
 namespace Geom {
 
-class OptInterval;
+/**
+ * @brief Range of real numbers that can be empty.
+ * @ingroup Primitives
+ */
+typedef GenericOptInterval<Coord> OptInterval;
 
 /** 
- * @brief Range of numbers that is never empty.
+ * @brief Range of real numbers that is never empty.
  *
  * Intervals are closed ranges \f$[a, b]\f$, which means they include their endpoints.
  * To use them as open ranges, you can use the interiorContains() methods.
@@ -57,32 +62,24 @@ class OptInterval;
  * @ingroup Primitives
  */
 class Interval
-    : boost::equality_comparable< Interval
-    , boost::additive< Interval
+    : public GenericInterval<Coord>
     , boost::multipliable< Interval
-    , boost::arithmetic< Interval, Coord
-    , boost::orable< Interval
-      > > > > >
+    , boost::multipliable< Interval, Coord
+      > >
 {
-private:
-    /// @invariant _b[0] <= _b[1]
-    Coord _b[2];
-
+    typedef GenericInterval<Coord> Base;
 public:
     /// @name Create intervals.
     /// @{
     /** @brief Create an interval that contains only zero. */
-    explicit Interval() { _b[0] = 0;  _b[1] = 0; }
+    Interval() {}
     /** @brief Create an interval that contains a single point. */
-    explicit Interval(Coord u) { _b[0] = _b[1] = u; }
+    explicit Interval(Coord u) : Base(u) {}
     /** @brief Create an interval that contains all points between @c u and @c v. */
-    Interval(Coord u, Coord v) {
-        if (u <= v) {
-            _b[0] = u; _b[1] = v;
-        } else {
-            _b[0] = v; _b[1] = u;
-        }
-    }
+    Interval(Coord u, Coord v) : Base(u,v) {}
+    /** @brief Convert from integer interval */
+    Interval(IntInterval const &i) : Base(i.min(), i.max()) {}
+    Interval(Base const &b) : Base(b) {}
 
     /** @brief Create an interval containing a range of values.
      * The resulting interval will contain all values from the given range.
@@ -93,9 +90,7 @@ public:
      * @return Interval that contains all values from [start, end). */
     template <typename InputIterator>
     static Interval from_range(InputIterator start, InputIterator end) {
-        assert(start != end);
-        Interval result(*start++);
-        for (; start != end; ++start) result.expandTo(*start);
+        Interval result = Base::from_range(start, end);
         return result;
     }
     /** @brief Create an interval from a C-style array of values it should contain. */
@@ -107,114 +102,38 @@ public:
 
     /// @name Inspect endpoints.
     /// @{
+    /** @brief Access endpoints by value.
+     * @deprecated Use min() and max() instead */
     Coord operator[](unsigned i) const { return _b[i]; }
+    /** @brief Access endpoints by reference.
+     * @deprecated Use min() and max() instead
+     * @todo Remove Interval index operator, which can be used to break the invariant */
     Coord& operator[](unsigned i) { return _b[i]; }
 
-    Coord min() const { return _b[0]; }
-    Coord max() const { return _b[1]; }
-    Coord extent() const { return _b[1] - _b[0]; }
-    Coord middle() const { return (_b[1] + _b[0]) * 0.5; }
-    bool isSingular() const { return _b[0] == _b[1]; }
     bool isFinite() const {
-        return IS_FINITE(_b[0]) && IS_FINITE(_b[1]);
+        return IS_FINITE(min()) && IS_FINITE(max());
     }
     /// @}
 
     /// @name Test coordinates and other intervals for inclusion.
     /// @{
-    /** @brief Check whether the interval includes this number. */
-    bool contains(Coord val) const { return _b[0] <= val && val <= _b[1]; }
     /** @brief Check whether the interior of the interval includes this number.
      * Interior means all numbers in the interval except its ends. */
-    bool interiorContains(Coord val) const { return _b[0] < val && val < _b[1]; }
-    /** @brief Check whether the interval includes the given interval. */
-    bool contains(Interval const &val) const { return _b[0] <= val._b[0] && val._b[1] <= _b[1]; }
+    bool interiorContains(Coord val) const { return min() < val && val < max(); }
     /** @brief Check whether the interior of the interval includes the given interval.
      * Interior means all numbers in the interval except its ends. */
-    bool interiorContains(Interval const &val) const { return _b[0] < val._b[0] && val._b[1] < _b[1]; }
-    /** @brief Check whether the intervals have any common elements. */
-    bool intersects(Interval const &val) const {
-        return contains(val._b[0]) || contains(val._b[1]) || val.contains(*this);
-    }
+    bool interiorContains(Interval const &val) const { return min() < val.min() && val.max() < max(); }
     /** @brief Check whether the interiors of the intervals have any common elements. */
     bool interiorIntersects(Interval const &val) const {
-        return interiorContains(val._b[0]) || interiorContains(val._b[1]) || val.interiorContains(*this);
-    }
-    /// @}
-
-    /// @name Modify the interval.
-    /// @{
-    //TODO: NaN handleage for the next two?
-    /** @brief Set the lower boundary of the interval.
-     * When the given number is larger than the interval's largest element,
-     * it will be reduced to the single number @c val. */
-    void setMin(Coord val) {
-        if(val > _b[1]) {
-            _b[0] = _b[1] = val;
-        } else {
-            _b[0] = val;
-        }
-    }
-    /** @brief Set the upper boundary of the interval.
-     * When the given number is smaller than the interval's smallest element,
-     * it will be reduced to the single number @c val. */
-    void setMax(Coord val) {
-        if(val < _b[0]) {
-            _b[1] = _b[0] = val;
-        } else {
-            _b[1] = val;
-        }
-    }
-    /** @brief Extend the interval to include the given number. */
-    void expandTo(Coord val) {
-       if(val < _b[0]) _b[0] = val;
-       if(val > _b[1]) _b[1] = val;  //no else, as we want to handle NaN
-    }
-    /** @brief Expand or shrink the interval in both directions by the given amount.
-     * After this method, the interval's length (extent) will be increased by
-     * <code>amount * 2</code>. Negative values can be given; they will shrink the interval.
-     * Shrinking by a value larger than half the interval's length will create a degenerate
-     * interval containing only the midpoint of the original. */
-    void expandBy(double amount) {
-        _b[0] -= amount;
-        _b[1] += amount;
-        if (_b[0] > _b[1]) {
-            Coord halfway = (_b[0]+_b[1])/2;
-            _b[0] = _b[1] = halfway;
-        }
-    }
-    /** @brief Union the interval with another one.
-     * The resulting interval will contain all points of both intervals.
-     * It might also contain some points which didn't belong to either - this happens
-     * when the intervals did not have any common elements. */
-    void unionWith(const Interval & a) {
-        if(a._b[0] < _b[0]) _b[0] = a._b[0];
-        if(a._b[1] > _b[1]) _b[1] = a._b[1];
+        return interiorContains(val.min()) || interiorContains(val.max()) || val.interiorContains(*this);
     }
     /// @}
 
     /// @name Operators
     /// @{
-    inline operator OptInterval();
-    bool operator==(Interval const &other) const { return _b[0] == other._b[0] && _b[1] == other._b[1]; }
-    
-    //IMPL: OffsetableConcept
-    //TODO: rename output_type to something else in the concept
-    typedef Coord output_type;
-    /** @brief Offset the interval by a specified amount */
-    Interval &operator+=(Coord amnt) {
-        _b[0] += amnt; _b[1] += amnt;
-        return *this;
-    }
-    /** @brief Offset the interval by the negation of the specified amount */
-    Interval &operator-=(Coord amnt) {
-        _b[0] -= amnt; _b[1] -= amnt;
-        return *this;
-    }
+    inline operator OptInterval() { return OptInterval(*this); }
     
     // IMPL: ScalableConcept
-    /** @brief Return an interval mirrored about 0 */
-    Interval operator-() const { return Interval(-_b[1], -_b[0]); }
     /** @brief Scale an interval */
     Interval &operator*=(Coord s) {
         _b[0] *= s;
@@ -229,25 +148,6 @@ public:
         if(s < 0) std::swap(_b[0], _b[1]);
         return *this;
     }
-    // IMPL: AddableConcept
-    /** @brief Add two intervals.
-     * Sum is defined as the set of points that can be obtained by adding any two values
-     * from both operands: \f$S = \{x \in A, y \in B: x + y\}\f$ */
-    Interval &operator+=(Interval const &o) {
-        _b[0] += o._b[0];
-        _b[1] += o._b[1];
-        return *this;
-    }
-    /** @brief Subtract two intervals.
-     * Difference is defined as the set of points that can be obtained by subtracting
-     * any value from the second operand from any value from the first operand:
-     * \f$S = \{x \in A, y \in B: x - y\}\f$ */
-    Interval &operator-=(Interval const &o) {
-        // equal to *this += -o
-        _b[0] -= o._b[1];
-        _b[1] -= o._b[0];
-        return *this;
-    }
     /** @brief Multiply two intervals.
      * Product is defined as the set of points that can be obtained by multiplying
      * any value from the second operand by any value from the first operand:
@@ -261,121 +161,25 @@ public:
         expandTo(mx * o.max());
         return *this;
     }
-    /** @brief Union two intervals.
-     * Note that intersection is only defined for OptIntervals, because the result
-     * of an intersection can be empty, while an Interval cannot. */
-    Interval &operator|=(Interval const &o) {
-        unionWith(o);
-        return *this;
-    }
     /// @}
-};
-
-/** @brief Union two intervals
- * @relates Interval */
-inline Interval unify(Interval const &a, Interval const &b) {
-    return a | b;
-}
-
-/**
- * @brief A range of numbers that can be empty.
- * @ingroup Primitives
- */
-class OptInterval
-    : public boost::optional<Interval>
-    , boost::orable< OptInterval
-    , boost::andable< OptInterval
-      > >
-{
-public:
-    /// @name Create optionally empty intervals.
+    
+    /// @name Rounding to integer values
     /// @{
-    /** @brief Create an empty interval. */
-    OptInterval() : boost::optional<Interval>() {};
-    /** @brief Wrap an existing interval. */
-    OptInterval(Interval const &a) : boost::optional<Interval>(a) {};
-    /** @brief Create an interval containing a single point. */
-    OptInterval(Coord u) : boost::optional<Interval>(Interval(u)) {};
-    /** @brief Create an interval containing a range of numbers. */
-    OptInterval(Coord u, Coord v) : boost::optional<Interval>(Interval(u,v)) {};
-
-    /** @brief Create a possibly empty interval containing a range of values.
-     * The resulting interval will contain all values from the given range.
-     * The return type of iterators must be convertible to double. The given range
-     * may be empty.
-     * @param start Beginning of the range
-     * @param end   End of the range
-     * @return Interval that contains all values from [start, end), or nothing if the range
-     *         is empty. */
-    template <typename InputIterator>
-    static OptInterval from_range(InputIterator start, InputIterator end) {
-        if (start == end) {
-            OptInterval ret;
-            return ret;
-        }
-        OptInterval ret(Interval::from_range(start, end));
+    /** @brief Return the smallest integer interval which contains this one. */
+    IntInterval roundOutwards() const {
+        IntInterval ret(floor(min()), ceil(max()));
         return ret;
     }
-    /// @}
-
-    /** @brief Check whether this OptInterval is empty. */
-    bool isEmpty() { return !*this; };
-
-    /** @brief Union with another interval, gracefully handling empty ones. */
-    inline void unionWith(OptInterval const &a) {
-        if (a) {
-            if (*this) { // check that we are not empty
-                (*this)->unionWith(*a);
-            } else {
-                *this = a;
-            }
-        }
-    }
-    inline void intersectWith(OptInterval const &o) {
-        if (o && *this) {
-            Coord u, v;
-            u = std::max((*this)->min(), o->min());
-            v = std::min((*this)->max(), o->max());
-            if (u <= v) {
-                *this = Interval(u, v);
-                return;
-            }
-        }
-        (*static_cast<boost::optional<Interval>*>(this)) = boost::none;
-    }
-    OptInterval &operator|=(OptInterval const &o) {
-        unionWith(o);
-        return *this;
-    }
-    OptInterval &operator&=(OptInterval const &o) {
-        intersectWith(o);
-        return *this;
+    /** @brief Return the largest integer interval which is contained in this one. */
+    OptIntInterval roundInwards() const {
+        IntCoord u = ceil(min()), v = floor(max());
+        if (u > v) { OptIntInterval e; return e; }
+        IntInterval ret(u, v);
+        return ret;
     }
+    /// @}
 };
 
-/** @brief Intersect two intervals and return a possibly empty range of numbers
- * @relates OptInterval */
-inline OptInterval intersect(Interval const &a, Interval const &b) {
-    return OptInterval(a) & OptInterval(b);
-}
-/** @brief Intersect two intervals and return a possibly empty range of numbers
- * @relates OptInterval */
-inline OptInterval operator&(Interval const &a, Interval const &b) {
-    return OptInterval(a) & OptInterval(b);
-}
-
-inline Interval::operator OptInterval() {
-    return OptInterval(*this);
-}
-
-#ifdef _GLIBCXX_IOSTREAM
-inline std::ostream &operator<< (std::ostream &os, 
-                                 const Geom::Interval &I) {
-    os << "Interval("<<I[0] << ", "<<I[1] << ")";
-    return os;
-}
-#endif
-
 }
 #endif //SEEN_INTERVAL_H