#include "config.h"
#include "ShapeInterval.h"
#include <wtf/MathExtras.h>
namespace WebCore {
struct IntervalX1Comparator {
bool operator() (const ShapeInterval& i1, const ShapeInterval& i2) const
{
return i1.x1 < i2.x1;
}
};
bool ShapeInterval::intersect(const ShapeInterval& i, ShapeInterval& rv) const
{
if (x2 < i.x1 || x1 > i.x2)
return false;
rv.x1 = std::max(x1, i.x1);
rv.x2 = std::min(x2, i.x2);
return true;
}
void sortShapeIntervals(Vector<ShapeInterval>& v)
{
std::sort(v.begin(), v.end(), IntervalX1Comparator());
}
void mergeShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
{
if (!v1.size())
rv.appendRange(v2.begin(), v2.end());
else if (!v2.size())
rv.appendRange(v1.begin(), v1.end());
else {
Vector<ShapeInterval> v(v1.size() + v2.size());
ShapeInterval* interval = 0;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin(), IntervalX1Comparator());
for (size_t i = 0; i < v.size(); i++) {
if (!interval)
interval = &v[i];
else if (v[i].x1 >= interval->x1 && v[i].x1 <= interval->x2) interval->x2 = std::max(interval->x2, v[i].x2);
else {
rv.append(*interval);
interval = &v[i];
}
}
if (interval)
rv.append(*interval);
}
}
void intersectShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
{
size_t v1Size = v1.size();
size_t v2Size = v2.size();
if (!v1Size || !v2Size)
return;
ShapeInterval interval;
bool overlap = false;
size_t i1 = 0;
size_t i2 = 0;
while (i1 < v1Size && i2 < v2Size) {
ShapeInterval v12;
if (v1[i1].intersect(v2[i2], v12)) {
if (!overlap || !v12.intersect(interval, interval)) {
if (overlap)
rv.append(interval);
interval = v12;
overlap = true;
}
if (v1[i1].x2 < v2[i2].x2)
i1++;
else
i2++;
} else {
if (overlap)
rv.append(interval);
overlap = false;
if (v1[i1].x1 < v2[i2].x1)
i1++;
else
i2++;
}
}
if (overlap)
rv.append(interval);
}
void subtractShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
{
size_t v1Size = v1.size();
size_t v2Size = v2.size();
if (!v1Size)
return;
if (!v2Size)
rv.appendRange(v1.begin(), v1.end());
else {
size_t i1 = 0, i2 = 0;
rv.appendRange(v1.begin(), v1.end());
while (i1 < rv.size() && i2 < v2Size) {
ShapeInterval& interval1 = rv[i1];
const ShapeInterval& interval2 = v2[i2];
if (interval2.x1 <= interval1.x1 && interval2.x2 >= interval1.x2)
rv.remove(i1);
else if (interval2.x2 < interval1.x1)
i2 += 1;
else if (interval2.x1 > interval1.x2)
i1 += 1;
else if (interval2.x1 > interval1.x1 && interval2.x2 < interval1.x2) {
rv.insert(i1, ShapeInterval(interval1.x1, interval2.x1));
interval1.x1 = interval2.x2;
i2 += 1;
} else if (interval2.x1 <= interval1.x1) {
interval1.x1 = interval2.x2;
i2 += 1;
} else { interval1.x2 = interval2.x1;
i1 += 1;
}
}
}
}
}