src/2geom/interval.h

   1 /*
   2  * interval.h - Simple closed interval class
   3  *
   4  * Copyright 2007 Michael Sloan <mgsloan@gmail.com>
   5  *
   6  * Original Rect/Range code by:
   7  *   Lauris Kaplinski <lauris@kaplinski.com>
   8  *   Nathan Hurst <njh@mail.csse.monash.edu.au>
   9  *   bulia byak <buliabyak@users.sf.net>
  10  *   MenTaLguY <mental@rydia.net>
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it either under the terms of the GNU Lesser General Public
  14  * License version 2.1 as published by the Free Software Foundation
  15  * (the "LGPL") or, at your option, under the terms of the Mozilla
  16  * Public License Version 1.1 (the "MPL"). If you do not alter this
  17  * notice, a recipient may use your version of this file under either
  18  * the MPL or the LGPL.
  19  *
  20  * You should have received a copy of the LGPL along with this library
  21  * in the file COPYING-LGPL-2.1; if not, output to the Free Software
  22  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  23  * You should have received a copy of the MPL along with this library
  24  * in the file COPYING-MPL-1.1
  25  *
  26  * The contents of this file are subject to the Mozilla Public License
  27  * Version 1.1 (the "License"); you may not use this file except in
  28  * compliance with the License. You may obtain a copy of the License at
  29  * http://www.mozilla.org/MPL/
  30  *
  31  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  32  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  33  * the specific language governing rights and limitations.
  34  *
  35  */
  36 #ifndef SEEN_INTERVAL_H
  37 #define SEEN_INTERVAL_H
  38
  39 #include <assert.h>
  40 #include "coord.h"
  41
  42 #include <boost/optional/optional.hpp>
  43
  44 namespace Geom {
  45
  46 //
  47 class Interval {
  48 private:
  49     Coord _b[2];
  50
  51 public:
  52     //TODO: I just know this'll pop up somewhere, starting off someone's interval at 0...  I can't see how to avoid this.
  53     explicit Interval() { _b[0] = _b[1] = 0; }
  54     explicit Interval(Coord u) { _b[0] = _b[1] = u; }
  55     Interval(Coord u, Coord v) {
  56         if(u < v) {
  57             _b[0] = u; _b[1] = v;
  58         } else {
  59             _b[0] = v; _b[1] = u;
  60         }
  61     }
  62
  63     double operator[](unsigned i) const {
  64         assert(i < 2);
  65         return _b[i];
  66     }
  67     inline double& operator[](unsigned i) { return _b[i]; }  //Trust the user...
  68
  69     inline Coord min() const { return _b[0]; }
  70     inline Coord max() const { return _b[1]; }
  71     inline Coord extent() const { return _b[1] - _b[0]; }
  72     inline Coord middle() const { return (_b[1] + _b[0]) * 0.5; }
  73
  74     inline bool isEmpty() const { return _b[0] == _b[1]; }
  75     inline bool contains(Coord val) const { return _b[0] <= val && val <= _b[1]; }
  76     bool contains(const Interval & val) const { return _b[0] <= val._b[0] && val._b[1] <= _b[1]; }
  77     bool intersects(const Interval & val) const {
  78         return contains(val._b[0]) || contains(val._b[1]) || val.contains(*this);
  79     }
  80
  81     inline bool operator==(Interval other) { return _b[0] == other._b[0] && _b[1] == other._b[1]; }
  82     inline bool operator!=(Interval other) { return _b[0] != other._b[0] || _b[1] != other._b[1]; }
  83
  84     //IMPL: OffsetableConcept
  85     //TODO: rename output_type to something else in the concept
  86     typedef Coord output_type;
  87     inline Interval operator+(Coord amnt) {
  88         return Interval(_b[0] + amnt, _b[1] + amnt);
  89     }
  90     inline Interval operator-(Coord amnt) {
  91         return Interval(_b[0] - amnt, _b[1] - amnt);
  92     }
  93     inline Interval operator+=(Coord amnt) {
  94         _b[0] += amnt; _b[1] += amnt;
  95         return *this;
  96     }
  97     inline Interval operator-=(Coord amnt) {
  98         _b[0] -= amnt; _b[1] -= amnt;
  99         return *this;
 100     }
 101
 102     //IMPL: ScalableConcept
 103     inline Interval operator-() const { return Interval(*this); }
 104     inline Interval operator*(Coord s) const { return Interval(_b[0]*s, _b[1]*s); }
 105     inline Interval operator/(Coord s) const { return Interval(_b[0]/s, _b[1]/s); }
 106     Interval operator*=(Coord s) {
 107         if(s < 0) {
 108             Coord temp = _b[0];
 109             _b[0] = _b[1]*s;
 110             _b[1] = temp*s;
 111         } else {
 112             _b[0] *= s;
 113             _b[1] *= s;
 114         }
 115         return *this;
 116     }
 117     Interval operator/=(Coord s) {
 118         //TODO: what about s=0?
 119         if(s < 0) {
 120             Coord temp = _b[0];
 121             _b[0] = _b[1]/s;
 122             _b[1] = temp/s;
 123         } else {
 124             _b[0] /= s;
 125             _b[1] /= s;
 126         }
 127         return *this;
 128     }
 129
 130     //TODO: NaN handleage for the next two?
 131     //TODO: Evaluate if wrap behaviour is proper.
 132     //If val > max, then rather than becoming a min==max range, it 'wraps' over
 133     void setMin(Coord val) {
 134         if(val > _b[1]) {
 135             _b[0] = _b[1];
 136             _b[1] = val;
 137         } else {
 138             _b[0] = val;
 139         }
 140     }
 141     //If val < min, then rather than becoming a min==max range, it 'wraps' over
 142     void setMax(Coord val) {
 143         if(val < _b[0]) {
 144             _b[1] = _b[0];
 145             _b[0] = val;
 146         } else {
 147             _b[1] = val;
 148         }
 149     }
 150
 151     inline void extendTo(Coord val) {
 152        if(val < _b[0]) _b[0] = val;
 153        if(val > _b[1]) _b[1] = val;  //no else, as we want to handle NaN
 154     }
 155
 156     static Interval fromArray(const Coord* c, int n) {
 157         assert(n > 0);
 158         Interval result(c[0]);
 159         for(int i = 1; i < n; i++) result.extendTo(c[i]);
 160         return result;
 161     }
 162
 163     inline void expandBy(double amnt) {
 164         _b[0] -= amnt;
 165         _b[1] += amnt;
 166     }
 167
 168     inline void unionWith(const Interval & a) {
 169         if(a._b[0] < _b[0]) _b[0] = a._b[0];
 170         if(a._b[1] > _b[1]) _b[1] = a._b[1];
 171     }
 172 };
 173
 174 //IMPL: AddableConcept
 175 inline Interval operator+(const Interval & a, const Interval & b) {
 176     return Interval(a.min() + b.min(), a.max() + b.max());
 177 }
 178 inline Interval operator-(const Interval & a, const Interval & b) {
 179     return Interval(a.min() - b.max(), a.max() - b.min());
 180 }
 181 inline Interval operator+=(Interval & a, const Interval & b) { a = a + b; return a; }
 182 inline Interval operator-=(Interval & a, const Interval & b) { a = a - b; return a; }
 183
 184 //There might be impls of this based off sign checks
 185 inline Interval operator*(const Interval & a, const Interval & b) {
 186     Interval res(a.min() * b.min());
 187     res.extendTo(a.min() * b.max());
 188     res.extendTo(a.max() * b.min());
 189     res.extendTo(a.max() * b.max());
 190     return res;
 191 }
 192 inline Interval operator*=(Interval & a, const Interval & b) { a = a * b; return a; }
 193
 194 /* reinstate if useful (doesn't do the proper thing for 0 inclusion)
 195 inline Interval operator/(const Interval & a, const Interval & b) {
 196     Interval res(a.min() / b.min());
 197     res.extendTo(a.min() / b.max());
 198     res.extendTo(a.max() / b.min());
 199     res.extendTo(a.max() / b.max());
 200     return res;
 201 }
 202 inline Interval operator/=(Interval & a, const Interval & b) { a = a / b; return a; }
 203 */
 204
 205 // 'union' conflicts with C keyword
 206 inline Interval unify(const Interval & a, const Interval & b) {
 207     return Interval(std::min(a.min(), b.min()),
 208                     std::max(a.max(), b.max()));
 209 }
 210 inline boost::optional<Interval> intersect(const Interval & a, const Interval & b) {
 211     Coord u = std::max(a.min(), b.min()),
 212           v = std::min(a.max(), b.max());
 213     //technically >= might be incorrect, but singulars suck
 214     return u >= v ? boost::optional<Interval>()
 215                   : boost::optional<Interval>(Interval(u, v));
 216 }
 217
 218 }
 219 #endif //SEEN_INTERVAL_H