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 |