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 "PODArena.h"
30#include "PODInterval.h"
31#include "PODRedBlackTree.h"
32#include <wtf/Assertions.h>
33#include <wtf/Noncopyable.h>
34#include <wtf/Vector.h>
35
36namespace WebCore {
37
38#ifndef NDEBUG
39template<class T>
40struct ValueToString;
41#endif
42
43template <class T, class UserData = void*>
44class PODIntervalSearchAdapter {
45public:
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
63private:
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.
72template<class T, class UserData = void*>
73class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData> > {
74    WTF_MAKE_NONCOPYABLE(PODIntervalTree);
75public:
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
135    {
136        if (!PODRedBlackTree<IntervalType>::checkInvariants())
137            return false;
138        if (!this->root())
139            return true;
140        return checkInvariantsFromNode(this->root(), 0);
141    }
142
143private:
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)
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        if (localMaxValue < node->data().high())
238            localMaxValue = node->data().high();
239        if (!(localMaxValue == node->data().maxHigh())) {
240#ifndef NDEBUG
241            String localMaxValueString = ValueToString<T>::string(localMaxValue);
242            LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
243                      node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
244#endif
245            return false;
246        }
247        if (currentMaxValue)
248            *currentMaxValue = localMaxValue;
249        return true;
250    }
251};
252
253#ifndef NDEBUG
254// Support for printing PODIntervals at the PODRedBlackTree level.
255template<class T, class UserData>
256struct ValueToString<PODInterval<T, UserData> > {
257    static String string(const PODInterval<T, UserData>& interval)
258    {
259        return interval.toString();
260    }
261};
262#endif
263
264} // namespace WebCore
265
266#endif // PODIntervalTree_h
267