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