blob: 5902380529fa5604a01e682a59339a0f14ec8463 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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;
}
});
}
|
