1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 //    names, trademarks, service marks, or product names of the Licensor
11 //    and its affiliates, except as required to comply with Section 4(c) of
12 //    the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 //     http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_BASE_GF_INTERVAL_H
25 #define PXR_BASE_GF_INTERVAL_H
26 
27 /// \file gf/interval.h
28 /// \ingroup group_gf_BasicMath
29 
30 #include "pxr/pxr.h"
31 #include "pxr/base/gf/math.h"
32 #include "pxr/base/gf/api.h"
33 
34 #include <boost/functional/hash.hpp>
35 
36 #include <float.h>
37 #include <iosfwd>
38 #include <limits>
39 
40 PXR_NAMESPACE_OPEN_SCOPE
41 
42 /// \class GfInterval
43 /// \ingroup group_gf_BasicMath
44 ///
45 /// A basic mathematical interval class.
46 ///
47 /// Can represent intervals with either open or closed boundary
48 /// conditions.
49 ///
50 class GfInterval
51 {
52 public:
53     /// \name Constructors
54     ///@{
55 
56     /// Construct an empty open interval, (0,0).
GfInterval()57     GfInterval() :
58         _min(0.0, false),
59         _max(0.0, false)
60     {}
61 
62     /// Construct a closed interval representing the single point, as [val,val].
GfInterval(double val)63     GfInterval(double val) :
64         _min(val, true),
65         _max(val, true)
66     {}
67 
68     /// Construct an interval with the given arguments.
69     GfInterval(double min, double max,
70                bool minClosed=true, bool maxClosed=true) :
_min(min,minClosed)71         _min(min, minClosed),
72         _max(max, maxClosed)
73     {}
74 
75     ///@}
76 
77     /// Equality operator.
78     bool operator==(const GfInterval &rhs) const {
79         return _min == rhs._min && _max == rhs._max;
80     }
81 
82     /// Inequality operator.
83     bool operator!=(const GfInterval &rhs) const {
84         return !(*this == rhs);
85     }
86 
87     /// Less-than operator.
88     bool operator<(const GfInterval &rhs) const {
89         // Compare min bound
90         if (_min != rhs._min)
91             return _min < rhs._min;
92 
93         // Compare max bound
94         if (_max != rhs._max)
95             return _max < rhs._max;
96 
97         // Equal
98         return false;
99     }
100 
101     /// Hash value.
102     /// Just a basic hash function, not particularly high quality.
Hash()103     size_t Hash() const { return hash_value(*this); }
104 
hash_value(GfInterval const & i)105     friend inline size_t hash_value(GfInterval const &i) {
106         size_t h = 0;
107         boost::hash_combine(h, i._min);
108         boost::hash_combine(h, i._max);
109         return h;
110     }
111 
112     /// Minimum value
GetMin()113     double GetMin() const { return _min.value; }
114 
115     /// Maximum value
GetMax()116     double GetMax() const { return _max.value; }
117 
118     /// Set minimum value
SetMin(double v)119     void SetMin(double v) {
120         _min = _Bound(v, _min.closed);
121     }
122 
123     /// Set minimum value and boundary condition
SetMin(double v,bool minClosed)124     void SetMin(double v, bool minClosed ) {
125         _min = _Bound(v, minClosed);
126     }
127 
128     /// Set maximum value
SetMax(double v)129     void SetMax(double v) {
130         _max = _Bound(v, _max.closed);
131     }
132 
133     /// Set maximum value and boundary condition
SetMax(double v,bool maxClosed)134     void SetMax(double v, bool maxClosed ) {
135         _max = _Bound(v, maxClosed);
136     }
137 
138     /// Minimum boundary condition
IsMinClosed()139     bool IsMinClosed() const { return _min.closed; }
140 
141     /// Maximum boundary condition
IsMaxClosed()142     bool IsMaxClosed() const { return _max.closed; }
143 
144     /// Minimum boundary condition
IsMinOpen()145     bool IsMinOpen() const { return ! _min.closed; }
146 
147     /// Maximum boundary condition
IsMaxOpen()148     bool IsMaxOpen() const { return ! _max.closed; }
149 
150     /// Returns true if the maximum value is finite.
IsMaxFinite()151     bool IsMaxFinite() const {
152         return (_max.value != -std::numeric_limits<double>::infinity()
153             && _max.value !=  std::numeric_limits<double>::infinity());
154     }
155 
156     /// Returns true if the minimum value is finite.
IsMinFinite()157     bool IsMinFinite() const {
158         return (_min.value != -std::numeric_limits<double>::infinity()
159             && _min.value !=  std::numeric_limits<double>::infinity());
160     }
161 
162     /// Returns true if both the maximum and minimum value are finite.
IsFinite()163     bool IsFinite() const {
164         return IsMaxFinite() && IsMinFinite();
165     }
166 
167     /// Return true iff the interval is empty.
IsEmpty()168     bool IsEmpty() const {
169         return (_min.value > _max.value) ||
170             ((_min.value == _max.value)
171              && (! _min.closed || !_max.closed));
172     }
173 
174     /// Width of the interval.
175     /// An empty interval has size 0.
GetSize()176     double GetSize() const {
177         return GfMax( 0.0, _max.value - _min.value );
178     }
179 
180     // For 2x compatibility
Size()181     double Size() const { return GetSize(); }
182 
183     /// Return true iff the value d is contained in the interval.
184     /// An empty interval contains no values.
Contains(double d)185     bool Contains(double d) const {
186         return ((d > _min.value) || (d == _min.value && _min.closed))
187            &&  ((d < _max.value) || (d == _max.value && _max.closed));
188     }
189 
190     // For 2x compatibility
In(double d)191     bool In(double d) const { return Contains(d); }
192 
193     /// Return true iff the interval i is entirely contained in the interval.
194     /// An empty interval contains no intervals, not even other
195     /// empty intervals.
Contains(const GfInterval & i)196     bool Contains(const GfInterval &i) const {
197         return (*this & i) == i;
198     }
199 
200     /// Return true iff the given interval i intersects this interval.
Intersects(const GfInterval & i)201     bool Intersects(const GfInterval &i) const {
202         return !(*this & i).IsEmpty();
203     }
204 
205     /// \name Math operations
206     ///@{
207 
208     /// Boolean intersection.
209     GfInterval & operator&=(const GfInterval &rhs) {
210         if (IsEmpty()) {
211             // No change
212         } else if (rhs.IsEmpty()) {
213             // Intersection is empty
214             *this = GfInterval();
215         } else {
216             // Intersect min edge
217             if (_min.value < rhs._min.value)
218                 _min = rhs._min;
219             else if (_min.value == rhs._min.value)
220                 _min.closed &= rhs._min.closed;
221 
222             // Intersect max edge
223             if (_max.value > rhs._max.value)
224                 _max = rhs._max;
225             else if (_max.value == rhs._max.value)
226                 _max.closed &= rhs._max.closed;
227         }
228         return *this;
229     }
230 
231     /// Returns the interval that bounds the union of this interval and rhs.
232     GfInterval & operator|=(const GfInterval &rhs) {
233         if (IsEmpty()) {
234             *this = rhs;
235         } else if (rhs.IsEmpty()) {
236             // No change
237         } else {
238             // Expand min edge
239             if (_min.value > rhs._min.value)
240                 _min = rhs._min;
241             else if (_min.value == rhs._min.value)
242                 _min.closed |= rhs._min.closed;
243 
244             // Expand max edge
245             if (_max.value < rhs._max.value)
246                 _max = rhs._max;
247             else if (_max.value == rhs._max.value)
248                 _max.closed |= rhs._max.closed;
249         }
250         return *this;
251     }
252 
253     /// Interval addition.
254     GfInterval & operator+=(const GfInterval &rhs) {
255         if (!rhs.IsEmpty()) {
256             _min.value += rhs._min.value;
257             _max.value += rhs._max.value;
258             _min.closed &= rhs._min.closed;
259             _max.closed &= rhs._max.closed;
260         }
261         return *this;
262     }
263 
264     /// Interval subtraction.
265     GfInterval & operator-=(const GfInterval &rhs) {
266         return *this += -rhs;
267     }
268 
269     /// Interval unary minus.
270     GfInterval operator-() const {
271         return GfInterval(-_max.value, -_min.value, _max.closed, _min.closed);
272     }
273 
274     /// Interval multiplication.
275     GfInterval & operator*=(const GfInterval &rhs) {
276         const _Bound a = _min * rhs._min;
277         const _Bound b = _min * rhs._max;
278         const _Bound c = _max * rhs._min;
279         const _Bound d = _max * rhs._max;
280         _max = _Max( _Max(a,b), _Max(c,d) );
281         _min = _Min( _Min(a,b), _Min(c,d) );
282         return *this;
283     }
284 
285     /// Greater than operator
286     bool operator>(const GfInterval& rhs) {
287         // Defined in terms of operator<()
288         return rhs < *this;
289     }
290 
291     /// Less than or equal operator
292     bool operator<=(const GfInterval& rhs) {
293         // Defined in terms of operator<()
294         return !(rhs < *this);
295     }
296 
297     /// Greater than or equal operator
298     bool operator>=(const GfInterval& rhs) {
299         // Defined in terms of operator<()
300         return !(*this < rhs);
301     }
302 
303     /// Union operator
304     GfInterval operator|(const GfInterval& rhs) const {
305         // Defined in terms of operator |=()
306         GfInterval tmp(*this);
307         tmp |= rhs;
308         return tmp;
309     }
310 
311     /// Intersection operator
312     GfInterval operator&(const GfInterval& rhs) const {
313         // Defined in terms of operator &=()
314         GfInterval tmp(*this);
315         tmp &= rhs;
316         return tmp;
317     }
318 
319     /// Addition operator
320     GfInterval operator+(const GfInterval& rhs) const {
321         // Defined in terms of operator +=()
322         GfInterval tmp(*this);
323         tmp += rhs;
324         return tmp;
325     }
326 
327     /// Subtraction operator
328     GfInterval operator-(const GfInterval& rhs) const {
329         // Defined in terms of operator -=()
330         GfInterval tmp(*this);
331         tmp -= rhs;
332         return tmp;
333     }
334 
335     /// Multiplication operator
336     GfInterval operator*(const GfInterval& rhs) const {
337         // Defined in terms of operator *=()
338         GfInterval tmp(*this);
339         tmp *= rhs;
340         return tmp;
341     }
342 
343     ///@}
344 
345     /// Returns the full interval (-inf, inf).
GetFullInterval()346     static GfInterval GetFullInterval() {
347         return GfInterval( -std::numeric_limits<double>::infinity(),
348                             std::numeric_limits<double>::infinity(),
349                             false, false );
350     }
351 
352 private:
353     // Helper struct to represent interval boundaries.
354     struct _Bound {
355         // Boundary value.
356         double value;
357         // Boundary condition.  The boundary value is included in interval
358         // only if the boundary is closed.
359         bool closed;
360 
_Bound_Bound361         _Bound(double val, bool isClosed) :
362             value(val),
363             closed(isClosed)
364         {
365             // Closed boundaries on infinite values do not make sense so
366             // force the bound to be open
367             if (value == -std::numeric_limits<double>::infinity() ||
368                 value == std::numeric_limits<double>::infinity()) {
369                 closed = false;
370             }
371         }
372 
373         bool operator==(const _Bound &rhs) const {
374             return value == rhs.value && closed == rhs.closed;
375         }
376 
377         bool operator!=(const _Bound &rhs) const {
378             return !(*this == rhs);
379         }
380 
381         bool operator<(const _Bound &rhs) const {
382             return value < rhs.value || (value == rhs.value && closed && !rhs.closed);
383         }
384 
385         _Bound & operator=(const _Bound &rhs) {
386             value  = rhs.value;
387             closed = rhs.closed;
388             return *this;
389         }
390         _Bound operator*(const _Bound &rhs) const {
391             return _Bound( value * rhs.value, closed & rhs.closed );
392         }
hash_value_Bound393         friend inline size_t hash_value(const _Bound &b) {
394             size_t h = 0;
395             boost::hash_combine(h, b.value);
396             boost::hash_combine(h, b.closed);
397             return h;
398         }
399     };
400 
401     // Return the lesser minimum bound, handling boundary conditions.
402     inline static const _Bound &
_Min(const _Bound & a,const _Bound & b)403     _Min( const _Bound &a, const _Bound &b ) {
404         return (a.value < b.value
405             || ((a.value == b.value) && a.closed && !b.closed)) ?
406             a : b;
407     }
408 
409     // Return the greater maximum bound, handling boundary conditions.
410     inline static const _Bound &
_Max(const _Bound & a,const _Bound & b)411     _Max( const _Bound &a, const _Bound &b ) {
412         return (a.value < b.value
413             || ((a.value == b.value) && !a.closed && b.closed)) ?
414             b : a;
415     }
416 
417     /// Data
418     _Bound _min, _max;
419 };
420 
421 /// Output a GfInterval using the format (x, y).
422 /// \ingroup group_gf_DebuggingOutput
423 GF_API std::ostream &operator<<(std::ostream&, const GfInterval&);
424 
425 PXR_NAMESPACE_CLOSE_SCOPE
426 
427 #endif // PXR_BASE_GF_INTERVAL_H
428