Source/WebCore/platform/PODIntervalTree.h

/*
 * Copyright (C) 2010 Google Inc. All rights reserved.
 * Copyright (C) 2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once

#include "PODInterval.h"
#include "PODRedBlackTree.h"
#include <wtf/Optional.h>
#include <wtf/Vector.h>

// FIXME: The prefix "POD" here isn't correct; this tree works with non-POD types.

namespace WebCore {

template <class T, class UserData>
class PODIntervalSearchAdapter {
public:
    typedef PODInterval<T, UserData> IntervalType;
    
    PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
        : m_result(result)
        , m_lowValue(lowValue)
        , m_highValue(highValue)
    {
    }
    
    const T& lowValue() const { return m_lowValue; }
    const T& highValue() const { return m_highValue; }
    void collectIfNeeded(const IntervalType& data) const
    {
        if (data.overlaps(m_lowValue, m_highValue))
            m_result.append(data);
    }

private:
    Vector<IntervalType>& m_result;
    T m_lowValue;
    T m_highValue;
};

struct PODIntervalNodeUpdater;

// An interval tree, which is a form of augmented red-black tree. It
// supports efficient (O(lg n)) insertion, removal and querying of
// intervals in the tree.
template<class T, class UserData>
class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true> {
    WTF_MAKE_FAST_ALLOCATED;
public:
    // Typedef to reduce typing when declaring intervals to be stored in
    // this tree.
    typedef PODInterval<T, UserData> IntervalType;
    typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;

    // Returns all intervals in the tree which overlap the given query
    // interval. The returned intervals are sorted by increasing low
    // endpoint.
    Vector<IntervalType> allOverlaps(const IntervalType& interval) const
    {
        Vector<IntervalType> result;
        IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
        allOverlapsWithAdapter<IntervalSearchAdapterType>(adapter);
        return result;
    }

    template <class AdapterType>
    void allOverlapsWithAdapter(AdapterType& adapter) const
    {
        // Explicit dereference of "this" required because of
        // inheritance rules in template classes.
        searchForOverlapsFrom<AdapterType>(this->root(), adapter);
    }

    // Helper to create interval objects.
    static IntervalType createInterval(const T& low, const T& high, UserData&& data = { })
    {
        return IntervalType(low, high, WTFMove(data));
    }

    Optional<IntervalType> nextIntervalAfter(const T& point)
    {
        auto next = smallestNodeGreaterThanFrom(point, this->root());
        if (!next)
            return WTF::nullopt;
        return next->data();
    }

#ifndef NDEBUG

    bool checkInvariants() const
    {
        if (!Base::checkInvariants())
            return false;
        if (!this->root())
            return true;
        return checkInvariantsFromNode(this->root(), 0);
    }

#endif

private:
    using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true>;
    typedef typename Base::Node IntervalNode;

    // Starting from the given node, adds all overlaps with the given
    // interval to the result vector. The intervals are sorted by
    // increasing low endpoint.
    template <class AdapterType>
    void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
    {
        if (!node)
            return;

        // Because the intervals are sorted by left endpoint, inorder
        // traversal produces results sorted as desired.

        // See whether we need to traverse the left subtree.
        IntervalNode* left = node->left();
        if (left
            // This is phrased this way to avoid the need for operator
            // <= on type T.
            && !(left->data().maxHigh() < adapter.lowValue()))
            searchForOverlapsFrom<AdapterType>(left, adapter);

        // Check for overlap with current node.
        adapter.collectIfNeeded(node->data());

        // See whether we need to traverse the right subtree.
        // This is phrased this way to avoid the need for operator <=
        // on type T.
        if (!(adapter.highValue() < node->data().low()))
            searchForOverlapsFrom<AdapterType>(node->right(), adapter);
    }

    IntervalNode* smallestNodeGreaterThanFrom(const T& point, IntervalNode* node) const
    {
        if (!node)
            return nullptr;

        if (!(point < node->data().low()))
            return smallestNodeGreaterThanFrom(point, node->right());

        if (auto left = smallestNodeGreaterThanFrom(point, node->right()))
            return left;

        return node;
    }

#ifndef NDEBUG

    bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const
    {
        // These assignments are only done in order to avoid requiring
        // a default constructor on type T.
        T leftMaxValue(node->data().maxHigh());
        T rightMaxValue(node->data().maxHigh());
        IntervalNode* left = node->left();
        IntervalNode* right = node->right();
        if (left) {
            if (!checkInvariantsFromNode(left, &leftMaxValue))
                return false;
        }
        if (right) {
            if (!checkInvariantsFromNode(right, &rightMaxValue))
                return false;
        }
        if (!left && !right) {
            // Base case.
            if (currentMaxValue)
                *currentMaxValue = node->data().high();
            return (node->data().high() == node->data().maxHigh());
        }
        T localMaxValue(node->data().maxHigh());
        if (!left || !right) {
            if (left)
                localMaxValue = leftMaxValue;
            else
                localMaxValue = rightMaxValue;
        } else
            localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue;
        if (localMaxValue < node->data().high())
            localMaxValue = node->data().high();
        if (!(localMaxValue == node->data().maxHigh())) {
            TextStream stream;
            stream << "localMaxValue=" << localMaxValue << "and data =" << node->data();
            LOG_ERROR("PODIntervalTree verification failed at node 0x%p: %s",
                node, stream.release().utf8().data());
            return false;
        }
        if (currentMaxValue)
            *currentMaxValue = localMaxValue;
        return true;
    }

#endif

};

struct PODIntervalNodeUpdater {
    template<typename Node> static bool update(Node& node)
    {
        auto* curMax = &node.data().high();
        auto* left = node.left();
        if (left) {
            if (*curMax < left->data().maxHigh())
                curMax = &left->data().maxHigh();
        }
        auto* right = node.right();
        if (right) {
            if (*curMax < right->data().maxHigh())
                curMax = &right->data().maxHigh();
        }
        // This is phrased like this to avoid needing operator!= on type T.
        if (!(*curMax == node.data().maxHigh())) {
            node.data().setMaxHigh(*curMax);
            return true;
        }
        return false;
    }
};

} // namespace WebCore