| /* |
| 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; |
| }; |
| }; |
| |