@@ -124,6 +124,13 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => { |
124 | 124 | /** @type {Node<T>[]} */ |
125 | 125 | const initialNodes = []; |
126 | 126 |
|
| 127 | + // lexically ordering of keys |
| 128 | + nodes.sort((a, b) => { |
| 129 | + if (a.key < b.key) return -1; |
| 130 | + if (a.key > b.key) return 1; |
| 131 | + return 0; |
| 132 | + }); |
| 133 | + |
127 | 134 | // return nodes bigger than maxSize directly as group |
128 | 135 | for (const node of nodes) { |
129 | 136 | if (node.size >= maxSize) { |
@@ -134,13 +141,6 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => { |
134 | 141 | } |
135 | 142 |
|
136 | 143 | if (initialNodes.length > 0) { |
137 | | - // lexically ordering of keys |
138 | | - initialNodes.sort((a, b) => { |
139 | | - if (a.key < b.key) return -1; |
140 | | - if (a.key > b.key) return 1; |
141 | | - return 0; |
142 | | - }); |
143 | | - |
144 | 144 | // calculate similarities between lexically adjacent nodes |
145 | 145 | /** @type {number[]} */ |
146 | 146 | const similarities = []; |
@@ -150,77 +150,99 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => { |
150 | 150 | similarities.push(similarity(a.key, b.key)); |
151 | 151 | } |
152 | 152 |
|
153 | | - const queue = [new Group(initialNodes, similarities)]; |
| 153 | + const initialGroup = new Group(initialNodes, similarities); |
154 | 154 |
|
155 | | - while (queue.length) { |
156 | | - const group = queue.pop(); |
157 | | - // only groups bigger than maxSize need to be splitted |
158 | | - if (group.size < maxSize) { |
159 | | - result.push(group); |
160 | | - continue; |
| 155 | + if (initialGroup.size < minSize) { |
| 156 | + // We hit an edgecase where the working set is already smaller than minSize |
| 157 | + // We merge it with the smallest result node to keep minSize intact |
| 158 | + if (result.length > 0) { |
| 159 | + const smallestGroup = result.reduce( |
| 160 | + (min, group) => (min.size > group.size ? group : min) |
| 161 | + ); |
| 162 | + for (const node of initialGroup.nodes) smallestGroup.nodes.push(node); |
| 163 | + smallestGroup.nodes.sort((a, b) => { |
| 164 | + if (a.key < b.key) return -1; |
| 165 | + if (a.key > b.key) return 1; |
| 166 | + return 0; |
| 167 | + }); |
| 168 | + } else { |
| 169 | + // There are no other nodes |
| 170 | + // We use all nodes and have to accept that it's smaller than minSize |
| 171 | + result.push(initialGroup); |
161 | 172 | } |
| 173 | + } else { |
| 174 | + const queue = [initialGroup]; |
162 | 175 |
|
163 | | - // find unsplittable area from left and right |
164 | | - // going minSize from left and right |
165 | | - // at least one node need to be included otherwise we get stuck |
166 | | - let left = 0; |
167 | | - let leftSize = 0; |
168 | | - while (leftSize <= minSize) { |
169 | | - leftSize += group.nodes[left].size; |
170 | | - left++; |
171 | | - } |
172 | | - let right = group.nodes.length - 1; |
173 | | - let rightSize = 0; |
174 | | - while (rightSize <= minSize) { |
175 | | - rightSize += group.nodes[right].size; |
176 | | - right--; |
177 | | - } |
| 176 | + while (queue.length) { |
| 177 | + const group = queue.pop(); |
| 178 | + // only groups bigger than maxSize need to be splitted |
| 179 | + if (group.size < maxSize) { |
| 180 | + result.push(group); |
| 181 | + continue; |
| 182 | + } |
178 | 183 |
|
179 | | - if (left - 1 > right) { |
180 | | - // can't split group while holding minSize |
181 | | - // because minSize is preferred of maxSize we return |
182 | | - // the group here even while it's too big |
183 | | - // To avoid this make sure maxSize > minSize * 3 |
184 | | - result.push(group); |
185 | | - continue; |
186 | | - } |
187 | | - if (left <= right) { |
188 | | - // when there is a area between left and right |
189 | | - // we look for best split point |
190 | | - // we split at the minimum similarity |
191 | | - // here key space is separated the most |
192 | | - let best = left - 1; |
193 | | - let bestSimilarity = group.similarities[best]; |
194 | | - for (let i = left; i <= right; i++) { |
195 | | - const similarity = group.similarities[i]; |
196 | | - if (similarity < bestSimilarity) { |
197 | | - best = i; |
198 | | - bestSimilarity = similarity; |
| 184 | + // find unsplittable area from left and right |
| 185 | + // going minSize from left and right |
| 186 | + // at least one node need to be included otherwise we get stuck |
| 187 | + let left = 0; |
| 188 | + let leftSize = 0; |
| 189 | + while (leftSize <= minSize) { |
| 190 | + leftSize += group.nodes[left].size; |
| 191 | + left++; |
| 192 | + } |
| 193 | + let right = group.nodes.length - 1; |
| 194 | + let rightSize = 0; |
| 195 | + while (rightSize <= minSize) { |
| 196 | + rightSize += group.nodes[right].size; |
| 197 | + right--; |
| 198 | + } |
| 199 | + |
| 200 | + if (left - 1 > right) { |
| 201 | + // can't split group while holding minSize |
| 202 | + // because minSize is preferred of maxSize we return |
| 203 | + // the group here even while it's too big |
| 204 | + // To avoid this make sure maxSize > minSize * 3 |
| 205 | + result.push(group); |
| 206 | + continue; |
| 207 | + } |
| 208 | + if (left <= right) { |
| 209 | + // when there is a area between left and right |
| 210 | + // we look for best split point |
| 211 | + // we split at the minimum similarity |
| 212 | + // here key space is separated the most |
| 213 | + let best = left - 1; |
| 214 | + let bestSimilarity = group.similarities[best]; |
| 215 | + for (let i = left; i <= right; i++) { |
| 216 | + const similarity = group.similarities[i]; |
| 217 | + if (similarity < bestSimilarity) { |
| 218 | + best = i; |
| 219 | + bestSimilarity = similarity; |
| 220 | + } |
199 | 221 | } |
| 222 | + left = best + 1; |
| 223 | + right = best; |
200 | 224 | } |
201 | | - left = best + 1; |
202 | | - right = best; |
203 | | - } |
204 | 225 |
|
205 | | - // create two new groups for left and right area |
206 | | - // and queue them up |
207 | | - const rightNodes = [group.nodes[right + 1]]; |
208 | | - /** @type {number[]} */ |
209 | | - const rightSimilaries = []; |
210 | | - for (let i = right + 2; i < group.nodes.length; i++) { |
211 | | - rightSimilaries.push(group.similarities[i - 1]); |
212 | | - rightNodes.push(group.nodes[i]); |
213 | | - } |
214 | | - queue.push(new Group(rightNodes, rightSimilaries)); |
215 | | - |
216 | | - const leftNodes = [group.nodes[0]]; |
217 | | - /** @type {number[]} */ |
218 | | - const leftSimilaries = []; |
219 | | - for (let i = 1; i < left; i++) { |
220 | | - leftSimilaries.push(group.similarities[i - 1]); |
221 | | - leftNodes.push(group.nodes[i]); |
| 226 | + // create two new groups for left and right area |
| 227 | + // and queue them up |
| 228 | + const rightNodes = [group.nodes[right + 1]]; |
| 229 | + /** @type {number[]} */ |
| 230 | + const rightSimilaries = []; |
| 231 | + for (let i = right + 2; i < group.nodes.length; i++) { |
| 232 | + rightSimilaries.push(group.similarities[i - 1]); |
| 233 | + rightNodes.push(group.nodes[i]); |
| 234 | + } |
| 235 | + queue.push(new Group(rightNodes, rightSimilaries)); |
| 236 | + |
| 237 | + const leftNodes = [group.nodes[0]]; |
| 238 | + /** @type {number[]} */ |
| 239 | + const leftSimilaries = []; |
| 240 | + for (let i = 1; i < left; i++) { |
| 241 | + leftSimilaries.push(group.similarities[i - 1]); |
| 242 | + leftNodes.push(group.nodes[i]); |
| 243 | + } |
| 244 | + queue.push(new Group(leftNodes, leftSimilaries)); |
222 | 245 | } |
223 | | - queue.push(new Group(leftNodes, leftSimilaries)); |
224 | 246 | } |
225 | 247 | } |
226 | 248 |
|
|