15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010 Google Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef PODIntervalTree_h 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define PODIntervalTree_h 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 291e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODArena.h" 301e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODInterval.h" 311e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODRedBlackTree.h" 327757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Assertions.h" 337757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Noncopyable.h" 347757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Vector.h" 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 36c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<class T> 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString; 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template <class T, class UserData = void*> 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class PODIntervalSearchAdapter { 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef PODInterval<T, UserData> IntervalType; 4702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_result(result) 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_lowValue(lowValue) 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_highValue(highValue) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T& lowValue() const { return m_lowValue; } 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T& highValue() const { return m_highValue; } 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void collectIfNeeded(const IntervalType& data) const 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (data.overlaps(m_lowValue, m_highValue)) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_result.append(data); 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntervalType>& m_result; 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T m_lowValue; 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T m_highValue; 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// An interval tree, which is a form of augmented red-black tree. It 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// supports efficient (O(lg n)) insertion, removal and querying of 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// intervals in the tree. 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<class T, class UserData = void*> 7309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class PODIntervalTree FINAL : public PODRedBlackTree<PODInterval<T, UserData> > { 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(PODIntervalTree); 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Typedef to reduce typing when declaring intervals to be stored in 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // this tree. 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef PODInterval<T, UserData> IntervalType; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType; 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree(UninitializedTreeEnum unitializedTree) 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : PODRedBlackTree<IntervalType>(unitializedTree) 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) init(); 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree() 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : PODRedBlackTree<IntervalType>() 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) init(); 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) explicit PODIntervalTree(PassRefPtr<PODArena> arena) 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : PODRedBlackTree<IntervalType>(arena) 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) init(); 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns all intervals in the tree which overlap the given query 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // interval. The returned intervals are sorted by increasing low 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // endpoint. 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntervalType> allOverlaps(const IntervalType& interval) const 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<IntervalType> result; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) allOverlaps(interval, result); 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns all intervals in the tree which overlap the given query 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // interval. The returned intervals are sorted by increasing low 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // endpoint. 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Explicit dereference of "this" required because of 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // inheritance rules in template classes. 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalSearchAdapterType adapter(result, interval.low(), interval.high()); 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter); 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <class AdapterType> 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void allOverlapsWithAdapter(AdapterType& adapter) const 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Explicit dereference of "this" required because of 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // inheritance rules in template classes. 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) searchForOverlapsFrom<AdapterType>(this->root(), adapter); 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Helper to create interval objects. 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static IntervalType createInterval(const T& low, const T& high, const UserData data = 0) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return IntervalType(low, high, data); 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) virtual bool checkInvariants() const OVERRIDE 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!PODRedBlackTree<IntervalType>::checkInvariants()) 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this->root()) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return checkInvariantsFromNode(this->root(), 0); 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Initializes the tree. 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void init() 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Explicit dereference of "this" required because of 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // inheritance rules in template classes. 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->setNeedsFullOrderingComparisons(true); 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Starting from the given node, adds all overlaps with the given 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // interval to the result vector. The intervals are sorted by 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // increasing low endpoint. 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <class AdapterType> 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!node) 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Because the intervals are sorted by left endpoint, inorder 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // traversal produces results sorted as desired. 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See whether we need to traverse the left subtree. 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalNode* left = node->left(); 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is phrased this way to avoid the need for operator 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // <= on type T. 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) && !(left->data().maxHigh() < adapter.lowValue())) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) searchForOverlapsFrom<AdapterType>(left, adapter); 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Check for overlap with current node. 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) adapter.collectIfNeeded(node->data()); 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See whether we need to traverse the right subtree. 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is phrased this way to avoid the need for operator <= 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // on type T. 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(adapter.highValue() < node->data().low())) 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) searchForOverlapsFrom<AdapterType>(node->right(), adapter); 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 18409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) virtual bool updateNode(IntervalNode* node) OVERRIDE 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Would use const T&, but need to reassign this reference in this 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // function. 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T* curMax = &node->data().high(); 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalNode* left = node->left(); 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left) { 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*curMax < left->data().maxHigh()) 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) curMax = &left->data().maxHigh(); 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalNode* right = node->right(); 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (right) { 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*curMax < right->data().maxHigh()) 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) curMax = &right->data().maxHigh(); 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is phrased like this to avoid needing operator!= on type T. 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(*curMax == node->data().maxHigh())) { 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->data().setMaxHigh(*curMax); 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These assignments are only done in order to avoid requiring 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // a default constructor on type T. 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T leftMaxValue(node->data().maxHigh()); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T rightMaxValue(node->data().maxHigh()); 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalNode* left = node->left(); 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalNode* right = node->right(); 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left) { 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!checkInvariantsFromNode(left, &leftMaxValue)) 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (right) { 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!checkInvariantsFromNode(right, &rightMaxValue)) 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!left && !right) { 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Base case. 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (currentMaxValue) 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *currentMaxValue = node->data().high(); 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return (node->data().high() == node->data().maxHigh()); 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T localMaxValue(node->data().maxHigh()); 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!left || !right) { 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left) 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) localMaxValue = leftMaxValue; 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) localMaxValue = rightMaxValue; 2351e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue; 2371e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (localMaxValue < node->data().high()) 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) localMaxValue = node->data().high(); 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(localMaxValue == node->data().maxHigh())) { 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) String localMaxValueString = ValueToString<T>::string(localMaxValue); 243a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s", 2441e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) node, localMaxValueString.utf8().data(), node->data().toString().utf8().data()); 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (currentMaxValue) 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *currentMaxValue = localMaxValue; 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Support for printing PODIntervals at the PODRedBlackTree level. 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<class T, class UserData> 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<PODInterval<T, UserData> > { 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(const PODInterval<T, UserData>& interval) 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return interval.toString(); 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // PODIntervalTree_h 268