3 var makeTree = require("../rbtree.js")
4 var tape = require("tape")
5 var util = require("util")
6 var iota = require("iota-array")
8 var COLORS = [ "r", "b", "bb" ]
10 function printTree(tree) {
14 return [ COLORS[tree._color], tree.key, printTree(tree.left), printTree(tree.right) ]
18 console.log(util.inspect(printTree(t.root), {depth:12}))
21 //Ensures the red black axioms are satisfied by tree
22 function checkTree(tree, t) {
26 t.equals(tree.root._color, 1, "root is black")
27 function checkNode(node) {
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")
35 t.equals(node._color, 1, "node color must be red or black")
38 t.assert(tree._compare(node.left.key, node.key) <= 0, "left tree order invariant")
41 t.assert(tree._compare(node.right.key, node.key) >= 0, "right tree order invariant")
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]
49 var r = checkNode(tree.root)
50 t.equals(r[1], tree.length, "tree length")
53 tape("insert()", function(t) {
58 for(var i=20; i>=0; --i) {
60 var next = u.insert(x, true)
63 t.equals(u.length, arr.length)
67 for(var i=-20; i<0; ++i) {
69 var next = u.insert(x, true)
72 arr.sort(function(a,b) { return a-b })
74 u.forEach(function(k,v) {
75 t.equals(k, arr[ptr++])
77 t.equals(ptr, arr.length)
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")
89 t.assert(start.hasNext, "hasNext()")
91 t.assert(!start.hasNext, "eof hasNext()")
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")
102 tape("foreach", function(t) {
103 var u = iota(31).reduce(function(u, k, v) {
104 return u.insert(k, v)
107 //Check basic foreach
110 u.forEach(function(k,v) {
114 t.same(visit_keys, u.keys)
115 t.same(visit_vals, u.values)
117 //Check foreach with termination
120 t.equals(u.forEach(function(k,v) {
127 t.same(visit_keys, u.keys.slice(0, 5))
128 t.same(visit_vals, u.values.slice(0, 5))
130 //Check half interval foreach
133 u.forEach(function(k,v) {
137 t.same(visit_keys, u.keys.slice(3))
138 t.same(visit_vals, u.values.slice(3))
140 //Check half interval foreach with termination
143 t.equals(u.forEach(function(k,v) {
150 t.same(visit_keys, u.keys.slice(3, 12))
151 t.same(visit_vals, u.values.slice(3, 12))
154 //Check interval foreach
157 u.forEach(function(k,v) {
161 t.same(visit_keys, u.keys.slice(3, 15))
162 t.same(visit_vals, u.values.slice(3, 15))
164 //Check interval foreach with termination
167 t.equals(u.forEach(function(k,v) {
174 t.same(visit_keys, u.keys.slice(3, 12))
175 t.same(visit_vals, u.values.slice(3, 12))
180 function compareIterators(a, b, t) {
181 t.equals(a.tree, b.tree, "iter trees")
182 t.equals(a.valid, b.valid, "iter validity")
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")
192 tape("iterators", function(t) {
193 var u = iota(20).reduce(function(u, k, v) {
194 return u.insert(k, v)
197 //Try walking forward
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) {
204 compareIterators(iter, v, t)
205 t.equals(iter.index, i)
208 t.ok(!iter.valid, "must be eof iterator")
210 //Check if the clone worked
211 compareIterators(c, u.begin, t)
213 //Try walking backward
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) {
219 compareIterators(iter, v, t)
220 t.equals(iter.index, i)
223 t.ok(!iter.valid, "must be eof iterator")
229 tape("remove()", function(t) {
231 var sz = [1, 2, 10, 20, 23, 31, 32, 33]
232 for(var n=0; n<sz.length; ++n) {
234 var u = iota(c).reduce(function(u, k, v) {
235 return u.insert(k, v)
237 for(var i=0; i<c; ++i) {
238 checkTree(u.remove(i), t)
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)
250 for(var iter=u.begin; iter.hasNext; iter.next()) {
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)
262 tape("keys and values", function(t) {
264 var original_keys = [ "potato", "sock", "foot", "apple", "newspaper", "gameboy" ]
265 var original_values = [ 42, 10, false, "!!!", {}, null ]
268 for(var i=0; i<original_keys.length; ++i) {
269 u = u.insert(original_keys[i], original_values[i])
272 var zipped = iota(6).map(function(i) {
273 return [ original_keys[i], original_values[i] ]
276 zipped.sort(function(a,b) {
277 if(a[0] < b[0]) { return -1 }
278 if(a[0] > b[0]) { return 1 }
282 var keys = zipped.map(function(v) { return v[0] })
283 var values = zipped.map(function(v) { return v[1] })
286 t.same(u.values, values)
291 tape("searching", function(t) {
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)
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])
304 t.equals(u.get(-1), undefined, "get missing")
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")
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")
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")
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")
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")
348 for(var i=0; i<arr.length; ++i) {
349 t.equals(u.find(arr[i]).key, arr[i], "find " + i)
352 for(var i=0; i<arr.length; ++i) {
353 t.equals(u.at(i).key, arr[i], "at " + i)
355 t.equals(u.at(-1).valid, false, "at missing small")
356 t.equals(u.at(1000).valid, false, "at missing big")
362 tape("slab-sequence", function(t) {
364 var tree = makeTree()
366 tree=tree.insert(0, 0)
368 t.same(tree.values, [0])
370 tree=tree.insert(1, 1)
372 t.same(tree.values, [0,1])
374 tree=tree.insert(0.5, 2)
376 t.same(tree.values, [0,2,1])
378 tree=tree.insert(0.25, 3)
380 t.same(tree.values, [0,3,2,1])
384 t.same(tree.values, [3,2,1])
386 tree=tree.insert(0.375, 4)
388 t.same(tree.values, [3, 4, 2, 1])
392 t.same(tree.values, [3,4,2])
394 tree=tree.remove(0.5)
396 t.same(tree.values, [3,4])
398 tree=tree.remove(0.375)
400 t.same(tree.values, [3])
402 tree=tree.remove(0.25)
404 t.same(tree.values, [])
409 tape("slab-sequence-2", function(t) {
413 u=u.insert( 12 , 22 )
415 u=u.insert( 10 , 28 )
416 u=u.insert( 13 , 16 )
418 u=u.insert( 14 , 10 )
420 u=u.insert( 15 , 29 )
423 u=u.insert( 17 , 23 )
426 u=u.insert( 18 , 17 )
428 u=u.insert( 31 , 11 )
429 u=u.insert( 30 , 30 )
431 u=u.insert( 28 , 24 )
432 u=u.insert( 27 , 18 )
433 u=u.insert( 26 , 12 )
434 u=u.insert( 25 , 31 )
436 u=u.insert( 23 , 25 )
438 u=u.insert( 20 , 13 )
444 u=u.insert( 21 , 19 )
445 u=u.remove( 18 , 17 )
446 u=u.remove( 17 , 23 )
448 u=u.remove( 15 , 29 )
449 u=u.remove( 14 , 10 )
450 u=u.remove( 13 , 16 )
451 u=u.remove( 12 , 22 )
458 u=u.remove( 10 , 28 )
460 u=u.remove( 31 , 11 )
462 u=u.remove( 30 , 30 )
465 u=u.remove( 28 , 24 )
468 u=u.remove( 27 , 18 )
470 u=u.remove( 26 , 12 )
471 u=u.remove( 20 , 13 )
472 u=u.remove( 25 , 31 )
474 u=u.remove( 21 , 19 )
475 u=u.remove( 23 , 25 )