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
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
const EXPORTED_SYMBOLS = ["MsgKeySet"];
/**
* A structure to represent a set of articles. This is usually for lines from
* the newsrc, which have article lists like
*
* 1-29627,29635,29658,32861-32863
*
* so the data has these properties:
*
* - strictly increasing
* - large subsequences of monotonically increasing ranges
* - gaps in the set are usually small, but not always
* - consecutive ranges tend to be large
*/
class MsgKeySet {
/**
* @param {string} [str] - The raw string to represent a set of articles.
*/
constructor(str) {
// An array of tuples, each tuple contains the start and end value of a sub
// range.
// @type {Array<[number, number]>}
this._ranges = str
? str.split(",").map(part => {
let [start, end] = part.split("-");
return [+start, +end || +start];
})
: [];
}
/**
* Add a value to the set.
*
* @param {number} value - The value to add.
*/
add(value) {
this.addRange(value, value);
}
/**
* Add a range to the set.
*
* @param {number} low - The smallest value of the range.
* @param {number} high - The largest value of the range.
*/
addRange(low, high) {
let index = 0;
for (let [start] of this._ranges) {
if (start > low) {
break;
}
index++;
}
this._ranges.splice(index, 0, [low, high]);
this._rebuild();
}
/**
* Check if a value is in the set.
*
* @param {number} value - The value to check.
* @returns {boolean}
*/
has(value) {
return this._ranges.some(([start, end]) =>
end ? start <= value && value <= end : start == value
);
}
/**
* Get the last range that is in the input range, but not in the key set.
*
* @param {number} low - The smallest value of the input range.
* @param {number} high - The largest value of the input range.
* @returns {number[]} - Array of lenght two with [low, high].
*/
getLastMissingRange(low, high) {
let length = this._ranges.length;
for (let i = length - 1; i >= 0; i--) {
let [start, end] = this._ranges[i];
if (end < high) {
return [Math.max(low, end + 1), high];
} else if (low < start && high > start) {
high = start - 1;
} else {
return [];
}
}
return [low, high];
}
/**
* Get the string representation of the key set.
*
* @returns {string}
*/
toString() {
return this._ranges
.map(([start, end]) => (start == end ? start : `${start}-${end}`))
.join(",");
}
/**
* Sub ranges may become overlapped after some operations. This method merges
* them if needed.
*/
_rebuild() {
if (this._ranges.length < 2) {
return;
}
let newRanges = [];
let [cursorStart, cursorEnd] = this._ranges[0];
for (let [start, end] of this._ranges.slice(1)) {
if (cursorEnd < start - 1) {
// No overlap between the two ranges.
newRanges.push([cursorStart, cursorEnd]);
cursorStart = start;
cursorEnd = end;
} else {
// Overlapped, merge them.
cursorEnd = end;
}
}
newRanges.push([cursorStart, cursorEnd]);
this._ranges = newRanges;
}
}
|
