/**
* @license
* Copyright The Closure Library Authors.
* SPDX-License-Identifier: Apache-2.0
*/
/**
* @fileoverview A RangeSet is a structure that manages a list of ranges.
* Numeric ranges may be added and removed from the RangeSet, and the set may
* be queried for the presence or absence of individual values or ranges of
* values.
*
* This may be used, for example, to track the availability of sparse elements
* in an array without iterating over the entire array.
*/
goog.provide('goog.math.RangeSet');
goog.require('goog.array');
goog.require('goog.iter.Iterator');
goog.require('goog.iter.StopIteration');
goog.require('goog.math.Range');
/**
* Constructs a new RangeSet, which can store numeric ranges.
*
* Ranges are treated as half-closed: that is, they are exclusive of their end
* value [start, end).
*
* New ranges added to the set which overlap the values in one or more existing
* ranges will be merged.
*
* @struct
* @constructor
* @final
*/
goog.math.RangeSet = function() {
'use strict';
/**
* A sorted list of ranges that represent the values in the set.
* @type {!Array<!goog.math.Range>}
* @private
*/
this.ranges_ = [];
};
if (goog.DEBUG) {
/**
* @return {string} A debug string in the form [[1, 5], [8, 9], [15, 30]].
* @override
*/
goog.math.RangeSet.prototype.toString = function() {
'use strict';
return '[' + this.ranges_.join(', ') + ']';
};
}
/**
* Compares two sets for equality.
*
* @param {goog.math.RangeSet} a A range set.
* @param {goog.math.RangeSet} b A range set.
* @return {boolean} Whether both sets contain the same values.
*/
goog.math.RangeSet.equals = function(a, b) {
'use strict';
// Fast check for object equality. Also succeeds if a and b are both null.
return a == b ||
!!(a && b &&
goog.array.equals(a.ranges_, b.ranges_, goog.math.Range.equals));
};
/**
* @return {!goog.math.RangeSet} A new RangeSet containing the same values as
* this one.
*/
goog.math.RangeSet.prototype.clone = function() {
'use strict';
var set = new goog.math.RangeSet();
for (var i = this.ranges_.length; i--;) {
set.ranges_[i] = this.ranges_[i].clone();
}
return set;
};
/**
* Adds a range to the set. If the new range overlaps existing values, those
* ranges will be merged.
*
* @param {goog.math.Range} a The range to add.
*/
goog.math.RangeSet.prototype.add = function(a) {
'use strict';
if (a.end <= a.start) {
// Empty ranges are ignored.
return;
}
a = a.clone();
// Find the insertion point.
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (a.start <= b.end) {
a.start = Math.min(a.start, b.start);
break;
}
}
var insertionPoint = i;
for (; b = this.ranges_[i]; i++) {
if (a.end < b.start) {
break;
}
a.end = Math.max(a.end, b.end);
}
this.ranges_.splice(insertionPoint, i - insertionPoint, a);
};
/**
* Removes a range of values from the set.
*
* @param {goog.math.Range} a The range to remove.
*/
goog.math.RangeSet.prototype.remove = function(a) {
'use strict';
if (a.end <= a.start) {
// Empty ranges are ignored.
return;
}
// Find the insertion point.
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (a.start < b.end) {
break;
}
}
if (!b || a.end < b.start) {
// The range being removed doesn't overlap any existing range. Exit early.
return;
}
var insertionPoint = i;
if (a.start > b.start) {
// There is an overlap with the nearest range. Modify it accordingly.
insertionPoint++;
if (a.end < b.end) {
goog.array.insertAt(
this.ranges_, new goog.math.Range(a.end, b.end), insertionPoint);
}
b.end = a.start;
}
for (i = insertionPoint; b = this.ranges_[i]; i++) {
b.start = Math.max(a.end, b.start);
if (a.end < b.end) {
break;
}
}
this.ranges_.splice(insertionPoint, i - insertionPoint);
};
/**
* Determines whether a given range is in the set. Only succeeds if the entire
* range is available.
*
* @param {goog.math.Range} a The query range.
* @return {boolean} Whether the entire requested range is set.
*/
goog.math.RangeSet.prototype.contains = function(a) {
'use strict';
if (a.end <= a.start) {
return false;
}
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (a.start < b.end) {
if (a.end >= b.start) {
return goog.math.Range.contains(b, a);
}
break;
}
}
return false;
};
/**
* Determines whether a given value is set in the RangeSet.
*
* @param {number} value The value to test.
* @return {boolean} Whether the given value is in the set.
*/
goog.math.RangeSet.prototype.containsValue = function(value) {
'use strict';
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (value < b.end) {
if (value >= b.start) {
return true;
}
break;
}
}
return false;
};
/**
* Returns the union of this RangeSet with another.
*
* @param {goog.math.RangeSet} set Another RangeSet.
* @return {!goog.math.RangeSet} A new RangeSet containing all values from
* either set.
*/
goog.math.RangeSet.prototype.union = function(set) {
'use strict';
// TODO(brenneman): A linear-time merge would be preferable if it is ever a
// bottleneck.
set = set.clone();
for (var i = 0, a; a = this.ranges_[i]; i++) {
set.add(a);
}
return set;
};
/**
* Subtracts the ranges of another set from this one, returning the result
* as a new RangeSet.
*
* @param {!goog.math.RangeSet} set The RangeSet to subtract.
* @return {!goog.math.RangeSet} A new RangeSet containing all values in this
* set minus the values of the input set.
*/
goog.math.RangeSet.prototype.difference = function(set) {
'use strict';
var ret = this.clone();
for (var i = 0, a; a = set.ranges_[i]; i++) {
ret.remove(a);
}
return ret;
};
/**
* Intersects this RangeSet with another.
*
* @param {goog.math.RangeSet} set The RangeSet to intersect with.
* @return {!goog.math.RangeSet} A new RangeSet containing all values set in
* both this and the input set.
*/
goog.math.RangeSet.prototype.intersection = function(set) {
'use strict';
if (this.isEmpty() || set.isEmpty()) {
return new goog.math.RangeSet();
}
return this.difference(set.inverse(this.getBounds()));
};
/**
* Creates a subset of this set over the input range.
*
* @param {goog.math.Range} range The range to copy into the slice.
* @return {!goog.math.RangeSet} A new RangeSet with a copy of the values in the
* input range.
*/
goog.math.RangeSet.prototype.slice = function(range) {
'use strict';
var set = new goog.math.RangeSet();
if (range.start >= range.end) {
return set;
}
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (b.end <= range.start) {
continue;
}
if (b.start > range.end) {
break;
}
set.add(
new goog.math.Range(
Math.max(range.start, b.start), Math.min(range.end, b.end)));
}
return set;
};
/**
* Creates an inverted slice of this set over the input range.
*
* @param {goog.math.Range} range The range to copy into the slice.
* @return {!goog.math.RangeSet} A new RangeSet containing inverted values from
* the original over the input range.
*/
goog.math.RangeSet.prototype.inverse = function(range) {
'use strict';
var set = new goog.math.RangeSet();
set.add(range);
for (var i = 0, b; b = this.ranges_[i]; i++) {
if (range.start >= b.end) {
continue;
}
if (range.end < b.start) {
break;
}
set.remove(b);
}
return set;
};
/**
* @return {number} The sum of the lengths of ranges covered in the set.
*/
goog.math.RangeSet.prototype.coveredLength = function() {
'use strict';
return /** @type {number} */ (this.ranges_.reduce(function(res, range) {
'use strict';
return res + range.end - range.start;
}, 0));
};
/**
* @return {goog.math.Range} The total range this set covers, ignoring any
* gaps between ranges.
*/
goog.math.RangeSet.prototype.getBounds = function() {
'use strict';
if (this.ranges_.length) {
return new goog.math.Range(
this.ranges_[0].start, goog.array.peek(this.ranges_).end);
}
return null;
};
/**
* @return {boolean} Whether any ranges are currently in the set.
*/
goog.math.RangeSet.prototype.isEmpty = function() {
'use strict';
return this.ranges_.length == 0;
};
/**
* Removes all values in the set.
*/
goog.math.RangeSet.prototype.clear = function() {
'use strict';
this.ranges_.length = 0;
};
/**
* Returns an iterator that iterates over the ranges in the RangeSet.
*
* @param {boolean=} opt_keys Ignored for RangeSets.
* @return {!goog.iter.Iterator} An iterator over the values in the set.
*/
goog.math.RangeSet.prototype.__iterator__ = function(opt_keys) {
'use strict';
var i = 0;
var list = this.ranges_;
var iterator = new goog.iter.Iterator();
iterator.nextValueOrThrow = function() {
'use strict';
if (i >= list.length) {
throw goog.iter.StopIteration;
}
return list[i++].clone();
};
return iterator;
};
Codebase Browser
chromium