range_set.cc 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "pdf/loader/range_set.h"
  5. #include <algorithm>
  6. #include <sstream>
  7. #include <vector>
  8. namespace chrome_pdf {
  9. namespace {
  10. gfx::Range FixDirection(const gfx::Range& range) {
  11. if (!range.IsValid() || !range.is_reversed())
  12. return range;
  13. return gfx::Range(range.end() + 1, range.start() + 1);
  14. }
  15. } // namespace
  16. RangeSet::RangeSet() = default;
  17. RangeSet::RangeSet(const gfx::Range& range) {
  18. Union(range);
  19. }
  20. RangeSet::RangeSet(const RangeSet& range_set) = default;
  21. RangeSet::RangeSet(RangeSet&& range_set)
  22. : ranges_(std::move(range_set.ranges_)) {}
  23. RangeSet& RangeSet::operator=(const RangeSet& other) = default;
  24. RangeSet::~RangeSet() = default;
  25. bool RangeSet::operator==(const RangeSet& other) const {
  26. return other.ranges_ == ranges_;
  27. }
  28. bool RangeSet::operator!=(const RangeSet& other) const {
  29. return other.ranges_ != ranges_;
  30. }
  31. void RangeSet::Union(const gfx::Range& range) {
  32. if (range.is_empty())
  33. return;
  34. gfx::Range fixed_range = FixDirection(range);
  35. if (IsEmpty()) {
  36. ranges_.insert(fixed_range);
  37. return;
  38. }
  39. auto start = ranges_.upper_bound(fixed_range);
  40. if (start != ranges_.begin())
  41. --start; // start now points to the key equal or lower than offset.
  42. if (start->end() < fixed_range.start())
  43. ++start; // start element is entirely before current range, skip it.
  44. auto end = ranges_.upper_bound(gfx::Range(fixed_range.end()));
  45. if (start == end) { // No ranges to merge.
  46. ranges_.insert(fixed_range);
  47. return;
  48. }
  49. --end;
  50. int new_start = std::min<size_t>(start->start(), fixed_range.start());
  51. int new_end = std::max(end->end(), fixed_range.end());
  52. ranges_.erase(start, ++end);
  53. ranges_.insert(gfx::Range(new_start, new_end));
  54. }
  55. void RangeSet::Union(const RangeSet& range_set) {
  56. if (&range_set == this)
  57. return;
  58. for (const auto& it : range_set.ranges()) {
  59. Union(it);
  60. }
  61. }
  62. bool RangeSet::Contains(uint32_t point) const {
  63. return Contains(gfx::Range(point, point + 1));
  64. }
  65. bool RangeSet::Contains(const gfx::Range& range) const {
  66. if (range.is_empty())
  67. return false;
  68. const gfx::Range fixed_range = FixDirection(range);
  69. auto it = ranges().upper_bound(fixed_range);
  70. if (it == ranges().begin())
  71. return false; // No ranges includes range.start().
  72. --it; // Now it starts equal or before range.start().
  73. return it->end() >= fixed_range.end();
  74. }
  75. bool RangeSet::Contains(const RangeSet& range_set) const {
  76. for (const auto& it : range_set.ranges()) {
  77. if (!Contains(it))
  78. return false;
  79. }
  80. return true;
  81. }
  82. bool RangeSet::Intersects(const gfx::Range& range) const {
  83. if (IsEmpty() || range.is_empty())
  84. return false;
  85. const gfx::Range fixed_range = FixDirection(range);
  86. auto start = ranges_.upper_bound(fixed_range);
  87. if (start != ranges_.begin()) {
  88. --start;
  89. }
  90. // start now points to the key equal or lower than range.start().
  91. if (start->end() < range.start()) {
  92. // start element is entirely before current range, skip it.
  93. ++start;
  94. }
  95. auto end = ranges_.upper_bound(gfx::Range(fixed_range.end()));
  96. for (auto it = start; it != end; ++it) {
  97. if (fixed_range.end() > it->start() && fixed_range.start() < it->end())
  98. return true;
  99. }
  100. return false;
  101. }
  102. bool RangeSet::Intersects(const RangeSet& range_set) const {
  103. for (const auto& it : range_set.ranges()) {
  104. if (Intersects(it))
  105. return true;
  106. }
  107. return false;
  108. }
  109. void RangeSet::Intersect(const gfx::Range& range) {
  110. Intersect(RangeSet(range));
  111. }
  112. void RangeSet::Intersect(const RangeSet& range_set) {
  113. if (IsEmpty())
  114. return;
  115. RangesContainer new_ranges;
  116. for (const auto& range : range_set.ranges()) {
  117. auto start = ranges_.upper_bound(range);
  118. if (start != ranges_.begin())
  119. --start; // start now points to the key equal or lower than
  120. // range.start().
  121. if (start->end() < range.start())
  122. ++start; // start element is entirely before current range, skip it.
  123. auto end = ranges_.upper_bound(gfx::Range(range.end()));
  124. if (start == end) { // No data in the current range available.
  125. continue;
  126. }
  127. for (auto it = start; it != end; ++it) {
  128. const gfx::Range new_range = range.Intersect(*it);
  129. if (!new_range.is_empty()) {
  130. new_ranges.insert(new_range);
  131. }
  132. }
  133. }
  134. new_ranges.swap(ranges_);
  135. }
  136. void RangeSet::Subtract(const gfx::Range& range) {
  137. if (range.is_empty() || IsEmpty())
  138. return;
  139. const gfx::Range fixed_range = FixDirection(range);
  140. auto start = ranges_.upper_bound(fixed_range);
  141. if (start != ranges_.begin())
  142. --start; // start now points to the key equal or lower than
  143. // range.start().
  144. if (start->end() < fixed_range.start())
  145. ++start; // start element is entirely before current range, skip it.
  146. auto end = ranges_.upper_bound(gfx::Range(fixed_range.end()));
  147. if (start == end) { // No data in the current range available.
  148. return;
  149. }
  150. std::vector<gfx::Range> new_ranges;
  151. for (auto it = start; it != end; ++it) {
  152. const gfx::Range left(it->start(),
  153. std::min(it->end(), fixed_range.start()));
  154. const gfx::Range right(std::max(it->start(), fixed_range.end()), it->end());
  155. if (!left.is_empty() && !left.is_reversed()) {
  156. new_ranges.push_back(left);
  157. }
  158. if (!right.is_empty() && !right.is_reversed() && right != left) {
  159. new_ranges.push_back(right);
  160. }
  161. }
  162. ranges_.erase(start, end);
  163. for (const auto& it : new_ranges) {
  164. ranges_.insert(it);
  165. }
  166. }
  167. void RangeSet::Subtract(const RangeSet& range_set) {
  168. if (&range_set == this) {
  169. ranges_.clear();
  170. return;
  171. }
  172. for (const auto& range : range_set.ranges()) {
  173. Subtract(range);
  174. }
  175. }
  176. void RangeSet::Xor(const gfx::Range& range) {
  177. Xor(RangeSet(range));
  178. }
  179. void RangeSet::Xor(const RangeSet& range_set) {
  180. RangeSet tmp = *this;
  181. tmp.Intersect(range_set);
  182. Union(range_set);
  183. Subtract(tmp);
  184. }
  185. bool RangeSet::IsEmpty() const {
  186. return ranges().empty();
  187. }
  188. void RangeSet::Clear() {
  189. ranges_.clear();
  190. }
  191. gfx::Range RangeSet::First() const {
  192. return *ranges().begin();
  193. }
  194. gfx::Range RangeSet::Last() const {
  195. return *ranges().rbegin();
  196. }
  197. std::string RangeSet::ToString() const {
  198. std::stringstream ss;
  199. ss << "{";
  200. for (const auto& it : ranges()) {
  201. ss << "[" << it.start() << "," << it.end() << ")";
  202. }
  203. ss << "}";
  204. return ss.str();
  205. }
  206. } // namespace chrome_pdf
  207. std::ostream& operator<<(std::ostream& os,
  208. const chrome_pdf::RangeSet& range_set) {
  209. return (os << range_set.ToString());
  210. }