#pragma once
#include "PODInterval.h"
#include "PODRedBlackTree.h"
#include <wtf/Optional.h>
#include <wtf/Vector.h>
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;
template<class T, class UserData>
class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true> {
WTF_MAKE_FAST_ALLOCATED;
public:
typedef PODInterval<T, UserData> IntervalType;
typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
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
{
searchForOverlapsFrom<AdapterType>(this->root(), adapter);
}
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;
template <class AdapterType>
void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
{
if (!node)
return;
IntervalNode* left = node->left();
if (left
&& !(left->data().maxHigh() < adapter.lowValue()))
searchForOverlapsFrom<AdapterType>(left, adapter);
adapter.collectIfNeeded(node->data());
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
{
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) {
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();
}
if (!(*curMax == node.data().maxHigh())) {
node.data().setMaxHigh(*curMax);
return true;
}
return false;
}
};
}