123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250 |
- // 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/loader/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());
- }
|