//
	// The Hashtable object implements a keyed list of values. It is stored in a Binary Tree
	//	structure to facilitate the fastest lookups.
	//
function Hashtable(){
	this.init = HashtableInit;
	
	this.init();
}

function HashtableInit(){
	this.startItem = null;
	this.itemsCount = 0;

	this.clear = HashtableClear;
	this.clone = HashtableClone;
	this.containsKey = HashtableContainsKey;
	this.get = HashtableGet;
	this.isEmpty = HashtableIsEmpty;
	this.keys = HashtableKeys;
	this.put = HashtablePut;
	this.iterator = HashtableIterator;
	this.remove = HashtableRemove;
	this.size = HashtableSize;
}

function HashtableClear(){
	this.startItem = null;
	this.itemsCount = 0;
}

function HashtableClone(rBase,rItem){
	if(rBase == null || rBase == undefined){
		rBase = new new Hashtable();
	}
	if(rItem == null || rItem == undefined){
		this.clone(this.startItem);
	} else {
		rBase.put(rItem.key,rItem.value);
		if(this.left != null){
			this.clone(rBase,this.left);
		}
		if(this.right != null){
			this.clone(rBase,this.right);
		}
	}
}

function HashtableSize(){
	return this.itemsCount;
}

function HashtableIsEmpty(){
	return this.itemsCount == 0;
}

function HashtablePut(sKey,rValue){
		//
		// Special case handling for the start item
		//
	if(this.startItem == null){
		this.startItem = new HashtableItem(sKey,rValue);
		this.itemsCount ++;
	}
		//
		// Either find the leaf spot for a new item or find a matching key item
		//
	var rItem = this.startItem;
	while(true){
		if(rItem.key == sKey){
			rItem.value = rValue;
			break;
		} else if(sKey > rItem.key){
			if(rItem.right == null){
				rItem.right = new HashtableItem(sKey,rValue);
				this.itemsCount ++;
				break;
			} else {
				rItem = rItem.right;
			}
		} else {
			if(rItem.left == null){
				rItem.left = new HashtableItem(sKey,rValue);
				this.itemsCount ++;
				break;
			} else {
				rItem = rItem.left;
			}
		}
	}
}

function HashtableGet(sKey){
	var rItem = this.startItem;
	while(rItem != null){
		if(rItem.key == sKey){
			return rItem.value;
		} else if(sKey > rItem.key){
			rItem = rItem.right;
		} else {
			rItem = rItem.left;
		}
	}
	return undefined;
}

function HashtableContainsKey(sKey){
	var rItem = this.startItem;
	while(rItem != null){
		if(rItem.key == sKey){
			return true;
		} else if(sKey > rItem.key){
			rItem = rItem.right;
		} else {
			rItem = rItem.left;
		}
	}
	return false;
}
function HashtableRemove(sKey){
	if(this.startItem.key == sKey){
		this.startItem = null;
		return sKey;
	}
	var rItem = this.startItem;
	while(true){
		if(sKey < rItem.key){
			if(rItem.left == null){
				break;
			} else if(rItem.left.key == sKey){
				var rRemoveItem = rItem.left;
				if(rRemoveItem.left == null && rRemoveItem.right == null){
						//
						// We are removing a leaf so we can just get rid of it.
						//
					rItem.left = null;
					this.itemsCount --;
					return;
				} else {
						//
						// This is not a leaf so we need to find a leaf on the left branch
						// 	to replace this item we are removing
						//
					var rLeafItem = rRemoveItem;
					while(true){
						if(rLeafItem.left != null){
							rLeafItem = rLeafItem.left;
						} else if(rLeafItem.right != null){
							rLeafItem = rLeafItem.right;
						} else {
							break;
						}
					}
						//
						// We found our leaf item so replace our remove item with the leaf item
						//
					rItem.left = rLeafItem;
					this.itemsCount --;
					return;
				}
			} else {
				rItem = rItem.left;
			}
		} else if(sKey > rItem.key){
			if(rItem.right == null){
				break;
			} else if(rItem.right.key == sKey){
				var rRemoveItem = rItem.right;
				if(rRemoveItem.right == null && rRemoveItem.right == null){
						//
						// We are removing a leaf so we can just get rid of it.
						//
					rItem.right = null;
					this.itemsCount --;
					return;
				} else {
						//
						// This is not a leaf so we need to find a leaf on the right branch
						// 	to replace this item we are removing
						//
					var rLeafItem = rRemoveItem;
					while(true){
						if(rLeafItem.right != null){
							rLeafItem = rLeafItem.right;
						} else if(rLeafItem.right != null){
							rLeafItem = rLeafItem.right;
						} else {
							break;
						}
					}
						//
						// We found our leaf item so replace our remove item with the leaf item
						//
					rItem.right = rLeafItem;
					this.itemsCount --;
					return;
				}
			} else {
				rItem = rItem.right;
			}
		}
	}
	return undefined;
}

