.config/coc/extensions/node_modules/coc-prettier/node_modules/functional-red-black-tree/test/test.js

   1 "use strict"
   2
   3 var makeTree = require("../rbtree.js")
   4 var tape = require("tape")
   5 var util = require("util")
   6 var iota = require("iota-array")
   7
   8 var COLORS = [ "r", "b", "bb" ]
   9
  10 function printTree(tree) {
  11   if(!tree) {
  12     return []
  13   }
  14   return [ COLORS[tree._color], tree.key, printTree(tree.left), printTree(tree.right) ]
  15 }
  16
  17 function print(t) {
  18   console.log(util.inspect(printTree(t.root), {depth:12}))
  19 }
  20
  21 //Ensures the red black axioms are satisfied by tree
  22 function checkTree(tree, t) {
  23   if(!tree.root) {
  24     return
  25   }
  26   t.equals(tree.root._color, 1, "root is black")
  27   function checkNode(node) {
  28     if(!node) {
  29       return [1, 0]
  30     }
  31     if(node._color === 0) {
  32       t.assert(!node.left || node.left._color === 1, "children of red node must be black")
  33       t.assert(!node.right || node.right._color === 1, "children of red node must be black")
  34     } else {
  35       t.equals(node._color, 1, "node color must be red or black")
  36     }
  37     if(node.left) {
  38       t.assert(tree._compare(node.left.key, node.key) <= 0, "left tree order invariant")
  39     }
  40     if(node.right) {
  41       t.assert(tree._compare(node.right.key, node.key) >= 0, "right tree order invariant")
  42     }
  43     var cl = checkNode(node.left)
  44     var cr = checkNode(node.right)
  45     t.equals(cl[0], cr[0], "number of black nodes along all paths to root must be constant")
  46     t.equals(cl[1] + cr[1] + 1, node._count, "item count consistency")
  47     return [cl[0] + node._color,  cl[1] + cr[1] + 1]
  48   }
  49   var r = checkNode(tree.root)
  50   t.equals(r[1], tree.length, "tree length")
  51 }
  52
  53 tape("insert()", function(t) {
  54   var t1 = makeTree()
  55
  56   var u = t1
  57   var arr = []
  58   for(var i=20; i>=0; --i) {
  59     var x = i
  60     var next = u.insert(x, true)
  61     checkTree(u, t)
  62     checkTree(next, t)
  63     t.equals(u.length, arr.length)
  64     arr.push(x)
  65     u = next
  66   }
  67   for(var i=-20; i<0; ++i) {
  68     var x = i
  69     var next = u.insert(x, true)
  70     checkTree(u, t)
  71     checkTree(next, t)
  72     arr.sort(function(a,b) { return a-b })
  73     var ptr = 0
  74     u.forEach(function(k,v) {
  75       t.equals(k, arr[ptr++])
  76     })
  77     t.equals(ptr, arr.length)
  78     arr.push(x)
  79     u = next
  80   }
  81
  82   var start = u.begin
  83   for(var i=-20, j=0; j<=40; ++i, ++j) {
  84     t.equals(u.at(j).key, i, "checking at()")
  85     t.equals(start.key, i, "checking iter")
  86     t.equals(start.index, j, "checking index")
  87     t.assert(start.valid, "checking valid")
  88     if(j < 40) {
  89       t.assert(start.hasNext, "hasNext()")
  90     } else {
  91       t.assert(!start.hasNext, "eof hasNext()")
  92     }
  93     start.next()
  94   }
  95   t.assert(!start.valid, "invalid eof iterator")
  96   t.assert(!start.hasNext, "hasNext() at eof fail")
  97   t.equals(start.index, 41, "eof index")
  98
  99   t.end()
 100 })
 101
 102 tape("foreach", function(t) {
 103   var u = iota(31).reduce(function(u, k, v) {
 104     return u.insert(k, v)
 105   }, makeTree())
 106
 107   //Check basic foreach
 108   var visit_keys = []
 109   var visit_vals = []
 110   u.forEach(function(k,v) {
 111     visit_keys.push(k)
 112     visit_vals.push(v)
 113   })
 114   t.same(visit_keys, u.keys)
 115   t.same(visit_vals, u.values)
 116
 117   //Check foreach with termination
 118   visit_keys = []
 119   visit_vals = []
 120   t.equals(u.forEach(function(k,v) {
 121     if(k === 5) {
 122       return 1000
 123     }
 124     visit_keys.push(k)
 125     visit_vals.push(v)
 126   }), 1000)
 127   t.same(visit_keys, u.keys.slice(0, 5))
 128   t.same(visit_vals, u.values.slice(0, 5))
 129
 130   //Check half interval foreach
 131   visit_keys = []
 132   visit_vals = []
 133   u.forEach(function(k,v) {
 134     visit_keys.push(k)
 135     visit_vals.push(v)
 136   }, 3)
 137   t.same(visit_keys, u.keys.slice(3))
 138   t.same(visit_vals, u.values.slice(3))
 139
 140   //Check half interval foreach with termination
 141   visit_keys = []
 142   visit_vals = []
 143   t.equals(u.forEach(function(k,v) {
 144     if(k === 12) {
 145       return 1000
 146     }
 147     visit_keys.push(k)
 148     visit_vals.push(v)
 149   }, 3), 1000)
 150   t.same(visit_keys, u.keys.slice(3, 12))
 151   t.same(visit_vals, u.values.slice(3, 12))
 152
 153
 154   //Check interval foreach
 155   visit_keys = []
 156   visit_vals = []
 157   u.forEach(function(k,v) {
 158     visit_keys.push(k)
 159     visit_vals.push(v)
 160   }, 3, 15)
 161   t.same(visit_keys, u.keys.slice(3, 15))
 162   t.same(visit_vals, u.values.slice(3, 15))
 163
 164   //Check interval foreach with termination
 165   visit_keys = []
 166   visit_vals = []
 167   t.equals(u.forEach(function(k,v) {
 168     if(k === 12) {
 169       return 1000
 170     }
 171     visit_keys.push(k)
 172     visit_vals.push(v)
 173   }, 3, 15), 1000)
 174   t.same(visit_keys, u.keys.slice(3, 12))
 175   t.same(visit_vals, u.values.slice(3, 12))
 176
 177   t.end()
 178 })
 179
 180 function compareIterators(a, b, t) {
 181   t.equals(a.tree, b.tree, "iter trees")
 182   t.equals(a.valid, b.valid, "iter validity")
 183   if(!b.valid) {
 184     return
 185   }
 186   t.equals(a.node, b.node, "iter node")
 187   t.equals(a.key, b.key, "iter key")
 188   t.equals(a.value, b.value, "iter value")
 189   t.equals(a.index, b.index, "iter index")
 190 }
 191
 192 tape("iterators", function(t) {
 193   var u = iota(20).reduce(function(u, k, v) {
 194     return u.insert(k, v)
 195   }, makeTree())
 196
 197   //Try walking forward
 198   var iter = u.begin
 199   var c = iter.clone()
 200   t.ok(iter.hasNext, "must have next at beginneing")
 201   t.ok(!iter.hasPrev, "must not have predecessor")
 202   for(var i=0; i<20; ++i) {
 203     var v = u.at(i)
 204     compareIterators(iter, v, t)
 205     t.equals(iter.index, i)
 206     iter.next()
 207   }
 208   t.ok(!iter.valid, "must be eof iterator")
 209
 210   //Check if the clone worked
 211   compareIterators(c, u.begin, t)
 212
 213   //Try walking backward
 214   var iter = u.end
 215   t.ok(!iter.hasNext, "must not have next")
 216   t.ok(iter.hasPrev, "must have predecessor")
 217   for(var i=19; i>=0; --i) {
 218     var v = u.at(i)
 219     compareIterators(iter, v, t)
 220     t.equals(iter.index, i)
 221     iter.prev()
 222   }
 223   t.ok(!iter.valid, "must be eof iterator")
 224
 225   t.end()
 226 })
 227
 228
 229 tape("remove()", function(t) {
 230
 231   var sz = [1, 2,  10, 20, 23, 31, 32, 33]
 232   for(var n=0; n<sz.length; ++n) {
 233     var c = sz[n]
 234     var u = iota(c).reduce(function(u, k, v) {
 235       return u.insert(k, v)
 236     }, makeTree())
 237     for(var i=0; i<c; ++i) {
 238       checkTree(u.remove(i), t)
 239     }
 240   }
 241
 242   t.end()
 243 })
 244
 245 tape("update()", function(t) {
 246   var arr = [0, 1, 2, 3, 4, 5, 6 ]
 247   var u = arr.reduce(function(u, k, v) {
 248     return u.insert(k, v)
 249   }, makeTree())
 250   for(var iter=u.begin; iter.hasNext; iter.next()) {
 251     var p = iter.value
 252     var updated = iter.update(1000)
 253     t.equals(iter.value, iter.key, "ensure no mutation")
 254     t.equals(updated.find(iter.key).value, 1000, "ensure update applied")
 255     checkTree(updated, t)
 256     checkTree(u, t)
 257   }
 258   t.end()
 259 })
 260
 261
 262 tape("keys and values", function(t) {
 263
 264   var original_keys = [ "potato", "sock", "foot", "apple", "newspaper", "gameboy" ]
 265   var original_values = [ 42, 10, false, "!!!", {}, null ]
 266
 267   var u = makeTree()
 268   for(var i=0; i<original_keys.length; ++i) {
 269     u = u.insert(original_keys[i], original_values[i])
 270   }
 271
 272   var zipped = iota(6).map(function(i) {
 273     return [ original_keys[i], original_values[i] ]
 274   })
 275
 276   zipped.sort(function(a,b) {
 277     if(a[0] < b[0]) { return -1 }
 278     if(a[0] > b[0]) { return 1 }
 279     return 0
 280   })
 281
 282   var keys = zipped.map(function(v) { return v[0] })
 283   var values = zipped.map(function(v) { return v[1] })
 284
 285   t.same(u.keys, keys)
 286   t.same(u.values, values)
 287
 288   t.end()
 289 })
 290
 291 tape("searching", function(t) {
 292
 293   var arr = [0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 6 ]
 294   var u = arr.reduce(function(u, k, v) {
 295     return u.insert(k, v)
 296   }, makeTree())
 297
 298
 299   for(var i=0; i<arr.length; ++i) {
 300     if(arr[i] !== arr[i-1] && arr[i] !== arr[i+1]) {
 301       t.equals(u.get(arr[i]), i, "get " + arr[i])
 302     }
 303   }
 304   t.equals(u.get(-1), undefined, "get missing")
 305
 306   t.equals(u.ge(3).index, 6, "ge simple")
 307   t.equals(u.ge(0.9).index, 1, "ge run start")
 308   t.equals(u.ge(1).index, 1, "ge run mid")
 309   t.equals(u.ge(1.1).index, 5, "ge run end")
 310   t.equals(u.ge(0).index, 0, "ge first")
 311   t.equals(u.ge(6).index, 9, "ge last")
 312   t.equals(u.ge(100).valid, false, "ge big")
 313   t.equals(u.ge(-1).index, 0, "ge small")
 314
 315   t.equals(u.gt(3).index, 7, "gt simple")
 316   t.equals(u.gt(0.9).index, 1, "gt run start")
 317   t.equals(u.gt(1).index, 5, "gt run mid")
 318   t.equals(u.gt(1.1).index, 5, "gt run end")
 319   t.equals(u.gt(0).index, 1, "gt first")
 320   t.equals(u.gt(6).valid, false, "gt last")
 321   t.equals(u.gt(100).valid, false, "gt big")
 322   t.equals(u.gt(-1).index, 0, "ge small")
 323
 324   t.equals(u.le(3).index, 6, "le simple")
 325   t.equals(u.le(0.9).index, 0, "le run start")
 326   t.equals(u.le(1).index, 4, "le run mid")
 327   t.equals(u.le(1.1).index, 4, "le run end")
 328   t.equals(u.le(0).index, 0, "le first")
 329   t.equals(u.le(6).index, 10, "le last")
 330   t.equals(u.le(100).index, 10, "le big")
 331   t.equals(u.le(-1).valid, false, "le small")
 332
 333   t.equals(u.lt(3).index, 5, "lt simple")
 334   t.equals(u.lt(0.9).index, 0, "lt run start")
 335   t.equals(u.lt(1).index, 0, "lt run mid")
 336   t.equals(u.lt(1.1).index, 4, "lt run end")
 337   t.equals(u.lt(0).valid, false, "lt first")
 338   t.equals(u.lt(6).index, 8, "lt last")
 339   t.equals(u.lt(100).index, 10, "lt big")
 340   t.equals(u.lt(-1).valid, false, "lt small")
 341
 342   t.equals(u.find(-1).valid, false, "find missing small")
 343   t.equals(u.find(10000).valid, false, "find missing big")
 344   t.equals(u.find(3).index, 6, "find simple")
 345   t.ok(u.find(1).index > 0, "find repeat")
 346   t.ok(u.find(1).index < 5, "find repeat")
 347
 348   for(var i=0; i<arr.length; ++i) {
 349     t.equals(u.find(arr[i]).key, arr[i], "find " + i)
 350   }
 351
 352   for(var i=0; i<arr.length; ++i) {
 353     t.equals(u.at(i).key, arr[i], "at " + i)
 354   }
 355   t.equals(u.at(-1).valid, false, "at missing small")
 356   t.equals(u.at(1000).valid, false, "at missing big")
 357
 358
 359   t.end()
 360 })
 361
 362 tape("slab-sequence", function(t) {
 363
 364   var tree = makeTree()
 365
 366   tree=tree.insert(0, 0)
 367   checkTree(tree, t)
 368   t.same(tree.values, [0])
 369
 370   tree=tree.insert(1, 1)
 371   checkTree(tree, t)
 372   t.same(tree.values, [0,1])
 373
 374   tree=tree.insert(0.5, 2)
 375   checkTree(tree, t)
 376   t.same(tree.values, [0,2,1])
 377
 378   tree=tree.insert(0.25, 3)
 379   checkTree(tree, t)
 380   t.same(tree.values, [0,3,2,1])
 381
 382   tree=tree.remove(0)
 383   checkTree(tree, t)
 384   t.same(tree.values, [3,2,1])
 385
 386   tree=tree.insert(0.375, 4)
 387   checkTree(tree, t)
 388   t.same(tree.values, [3, 4, 2, 1])
 389
 390   tree=tree.remove(1)
 391   checkTree(tree, t)
 392   t.same(tree.values, [3,4,2])
 393
 394   tree=tree.remove(0.5)
 395   checkTree(tree, t)
 396   t.same(tree.values, [3,4])
 397
 398   tree=tree.remove(0.375)
 399   checkTree(tree, t)
 400   t.same(tree.values, [3])
 401
 402   tree=tree.remove(0.25)
 403   checkTree(tree, t)
 404   t.same(tree.values, [])
 405
 406   t.end()
 407 })
 408
 409 tape("slab-sequence-2", function(t) {
 410
 411   var u = makeTree()
 412
 413   u=u.insert( 12 , 22 )
 414   u=u.insert( 11 , 3 )
 415   u=u.insert( 10 , 28 )
 416   u=u.insert( 13 , 16 )
 417   u=u.insert( 9 , 9 )
 418   u=u.insert( 14 , 10 )
 419   u=u.insert( 8 , 15 )
 420   u=u.insert( 15 , 29 )
 421   u=u.insert( 16 , 4 )
 422   u=u.insert( 7 , 21 )
 423   u=u.insert( 17 , 23 )
 424   u=u.insert( 6 , 2 )
 425   u=u.insert( 5 , 27 )
 426   u=u.insert( 18 , 17 )
 427   u=u.insert( 4 , 8 )
 428   u=u.insert( 31 , 11 )
 429   u=u.insert( 30 , 30 )
 430   u=u.insert( 29 , 5 )
 431   u=u.insert( 28 , 24 )
 432   u=u.insert( 27 , 18 )
 433   u=u.insert( 26 , 12 )
 434   u=u.insert( 25 , 31 )
 435   u=u.insert( 24 , 6 )
 436   u=u.insert( 23 , 25 )
 437   u=u.insert( 19 , 7 )
 438   u=u.insert( 20 , 13 )
 439   u=u.insert( 1 , 20 )
 440   u=u.insert( 0 , 14 )
 441   u=u.insert( 22 , 0 )
 442   u=u.insert( 2 , 1 )
 443   u=u.insert( 3 , 26 )
 444   u=u.insert( 21 , 19 )
 445   u=u.remove( 18 , 17 )
 446   u=u.remove( 17 , 23 )
 447   u=u.remove( 16 , 4 )
 448   u=u.remove( 15 , 29 )
 449   u=u.remove( 14 , 10 )
 450   u=u.remove( 13 , 16 )
 451   u=u.remove( 12 , 22 )
 452   u=u.remove( 6 , 2 )
 453   u=u.remove( 7 , 21 )
 454   u=u.remove( 8 , 15 )
 455   u=u.remove( 11 , 3 )
 456   u=u.remove( 4 , 8 )
 457   u=u.remove( 9 , 9 )
 458   u=u.remove( 10 , 28 )
 459   u=u.remove( 5 , 27 )
 460   u=u.remove( 31 , 11 )
 461   u=u.remove( 0 , 14 )
 462   u=u.remove( 30 , 30 )
 463   u=u.remove( 29 , 5 )
 464   u=u.remove( 1 , 20 )
 465   u=u.remove( 28 , 24 )
 466   u=u.remove( 2 , 1 )
 467   u=u.remove( 3 , 26 )
 468   u=u.remove( 27 , 18 )
 469   u=u.remove( 19 , 7 )
 470   u=u.remove( 26 , 12 )
 471   u=u.remove( 20 , 13 )
 472   u=u.remove( 25 , 31 )
 473   u=u.remove( 24 , 6 )
 474   u=u.remove( 21 , 19 )
 475   u=u.remove( 23 , 25 )
 476   u=u.remove( 22 , 0 )
 477
 478   t.end()
 479 })