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 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
    268