function HashtableKeys(){
	return new HashtableKeyIteratorItem(this.startItem);
}

function HashtableIterator(){
	return new HashtableIteratorItem(this.startItem);
}
	//
	// Vector Iterator Object
	//
function HashtableIteratorItem(rItem){
	this.item = rItem;
		//
		// We need to implement a stack structure for holding recursion depth
		//
	this.stack = new Array();
	this.stackCount = 0;
		
	this.hasNext = HashtableIteratorHasNext;
	this.next = HashtableIteratorNextValue;
	this.nextItem = HashtableIteratorNextItem;
}

function HashtableKeyIteratorItem(rItem){
	this.item = rItem;
		//
		// We need to implement a stack structure for holding recursion depth
		//
	this.stack = new Array();
	this.stackCount = 0;
		
	this.hasNext = HashtableIteratorHasNext;
	this.next = HashtableIteratorNextKey;
	this.nextItem = HashtableIteratorNextItem;
}
	//
	// This is an item that will go on the iterator stack to indicate
	//	which branch of the tree we have navigated down
	//
function HashtableIteratorStackItem(rItem,bNavLeft){
	this.item = rItem;
	this.navLeft = bNavLeft;
}
	//
	// This returns true if the iterator has more items
	//
function HashtableIteratorHasNext(){
	return this.item != null;
}
	//
	// Returns the value of the item in the iterator
	//
function HashtableIteratorNextValue(){
	var rItem = this.nextItem();
	return rItem.value;
}
	//
	// Returns the key of the item in the iterator
	//
function HashtableIteratorNextKey(){
	var rItem = this.nextItem();
	return rItem.key;
}
	//
	// This implements the next function by returning the current item
	//	in the iterator then walking the tree on the left then bubbling
	//	up using the stack to walk the right branches in a recursive type
	//	operation to get all of the items in the tree
	//
function HashtableIteratorNextItem(){
	if(this.item == null){
		return undefined;
	}
		//
		// Save the current item so we can return it later in the method
		//
	var rItem = this.item;
	if(this.item.left != null){
			//
			// There is a left branch on the node so push the node to the
			//	stack walk to the left node
			//
		this.stack[this.stackCount] = new HashtableIteratorStackItem(rItem,true);
		this.stackCount ++;
		this.item = this.item.left;
	} else if(this.item.right != null){
			//
			// There is a right branch on the node so push the node to the
			//	stack walk to the right node
			//
		this.stack[this.stackCount] = new HashtableIteratorStackItem(rItem,false);
		this.stackCount ++;
		this.item = this.item.right;
	} else if(this.stackCount > 0) {
			//
			// We have reached a leaf so step back up through the stack until we find
			//	a right branch to navigate down or we reach the root. If we are already
			//	on the right branch of a stack node then keep moving up the stack.
			//
		var rStackItem = this.stack[this.stackCount - 1];
		while((!rStackItem.navLeft || rStackItem.item.right == null) && this.stackCount > 1){
			this.stackCount --;
			rStackItem = this.stack[this.stackCount - 1];
		}
		
		if(rStackItem.item.right != null && rStackItem.navLeft){
				//
				// We can walk down a right branch and we are not currently on the right
				//	branch so take it
				//
			rStackItem.navLeft = false;
			this.item = rStackItem.item.right;
		} else {
				//
				// There are no more branches to take
				//
			this.item = null;
		}
	} else {
			//
			// We are at the root and there is no right or left branches to take
			//
		this.item = null;
	}
		//
		// Return the current item
		//
	return rItem;
}
	// ******************************
	// HashtableItem
	// ******************************
	//
	// This is the private data structure object that implements the binary tree. It is created by the 
	//	put() method
	//
function HashtableItem(sKey,rValue){
	this.left = null;
	this.right = null;
	this.key = sKey;
	this.value = rValue;
}