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

398