diff options
Diffstat (limited to '')
-rw-r--r-- | comm/mailnews/base/src/MsgKeySet.jsm | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/comm/mailnews/base/src/MsgKeySet.jsm b/comm/mailnews/base/src/MsgKeySet.jsm new file mode 100644 index 0000000000..bbbd580ba9 --- /dev/null +++ b/comm/mailnews/base/src/MsgKeySet.jsm @@ -0,0 +1,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; + } +} |