Subversion Repositories Applications.papyrus

Rev

Go to most recent revision | Details | 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 
 
11 
dojo.provide("dojo.collections.SkipList");
12 
dojo.require("dojo.collections.Collections");
13 
dojo.require("dojo.experimental");
14 
dojo.experimental("dojo.collections.SkipList");
15 
dojo.collections.SkipList = function () {
16 
	function node(height, val) {
17 
		this.value = val;
18 
		this.height = height;
19 
		this.nodes = new nodeList(height);
20 
		this.compare = function (val) {
21 
			if (this.value > val) {
22 
				return 1;
23 
			}
24 
			if (this.value < val) {
25 
				return -1;
26 
			}
27 
			return 0;
28 
		};
29 
		this.incrementHeight = function () {
30 
			this.nodes.incrementHeight();
31 
			this.height++;
32 
		};
33 
		this.decrementHeight = function () {
34 
			this.nodes.decrementHeight();
35 
			this.height--;
36 
		};
37 
	}
38 
	function nodeList(height) {
39 
		var arr = [];
40 
		this.height = height;
41 
		for (var i = 0; i < height; i++) {
42 
			arr[i] = null;
43 
		}
44 
		this.item = function (i) {
45 
			return arr[i];
46 
		};
47 
		this.incrementHeight = function () {
48 
			this.height++;
49 
			arr[this.height] = null;
50 
		};
51 
		this.decrementHeight = function () {
52 
			arr.splice(arr.length - 1, 1);
53 
			this.height--;
54 
		};
55 
	}
56 
	function iterator(list) {
57 
		this.element = list.head;
58 
		this.atEnd = function () {
59 
			return (this.element == null);
60 
		};
61 
		this.get = function () {
62 
			if (this.atEnd()) {
63 
				return null;
64 
			}
65 
			this.element = this.element.nodes[0];
66 
			return this.element;
67 
		};
68 
		this.reset = function () {
69 
			this.element = list.head;
70 
		};
71 
	}
72 
	function chooseRandomHeight(max) {
73 
		var level = 1;
74 
		while (Math.random() < PROB && level < max) {
75 
			level++;
76 
		}
77 
		return level;
78 
	}
79 
	var PROB = 0.5;
80 
	var comparisons = 0;
81 
	this.head = new node(1);
82 
	this.count = 0;
83 
	this.add = function (val) {
84 
		var updates = [];
85 
		var current = this.head;
86 
		for (var i = this.head.height; i >= 0; i--) {
87 
			if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) {
88 
				comparisons++;
89 
			}
90 
			while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) {
91 
				current = current.nodes[i];
92 
				comparisons++;
93 
			}
94 
			updates[i] = current;
95 
		}
96 
		if (current.nodes[0] != null && current.nodes[0].compare(val) == 0) {
97 
			return;
98 
		}
99 
		var n = new node(val, chooseRandomHeight(this.head.height + 1));
100 
		this.count++;
101 
		if (n.height > this.head.height) {
102 
			this.head.incrementHeight();
103 
			this.head.nodes[this.head.height - 1] = n;
104 
		}
105 
		for (i = 0; i < n.height; i++) {
106 
			if (i < updates.length) {
107 
				n.nodes[i] = updates[i].nodes[i];
108 
				updates[i].nodes[i] = n;
109 
			}
110 
		}
111 
	};
112 
	this.contains = function (val) {
113 
		var current = this.head;
114 
		var i;
115 
		for (i = this.head.height - 1; i >= 0; i--) {
116 
			while (current.item(i) != null) {
117 
				comparisons++;
118 
				var result = current.nodes[i].compare(val);
119 
				if (result == 0) {
120 
					return true;
121 
				} else {
122 
					if (result < 0) {
123 
						current = current.nodes[i];
124 
					} else {
125 
						break;
126 
					}
127 
				}
128 
			}
129 
		}
130 
		return false;
131 
	};
132 
	this.getIterator = function () {
133 
		return new iterator(this);
134 
	};
135 
	this.remove = function (val) {
136 
		var updates = [];
137 
		var current = this.head;
138 
		for (var i = this.head.height - 1; i >= 0; i--) {
139 
			if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) {
140 
				comparisons++;
141 
			}
142 
			while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) {
143 
				current = current.nodes[i];
144 
				comparisons++;
145 
			}
146 
			updates[i] = current;
147 
		}
148 
		current = current.nodes[0];
149 
		if (current != null && current.compare(val) == 0) {
150 
			this.count--;
151 
			for (var i = 0; i < this.head.height; i++) {
152 
				if (updates[i].nodes[i] != current) {
153 
					break;
154 
				} else {
155 
					updates[i].nodes[i] = current.nodes[i];
156 
				}
157 
			}
158 
			if (this.head.nodes[this.head.height - 1] == null) {
159 
				this.head.decrementHeight();
160 
			}
161 
		}
162 
	};
163 
	this.resetComparisons = function () {
164 
		comparisons = 0;
165 
	};
166 
};
167