Subversion Repositories Applications.papyrus

Rev

Rev 1372 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1318 alexandre_ 1 
/*
2 
	Copyright (c) 2004-2006, The Dojo Foundation
3 
	All Rights Reserved.
4 
 
5 
	Licensed under the Academic Free License version 2.1 or above OR the
6 
	modified BSD license. For more information on Dojo licensing, see:
7 
 
8 
		http://dojotoolkit.org/community/licensing.shtml
9 
*/
10 
 
1422 alexandre_ 11 
 
12 
 
1318 alexandre_ 13 
dojo.provide("dojo.collections.SkipList");
14 
dojo.require("dojo.collections.Collections");
15 
dojo.require("dojo.experimental");
16 
dojo.experimental("dojo.collections.SkipList");
17 
dojo.collections.SkipList = function () {
18 
	function node(height, val) {
19 
		this.value = val;
20 
		this.height = height;
21 
		this.nodes = new nodeList(height);
22 
		this.compare = function (val) {
23 
			if (this.value > val) {
24 
				return 1;
25 
			}
26 
			if (this.value < val) {
27 
				return -1;
28 
			}
29 
			return 0;
30 
		};
31 
		this.incrementHeight = function () {
32 
			this.nodes.incrementHeight();
33 
			this.height++;
34 
		};
35 
		this.decrementHeight = function () {
36 
			this.nodes.decrementHeight();
37 
			this.height--;
38 
		};
39 
	}
40 
	function nodeList(height) {
41 
		var arr = [];
42 
		this.height = height;
43 
		for (var i = 0; i < height; i++) {
44 
			arr[i] = null;
45 
		}
46 
		this.item = function (i) {
47 
			return arr[i];
48 
		};
49 
		this.incrementHeight = function () {
50 
			this.height++;
51 
			arr[this.height] = null;
52 
		};
53 
		this.decrementHeight = function () {
54 
			arr.splice(arr.length - 1, 1);
55 
			this.height--;
56 
		};
57 
	}
58 
	function iterator(list) {
59 
		this.element = list.head;
60 
		this.atEnd = function () {
61 
			return (this.element == null);
62 
		};
63 
		this.get = function () {
64 
			if (this.atEnd()) {
65 
				return null;
66 
			}
67 
			this.element = this.element.nodes[0];
68 
			return this.element;
69 
		};
70 
		this.reset = function () {
71 
			this.element = list.head;
72 
		};
73 
	}
74 
	function chooseRandomHeight(max) {
75 
		var level = 1;
76 
		while (Math.random() < PROB && level < max) {
77 
			level++;
78 
		}
79 
		return level;
80 
	}
81 
	var PROB = 0.5;
82 
	var comparisons = 0;
83 
	this.head = new node(1);
84 
	this.count = 0;
85 
	this.add = function (val) {
86 
		var updates = [];
87 
		var current = this.head;
88 
		for (var i = this.head.height; i >= 0; i--) {
89 
			if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) {
90 
				comparisons++;
91 
			}
92 
			while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) {
93 
				current = current.nodes[i];
94 
				comparisons++;
95 
			}
96 
			updates[i] = current;
97 
		}
98 
		if (current.nodes[0] != null && current.nodes[0].compare(val) == 0) {
99 
			return;
100 
		}
101 
		var n = new node(val, chooseRandomHeight(this.head.height + 1));
102 
		this.count++;
103 
		if (n.height > this.head.height) {
104 
			this.head.incrementHeight();
105 
			this.head.nodes[this.head.height - 1] = n;
106 
		}
107 
		for (i = 0; i < n.height; i++) {
108 
			if (i < updates.length) {
109 
				n.nodes[i] = updates[i].nodes[i];
110 
				updates[i].nodes[i] = n;
111 
			}
112 
		}
113 
	};
114 
	this.contains = function (val) {
115 
		var current = this.head;
116 
		var i;
117 
		for (i = this.head.height - 1; i >= 0; i--) {
118 
			while (current.item(i) != null) {
119 
				comparisons++;
120 
				var result = current.nodes[i].compare(val);
121 
				if (result == 0) {
122 
					return true;
123 
				} else {
124 
					if (result < 0) {
125 
						current = current.nodes[i];
126 
					} else {
127 
						break;
128 
					}
129 
				}
130 
			}
131 
		}
132 
		return false;
133 
	};
134 
	this.getIterator = function () {
135 
		return new iterator(this);
136 
	};
137 
	this.remove = function (val) {
138 
		var updates = [];
139 
		var current = this.head;
140 
		for (var i = this.head.height - 1; i >= 0; i--) {
141 
			if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) {
142 
				comparisons++;
143 
			}
144 
			while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) {
145 
				current = current.nodes[i];
146 
				comparisons++;
147 
			}
148 
			updates[i] = current;
149 
		}
150 
		current = current.nodes[0];
151 
		if (current != null && current.compare(val) == 0) {
152 
			this.count--;
153 
			for (var i = 0; i < this.head.height; i++) {
154 
				if (updates[i].nodes[i] != current) {
155 
					break;
156 
				} else {
157 
					updates[i].nodes[i] = current.nodes[i];
158 
				}
159 
			}
160 
			if (this.head.nodes[this.head.height - 1] == null) {
161 
				this.head.decrementHeight();
162 
			}
163 
		}
164 
	};
165 
	this.resetComparisons = function () {
166 
		comparisons = 0;
167 
	};
168 
};
169