third_party/WebKit/Source/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 #include "platform/heap/Handle.h"
  30 #ifndef NDEBUG
  31 #include "wtf/text/StringBuilder.h"
  32 #endif
  33
  34 namespace blink {
  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 ValueToString<T> {
  65 //       static String string(const T& t);
  66 //   };
  67 //   template<> struct 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
  74 #ifndef NDEBUG
  75 template<class T>
  76 struct ValueToString;
  77 #endif
  78
  79 template<class T, class UserData = void*>
  80 class PODInterval {
  81 public:
  82     // Constructor from endpoints. This constructor only works when the
  83     // UserData type is a pointer or other type which can be initialized
  84     // with 0.
  85     PODInterval(const T& low, const T& high)
  86         : m_low(low)
  87         , m_high(high)
  88         , m_data(0)
  89         , m_maxHigh(high)
  90     {
  91     }
  92
  93     // Constructor from two endpoints plus explicit user data.
  94     PODInterval(const T& low, const T& high, const UserData data)
  95         : m_low(low)
  96         , m_high(high)
  97         , m_data(data)
  98         , m_maxHigh(high)
  99     {
 100     }
 101
 102     const T& low() const { return m_low; }
 103     const T& high() const { return m_high; }
 104     const UserData& data() const { return m_data; }
 105
 106     bool overlaps(const T& low, const T& high) const
 107     {
 108         if (this->high() < low)
 109             return false;
 110         if (high < this->low())
 111             return false;
 112         return true;
 113     }
 114
 115     bool overlaps(const PODInterval& other) const
 116     {
 117         return overlaps(other.low(), other.high());
 118     }
 119
 120     // Returns true if this interval is "less" than the other. The
 121     // comparison is performed on the low endpoints of the intervals.
 122     bool operator<(const PODInterval& other) const
 123     {
 124         return low() < other.low();
 125     }
 126
 127     // Returns true if this interval is strictly equal to the other,
 128     // including comparison of the user data.
 129     bool operator==(const PODInterval& other) const
 130     {
 131         return (low() == other.low() && high() == other.high() && data() == other.data());
 132     }
 133
 134     const T& maxHigh() const { return m_maxHigh; }
 135     void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
 136
 137 #ifndef NDEBUG
 138     // Support for printing PODIntervals.
 139     String toString() const
 140     {
 141         StringBuilder builder;
 142         builder.appendLiteral("[PODInterval (");
 143         builder.append(ValueToString<T>::string(low()));
 144         builder.appendLiteral(", ");
 145         builder.append(ValueToString<T>::string(high()));
 146         builder.appendLiteral("), data=");
 147         builder.append(ValueToString<UserData>::string(data()));
 148         builder.appendLiteral(", maxHigh=");
 149         builder.append(ValueToString<T>::string(maxHigh()));
 150         builder.append(']');
 151         return builder.toString();
 152     }
 153 #endif
 154
 155 private:
 156     T m_low;
 157     T m_high;
 158     GC_PLUGIN_IGNORE("crbug.com/513116")
 159     UserData m_data;
 160     T m_maxHigh;
 161 };
 162
 163 } // namespace blink
 164
 165 #endif // PODInterval_h