Index: pdf/range_set.cc |
diff --git a/pdf/range_set.cc b/pdf/range_set.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..df53d660023e5f1bec8d1cbcf01005d39c7b0cb2 |
--- /dev/null |
+++ b/pdf/range_set.cc |
@@ -0,0 +1,253 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "pdf/range_set.h" |
+ |
+#include <algorithm> |
+#include <sstream> |
+#include <vector> |
+ |
+namespace chrome_pdf { |
+ |
+namespace { |
+ |
+gfx::Range FixDirection(const gfx::Range& range) { |
+ if (!range.IsValid() || !range.is_reversed()) |
+ return range; |
+ return gfx::Range(range.end() + 1, range.start() + 1); |
+} |
+ |
+} // namespace |
+ |
+RangeSet::RangeSet() {} |
+ |
+RangeSet::RangeSet(const gfx::Range& range) { |
+ Union(range); |
+} |
+ |
+RangeSet::RangeSet(const RangeSet& range_set) : ranges_(range_set.ranges_) {} |
+ |
+RangeSet::RangeSet(RangeSet&& range_set) |
+ : ranges_(std::move(range_set.ranges_)) {} |
+ |
+RangeSet& RangeSet::operator=(const RangeSet& other) { |
+ ranges_ = other.ranges_; |
+ return *this; |
+} |
+ |
+RangeSet::~RangeSet() {} |
+ |
+bool RangeSet::operator==(const RangeSet& other) const { |
+ return other.ranges_ == ranges_; |
+} |
+ |
+bool RangeSet::operator!=(const RangeSet& other) const { |
+ return other.ranges_ != ranges_; |
+} |
+ |
+void RangeSet::Union(const gfx::Range& range) { |
+ if (range.is_empty()) |
+ return; |
+ gfx::Range fixed_range = FixDirection(range); |
+ if (IsEmpty()) { |
+ ranges_.insert(fixed_range); |
+ return; |
+ } |
+ |
+ auto start = ranges_.upper_bound(fixed_range); |
+ if (start != ranges_.begin()) |
+ --start; // start now points to the key equal or lower than offset. |
+ if (start->end() < fixed_range.start()) |
+ ++start; // start element is entirely before current range, skip it. |
+ |
+ auto end = ranges_.upper_bound(gfx::Range(fixed_range.end())); |
+ if (start == end) { // No ranges to merge. |
+ ranges_.insert(fixed_range); |
+ return; |
+ } |
+ |
+ --end; |
+ |
+ int new_start = std::min<size_t>(start->start(), fixed_range.start()); |
+ int new_end = std::max(end->end(), fixed_range.end()); |
+ |
+ ranges_.erase(start, ++end); |
+ ranges_.insert(gfx::Range(new_start, new_end)); |
+} |
+ |
+void RangeSet::Union(const RangeSet& range_set) { |
+ if (&range_set == this) |
+ return; |
+ for (const auto& it : range_set.ranges()) { |
+ Union(it); |
+ } |
+} |
+ |
+bool RangeSet::Contains(uint32_t point) const { |
+ return Contains(gfx::Range(point, point + 1)); |
+} |
+ |
+bool RangeSet::Contains(const gfx::Range& range) const { |
+ if (range.is_empty()) |
+ return false; |
+ const gfx::Range fixed_range = FixDirection(range); |
+ auto it = ranges().upper_bound(fixed_range); |
+ if (it == ranges().begin()) |
+ return false; // No ranges includes range.start(). |
+ |
+ --it; // Now it starts equal or before range.start(). |
+ return it->end() >= fixed_range.end(); |
+} |
+ |
+bool RangeSet::Contains(const RangeSet& range_set) const { |
+ for (const auto& it : range_set.ranges()) { |
+ if (!Contains(it)) |
+ return false; |
+ } |
+ return true; |
+} |
+ |
+bool RangeSet::Intersects(const gfx::Range& range) const { |
+ if (IsEmpty() || range.is_empty()) |
+ return false; |
+ const gfx::Range fixed_range = FixDirection(range); |
+ auto start = ranges_.upper_bound(fixed_range); |
+ if (start != ranges_.begin()) { |
+ --start; |
+ } |
+ // start now points to the key equal or lower than range.start(). |
+ if (start->end() < range.start()) { |
+ // start element is entirely before current range, skip it. |
+ ++start; |
+ } |
+ auto end = ranges_.upper_bound(gfx::Range(fixed_range.end())); |
+ for (auto it = start; it != end; ++it) { |
+ if (fixed_range.end() > it->start() && fixed_range.start() < it->end()) |
+ return true; |
+ } |
+ return false; |
+} |
+ |
+bool RangeSet::Intersects(const RangeSet& range_set) const { |
+ for (const auto& it : range_set.ranges()) { |
+ if (Intersects(it)) |
+ return true; |
+ } |
+ return false; |
+} |
+ |
+void RangeSet::Intersect(const gfx::Range& range) { |
+ Intersect(RangeSet(range)); |
+} |
+ |
+void RangeSet::Intersect(const RangeSet& range_set) { |
+ if (IsEmpty()) |
+ return; |
+ RangesContainer new_ranges; |
+ for (const auto& range : range_set.ranges()) { |
+ auto start = ranges_.upper_bound(range); |
+ if (start != ranges_.begin()) |
+ --start; // start now points to the key equal or lower than |
+ // range.start(). |
+ if (start->end() < range.start()) |
+ ++start; // start element is entirely before current range, skip it. |
+ auto end = ranges_.upper_bound(gfx::Range(range.end())); |
+ if (start == end) { // No data in the current range available. |
+ continue; |
+ } |
+ for (auto it = start; it != end; ++it) { |
+ const gfx::Range new_range = range.Intersect(*it); |
+ if (!new_range.is_empty()) { |
+ new_ranges.insert(new_range); |
+ } |
+ } |
+ } |
+ new_ranges.swap(ranges_); |
+} |
+ |
+void RangeSet::Subtract(const gfx::Range& range) { |
+ if (range.is_empty() || IsEmpty()) |
+ return; |
+ const gfx::Range fixed_range = FixDirection(range); |
+ auto start = ranges_.upper_bound(fixed_range); |
+ if (start != ranges_.begin()) |
+ --start; // start now points to the key equal or lower than |
+ // range.start(). |
+ if (start->end() < fixed_range.start()) |
+ ++start; // start element is entirely before current range, skip it. |
+ auto end = ranges_.upper_bound(gfx::Range(fixed_range.end())); |
+ if (start == end) { // No data in the current range available. |
+ return; |
+ } |
+ std::vector<gfx::Range> new_ranges; |
+ for (auto it = start; it != end; ++it) { |
+ const gfx::Range left(it->start(), |
+ std::min(it->end(), fixed_range.start())); |
+ const gfx::Range right(std::max(it->start(), fixed_range.end()), it->end()); |
+ if (!left.is_empty() && !left.is_reversed()) { |
+ new_ranges.push_back(left); |
+ } |
+ if (!right.is_empty() && !right.is_reversed() && right != left) { |
+ new_ranges.push_back(right); |
+ } |
+ } |
+ ranges_.erase(start, end); |
+ for (const auto& it : new_ranges) { |
+ ranges_.insert(it); |
+ } |
+} |
+ |
+void RangeSet::Subtract(const RangeSet& range_set) { |
+ if (&range_set == this) { |
+ ranges_.clear(); |
+ return; |
+ } |
+ for (const auto& range : range_set.ranges()) { |
+ Subtract(range); |
+ } |
+} |
+ |
+void RangeSet::Xor(const gfx::Range& range) { |
+ Xor(RangeSet(range)); |
+} |
+ |
+void RangeSet::Xor(const RangeSet& range_set) { |
+ RangeSet tmp = *this; |
+ tmp.Intersect(range_set); |
+ Union(range_set); |
+ Subtract(tmp); |
+} |
+ |
+bool RangeSet::IsEmpty() const { |
+ return ranges().empty(); |
+} |
+ |
+void RangeSet::Clear() { |
+ ranges_.clear(); |
+} |
+ |
+gfx::Range RangeSet::First() const { |
+ return *ranges().begin(); |
+} |
+ |
+gfx::Range RangeSet::Last() const { |
+ return *ranges().rbegin(); |
+} |
+ |
+std::string RangeSet::ToString() const { |
+ std::stringstream ss; |
+ ss << "{"; |
+ for (const auto& it : ranges()) { |
+ ss << "[" << it.start() << "," << it.end() << ")"; |
+ } |
+ ss << "}"; |
+ return ss.str(); |
+} |
+ |
+} // namespace chrome_pdf |
+ |
+std::ostream& operator<<(std::ostream& os, |
+ const chrome_pdf::RangeSet& range_set) { |
+ return (os << range_set.ToString()); |
+} |