1 JXG = {}; 2 3 /** 4 * Balanced binary search tree 5 */ 6 JXG.BST = function() { 7 this.head = null; 8 this.z = null; 9 this.randomized = true; 10 }; 11 12 /** 13 * public 14 */ 15 JXG.BST.prototype.newNode = function(it, le, ri, n) { 16 return {item:it, l:le, r: ri, N: n}; 17 }; 18 19 JXG.BST.prototype.init = function(random) { 20 this.z =this.newNode(null, 0, 0, 0); 21 this.head = this.z; 22 if (typeof random != 'undefined') { 23 this.randomized = random; 24 } 25 }; 26 27 JXG.BST.prototype.count = function() { 28 return this.head.N; 29 }; 30 31 JXG.BST.prototype.search = function(val) { 32 return this.searchR(this.head, val); 33 }; 34 35 JXG.BST.prototype.insert = function(item) { 36 if (this.randomized) { 37 this.head = this.insertRandR(this.head, item); 38 } else { 39 this.head = this.insertR(this.head, item); 40 } 41 }; 42 43 JXG.BST.prototype.traverse = function(h, visit) { 44 if (this.isNil(h)) { 45 return; 46 } 47 visit(h); 48 this.traverse(h.l, visit); 49 this.traverse(h.r, visit); 50 }; 51 52 JXG.BST.prototype.insertHead = function(item) { 53 this.head = this.insertT(this.head, item); 54 }; 55 56 JXG.BST.prototype.deleteNode = function(v) { 57 this.head = this.deleteR(this.head, v); 58 }; 59 60 JXG.BST.prototype.join = function(a, b) { 61 if (this.isNil(b)) { return a; } 62 if (this.isNil(a)) { return b; } 63 64 b = this.insertT(b, a.item); 65 b.l = this.join(a.l, b.l); 66 b.r = this.join(a.r, b.r); 67 68 this.fixN(b); 69 70 delete (a); 71 return b; 72 }; 73 74 JXG.BST.prototype.select = function(k) { 75 return this.selectR(this.head, k); 76 }; 77 78 JXG.BST.prototype.balance = function() { 79 this.head = this.balanceR(this.head); 80 }; 81 82 JXG.BST.prototype.show = function() { 83 this.showR(this.head, 0); 84 }; 85 86 JXG.BST.prototype.joinRand = function(a, b) { 87 if (Math.random()/(1.0/(a.N+b.N) + 1) < a.N) { 88 return this.joinRandR(a, b); 89 } else { 90 return this.joinRandR(b, a); 91 } 92 }; 93 94 JXG.BST.prototype.minimum = function(h) { 95 if (this.isNil(h)) { 96 return h; 97 } 98 while (!this.isNil(h.l)) { 99 h = h.l; 100 } 101 return h; 102 }; 103 104 JXG.BST.prototype.maximum = function(h) { 105 if (this.isNil(h)) { 106 return h; 107 } 108 while (!this.isNil(h.r)) { 109 h = h.r; 110 } 111 return h; 112 }; 113 114 JXG.BST.prototype.next = function(node) { 115 var nxt, h = this.head; 116 117 // Trivial case 118 if (this.isNil(h)) { 119 return h; 120 } 121 122 if (!this.isNil(node.r)) { 123 return this.minimum(node.r); 124 } else { 125 while (!this.isNil(h)) { 126 if (node.item < h.item) { // <------------- 127 nxt = h; 128 h = h.l; 129 } else if (h.item < node.item) { // <------------- 130 h = h.r; 131 } else { 132 break; 133 } 134 } 135 } 136 137 return nxt; 138 }; 139 140 JXG.BST.prototype.prev = function(node) { 141 var nxt, h = this.head; 142 143 // Trivial case 144 if (this.isNil(h)) { 145 return h; 146 } 147 148 if (!this.isNil(node.l)) { 149 return this.maximum(node.l); 150 } else { 151 while (!this.isNil(h)) { 152 if (node.item < h.item) { // <------------- 153 h = h.l; 154 } else if (h.item < node.item) { // <------------- 155 nxt = h; 156 h = h.r; 157 } else { 158 break; 159 } 160 } 161 } 162 163 return nxt; 164 }; 165 166 167 /** 168 * private 169 */ 170 JXG.BST.prototype.fixN = function(h) { 171 h.N = h.l.N + h.r.N + 1; 172 }; 173 174 JXG.BST.prototype.isNil = function(h) { 175 if (h.l == 0 && h.r == 0) { 176 return true; 177 } else { 178 return false; 179 } 180 }; 181 182 JXG.BST.prototype.searchR = function(h, val) { 183 var t = h.item; // <------- 184 if (this.isNil(h)) { 185 return this.z; 186 } 187 if (val == t) { // <------- 188 return h; 189 } 190 if (val < t) { // <------- 191 return this.searchR(h.l, val); 192 } else { 193 return this.searchR(h.r, val); 194 } 195 }; 196 197 JXG.BST.prototype.insertR = function(h, item) { 198 var v = item, 199 t = h.item; 200 201 if (this.isNil(h)) { 202 return this.newNode(item, this.z, this.z, 1); 203 } 204 205 if (v < t) { // <--------- 206 h.l = this.insertR(h.l, item); 207 } else { 208 h.r = this.insertR(h.r, item); 209 } 210 h.N++; 211 return h; 212 }; 213 214 JXG.BST.prototype.rotR = function(h) { 215 var x = h.l; 216 h.l = x.r; 217 x.r = h; 218 219 this.fixN(h); 220 this.fixN(x); 221 return x; 222 }; 223 224 JXG.BST.prototype.rotL = function(h) { 225 var x = h.r, 226 n = x.N; 227 h.r = x.l; 228 x.l = h; 229 230 this.fixN(h); 231 this.fixN(x); 232 return x; 233 }; 234 235 JXG.BST.prototype.insertT = function(h, item) { 236 var v = item; // <--------------- 237 if (this.isNil(h)) { 238 return this.newNode(item, this.z, this.z, 1); 239 } 240 241 if (v < h.item) { // <--------------- 242 h.l = this.insertT(h.l, item); 243 h = this.rotR(h); 244 } else { 245 h.r = this.insertT(h.r, item); 246 h = this.rotL(h); 247 } 248 return h; 249 }; 250 251 JXG.BST.prototype.selectR = function(h, k) { 252 var t; 253 254 if (this.isNil(h)) { 255 return null; 256 } 257 t = (this.isNil(h.l)) ? 0 : h.l.N; 258 259 260 if (t > k) { 261 return this.selectR(h.l, k); 262 } 263 if (t < k) { 264 return this.selectR(h.r, k-t-1); 265 } 266 return h.item; 267 }; 268 269 JXG.BST.prototype.partR = function(h, k) { 270 var t = h.l.N; 271 272 if (t > k) { 273 h.l = this.partR(h.l, k); 274 h = this.rotR(h); 275 this.head = h; 276 } 277 if (t < k) { 278 h.r = this.partR(h.r, k-t-1); 279 h = this.rotL(h); 280 this.head = h; 281 } 282 return h; 283 }; 284 285 JXG.BST.prototype.joinLR = function(a, b) { 286 if (this.isNil(b)) { 287 return a; 288 } 289 290 b = this.partR(b, 0); 291 b.l = a; 292 this.fixN(b); 293 return b; 294 }; 295 296 JXG.BST.prototype.deleteR = function(h, v) { 297 var x, 298 t = h.item; // <---------------- 299 300 if (this.isNil(h)) { 301 return this.z; 302 } 303 304 if (v<t) { h.l = this.deleteR(h.l, v); } // <---------------- 305 if (t<v) { h.r = this.deleteR(h.r, v); } // <---------------- 306 if (t == v) { 307 x = h; 308 if (this.randomized) { 309 h = this.joinRandLR(h.l, h.r); 310 } else { 311 h = this.joinLR(h.l, h.r); 312 } 313 delete (x); 314 } 315 if (this.isNil(h)) { 316 this.fixN(h); 317 } 318 return h; 319 }; 320 321 JXG.BST.prototype.balanceR = function(h) { 322 if (h.N < 2) { 323 return h; 324 } 325 326 h = this.partR(h, Math.floor(h.N/2)); 327 328 h.l = this.balanceR(h.l); 329 h.r = this.balanceR(h.r); 330 return h; 331 } 332 333 /** 334 * Randomized Balnaced Binary Trees 335 */ 336 JXG.BST.prototype.insertRandR= function(h, item) { 337 var v = item, 338 t = h.item; 339 340 if (this.isNil(h)) { 341 return this.newNode(item, this.z, this.z, 1); 342 } 343 344 if (Math.random()<1.0/(h.N+1)) { 345 return this.insertT(h, item); 346 } 347 348 if (v < t) { // <--------- 349 h.l = this.insertRandR(h.l, item); 350 } else { 351 h.r = this.insertRandR(h.r, item); 352 } 353 h.N++; 354 return h; 355 }; 356 357 JXG.BST.prototype.joinRandR = function(a, b) { 358 if (this.isNil(a)) { 359 return b; 360 } 361 362 b = this.insertRandR(b, a.item); 363 b.l = this.joinRand(a.l, b.l); 364 b.r = this.joinRand(a.r, b.r); 365 366 this.fixN(b); 367 delete(a); 368 return b; 369 }; 370 371 JXG.BST.prototype.joinRandLR = function(a, b) { 372 if (this.isNil(a)) { return b; } 373 if (this.isNil(b)) { return a; } 374 375 if (Math.random()/(1.0/(a.N+b.N) + 1) < a.N) { 376 a.r = this.joinRandLR(a.r, b); 377 return a; 378 } else { 379 b.l = this.joinRandLR(a, b.l); 380 return b; 381 } 382 }; 383 384 /** 385 * Test output 386 */ 387 JXG.BST.prototype.printnode = function(node, hgt) { 388 var i, t=''; 389 for (i=0; i<hgt; i++) { 390 t += ' '; 391 } 392 t += '('+node.item + ',' + node.N+')'; 393 console.log(t); 394 }; 395 396 JXG.BST.prototype.showR = function(x, hgt) { 397 if (this.isNil(x)) { 398 this.printnode(x, hgt); 399 return; 400 } 401 this.showR(x.r, hgt+1); 402 this.printnode(x, hgt); 403 this.showR(x.l, hgt+1); 404 }; 405 406 407 /** 408 * Heap 409 */ 410 JXG.Heap = function() { 411 this.pq = []; 412 this.N = 0; 413 }; 414 415 /** 416 * public 417 */ 418 JXG.Heap.prototype.empty = function() { 419 this.pq = []; 420 this.N = 0; 421 }; 422 423 JXG.Heap.prototype.insert = function(v) { 424 this.pq[this.N] = v; 425 this.N++; 426 this.fixUp(this.N); 427 }; 428 429 JXG.Heap.prototype.delmax = function() { 430 this.exchange(0, this.N-1); 431 this.fixDown(0, this.N-1); 432 this.N--; 433 return this.pq[this.N]; 434 }; 435 436 /** 437 * private 438 */ 439 JXG.Heap.prototype.fixUp = function(k) { 440 var i = k-1; 441 while (i>0 && this.pq[Math.floor(i/2)] < this.pq[i]) { // <---------------- 442 this.exchange(Math.floor(i/2),i); 443 i = Math.floor(i/2); 444 }; 445 }; 446 447 JXG.Heap.prototype.fixDown = function(k, N) { 448 var j, i = k; 449 while (2*i<N) { 450 j = 2*i; 451 if (j<N && this.pq[j] < this.pq[j+1]) { // <---------------- 452 j++; 453 } 454 if (! (this.pq[i]<this.pq[j]) ) break; 455 this.exchange(i, j); 456 i = j; 457 } 458 }; 459 460 JXG.Heap.prototype.exchange = function(i, j) { 461 var t = this.pq[i]; 462 this.pq[i] = this.pq[j]; 463 this.pq[j] = t; 464 }; 465 466 467 468 469 470