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