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 "ValueToString.h" 31#include <wtf/text/StringBuilder.h> 32#endif 33 34namespace WebCore { 35 36// Class representing a closed interval which can hold an arbitrary 37// Plain Old Datatype (POD) as its endpoints and a piece of user 38// data. An important characteristic for the algorithms we use is that 39// if two intervals have identical endpoints but different user data, 40// they are not considered to be equal. This situation can arise when 41// representing the vertical extents of bounding boxes of overlapping 42// triangles, where the pointer to the triangle is the user data of 43// the interval. 44// 45// *Note* that the destructors of type T and UserData will *not* be 46// called by this class. They must not allocate any memory that is 47// required to be cleaned up in their destructors. 48// 49// The following constructors and operators must be implemented on 50// type T: 51// 52// - Copy constructor (if user data is desired) 53// - operator< 54// - operator== 55// - operator= 56// 57// If the UserData type is specified, it must support a copy 58// constructor and assignment operator. 59// 60// In debug mode, printing of intervals and the data they contain is 61// enabled. This requires the following template specializations to be 62// available: 63// 64// template<> struct WebCore::ValueToString<T> { 65// static String string(const T& t); 66// }; 67// template<> struct WebCore::ValueToString<UserData> { 68// static String string(const UserData& t); 69// }; 70// 71// Note that this class requires a copy constructor and assignment 72// operator in order to be stored in the red-black tree. 73 74template<class T, class UserData = void*> 75class PODInterval { 76public: 77 // Constructor from endpoints. This constructor only works when the 78 // UserData type is a pointer or other type which can be initialized 79 // with 0. 80 PODInterval(const T& low, const T& high) 81 : m_low(low) 82 , m_high(high) 83 , m_data(0) 84 , m_maxHigh(high) 85 { 86 } 87 88 // Constructor from two endpoints plus explicit user data. 89 PODInterval(const T& low, const T& high, const UserData data) 90 : m_low(low) 91 , m_high(high) 92 , m_data(data) 93 , m_maxHigh(high) 94 { 95 } 96 97 const T& low() const { return m_low; } 98 const T& high() const { return m_high; } 99 const UserData& data() const { return m_data; } 100 101 bool overlaps(const T& low, const T& high) const 102 { 103 if (this->high() < low) 104 return false; 105 if (high < this->low()) 106 return false; 107 return true; 108 } 109 110 bool overlaps(const PODInterval& other) const 111 { 112 return overlaps(other.low(), other.high()); 113 } 114 115 // Returns true if this interval is "less" than the other. The 116 // comparison is performed on the low endpoints of the intervals. 117 bool operator<(const PODInterval& other) const 118 { 119 return low() < other.low(); 120 } 121 122 // Returns true if this interval is strictly equal to the other, 123 // including comparison of the user data. 124 bool operator==(const PODInterval& other) const 125 { 126 return (low() == other.low() 127 && high() == other.high() 128 && data() == other.data()); 129 } 130 131 const T& maxHigh() const { return m_maxHigh; } 132 void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; } 133 134#ifndef NDEBUG 135 // Support for printing PODIntervals. 136 String toString() const 137 { 138 StringBuilder builder; 139 builder.append("[PODInterval ("); 140 builder.append(ValueToString<T>::string(low())); 141 builder.append(", "); 142 builder.append(ValueToString<T>::string(high())); 143 builder.append("), data="); 144 builder.append(ValueToString<UserData>::string(data())); 145 builder.append(", maxHigh="); 146 builder.append(ValueToString<T>::string(maxHigh())); 147 builder.append("]"); 148 return builder.toString(); 149 } 150#endif 151 152private: 153 T m_low; 154 T m_high; 155 UserData m_data; 156 T m_maxHigh; 157}; 158 159} // namespace WebCore 160 161#endif // PODInterval_h 162