| 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 |
}; |