123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396 |
- goog.provide('goog.math.RangeSet');
- goog.require('goog.array');
- goog.require('goog.iter.Iterator');
- goog.require('goog.iter.StopIteration');
- goog.require('goog.math.Range');
- goog.math.RangeSet = function() {
-
- this.ranges_ = [];
- };
- if (goog.DEBUG) {
-
- goog.math.RangeSet.prototype.toString = function() {
- return '[' + this.ranges_.join(', ') + ']';
- };
- }
- goog.math.RangeSet.equals = function(a, b) {
-
- return a == b ||
- !!(a && b &&
- goog.array.equals(a.ranges_, b.ranges_, goog.math.Range.equals));
- };
- goog.math.RangeSet.prototype.clone = function() {
- 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) {
- 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) {
- 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) {
- 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;
- };
- goog.math.RangeSet.prototype.containsValue = function(value) {
- for (var i = 0, b; b = this.ranges_[i]; i++) {
- if (value < b.end) {
- if (value >= b.start) {
- return true;
- }
- break;
- }
- }
- return false;
- };
- goog.math.RangeSet.prototype.union = function(set) {
-
-
- 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) {
- var ret = this.clone();
- for (var i = 0, a; a = set.ranges_[i]; i++) {
- ret.remove(a);
- }
- return ret;
- };
- goog.math.RangeSet.prototype.intersection = function(set) {
- 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) {
- 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) {
- 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() {
- return (
- goog.array.reduce(this.ranges_, function(res, range) {
- return res + range.end - range.start;
- }, 0));
- };
- goog.math.RangeSet.prototype.getBounds = function() {
- if (this.ranges_.length) {
- return new goog.math.Range(
- this.ranges_[0].start, goog.array.peek(this.ranges_).end);
- }
- return null;
- };
- goog.math.RangeSet.prototype.isEmpty = function() {
- return this.ranges_.length == 0;
- };
- goog.math.RangeSet.prototype.clear = function() {
- this.ranges_.length = 0;
- };
- goog.math.RangeSet.prototype.__iterator__ = function(opt_keys) {
- var i = 0;
- var list = this.ranges_;
- var iterator = new goog.iter.Iterator();
- iterator.next = function() {
- if (i >= list.length) {
- throw goog.iter.StopIteration;
- }
- return list[i++].clone();
- };
- return iterator;
- };
|