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 166
