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