Reland of Improve linearized pdf load/show time.

pdf/range_set.cc

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());
+}