btree.test.js
1 import { expect } from 'expect'; 2 3 import { buildModule } from '@bablr/btree/enhanceable'; 4 5 const { push, pop, addAt } = buildModule(2); 6 7 describe('btree of node size 2', () => { 8 describe('push', () => { 9 it('appends to a tree of size 0', () => { 10 expect(push([], 'a')).toEqual(['a']); 11 }); 12 13 it('appends to a tree of size 1', () => { 14 expect(push(['a'], 'b')).toEqual(['a', 'b']); 15 }); 16 17 it('appends to a tree of size 2', () => { 18 expect(push(['a', 'b'], 'c')).toEqual([3, [['a'], ['b', 'c']]]); 19 }); 20 21 it('appends to a tree of size 3', () => { 22 expect(push([3, [['a'], ['b', 'c']]], 'd')).toEqual([ 23 4, 24 [ 25 [2, [['a'], ['b']]], 26 [2, [['c', 'd']]], 27 ], 28 ]); 29 }); 30 31 it('appends to a tree of size 4', () => { 32 expect( 33 push( 34 [ 35 4, 36 [ 37 [2, [['a'], ['b']]], 38 [2, [['c', 'd']]], 39 ], 40 ], 41 'e', 42 ), 43 ).toEqual([ 44 5, 45 [ 46 [2, [['a'], ['b']]], 47 [3, [['c'], ['d', 'e']]], 48 ], 49 ]); 50 }); 51 52 it('appends to a tree of size 5', () => { 53 expect( 54 push( 55 [ 56 5, 57 [ 58 [2, [['a'], ['b']]], 59 [3, [['c'], ['d', 'e']]], 60 ], 61 ], 62 'f', 63 ), 64 ).toEqual([ 65 6, 66 [ 67 [ 68 4, 69 [ 70 [2, [['a'], ['b']]], 71 [2, [['c'], ['d']]], 72 ], 73 ], 74 [2, [[2, [['e', 'f']]]]], 75 ], 76 ]); 77 }); 78 79 it('appends to a tree of size 6', () => { 80 expect( 81 push( 82 [ 83 6, 84 [ 85 [3, [['a', 'b'], ['c']]], 86 [3, [['d'], ['e', 'f']]], 87 ], 88 ], 89 'g', 90 ), 91 ).toEqual([ 92 7, 93 [ 94 [ 95 5, 96 [ 97 [3, [['a', 'b'], ['c']]], 98 [2, [['d'], ['e']]], 99 ], 100 ], 101 [2, [[2, [['f', 'g']]]]], 102 ], 103 ]); 104 }); 105 106 it('adds to a tree of size 7', () => { 107 expect( 108 push( 109 [ 110 7, 111 [ 112 [ 113 5, 114 [ 115 [3, [['a', 'b'], ['c']]], 116 [2, [['d'], ['e']]], 117 ], 118 ], 119 [2, [[2, [['f', 'g']]]]], 120 ], 121 ], 122 'h', 123 ), 124 ).toEqual([ 125 8, 126 [ 127 [ 128 5, 129 [ 130 [3, [['a', 'b'], ['c']]], 131 [2, [['d'], ['e']]], 132 ], 133 ], 134 [3, [[3, [['f'], ['g', 'h']]]]], 135 ], 136 ]); 137 }); 138 139 it('builds a tree of size 11', () => { 140 let leaf = 'a'.charCodeAt(0); 141 const buildLeaf = () => { 142 return String.fromCharCode(leaf++); 143 }; 144 145 const addNodes = (n) => { 146 let tree = []; 147 for (let i = 0; i < n; i++) { 148 tree = push(tree, buildLeaf()); 149 } 150 return tree; 151 }; 152 153 expect(addNodes(11)).toEqual([ 154 11, 155 [ 156 [ 157 8, 158 [ 159 [ 160 4, 161 [ 162 [ 163 4, 164 [ 165 [2, [['a'], ['b']]], 166 [2, [['c'], ['d']]], 167 ], 168 ], 169 ], 170 ], 171 [ 172 4, 173 [ 174 [2, [[2, [['e'], ['f']]]]], 175 [2, [[2, [['g'], ['h']]]]], 176 ], 177 ], 178 ], 179 ], 180 [3, [[3, [[3, [[3, [['i'], ['j', 'k']]]]]]]]], 181 ], 182 ]); 183 }); 184 }); 185 186 describe('unshift', () => { 187 it('prepends to a tree of size 0', () => { 188 expect(addAt(0, [], 'z')).toEqual(['z']); 189 }); 190 191 it('prepends to a tree of size 1', () => { 192 expect(addAt(0, ['z'], 'y')).toEqual(['y', 'z']); 193 }); 194 195 it('prepends to a tree of size 2', () => { 196 expect(addAt(0, ['y', 'z'], 'x')).toEqual([3, [['x'], ['y', 'z']]]); 197 }); 198 199 it('prepends to a tree of size 3', () => { 200 expect(addAt(0, [3, [['x'], ['y', 'z']]], 'w')).toEqual([ 201 4, 202 [ 203 ['w', 'x'], 204 ['y', 'z'], 205 ], 206 ]); 207 }); 208 209 it('prepends to a tree of size 4', () => { 210 expect( 211 addAt( 212 0, 213 [ 214 4, 215 [ 216 ['w', 'x'], 217 ['y', 'z'], 218 ], 219 ], 220 'v', 221 ), 222 ).toEqual([ 223 5, 224 [ 225 [3, [['v'], ['w', 'x']]], 226 [2, [['y', 'z']]], 227 ], 228 ]); 229 }); 230 231 it('prepends to a tree of size 5', () => { 232 expect( 233 addAt( 234 0, 235 [ 236 5, 237 [ 238 [3, [['v'], ['w', 'x']]], 239 [2, [['y', 'z']]], 240 ], 241 ], 242 'u', 243 ), 244 ).toEqual([ 245 6, 246 [ 247 [ 248 4, 249 [ 250 ['u', 'v'], 251 ['w', 'x'], 252 ], 253 ], 254 [2, [['y', 'z']]], 255 ], 256 ]); 257 }); 258 259 it('prepends to a tree of size 6', () => { 260 expect( 261 addAt( 262 0, 263 [ 264 6, 265 [ 266 [ 267 4, 268 [ 269 ['u', 'v'], 270 ['w', 'x'], 271 ], 272 ], 273 [2, [['y', 'z']]], 274 ], 275 ], 276 't', 277 ), 278 ).toEqual([ 279 7, 280 [ 281 [ 282 5, 283 [ 284 [3, [['t'], ['u', 'v']]], 285 [2, [['w', 'x']]], 286 ], 287 ], 288 [2, [[2, [['y', 'z']]]]], 289 ], 290 ]); 291 }); 292 293 it('prepends to a tree of size 7', () => { 294 expect( 295 addAt( 296 0, 297 [ 298 7, 299 [ 300 [ 301 5, 302 [ 303 [3, [['t'], ['u', 'v']]], 304 [2, [['w', 'x']]], 305 ], 306 ], 307 [2, [[2, [['y', 'z']]]]], 308 ], 309 ], 310 's', 311 ), 312 ).toEqual([ 313 8, 314 [ 315 [ 316 6, 317 [ 318 [ 319 4, 320 [ 321 ['s', 't'], 322 ['u', 'v'], 323 ], 324 ], 325 [2, [['w', 'x']]], 326 ], 327 ], 328 [2, [[2, [['y', 'z']]]]], 329 ], 330 ]); 331 }); 332 }); 333 334 describe('pop', () => { 335 it('deletes from a tree of size 1', () => { 336 expect(pop(['a'])).toEqual([]); 337 }); 338 339 it('deletes from a tree of size 2', () => { 340 expect(pop(['a', 'b'])).toEqual(['a']); 341 }); 342 343 it('deletes from a tree of size 3', () => { 344 expect(pop([3, [['a', 'b'], ['c']]])).toEqual(['a', 'b']); 345 }); 346 347 it('deletes from a tree of size 4', () => { 348 expect( 349 pop([ 350 4, 351 [ 352 ['a', 'b'], 353 ['c', 'd'], 354 ], 355 ]), 356 ).toEqual([3, [['a', 'b'], ['c']]]); 357 }); 358 359 it('deletes from a tree of size 5', () => { 360 expect( 361 pop([ 362 5, 363 [ 364 [3, [['a', 'b'], ['c']]], 365 [2, [['d', 'e']]], 366 ], 367 ]), 368 ).toEqual([ 369 4, 370 [ 371 [3, [['a', 'b'], ['c']]], 372 [1, [['d']]], 373 ], 374 ]); 375 }); 376 }); 377 });