summaryrefslogtreecommitdiff
path: root/includes/js/dojox/encoding/compression/splay.js
diff options
context:
space:
mode:
Diffstat (limited to 'includes/js/dojox/encoding/compression/splay.js')
-rw-r--r--includes/js/dojox/encoding/compression/splay.js64
1 files changed, 64 insertions, 0 deletions
diff --git a/includes/js/dojox/encoding/compression/splay.js b/includes/js/dojox/encoding/compression/splay.js
new file mode 100644
index 0000000..5902380
--- /dev/null
+++ b/includes/js/dojox/encoding/compression/splay.js
@@ -0,0 +1,64 @@
+if(!dojo._hasResource["dojox.encoding.compression.splay"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
+dojo._hasResource["dojox.encoding.compression.splay"] = true;
+dojo.provide("dojox.encoding.compression.splay");
+dojo.require("dojox.encoding.bits");
+
+dojox.encoding.compression.Splay = function(n){
+ this.up = new Array(2 * n + 1);
+ this.left = new Array(n);
+ this.right = new Array(n);
+ this.reset();
+};
+
+dojo.extend(dojox.encoding.compression.Splay, {
+ reset: function(){
+ for(var i = 1; i < this.up.length; this.up[i] = Math.floor((i - 1) / 2), ++i);
+ for(var i = 0; i < this.left.length; this.left[i] = 2 * i + 1, this.right[i] = 2 * i + 2, ++i);
+ },
+ splay: function(i){
+ var a = i + this.left.length;
+ do{
+ var c = this.up[a];
+ if(c){ // root
+ // rotated pair
+ var d = this.up[c];
+ // swap descendants
+ var b = this.left[d];
+ if(c == b){
+ b = this.right[d];
+ this.right[d] = a;
+ } else {
+ this.left[d] = a;
+ }
+ this[a == this.left[c] ? "left" : "right"][c] = b;
+ this.up[a] = d;
+ this.up[b] = c;
+ a = d;
+ }else{
+ a = c;
+ }
+ }while(a); // root
+ },
+ encode: function(value, stream){
+ var s = [], a = value + this.left.length;
+ do{
+ s.push(this.right[this.up[a]] == a);
+ a = this.up[a];
+ }while(a); // root
+ this.splay(value);
+ var l = s.length;
+ while(s.length){ stream.putBits(s.pop() ? 1 : 0, 1); }
+ return l;
+ },
+ decode: function(stream){
+ var a = 0; // root;
+ do{
+ a = this[stream.getBits(1) ? "right" : "left"][a];
+ }while(a < this.left.length);
+ a -= this.left.length;
+ this.splay(a);
+ return a;
+ }
+});
+
+}