New file |
0,0 → 1,167 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
|
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
|
http://dojotoolkit.org/community/licensing.shtml |
*/ |
|
dojo.provide("dojo.collections.SkipList"); |
dojo.require("dojo.collections.Collections"); |
dojo.require("dojo.experimental"); |
dojo.experimental("dojo.collections.SkipList"); |
dojo.collections.SkipList = function () { |
function node(height, val) { |
this.value = val; |
this.height = height; |
this.nodes = new nodeList(height); |
this.compare = function (val) { |
if (this.value > val) { |
return 1; |
} |
if (this.value < val) { |
return -1; |
} |
return 0; |
}; |
this.incrementHeight = function () { |
this.nodes.incrementHeight(); |
this.height++; |
}; |
this.decrementHeight = function () { |
this.nodes.decrementHeight(); |
this.height--; |
}; |
} |
function nodeList(height) { |
var arr = []; |
this.height = height; |
for (var i = 0; i < height; i++) { |
arr[i] = null; |
} |
this.item = function (i) { |
return arr[i]; |
}; |
this.incrementHeight = function () { |
this.height++; |
arr[this.height] = null; |
}; |
this.decrementHeight = function () { |
arr.splice(arr.length - 1, 1); |
this.height--; |
}; |
} |
function iterator(list) { |
this.element = list.head; |
this.atEnd = function () { |
return (this.element == null); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = this.element.nodes[0]; |
return this.element; |
}; |
this.reset = function () { |
this.element = list.head; |
}; |
} |
function chooseRandomHeight(max) { |
var level = 1; |
while (Math.random() < PROB && level < max) { |
level++; |
} |
return level; |
} |
var PROB = 0.5; |
var comparisons = 0; |
this.head = new node(1); |
this.count = 0; |
this.add = function (val) { |
var updates = []; |
var current = this.head; |
for (var i = this.head.height; i >= 0; i--) { |
if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) { |
comparisons++; |
} |
while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) { |
current = current.nodes[i]; |
comparisons++; |
} |
updates[i] = current; |
} |
if (current.nodes[0] != null && current.nodes[0].compare(val) == 0) { |
return; |
} |
var n = new node(val, chooseRandomHeight(this.head.height + 1)); |
this.count++; |
if (n.height > this.head.height) { |
this.head.incrementHeight(); |
this.head.nodes[this.head.height - 1] = n; |
} |
for (i = 0; i < n.height; i++) { |
if (i < updates.length) { |
n.nodes[i] = updates[i].nodes[i]; |
updates[i].nodes[i] = n; |
} |
} |
}; |
this.contains = function (val) { |
var current = this.head; |
var i; |
for (i = this.head.height - 1; i >= 0; i--) { |
while (current.item(i) != null) { |
comparisons++; |
var result = current.nodes[i].compare(val); |
if (result == 0) { |
return true; |
} else { |
if (result < 0) { |
current = current.nodes[i]; |
} else { |
break; |
} |
} |
} |
} |
return false; |
}; |
this.getIterator = function () { |
return new iterator(this); |
}; |
this.remove = function (val) { |
var updates = []; |
var current = this.head; |
for (var i = this.head.height - 1; i >= 0; i--) { |
if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) { |
comparisons++; |
} |
while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) { |
current = current.nodes[i]; |
comparisons++; |
} |
updates[i] = current; |
} |
current = current.nodes[0]; |
if (current != null && current.compare(val) == 0) { |
this.count--; |
for (var i = 0; i < this.head.height; i++) { |
if (updates[i].nodes[i] != current) { |
break; |
} else { |
updates[i].nodes[i] = current.nodes[i]; |
} |
} |
if (this.head.nodes[this.head.height - 1] == null) { |
this.head.decrementHeight(); |
} |
} |
}; |
this.resetComparisons = function () { |
comparisons = 0; |
}; |
}; |
|