#ifndef PODIntervalTree_h
#define PODIntervalTree_h
#include "PODArena.h"
#include "PODInterval.h"
#include "PODRedBlackTree.h"
#include <wtf/Assertions.h>
#include <wtf/Noncopyable.h>
#include <wtf/Vector.h>
namespace WebCore {
#ifndef NDEBUG
template<class T>
struct ValueToString;
#endif
template<class T, class UserData = void*>
class PODIntervalTree : public PODRedBlackTree<PODInterval<T, UserData> > {
WTF_MAKE_NONCOPYABLE(PODIntervalTree);
public:
typedef PODInterval<T, UserData> IntervalType;
PODIntervalTree()
: PODRedBlackTree<IntervalType>()
{
init();
}
explicit PODIntervalTree(PassRefPtr<PODArena> arena)
: PODRedBlackTree<IntervalType>(arena)
{
init();
}
Vector<IntervalType> allOverlaps(const IntervalType& interval) const
{
Vector<IntervalType> result;
allOverlaps(interval, result);
return result;
}
void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const
{
searchForOverlapsFrom(this->root(), interval, result);
}
static IntervalType createInterval(const T& low, const T& high, const UserData data = 0)
{
return IntervalType(low, high, data);
}
virtual bool checkInvariants() const
{
if (!PODRedBlackTree<IntervalType>::checkInvariants())
return false;
if (!this->root())
return true;
return checkInvariantsFromNode(this->root(), 0);
}
private:
typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode;
void init()
{
this->setNeedsFullOrderingComparisons(true);
}
void searchForOverlapsFrom(IntervalNode* node, const IntervalType& interval, Vector<IntervalType>& res) const
{
if (!node)
return;
IntervalNode* left = node->left();
if (left
&& !(left->data().maxHigh() < interval.low()))
searchForOverlapsFrom(left, interval, res);
if (node->data().overlaps(interval))
res.append(node->data());
if (!(interval.high() < node->data().low()))
searchForOverlapsFrom(node->right(), interval, res);
}
virtual bool updateNode(IntervalNode* node)
{
const T* curMax = &node->data().high();
IntervalNode* left = node->left();
if (left) {
if (*curMax < left->data().maxHigh())
curMax = &left->data().maxHigh();
}
IntervalNode* 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;
}
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())) {
#ifndef NDEBUG
String localMaxValueString = ValueToString<T>::string(localMaxValue);
LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s",
node, localMaxValueString.utf8().data(), node->data().toString().utf8().data());
#endif
return false;
}
if (currentMaxValue)
*currentMaxValue = localMaxValue;
return true;
}
};
#ifndef NDEBUG
template<class T, class UserData>
struct ValueToString<PODInterval<T, UserData> > {
static String string(const PODInterval<T, UserData>& interval)
{
return interval.toString();
}
};
#endif
}
#endif // PODIntervalTree_h