/*
 btree.js (c) 2013 Daniel Wirtz <dcode@dcode.io>
 Released under the Apache License, Version 2.0
 see: http://github.com/dcodeIO/btree.js for details
*/
(function() {
'use strict';var e=null;
var module = {};
(function(r,s){function n(g){for(var h=[],l=0;l<arguments.length;l++)Array.prototype.push.apply(h,arguments[l]);return h}function m(g,h){for(var l=0;l<g.length;l++)if(g[l]===h)return l;return-l}var q={strcmp:function(g,h){for(var l,k,f=0;f<g.length;f++){if(f>=h.length)return 1;if((l=g.charCodeAt(f))<(k=h.charCodeAt(f)))return-1;if(l>k)return 1}return g.length==h.length?0:-1},numcmp:function(g,h){return g<h?-1:g>h?1:0},create:function(g,h){function l(a,b,d){this.parent=a;this.key=b;this.value=d}function k(a,
b,d){this.parent=a;this.a=b||[];this.a.forEach(function(a){a.parent=this},this);this.b=d||[e];this.b.forEach(function(a){a!==e&&(a.parent=this)},this)}function f(){this.root=new k(this)}g="undefined"==typeof g?52:"number"==typeof g?Math.floor(g):parseInt(g,10);1>g&&(g=1);var p=1<g?Math.floor(g/2):1;"function"!=typeof h&&(h=q.numcmp);k.prototype.search=function(a){if(0<this.a.length){var b=this.a[0];if(0==h(b.key,a))return{c:b,index:0};if(0>h(a,b.key))return this.b[0]!==e?this.b[0].search(a):{d:this,
index:0};for(b=1;b<this.a.length;b++){var d=this.a[b];if(0==h(d.key,a))return{c:d,index:b};if(0>h(a,d.key))break}return this.b[b]!==e?this.b[b].search(a):{d:this,index:b}}return{d:this,index:0}};k.prototype.get=function(a){a=this.search(a);if(a.c)return a.c.value};k.prototype.put=function(a,b,d){var c=this.search(a);if(c.c){if("undefined"!==typeof d&&!d)return!1;c.c.value=b;return!0}d=c.d;c=c.index;d.a.splice(c,0,new l(d,a,b));d.b.splice(c+1,0,e);d.a.length>g&&d.split();return!0};k.prototype.del=
function(a){var b=this.search(a);if(!b.c)return!1;a=b.c.parent;var b=b.index,d=a.b[b];if(d===e)a.a.splice(b,1),a.b.splice(b,1),a.e();else{var c=d.a[d.a.length-1];d.del(c.key);c.parent=a;a.a.splice(b,1,c)}return!0};k.prototype.e=function(){if(this.parent instanceof f)0==this.a.length&&this.b[0]!==e&&(this.parent.root=this.b[0],this.parent.root.parent=this.parent);else if(!(this.a.length>=p)){var a=m(this.parent.b,this),b=0<a?this.parent.b[a-1]:e,d=this.parent.b.length>a+1?this.parent.b[a+1]:e,c;if(d!==
e&&d.a.length>p)c=this.parent.a[a],c.parent=this,this.a.push(c),c=d.a.shift(),c.parent=this.parent,this.parent.a[a]=c,a=d.b.shift(),a!==e&&(a.parent=this),this.b.push(a);else if(b!==e&&b.a.length>p)c=this.parent.a[a-1],c.parent=this,this.a.unshift(c),c=b.a.pop(),c.parent=this.parent,this.parent.a[a-1]=c,a=b.b.pop(),a!==e&&(a.parent=this),this.b.unshift(a);else{if(d!==e)c=this.parent.a[a],b=new k(this.parent,n(this.a,[c],d.a),n(this.b,d.b)),this.parent.a.splice(a,1),this.parent.b.splice(a,2,b);else if(b!==
e)c=this.parent.a[a-1],b=new k(this.parent,n(b.a,[c],this.a),n(b.b,this.b)),this.parent.a.splice(a-1,1),this.parent.b.splice(a-1,2,b);else throw Error("Internal error: "+this.toString(!0)+" has neither a left nor a right sibling");this.parent.e()}}};k.prototype.f=function(a,b){a.parent=this;b.parent=this;if(0>h(a.key,this.a[0].key))this.a.unshift(a),this.b.splice(1,0,b);else{for(var d=1;d<this.a.length;d++)if(0>h(a.key,this.a[d].key)){this.a.splice(d,0,a);this.b.splice(d+1,0,b);break}d==this.a.length&&
(this.a.push(a),this.b.push(b))}this.a.length>g&&this.split()};k.prototype.split=function(){var a=Math.floor(this.a.length/2);if(this.parent instanceof f)this.b=[new k(this,this.a.slice(0,a),this.b.slice(0,a+1)),new k(this,this.a.slice(a+1),this.b.slice(a+1))],this.a=[this.a[a]];else{var b=this.a[a],d=new k(this.parent,this.a.slice(a+1),this.b.slice(a+1));this.a=this.a.slice(0,a);this.b=this.b.slice(0,a+1);this.parent.f(b,d)}};k.prototype.toString=function(a){for(var b=[],d=0;d<this.a.length;d++)b.push(this.a[d].key);
b="["+b.toString()+"]"+(this.parent instanceof f?":*":":"+this.parent);if(a)for(d=0;d<this.b.length;d++)b+=" -> "+this.b[d];return b};k.prototype.print=function(a){for(var b="",d=0;d<a;d++)b+=" ";for(d=this.a.length-1;0<=d;d--)this.b[d+1]!==e&&this.b[d+1].print(a+2),s.log(b+this.a[d].key+(this.parent instanceof f?"*":""));this.b[0]!==e&&this.b[0].print(a+2)};l.prototype.toString=function(){return""+this.key};f.prototype.put=function(a,b,d){if("undefined"===typeof a||a===e)throw Error("Illegal key: "+
a);if("undefined"===typeof b)throw Error("Illegal value: "+b);return this.root.put(a,b,d)};f.prototype.get=function(a){if("undefined"===typeof a||a===e)throw Error("Illegal key: "+a);return this.root.get(a)};f.prototype.del=function(a){if("undefined"===typeof a||a===e)throw Error("Illegal key: "+a);return this.root.del(a)};f.prototype.walkAsc=function(a,b,d){if(0!=this.root.a.length){"function"==typeof a?(d=a,a=b=e):"function"==typeof b&&(d=b,b=e);a="undefined"!=typeof a?a:e;b="undefined"!=typeof b?
b:e;var c;if(a===e){for(a=this.root;a.b[0]!==e;)a=a.b[0];c=0}else if(c=this.root.search(a),c.c)a=c.c.parent,c=m(a.a,c.c);else if(a=c.d,c=c.index,c>=a.a.length){if(a.parent instanceof f)return;c=m(a.parent.b,a);if(c>=a.parent.a.length)return;a=a.parent}for(;!(b!==e&&0<h(a.a[c].key,b))&&!d(a.a[c].key,a.a[c].value);)if(a.b[c+1]!==e){a=a.b[c+1];for(c=0;a.b[0]!==e;)a=a.b[0]}else if(a.a.length>c+1)c++;else{do{if(a.parent instanceof f)return;c=m(a.parent.b,a);a=a.parent}while(c>=a.a.length)}}};f.prototype.walk=
f.prototype.walkAsc;f.prototype.walkDesc=function(a,b,d){"function"==typeof a?(d=a,a=b=e):"function"==typeof b&&(d=b,b=e);a="undefined"!=typeof a?a:e;b="undefined"!=typeof b?b:e;var c;if(b===e){for(b=this.root;b.b[b.b.length-1]!==e;)b=b.b[b.b.length-1];c=b.a.length-1}else if(c=this.root.search(b),c.c)b=c.c.parent,c=m(b.a,c.c);else{b=c.d;for(c=c.index-1;0>c;){if(b.parent instanceof f)return;c=m(b.parent.b,b)-1;if(0>c)return;b=b.parent}}for(;!(a!==e&&0>h(b.a[c].key,a))&&!d(b.a[c].key,b.a[c].value);)if(b.b[c]!==
e){for(b=b.b[c];b.b[b.b.length-1]!==e;)b=b.b[b.b.length-1];c=b.a.length-1}else if(0<c)c--;else{do{if(b.parent instanceof f)return;c=m(b.parent.b,b)-1;b=b.parent}while(0>c)}};f.prototype.count=function(a,b){var d=0;this.walk("undefined"!=typeof a?a:e,"undefined"!=typeof b?b:e,function(){d++});return d};f.prototype.print=function(){this.root.print(0)};f.prototype.toString=function(){return"Tree("+g+") "+this.root.toString()};return f}};r.exports=q})(module,console);
window.btree = module.exports;
})();