Subversion Repositories Applications.papyrus

Rev

Details | Last modification | View Log | RSS feed

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