Home | History | Annotate | Download | only in platform
      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() && 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.append("[PODInterval (");
    142         builder.append(ValueToString<T>::string(low()));
    143         builder.append(", ");
    144         builder.append(ValueToString<T>::string(high()));
    145         builder.append("), data=");
    146         builder.append(ValueToString<UserData>::string(data()));
    147         builder.append(", maxHigh=");
    148         builder.append(ValueToString<T>::string(maxHigh()));
    149         builder.append("]");
    150         return builder.toString();
    151     }
    152 #endif
    153 
    154 private:
    155     T m_low;
    156     T m_high;
    157     UserData m_data;
    158     T m_maxHigh;
    159 };
    160 
    161 } // namespace WebCore
    162 
    163 #endif // PODInterval_h
    164