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