5c1dcc213a71d408eae7f7199732b83c04236ef2
[WebKit-https.git] / Source / WebCore / platform / PODInterval.h
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
33 namespace WebCore {
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 WebCore::ValueToString<T> {
64 //       static String string(const T& t);
65 //   };
66 //   template<> struct WebCore::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
74 template<class T>
75 struct ValueToString;
76 #endif
77
78 template<class T, class UserData = void*>
79 class PODInterval {
80 public:
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()
131                 && high() == other.high()
132                 && data() == other.data());
133     }
134
135     const T& maxHigh() const { return m_maxHigh; }
136     void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
137
138 #ifndef NDEBUG
139     // Support for printing PODIntervals.
140     String toString() const
141     {
142         StringBuilder builder;
143         builder.append("[PODInterval (");
144         builder.append(ValueToString<T>::string(low()));
145         builder.append(", ");
146         builder.append(ValueToString<T>::string(high()));
147         builder.append("), data=");
148         builder.append(ValueToString<UserData>::string(data()));
149         builder.append(", maxHigh=");
150         builder.append(ValueToString<T>::string(maxHigh()));
151         builder.append("]");
152         return builder.toString();
153     }
154 #endif
155
156 private:
157     T m_low;
158     T m_high;
159     UserData m_data;
160     T m_maxHigh;
161 };
162
163 } // namespace WebCore
164
165 #endif // PODInterval_h