skiplist.js

初学者

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