git.pond.sub.org Git - eow/blob - static/dojo-release-1.1.1/dojox/encoding/compression/splay.js

   1 if(!dojo._hasResource["dojox.encoding.compression.splay"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
   2 dojo._hasResource["dojox.encoding.compression.splay"] = true;
   3 dojo.provide("dojox.encoding.compression.splay");
   4 dojo.require("dojox.encoding.bits");
   5
   6 dojox.encoding.compression.Splay = function(n){
   7         this.up = new Array(2 * n + 1);
   8         this.left = new Array(n);
   9         this.right = new Array(n);
  10         this.reset();
  11 };
  12
  13 dojo.extend(dojox.encoding.compression.Splay, {
  14         reset: function(){
  15                 for(var i = 1; i < this.up.length; this.up[i] = Math.floor((i - 1) / 2), ++i);
  16                 for(var i = 0; i < this.left.length; this.left[i] = 2 * i + 1, this.right[i] = 2 * i + 2, ++i);
  17         },
  18         splay: function(i){
  19                 var a = i + this.left.length;
  20                 do{
  21                         var c = this.up[a];
  22                         if(c){  // root
  23                                 // rotated pair
  24                                 var d = this.up[c];
  25                                 // swap descendants
  26                                 var b = this.left[d];
  27                                 if(c == b){
  28                                         b = this.right[d];
  29                                         this.right[d] = a;
  30                                 } else {
  31                                         this.left[d] = a;
  32                                 }
  33                                 this[a == this.left[c] ? "left" : "right"][c] = b;
  34                                 this.up[a] = d;
  35                                 this.up[b] = c;
  36                                 a = d;
  37                         }else{
  38                                 a = c;
  39                         }
  40                 }while(a);      // root
  41         },
  42         encode: function(value, stream){
  43                 var s = [], a = value + this.left.length;
  44                 do{
  45                         s.push(this.right[this.up[a]] == a);
  46                         a = this.up[a];
  47                 }while(a);      // root
  48                 this.splay(value);
  49                 var l = s.length;
  50                 while(s.length){ stream.putBits(s.pop() ? 1 : 0, 1); }
  51                 return  l;
  52         },
  53         decode: function(stream){
  54                 var a = 0;      // root;
  55                 do{
  56                         a = this[stream.getBits(1) ? "right" : "left"][a];
  57                 }while(a < this.left.length);
  58                 a -= this.left.length;
  59                 this.splay(a);
  60                 return  a;
  61         }
  62 });
  63
  64 }