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