1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
cr.define('media', function() {
/**
* This class represents a collection of non-intersecting ranges. Ranges
* specified by (start, end) can be added and removed at will. It is used to
* record which sections of a media file have been cached, e.g. the first and
* last few kB plus several MB in the middle.
*
* Example usage:
* someRange.add(0, 100); // Contains 0-100.
* someRange.add(150, 200); // Contains 0-100, 150-200.
* someRange.remove(25, 75); // Contains 0-24, 76-100, 150-200.
* someRange.add(25, 149); // Contains 0-200.
*/
function DisjointRangeSet() {
this.ranges_ = {};
}
DisjointRangeSet.prototype = {
/**
* Deletes all ranges intersecting with (start ... end) and returns the
* extents of the cleared area.
* @param {int} start The start of the range to remove.
* @param {int} end The end of the range to remove.
* @param {int} sloppiness 0 removes only strictly overlapping ranges, and
* 1 removes adjacent ones.
* @return {Object} The start and end of the newly cleared range.
*/
clearRange: function(start, end, sloppiness) {
var ranges = this.ranges_;
var result = {start: start, end: end};
for (var rangeStart in this.ranges_) {
rangeEnd = this.ranges_[rangeStart];
// A range intersects another if its start lies within the other range
// or vice versa.
if ((rangeStart >= start && rangeStart <= (end + sloppiness)) ||
(start >= rangeStart && start <= (rangeEnd + sloppiness))) {
delete ranges[rangeStart];
result.start = Math.min(result.start, rangeStart);
result.end = Math.max(result.end, rangeEnd);
}
}
return result;
},
/**
* Adds a range to this DisjointRangeSet.
* Joins adjacent and overlapping ranges together.
* @param {int} start The beginning of the range to add, inclusive.
* @param {int} end The end of the range to add, inclusive.
*/
add: function(start, end) {
if (end < start)
return;
// Remove all touching ranges.
result = this.clearRange(start, end, 1);
// Add back a single contiguous range.
this.ranges_[Math.min(start, result.start)] = Math.max(end, result.end);
},
/**
* Combines a DisjointRangeSet with this one.
* @param {DisjointRangeSet} ranges A DisjointRangeSet to be squished into
* this one.
*/
merge: function(other) {
var ranges = this;
other.forEach(function(start, end) { ranges.add(start, end); });
},
/**
* Removes a range from this DisjointRangeSet.
* Will split existing ranges if necessary.
* @param {int} start The beginning of the range to remove, inclusive.
* @param {int} end The end of the range to remove, inclusive.
*/
remove: function(start, end) {
if (end < start)
return;
// Remove instersecting ranges.
result = this.clearRange(start, end, 0);
// Add back non-overlapping ranges.
if (result.start < start)
this.ranges_[result.start] = start - 1;
if (result.end > end)
this.ranges_[end + 1] = result.end;
},
/**
* Iterates over every contiguous range in this DisjointRangeSet, calling a
* function for each (start, end).
* @param {function(int, int)} iterator The function to call on each range.
*/
forEach: function(iterator) {
for (var start in this.ranges_)
iterator(start, this.ranges_[start]);
},
/**
* Maps this DisjointRangeSet to an array by calling a given function on the
* start and end of each contiguous range, sorted by start.
* @param {function(int, int)} mapper Maps a range to an array element.
* @return {Array} An array of each mapper(range).
*/
map: function(mapper) {
var starts = [];
for (var start in this.ranges_)
starts.push(parseInt(start));
starts.sort(function(a, b) {
return a - b;
});
var ranges = this.ranges_;
var results = starts.map(function(s) {
return mapper(s, ranges[s]);
});
return results;
},
/**
* Finds the maximum value present in any of the contained ranges.
* @return {int} The maximum value contained by this DisjointRangeSet.
*/
max: function() {
var max = -Infinity;
for (var start in this.ranges_)
max = Math.max(max, this.ranges_[start]);
return max;
},
};
return {
DisjointRangeSet: DisjointRangeSet
};
});
|
