[6a3a178] | 1 | /*
|
---|
| 2 | MIT License http://www.opensource.org/licenses/mit-license.php
|
---|
| 3 | Author Tobias Koppers @sokra
|
---|
| 4 | */
|
---|
| 5 |
|
---|
| 6 | "use strict";
|
---|
| 7 |
|
---|
| 8 | const NONE = Symbol("not sorted");
|
---|
| 9 |
|
---|
| 10 | /**
|
---|
| 11 | * A subset of Set that offers sorting functionality
|
---|
| 12 | * @template T item type in set
|
---|
| 13 | * @extends {Set<T>}
|
---|
| 14 | */
|
---|
| 15 | class SortableSet extends Set {
|
---|
| 16 | /**
|
---|
| 17 | * Create a new sortable set
|
---|
| 18 | * @param {Iterable<T>=} initialIterable The initial iterable value
|
---|
| 19 | * @typedef {function(T, T): number} SortFunction
|
---|
| 20 | * @param {SortFunction=} defaultSort Default sorting function
|
---|
| 21 | */
|
---|
| 22 | constructor(initialIterable, defaultSort) {
|
---|
| 23 | super(initialIterable);
|
---|
| 24 | /** @private @type {undefined | function(T, T): number}} */
|
---|
| 25 | this._sortFn = defaultSort;
|
---|
| 26 | /** @private @type {typeof NONE | undefined | function(T, T): number}} */
|
---|
| 27 | this._lastActiveSortFn = NONE;
|
---|
| 28 | /** @private @type {Map<Function, any> | undefined} */
|
---|
| 29 | this._cache = undefined;
|
---|
| 30 | /** @private @type {Map<Function, any> | undefined} */
|
---|
| 31 | this._cacheOrderIndependent = undefined;
|
---|
| 32 | }
|
---|
| 33 |
|
---|
| 34 | /**
|
---|
| 35 | * @param {T} value value to add to set
|
---|
| 36 | * @returns {this} returns itself
|
---|
| 37 | */
|
---|
| 38 | add(value) {
|
---|
| 39 | this._lastActiveSortFn = NONE;
|
---|
| 40 | this._invalidateCache();
|
---|
| 41 | this._invalidateOrderedCache();
|
---|
| 42 | super.add(value);
|
---|
| 43 | return this;
|
---|
| 44 | }
|
---|
| 45 |
|
---|
| 46 | /**
|
---|
| 47 | * @param {T} value value to delete
|
---|
| 48 | * @returns {boolean} true if value existed in set, false otherwise
|
---|
| 49 | */
|
---|
| 50 | delete(value) {
|
---|
| 51 | this._invalidateCache();
|
---|
| 52 | this._invalidateOrderedCache();
|
---|
| 53 | return super.delete(value);
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | /**
|
---|
| 57 | * @returns {void}
|
---|
| 58 | */
|
---|
| 59 | clear() {
|
---|
| 60 | this._invalidateCache();
|
---|
| 61 | this._invalidateOrderedCache();
|
---|
| 62 | return super.clear();
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | /**
|
---|
| 66 | * Sort with a comparer function
|
---|
| 67 | * @param {SortFunction} sortFn Sorting comparer function
|
---|
| 68 | * @returns {void}
|
---|
| 69 | */
|
---|
| 70 | sortWith(sortFn) {
|
---|
| 71 | if (this.size <= 1 || sortFn === this._lastActiveSortFn) {
|
---|
| 72 | // already sorted - nothing to do
|
---|
| 73 | return;
|
---|
| 74 | }
|
---|
| 75 |
|
---|
| 76 | const sortedArray = Array.from(this).sort(sortFn);
|
---|
| 77 | super.clear();
|
---|
| 78 | for (let i = 0; i < sortedArray.length; i += 1) {
|
---|
| 79 | super.add(sortedArray[i]);
|
---|
| 80 | }
|
---|
| 81 | this._lastActiveSortFn = sortFn;
|
---|
| 82 | this._invalidateCache();
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 | sort() {
|
---|
| 86 | this.sortWith(this._sortFn);
|
---|
| 87 | return this;
|
---|
| 88 | }
|
---|
| 89 |
|
---|
| 90 | /**
|
---|
| 91 | * Get data from cache
|
---|
| 92 | * @template R
|
---|
| 93 | * @param {function(SortableSet<T>): R} fn function to calculate value
|
---|
| 94 | * @returns {R} returns result of fn(this), cached until set changes
|
---|
| 95 | */
|
---|
| 96 | getFromCache(fn) {
|
---|
| 97 | if (this._cache === undefined) {
|
---|
| 98 | this._cache = new Map();
|
---|
| 99 | } else {
|
---|
| 100 | const result = this._cache.get(fn);
|
---|
| 101 | const data = /** @type {R} */ (result);
|
---|
| 102 | if (data !== undefined) {
|
---|
| 103 | return data;
|
---|
| 104 | }
|
---|
| 105 | }
|
---|
| 106 | const newData = fn(this);
|
---|
| 107 | this._cache.set(fn, newData);
|
---|
| 108 | return newData;
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | /**
|
---|
| 112 | * Get data from cache (ignoring sorting)
|
---|
| 113 | * @template R
|
---|
| 114 | * @param {function(SortableSet<T>): R} fn function to calculate value
|
---|
| 115 | * @returns {R} returns result of fn(this), cached until set changes
|
---|
| 116 | */
|
---|
| 117 | getFromUnorderedCache(fn) {
|
---|
| 118 | if (this._cacheOrderIndependent === undefined) {
|
---|
| 119 | this._cacheOrderIndependent = new Map();
|
---|
| 120 | } else {
|
---|
| 121 | const result = this._cacheOrderIndependent.get(fn);
|
---|
| 122 | const data = /** @type {R} */ (result);
|
---|
| 123 | if (data !== undefined) {
|
---|
| 124 | return data;
|
---|
| 125 | }
|
---|
| 126 | }
|
---|
| 127 | const newData = fn(this);
|
---|
| 128 | this._cacheOrderIndependent.set(fn, newData);
|
---|
| 129 | return newData;
|
---|
| 130 | }
|
---|
| 131 |
|
---|
| 132 | /**
|
---|
| 133 | * @private
|
---|
| 134 | * @returns {void}
|
---|
| 135 | */
|
---|
| 136 | _invalidateCache() {
|
---|
| 137 | if (this._cache !== undefined) {
|
---|
| 138 | this._cache.clear();
|
---|
| 139 | }
|
---|
| 140 | }
|
---|
| 141 |
|
---|
| 142 | /**
|
---|
| 143 | * @private
|
---|
| 144 | * @returns {void}
|
---|
| 145 | */
|
---|
| 146 | _invalidateOrderedCache() {
|
---|
| 147 | if (this._cacheOrderIndependent !== undefined) {
|
---|
| 148 | this._cacheOrderIndependent.clear();
|
---|
| 149 | }
|
---|
| 150 | }
|
---|
| 151 |
|
---|
| 152 | /**
|
---|
| 153 | * @returns {T[]} the raw array
|
---|
| 154 | */
|
---|
| 155 | toJSON() {
|
---|
| 156 | return Array.from(this);
|
---|
| 157 | }
|
---|
| 158 | }
|
---|
| 159 |
|
---|
| 160 | module.exports = SortableSet;
|
---|