Source/WebCore/platform/PODIntervalTree.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 PODIntervalTree_h
  27 #define PODIntervalTree_h
  28
  29 #include "PODInterval.h"
  30 #include "PODRedBlackTree.h"
  31 #include "ValueToString.h"
  32 #include <wtf/Assertions.h>
  33 #include <wtf/Noncopyable.h>
  34 #include <wtf/Vector.h>
  35
  36 namespace WebCore {
  37
  38 template <class T, class UserData = void*>
  39 class PODIntervalSearchAdapter {
  40 public:
  41     typedef PODInterval<T, UserData> IntervalType;
  42
  43     PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
  44         : m_result(result)
  45         , m_lowValue(lowValue)
  46         , m_highValue(highValue)
  47     {
  48     }
  49
  50     const T& lowValue() const { return m_lowValue; }
  51     const T& highValue() const { return m_highValue; }
  52     void collectIfNeeded(const IntervalType& data) const
  53     {
  54         if (data.overlaps(m_lowValue, m_highValue))
  55             m_result.append(data);
  56     }
  57
  58 private:
  59     Vector<IntervalType>& m_result;
  60     T m_lowValue;
  61     T m_highValue;
  62 };
  63
  64 // An interval tree, which is a form of augmented red-black tree. It
  65 // supports efficient (O(lg n)) insertion, removal and querying of
  66 // intervals in the tree.
  67 template<class T, class UserData = void*>
  68 class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData>> {
  69     WTF_MAKE_FAST_ALLOCATED;
  70     WTF_MAKE_NONCOPYABLE(PODIntervalTree);
  71 public:
  72     // Typedef to reduce typing when declaring intervals to be stored in
  73     // this tree.
  74     typedef PODInterval<T, UserData> IntervalType;
  75     typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
  76
  77     PODIntervalTree()
  78         : PODRedBlackTree<IntervalType>()
  79     {
  80         init();
  81     }
  82
  83     // Returns all intervals in the tree which overlap the given query
  84     // interval. The returned intervals are sorted by increasing low
  85     // endpoint.
  86     Vector<IntervalType> allOverlaps(const IntervalType& interval) const
  87     {
  88         Vector<IntervalType> result;
  89         allOverlaps(interval, result);
  90         return result;
  91     }
  92
  93     // Returns all intervals in the tree which overlap the given query
  94     // interval. The returned intervals are sorted by increasing low
  95     // endpoint.
  96     void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const
  97     {
  98         // Explicit dereference of "this" required because of
  99         // inheritance rules in template classes.
 100         IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
 101         searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
 102     }
 103
 104     template <class AdapterType>
 105     void allOverlapsWithAdapter(AdapterType& adapter) const
 106     {
 107         // Explicit dereference of "this" required because of
 108         // inheritance rules in template classes.
 109         searchForOverlapsFrom<AdapterType>(this->root(), adapter);
 110     }
 111
 112     // Helper to create interval objects.
 113     static IntervalType createInterval(const T& low, const T& high, const UserData data = 0)
 114     {
 115         return IntervalType(low, high, data);
 116     }
 117
 118     bool checkInvariants() const override
 119     {
 120         if (!PODRedBlackTree<IntervalType>::checkInvariants())
 121             return false;
 122         if (!this->root())
 123             return true;
 124         return checkInvariantsFromNode(this->root(), 0);
 125     }
 126
 127 private:
 128     typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode;
 129
 130     // Initializes the tree.
 131     void init()
 132     {
 133         // Explicit dereference of "this" required because of
 134         // inheritance rules in template classes.
 135         this->setNeedsFullOrderingComparisons(true);
 136     }
 137
 138     // Starting from the given node, adds all overlaps with the given
 139     // interval to the result vector. The intervals are sorted by
 140     // increasing low endpoint.
 141     template <class AdapterType>
 142     void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
 143     {
 144         if (!node)
 145             return;
 146
 147         // Because the intervals are sorted by left endpoint, inorder
 148         // traversal produces results sorted as desired.
 149
 150         // See whether we need to traverse the left subtree.
 151         IntervalNode* left = node->left();
 152         if (left
 153             // This is phrased this way to avoid the need for operator
 154             // <= on type T.
 155             && !(left->data().maxHigh() < adapter.lowValue()))
 156             searchForOverlapsFrom<AdapterType>(left, adapter);
 157
 158         // Check for overlap with current node.
 159         adapter.collectIfNeeded(node->data());
 160
 161         // See whether we need to traverse the right subtree.
 162         // This is phrased this way to avoid the need for operator <=
 163         // on type T.
 164         if (!(adapter.highValue() < node->data().low()))
 165             searchForOverlapsFrom<AdapterType>(node->right(), adapter);
 166     }
 167
 168     bool updateNode(IntervalNode* node) override
 169     {
 170         // Would use const T&, but need to reassign this reference in this
 171         // function.
 172         const T* curMax = &node->data().high();
 173         IntervalNode* left = node->left();
 174         if (left) {
 175             if (*curMax < left->data().maxHigh())
 176                 curMax = &left->data().maxHigh();
 177         }
 178         IntervalNode* right = node->right();
 179         if (right) {
 180             if (*curMax < right->data().maxHigh())
 181                 curMax = &right->data().maxHigh();
 182         }
 183         // This is phrased like this to avoid needing operator!= on type T.
 184         if (!(*curMax == node->data().maxHigh())) {
 185             node->data().setMaxHigh(*curMax);
 186             return true;
 187         }
 188         return false;
 189     }
 190
 191     bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const
 192     {
 193         // These assignments are only done in order to avoid requiring
 194         // a default constructor on type T.
 195         T leftMaxValue(node->data().maxHigh());
 196         T rightMaxValue(node->data().maxHigh());
 197         IntervalNode* left = node->left();
 198         IntervalNode* right = node->right();
 199         if (left) {
 200             if (!checkInvariantsFromNode(left, &leftMaxValue))
 201                 return false;
 202         }
 203         if (right) {
 204             if (!checkInvariantsFromNode(right, &rightMaxValue))
 205                 return false;
 206         }
 207         if (!left && !right) {
 208             // Base case.
 209             if (currentMaxValue)
 210                 *currentMaxValue = node->data().high();
 211             return (node->data().high() == node->data().maxHigh());
 212         }
 213         T localMaxValue(node->data().maxHigh());
 214         if (!left || !right) {
 215             if (left)
 216                 localMaxValue = leftMaxValue;
 217             else
 218                 localMaxValue = rightMaxValue;
 219         } else
 220             localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue;
 221         if (localMaxValue < node->data().high())
 222             localMaxValue = node->data().high();
 223         if (!(localMaxValue == node->data().maxHigh())) {
 224 #ifndef NDEBUG
 225             String localMaxValueString = ValueToString<T>::string(localMaxValue);
 226             LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
 227                       node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
 228 #endif
 229             return false;
 230         }
 231         if (currentMaxValue)
 232             *currentMaxValue = localMaxValue;
 233         return true;
 234     }
 235 };
 236
 237 #ifndef NDEBUG
 238 // Support for printing PODIntervals at the PODRedBlackTree level.
 239 template<class T, class UserData>
 240 struct ValueToString<PODInterval<T, UserData>> {
 241     static String string(const PODInterval<T, UserData>& interval)
 242     {
 243         return interval.toString();
 244     }
 245 };
 246 #endif
 247
 248 } // namespace WebCore
 249
 250 #endif // PODIntervalTree_h