diff options
Diffstat (limited to 'Source/WebCore/rendering/ExclusionInterval.cpp')
| -rw-r--r-- | Source/WebCore/rendering/ExclusionInterval.cpp | 166 |
1 files changed, 166 insertions, 0 deletions
diff --git a/Source/WebCore/rendering/ExclusionInterval.cpp b/Source/WebCore/rendering/ExclusionInterval.cpp new file mode 100644 index 000000000..4e0ef7a98 --- /dev/null +++ b/Source/WebCore/rendering/ExclusionInterval.cpp @@ -0,0 +1,166 @@ +/* + * Copyright (C) 2012 Adobe Systems Incorporated. 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 THE COPYRIGHT HOLDERS AND 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 THE + * COPYRIGHT HOLDER OR 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. + */ + +#include "config.h" +#include "ExclusionInterval.h" + +#include <wtf/MathExtras.h> + +namespace WebCore { + +struct IntervalX1Comparator { + bool operator() (const ExclusionInterval& i1, const ExclusionInterval& i2) const + { + return i1.x1 < i2.x1; + } +}; + +bool ExclusionInterval::intersect(const ExclusionInterval& i, ExclusionInterval& 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 sortExclusionIntervals(Vector<ExclusionInterval>& v) +{ + std::sort(v.begin(), v.end(), IntervalX1Comparator()); +} + +void mergeExclusionIntervals(const Vector<ExclusionInterval>& v1, const Vector<ExclusionInterval>& v2, Vector<ExclusionInterval>& rv) +{ + if (!v1.size()) + rv.appendRange(v2.begin(), v2.end()); + else if (!v2.size()) + rv.appendRange(v1.begin(), v1.end()); + else { + Vector<ExclusionInterval> v(v1.size() + v2.size()); + ExclusionInterval* 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) // FIXME: 1st <= test not needed? + interval->x2 = std::max(interval->x2, v[i].x2); + else { + rv.append(*interval); + interval = &v[i]; + } + } + + if (interval) + rv.append(*interval); + } +} + +void intersectExclusionIntervals(const Vector<ExclusionInterval>& v1, const Vector<ExclusionInterval>& v2, Vector<ExclusionInterval>& rv) +{ + size_t v1Size = v1.size(); + size_t v2Size = v2.size(); + + if (!v1Size || !v2Size) + return; + + ExclusionInterval interval; + bool overlap = false; + size_t i1 = 0; + size_t i2 = 0; + + while (i1 < v1Size && i2 < v2Size) { + ExclusionInterval 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 subtractExclusionIntervals(const Vector<ExclusionInterval>& v1, const Vector<ExclusionInterval>& v2, Vector<ExclusionInterval>& 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) { + ExclusionInterval& interval1 = rv[i1]; + const ExclusionInterval& 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, ExclusionInterval(interval1.x1, interval2.x1)); + interval1.x1 = interval2.x2; + i2 += 1; + } else if (interval2.x1 <= interval1.x1) { + interval1.x1 = interval2.x2; + i2 += 1; + } else { // (interval2.x2 >= interval1.x2) + interval1.x2 = interval2.x1; + i1 += 1; + } + } + } +} + +} // namespace WebCore |