#ifndef ShapeInterval_h
#define ShapeInterval_h
#include "wtf/Vector.h"
namespace WebCore {
template <typename T>
class ShapeInterval {
WTF_MAKE_FAST_ALLOCATED;
public:
ShapeInterval(T x1 = 0, T x2 = 0)
: m_x1(x1)
, m_x2(x2)
{
ASSERT(x2 >= x1);
}
T x1() const { return m_x1; }
T x2() const { return m_x2; }
T width() const { return m_x2 - m_x1; }
bool isEmpty() const { return m_x1 == m_x2; }
void setX1(T x1)
{
ASSERT(m_x2 >= x1);
m_x1 = x1;
}
void setX2(T x2)
{
ASSERT(x2 >= m_x1);
m_x2 = x2;
}
void set(T x1, T x2)
{
ASSERT(x2 >= x1);
m_x1 = x1;
m_x2 = x2;
}
bool overlaps(const ShapeInterval<T>& interval) const
{
return x2() >= interval.x1() && x1() <= interval.x2();
}
bool contains(const ShapeInterval<T>& interval) const
{
return x1() <= interval.x1() && x2() >= interval.x2();
}
ShapeInterval<T> intersect(const ShapeInterval<T>& interval) const
{
ASSERT(overlaps(interval));
return ShapeInterval<T>(std::max<T>(x1(), interval.x1()), std::min<T>(x2(), interval.x2()));
}
typedef Vector<ShapeInterval<T> > ShapeIntervals;
typedef typename ShapeIntervals::const_iterator const_iterator;
typedef typename ShapeIntervals::iterator iterator;
static void uniteShapeIntervals(const ShapeIntervals& a, const ShapeIntervals& b, ShapeIntervals& result)
{
ASSERT(shapeIntervalsAreSortedAndDisjoint(a) && shapeIntervalsAreSortedAndDisjoint(b));
if (a.isEmpty() || a == b) {
result.appendRange(b.begin(), b.end());
return;
}
if (b.isEmpty()) {
result.appendRange(a.begin(), a.end());
return;
}
const_iterator aNext = a.begin();
const_iterator bNext = b.begin();
while (aNext != a.end() || bNext != b.end()) {
const_iterator next = (bNext == b.end() || (aNext != a.end() && aNext->x1() < bNext->x1())) ? aNext++ : bNext++;
if (result.isEmpty() || !result.last().overlaps(*next))
result.append(*next);
else
result.last().setX2(std::max<T>(result.last().x2(), next->x2()));
}
}
static void intersectShapeIntervals(const ShapeIntervals& a, const ShapeIntervals& b, ShapeIntervals& result)
{
ASSERT(shapeIntervalsAreSortedAndDisjoint(a) && shapeIntervalsAreSortedAndDisjoint(b));
if (a.isEmpty() || b.isEmpty())
return;
if (a == b) {
result.appendRange(a.begin(), a.end());
return;
}
const_iterator aNext = a.begin();
const_iterator bNext = b.begin();
const_iterator working = aNext->x1() < bNext->x1() ? aNext++ : bNext++;
while (aNext != a.end() || bNext != b.end()) {
const_iterator next = (bNext == b.end() || (aNext != a.end() && aNext->x1() < bNext->x1())) ? aNext++ : bNext++;
if (working->overlaps(*next)) {
result.append(working->intersect(*next));
if (next->x2() > working->x2())
working = next;
} else {
working = next;
}
}
}
static void subtractShapeIntervals(const ShapeIntervals& a, const ShapeIntervals& b, ShapeIntervals& result)
{
ASSERT(shapeIntervalsAreSortedAndDisjoint(a) && shapeIntervalsAreSortedAndDisjoint(b));
if (a.isEmpty() || a == b)
return;
if (b.isEmpty()) {
result.appendRange(a.begin(), a.end());
return;
}
const_iterator aNext = a.begin();
const_iterator bNext = b.begin();
ShapeInterval<T> aValue = *aNext;
ShapeInterval<T> bValue = *bNext;
do {
bool aIncrement = false;
bool bIncrement = false;
if (bValue.contains(aValue)) {
aIncrement = true;
} else if (aValue.contains(bValue)) {
if (bValue.x1() > aValue.x1())
result.append(ShapeInterval<T>(aValue.x1(), bValue.x1()));
if (aValue.x2() > bValue.x2())
aValue.setX1(bValue.x2());
else
aIncrement = true;
bIncrement = true;
} else if (aValue.overlaps(bValue)) {
if (aValue.x1() < bValue.x1()) {
result.append(ShapeInterval<T>(aValue.x1(), bValue.x1()));
aIncrement = true;
} else {
aValue.setX1(bValue.x2());
bIncrement = true;
}
} else {
if (aValue.x1() < bValue.x1()) {
result.append(aValue);
aIncrement = true;
} else {
bIncrement = true;
}
}
if (aIncrement && ++aNext != a.end())
aValue = *aNext;
if (bIncrement && ++bNext != b.end())
bValue = *bNext;
} while (aNext != a.end() && bNext != b.end());
if (aNext != a.end()) {
result.append(aValue);
result.appendRange(++aNext, a.end());
}
}
bool operator==(const ShapeInterval<T>& other) const { return x1() == other.x1() && x2() == other.x2(); }
bool operator!=(const ShapeInterval<T>& other) const { return !operator==(other); }
void unite(const ShapeInterval<T>& interval)
{
if (interval.isEmpty())
return;
if (isEmpty())
set(interval.x1(), interval.x2());
else
set(std::min<T>(x1(), interval.x1()), std::max<T>(x2(), interval.x2()));
}
private:
T m_x1;
T m_x2;
static bool shapeIntervalsAreSortedAndDisjoint(const ShapeIntervals& intervals)
{
for (unsigned i = 1; i < intervals.size(); i++) {
if (intervals[i - 1].x2() > intervals[i].x1())
return false;
}
return true;
}
};
typedef ShapeInterval<int> IntShapeInterval;
typedef ShapeInterval<float> FloatShapeInterval;
typedef Vector<IntShapeInterval> IntShapeIntervals;
typedef Vector<FloatShapeInterval> FloatShapeIntervals;
}
#endif