1/*
2 * Copyright (C) 2010 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef PODInterval_h
27#define PODInterval_h
28
29#ifndef NDEBUG
30#include "wtf/text/StringBuilder.h"
31#endif
32
33namespace blink {
34
35// Class representing a closed interval which can hold an arbitrary
36// Plain Old Datatype (POD) as its endpoints and a piece of user
37// data. An important characteristic for the algorithms we use is that
38// if two intervals have identical endpoints but different user data,
39// they are not considered to be equal. This situation can arise when
40// representing the vertical extents of bounding boxes of overlapping
41// triangles, where the pointer to the triangle is the user data of
42// the interval.
43//
44// *Note* that the destructors of type T and UserData will *not* be
45// called by this class. They must not allocate any memory that is
46// required to be cleaned up in their destructors.
47//
48// The following constructors and operators must be implemented on
49// type T:
50//
51//   - Copy constructor (if user data is desired)
52//   - operator<
53//   - operator==
54//   - operator=
55//
56// If the UserData type is specified, it must support a copy
57// constructor and assignment operator.
58//
59// In debug mode, printing of intervals and the data they contain is
60// enabled. This requires the following template specializations to be
61// available:
62//
63//   template<> struct ValueToString<T> {
64//       static String string(const T& t);
65//   };
66//   template<> struct ValueToString<UserData> {
67//       static String string(const UserData& t);
68//   };
69//
70// Note that this class requires a copy constructor and assignment
71// operator in order to be stored in the red-black tree.
72
73#ifndef NDEBUG
74template<class T>
75struct ValueToString;
76#endif
77
78template<class T, class UserData = void*>
79class PODInterval {
80public:
81    // Constructor from endpoints. This constructor only works when the
82    // UserData type is a pointer or other type which can be initialized
83    // with 0.
84    PODInterval(const T& low, const T& high)
85        : m_low(low)
86        , m_high(high)
87        , m_data(0)
88        , m_maxHigh(high)
89    {
90    }
91
92    // Constructor from two endpoints plus explicit user data.
93    PODInterval(const T& low, const T& high, const UserData data)
94        : m_low(low)
95        , m_high(high)
96        , m_data(data)
97        , m_maxHigh(high)
98    {
99    }
100
101    const T& low() const { return m_low; }
102    const T& high() const { return m_high; }
103    const UserData& data() const { return m_data; }
104
105    bool overlaps(const T& low, const T& high) const
106    {
107        if (this->high() < low)
108            return false;
109        if (high < this->low())
110            return false;
111        return true;
112    }
113
114    bool overlaps(const PODInterval& other) const
115    {
116        return overlaps(other.low(), other.high());
117    }
118
119    // Returns true if this interval is "less" than the other. The
120    // comparison is performed on the low endpoints of the intervals.
121    bool operator<(const PODInterval& other) const
122    {
123        return low() < other.low();
124    }
125
126    // Returns true if this interval is strictly equal to the other,
127    // including comparison of the user data.
128    bool operator==(const PODInterval& other) const
129    {
130        return (low() == other.low() && high() == other.high() && data() == other.data());
131    }
132
133    const T& maxHigh() const { return m_maxHigh; }
134    void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
135
136#ifndef NDEBUG
137    // Support for printing PODIntervals.
138    String toString() const
139    {
140        StringBuilder builder;
141        builder.appendLiteral("[PODInterval (");
142        builder.append(ValueToString<T>::string(low()));
143        builder.appendLiteral(", ");
144        builder.append(ValueToString<T>::string(high()));
145        builder.appendLiteral("), data=");
146        builder.append(ValueToString<UserData>::string(data()));
147        builder.appendLiteral(", maxHigh=");
148        builder.append(ValueToString<T>::string(maxHigh()));
149        builder.append(']');
150        return builder.toString();
151    }
152#endif
153
154private:
155    T m_low;
156    T m_high;
157    UserData m_data;
158    T m_maxHigh;
159};
160
161} // namespace blink
162
163#endif // PODInterval_h
164