Debian Codegraph @

closure-library/closure/goog/math/rangeset.js

raw
1 // Copyright 2009 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview A RangeSet is a structure that manages a list of ranges.
17 * Numeric ranges may be added and removed from the RangeSet, and the set may
18 * be queried for the presence or absence of individual values or ranges of
19 * values.
20 *
21 * This may be used, for example, to track the availability of sparse elements
22 * in an array without iterating over the entire array.
23 *
24 * @author [email protected] (Shawn Brenneman)
25 */
26
27 goog.provide('goog.math.RangeSet');
28
29 goog.require('goog.array');
30 goog.require('goog.iter.Iterator');
31 goog.require('goog.iter.StopIteration');
32 goog.require('goog.math.Range');
33
34
35
36 /**
37 * Constructs a new RangeSet, which can store numeric ranges.
38 *
39 * Ranges are treated as half-closed: that is, they are exclusive of their end
40 * value [start, end).
41 *
42 * New ranges added to the set which overlap the values in one or more existing
43 * ranges will be merged.
44 *
45 * @struct
46 * @constructor
47 * @final
48 */
49 goog.math.RangeSet = function() {
50 /**
51 * A sorted list of ranges that represent the values in the set.
52 * @type {!Array<!goog.math.Range>}
53 * @private
54 */
55 this.ranges_ = [];
56 };
57
58
59 if (goog.DEBUG) {
60 /**
61 * @return {string} A debug string in the form [[1, 5], [8, 9], [15, 30]].
62 * @override
63 */
64 goog.math.RangeSet.prototype.toString = function() {
65 return '[' + this.ranges_.join(', ') + ']';
66 };
67 }
68
69
70 /**
71 * Compares two sets for equality.
72 *
73 * @param {goog.math.RangeSet} a A range set.
74 * @param {goog.math.RangeSet} b A range set.
75 * @return {boolean} Whether both sets contain the same values.
76 */
77 goog.math.RangeSet.equals = function(a, b) {
78 // Fast check for object equality. Also succeeds if a and b are both null.
79 return a == b ||
80 !!(a && b &&
81 goog.array.equals(a.ranges_, b.ranges_, goog.math.Range.equals));
82 };
83
84
85 /**
86 * @return {!goog.math.RangeSet} A new RangeSet containing the same values as
87 * this one.
88 */
89 goog.math.RangeSet.prototype.clone = function() {
90 var set = new goog.math.RangeSet();
91
92 for (var i = this.ranges_.length; i--;) {
93 set.ranges_[i] = this.ranges_[i].clone();
94 }
95
96 return set;
97 };
98
99
100 /**
101 * Adds a range to the set. If the new range overlaps existing values, those
102 * ranges will be merged.
103 *
104 * @param {goog.math.Range} a The range to add.
105 */
106 goog.math.RangeSet.prototype.add = function(a) {
107 if (a.end <= a.start) {
108 // Empty ranges are ignored.
109 return;
110 }
111
112 a = a.clone();
113
114 // Find the insertion point.
115 for (var i = 0, b; b = this.ranges_[i]; i++) {
116 if (a.start <= b.end) {
117 a.start = Math.min(a.start, b.start);
118 break;
119 }
120 }
121
122 var insertionPoint = i;
123
124 for (; b = this.ranges_[i]; i++) {
125 if (a.end < b.start) {
126 break;
127 }
128 a.end = Math.max(a.end, b.end);
129 }
130
131 this.ranges_.splice(insertionPoint, i - insertionPoint, a);
132 };
133
134
135 /**
136 * Removes a range of values from the set.
137 *
138 * @param {goog.math.Range} a The range to remove.
139 */
140 goog.math.RangeSet.prototype.remove = function(a) {
141 if (a.end <= a.start) {
142 // Empty ranges are ignored.
143 return;
144 }
145
146 // Find the insertion point.
147 for (var i = 0, b; b = this.ranges_[i]; i++) {
148 if (a.start < b.end) {
149 break;
150 }
151 }
152
153 if (!b || a.end < b.start) {
154 // The range being removed doesn't overlap any existing range. Exit early.
155 return;
156 }
157
158 var insertionPoint = i;
159
160 if (a.start > b.start) {
161 // There is an overlap with the nearest range. Modify it accordingly.
162 insertionPoint++;
163
164 if (a.end < b.end) {
165 goog.array.insertAt(
166 this.ranges_, new goog.math.Range(a.end, b.end), insertionPoint);
167 }
168 b.end = a.start;
169 }
170
171 for (i = insertionPoint; b = this.ranges_[i]; i++) {
172 b.start = Math.max(a.end, b.start);
173 if (a.end < b.end) {
174 break;
175 }
176 }
177
178 this.ranges_.splice(insertionPoint, i - insertionPoint);
179 };
180
181
182 /**
183 * Determines whether a given range is in the set. Only succeeds if the entire
184 * range is available.
185 *
186 * @param {goog.math.Range} a The query range.
187 * @return {boolean} Whether the entire requested range is set.
188 */
189 goog.math.RangeSet.prototype.contains = function(a) {
190 if (a.end <= a.start) {
191 return false;
192 }
193
194 for (var i = 0, b; b = this.ranges_[i]; i++) {
195 if (a.start < b.end) {
196 if (a.end >= b.start) {
197 return goog.math.Range.contains(b, a);
198 }
199 break;
200 }
201 }
202 return false;
203 };
204
205
206 /**
207 * Determines whether a given value is set in the RangeSet.
208 *
209 * @param {number} value The value to test.
210 * @return {boolean} Whether the given value is in the set.
211 */
212 goog.math.RangeSet.prototype.containsValue = function(value) {
213 for (var i = 0, b; b = this.ranges_[i]; i++) {
214 if (value < b.end) {
215 if (value >= b.start) {
216 return true;
217 }
218 break;
219 }
220 }
221 return false;
222 };
223
224
225 /**
226 * Returns the union of this RangeSet with another.
227 *
228 * @param {goog.math.RangeSet} set Another RangeSet.
229 * @return {!goog.math.RangeSet} A new RangeSet containing all values from
230 * either set.
231 */
232 goog.math.RangeSet.prototype.union = function(set) {
233 // TODO(brenneman): A linear-time merge would be preferable if it is ever a
234 // bottleneck.
235 set = set.clone();
236
237 for (var i = 0, a; a = this.ranges_[i]; i++) {
238 set.add(a);
239 }
240
241 return set;
242 };
243
244
245 /**
246 * Subtracts the ranges of another set from this one, returning the result
247 * as a new RangeSet.
248 *
249 * @param {!goog.math.RangeSet} set The RangeSet to subtract.
250 * @return {!goog.math.RangeSet} A new RangeSet containing all values in this
251 * set minus the values of the input set.
252 */
253 goog.math.RangeSet.prototype.difference = function(set) {
254 var ret = this.clone();
255
256 for (var i = 0, a; a = set.ranges_[i]; i++) {
257 ret.remove(a);
258 }
259
260 return ret;
261 };
262
263
264 /**
265 * Intersects this RangeSet with another.
266 *
267 * @param {goog.math.RangeSet} set The RangeSet to intersect with.
268 * @return {!goog.math.RangeSet} A new RangeSet containing all values set in
269 * both this and the input set.
270 */
271 goog.math.RangeSet.prototype.intersection = function(set) {
272 if (this.isEmpty() || set.isEmpty()) {
273 return new goog.math.RangeSet();
274 }
275
276 return this.difference(set.inverse(this.getBounds()));
277 };
278
279
280 /**
281 * Creates a subset of this set over the input range.
282 *
283 * @param {goog.math.Range} range The range to copy into the slice.
284 * @return {!goog.math.RangeSet} A new RangeSet with a copy of the values in the
285 * input range.
286 */
287 goog.math.RangeSet.prototype.slice = function(range) {
288 var set = new goog.math.RangeSet();
289 if (range.start >= range.end) {
290 return set;
291 }
292
293 for (var i = 0, b; b = this.ranges_[i]; i++) {
294 if (b.end <= range.start) {
295 continue;
296 }
297 if (b.start > range.end) {
298 break;
299 }
300
301 set.add(
302 new goog.math.Range(
303 Math.max(range.start, b.start), Math.min(range.end, b.end)));
304 }
305
306 return set;
307 };
308
309
310 /**
311 * Creates an inverted slice of this set over the input range.
312 *
313 * @param {goog.math.Range} range The range to copy into the slice.
314 * @return {!goog.math.RangeSet} A new RangeSet containing inverted values from
315 * the original over the input range.
316 */
317 goog.math.RangeSet.prototype.inverse = function(range) {
318 var set = new goog.math.RangeSet();
319
320 set.add(range);
321 for (var i = 0, b; b = this.ranges_[i]; i++) {
322 if (range.start >= b.end) {
323 continue;
324 }
325 if (range.end < b.start) {
326 break;
327 }
328
329 set.remove(b);
330 }
331
332 return set;
333 };
334
335
336 /**
337 * @return {number} The sum of the lengths of ranges covered in the set.
338 */
339 goog.math.RangeSet.prototype.coveredLength = function() {
340 return /** @type {number} */ (
341 goog.array.reduce(this.ranges_, function(res, range) {
342 return res + range.end - range.start;
343 }, 0));
344 };
345
346
347 /**
348 * @return {goog.math.Range} The total range this set covers, ignoring any
349 * gaps between ranges.
350 */
351 goog.math.RangeSet.prototype.getBounds = function() {
352 if (this.ranges_.length) {
353 return new goog.math.Range(
354 this.ranges_[0].start, goog.array.peek(this.ranges_).end);
355 }
356
357 return null;
358 };
359
360
361 /**
362 * @return {boolean} Whether any ranges are currently in the set.
363 */
364 goog.math.RangeSet.prototype.isEmpty = function() {
365 return this.ranges_.length == 0;
366 };
367
368
369 /**
370 * Removes all values in the set.
371 */
372 goog.math.RangeSet.prototype.clear = function() {
373 this.ranges_.length = 0;
374 };
375
376
377 /**
378 * Returns an iterator that iterates over the ranges in the RangeSet.
379 *
380 * @param {boolean=} opt_keys Ignored for RangeSets.
381 * @return {!goog.iter.Iterator} An iterator over the values in the set.
382 */
383 goog.math.RangeSet.prototype.__iterator__ = function(opt_keys) {
384 var i = 0;
385 var list = this.ranges_;
386
387 var iterator = new goog.iter.Iterator();
388 iterator.next = function() {
389 if (i >= list.length) {
390 throw goog.iter.StopIteration;
391 }
392 return list[i++].clone();
393 };
394
395 return iterator;
396 };