src/2geom/interval.h

   1 /**
   2  * \file
   3  * \brief  Simple closed interval class
   4  *
   5  * Copyright 2007 Michael Sloan <mgsloan@gmail.com>
   6  *
   7  * Original Rect/Range code by:
   8  *   Lauris Kaplinski <lauris@kaplinski.com>
   9  *   Nathan Hurst <njh@mail.csse.monash.edu.au>
  10  *   bulia byak <buliabyak@users.sf.net>
  11  *   MenTaLguY <mental@rydia.net>
  12  *
  13  * This library is free software; you can redistribute it and/or
  14  * modify it either under the terms of the GNU Lesser General Public
  15  * License version 2.1 as published by the Free Software Foundation
  16  * (the "LGPL") or, at your option, under the terms of the Mozilla
  17  * Public License Version 1.1 (the "MPL"). If you do not alter this
  18  * notice, a recipient may use your version of this file under either
  19  * the MPL or the LGPL.
  20  *
  21  * You should have received a copy of the LGPL along with this library
  22  * in the file COPYING-LGPL-2.1; if not, output to the Free Software
  23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  24  * You should have received a copy of the MPL along with this library
  25  * in the file COPYING-MPL-1.1
  26  *
  27  * The contents of this file are subject to the Mozilla Public License
  28  * Version 1.1 (the "License"); you may not use this file except in
  29  * compliance with the License. You may obtain a copy of the License at
  30  * http://www.mozilla.org/MPL/
  31  *
  32  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  33  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  34  * the specific language governing rights and limitations.
  35  *
  36  */
  37 #ifndef SEEN_INTERVAL_H
  38 #define SEEN_INTERVAL_H
  39
  40 #include <assert.h>
  41 #include <2geom/coord.h>
  42
  43 #include <boost/optional/optional.hpp>
  44
  45 namespace Geom {
  46
  47 class Interval;
  48
  49 /**
  50  * \brief This class represents a range of numbers that is never empty.
  51  *
  52  * The endpoints are included in the range.
  53  */
  54 class Interval {
  55 private:
  56     Coord _b[2];
  57
  58 public:
  59     /// The default constructor creates an interval [0,0]  DO NOT RELY ON THIS, BEST NOT TO USE THIS CONSTRUCTOR
  60     explicit Interval() { _b[0] = 0;  _b[1] = 0; }
  61     explicit Interval(Coord u) { _b[0] = _b[1] = u; }
  62     /* When creating an Interval using the constructor specifying the exact range, the created interval
  63      * will be [u,v] when u<=v ; and will be [v,u] when v < u !!!
  64      */
  65     Interval(Coord u, Coord v) {
  66         if(u < v) {
  67             _b[0] = u; _b[1] = v;
  68         } else {
  69             _b[0] = v; _b[1] = u;
  70         }
  71     }
  72
  73     double operator[](unsigned i) const {
  74         assert(i < 2);
  75         return _b[i];
  76     }
  77     inline double& operator[](unsigned i) { return _b[i]; }  //Trust the user...
  78
  79     inline Coord min() const { return _b[0]; }
  80     inline Coord max() const { return _b[1]; }
  81     inline Coord extent() const { return _b[1] - _b[0]; }
  82     inline Coord middle() const { return (_b[1] + _b[0]) * 0.5; }
  83
  84 //    inline bool isEmpty() const { return _b[0] > _b[1]; }
  85     inline bool isSingular() const { return _b[0] == _b[1]; }
  86     inline bool contains(Coord val) const { return _b[0] <= val && val <= _b[1]; }
  87     bool contains(const Interval & val) const { return _b[0] <= val._b[0] && val._b[1] <= _b[1]; }
  88     bool intersects(const Interval & val) const {
  89         return contains(val._b[0]) || contains(val._b[1]) || val.contains(*this);
  90     }
  91
  92     inline bool operator==(Interval other) const { return _b[0] == other._b[0] && _b[1] == other._b[1]; }
  93     inline bool operator!=(Interval other) const { return _b[0] != other._b[0] || _b[1] != other._b[1]; }
  94
  95     //IMPL: OffsetableConcept
  96     //TODO: rename output_type to something else in the concept
  97     typedef Coord output_type;
  98     inline Interval operator+(Coord amnt) {
  99         return Interval(_b[0] + amnt, _b[1] + amnt);
 100     }
 101     inline Interval operator-(Coord amnt) {
 102         return Interval(_b[0] - amnt, _b[1] - amnt);
 103     }
 104     inline Interval operator+=(Coord amnt) {
 105         _b[0] += amnt; _b[1] += amnt;
 106         return *this;
 107     }
 108     inline Interval operator-=(Coord amnt) {
 109         _b[0] -= amnt; _b[1] -= amnt;
 110         return *this;
 111     }
 112
 113     //IMPL: ScalableConcept
 114     inline Interval operator-() const { return Interval(*this); }
 115     inline Interval operator*(Coord s) const { return Interval(_b[0]*s, _b[1]*s); }
 116     inline Interval operator/(Coord s) const { return Interval(_b[0]/s, _b[1]/s); }
 117     Interval operator*=(Coord s) {
 118         if(s < 0) {
 119             Coord temp = _b[0];
 120             _b[0] = _b[1]*s;
 121             _b[1] = temp*s;
 122         } else {
 123             _b[0] *= s;
 124             _b[1] *= s;
 125         }
 126         return *this;
 127     }
 128     Interval operator/=(Coord s) {
 129         //TODO: what about s=0?
 130         if(s < 0) {
 131             Coord temp = _b[0];
 132             _b[0] = _b[1]/s;
 133             _b[1] = temp/s;
 134         } else {
 135             _b[0] /= s;
 136             _b[1] /= s;
 137         }
 138         return *this;
 139     }
 140
 141     //TODO: NaN handleage for the next two?
 142     //TODO: Evaluate if wrap behaviour is proper.
 143     //If val > max, then rather than becoming a min==max range, it 'wraps' over
 144     void setMin(Coord val) {
 145         if(val > _b[1]) {
 146             _b[0] = _b[1];
 147             _b[1] = val;
 148         } else {
 149             _b[0] = val;
 150         }
 151     }
 152     //If val < min, then rather than becoming a min==max range, it 'wraps' over
 153     void setMax(Coord val) {
 154         if(val < _b[0]) {
 155             _b[1] = _b[0];
 156             _b[0] = val;
 157         } else {
 158             _b[1] = val;
 159         }
 160     }
 161
 162     inline void extendTo(Coord val) {
 163        if(val < _b[0]) _b[0] = val;
 164        if(val > _b[1]) _b[1] = val;  //no else, as we want to handle NaN
 165     }
 166
 167     static Interval fromArray(const Coord* c, int n) {
 168         assert(n > 0);
 169         Interval result(c[0]);
 170         for(int i = 1; i < n; i++) result.extendTo(c[i]);
 171         return result;
 172     }
 173
 174     /** When this would create an empty interval, the interval will be the centerpoint of the old range only.
 175      */
 176     inline void expandBy(double amnt) {
 177         _b[0] -= amnt;
 178         _b[1] += amnt;
 179         if (_b[0] > _b[1]) {
 180             Coord halfway = (_b[0]+_b[1])/2;
 181             _b[0] = _b[1] = halfway;
 182         }
 183     }
 184
 185     inline void unionWith(const Interval & a) {
 186         if(a._b[0] < _b[0]) _b[0] = a._b[0];
 187         if(a._b[1] > _b[1]) _b[1] = a._b[1];
 188     }
 189 };
 190
 191 //IMPL: AddableConcept
 192 inline Interval operator+(const Interval & a, const Interval & b) {
 193     return Interval(a.min() + b.min(), a.max() + b.max());
 194 }
 195 inline Interval operator-(const Interval & a, const Interval & b) {
 196     return Interval(a.min() - b.max(), a.max() - b.min());
 197 }
 198 inline Interval operator+=(Interval & a, const Interval & b) { a = a + b; return a; }
 199 inline Interval operator-=(Interval & a, const Interval & b) { a = a - b; return a; }
 200
 201 //There might be impls of this based off sign checks
 202 inline Interval operator*(const Interval & a, const Interval & b) {
 203     Interval res(a.min() * b.min());
 204     res.extendTo(a.min() * b.max());
 205     res.extendTo(a.max() * b.min());
 206     res.extendTo(a.max() * b.max());
 207     return res;
 208 }
 209 inline Interval operator*=(Interval & a, const Interval & b) { a = a * b; return a; }
 210
 211 /* reinstate if useful (doesn't do the proper thing for 0 inclusion)
 212 inline Interval operator/(const Interval & a, const Interval & b) {
 213     Interval res(a.min() / b.min());
 214     res.extendTo(a.min() / b.max());
 215     res.extendTo(a.max() / b.min());
 216     res.extendTo(a.max() / b.max());
 217     return res;
 218 }
 219 inline Interval operator/=(Interval & a, const Interval & b) { a = a / b; return a; }
 220 */
 221
 222 // 'union' conflicts with C keyword
 223 inline Interval unify(const Interval & a, const Interval & b) {
 224     return Interval(std::min(a.min(), b.min()),
 225                     std::max(a.max(), b.max()));
 226 }
 227
 228 /**
 229  * \brief OptInterval is an Interval that can be empty.
 230  */
 231 class OptInterval : public boost::optional<Interval> {
 232 public:
 233     OptInterval() : boost::optional<Interval>() {};
 234     OptInterval(Interval const &a) : boost::optional<Interval>(a) {};
 235     OptInterval(Coord u) : boost::optional<Interval>(Interval(u)) {};
 236     OptInterval(Coord u, Coord v) : boost::optional<Interval>(Interval(u,v)) {};
 237
 238     /**
 239      * Check whether this OptInterval is empty or not.
 240      */
 241     inline bool isEmpty() { return (*this == false); };
 242
 243     /**
 244      * If \c this is empty, copy argument \c a. Otherwise, union with it (and do nothing when \c a is empty)
 245      */
 246     inline void unionWith(const OptInterval & a) {
 247         if (a) {
 248             if (*this) { // check that we are not empty
 249                 (*this)->unionWith(*a);
 250             } else {
 251                 *this = a;
 252             }
 253         }
 254     }
 255 };
 256
 257 inline OptInterval intersect(const Interval & a, const Interval & b) {
 258     Coord u = std::max(a.min(), b.min()),
 259           v = std::min(a.max(), b.max());
 260     //technically >= might be incorrect, but singulars suck
 261     return u > v ? OptInterval()
 262                   : OptInterval(Interval(u, v));
 263 }
 264
 265 #ifdef _GLIBCXX_IOSTREAM
 266 inline std::ostream &operator<< (std::ostream &os,
 267                                  const Geom::Interval &I) {
 268     os << "Interval("<<I[0] << ", "<<I[1] << ")";
 269     return os;
 270 }
 271 #endif
 272
 273 }
 274 #endif //SEEN_INTERVAL_H
 275
 276 /*
 277   Local Variables:
 278   mode:c++
 279   c-file-style:"stroustrup"
 280   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 281   indent-tabs-mode:nil
 282   fill-column:99
 283   End:
 284 */
 285 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :