| // 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() = default; |
| |
| RangeSet::RangeSet(const gfx::Range& range) { |
| Union(range); |
| } |
| |
| RangeSet::RangeSet(const RangeSet& range_set) = default; |
| |
| RangeSet::RangeSet(RangeSet&& range_set) |
| : ranges_(std::move(range_set.ranges_)) {} |
| |
| RangeSet& RangeSet::operator=(const RangeSet& other) = default; |
| |
| RangeSet::~RangeSet() = default; |
| |
| 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()); |
| } |