var TREE_MAP_BLACK = true;
var TREE_MAP_RED = false;

function TreeMap(comparator) {
	this.root = null;
	
	if (!comparator) this.comparator = new Comparator();
	else this.comparator = comparator;
	
	this.put	  		= TreeMap_put;
	this.get	  		= TreeMap_get;
	this.remove			= TreeMap_remove;
	this.getEntries 	= TreeMap_getEntries;
	this.getValues 		= TreeMap_getValues;
	this.getKeys		= TreeMap_getKeys;
	this.getEntry		= TreeMap_getEntry;
	
	this.rotateLeft 	= TreeMap_rotateLeft;
	this.rotateRight 	= TreeMap_rotateRight;
	this.firstEntry		= TreeMap_firstEntry;
	this.lastEntry      = TreeMap_lastEntry;
	this.successor		= TreeMap_successor;
	this.predecessor	= TreeMap_predecessor;
	
	this.swapPosition   = TreeMap_swapPosition;
	this.fixAfterInsertion = TreeMap_fixAfterInsertion;
	this.fixAfterDeletion = TreeMap_fixAfterDeletion;
	
	this.size = 0;
	this.incrementSize  = TreeMap_incrementSize;
	this.decrementSize  = TreeMap_decrementSize;
	
}


function TreeMap_put(key, value) {
	var t = this.root;
	
	if (t == null) {
		this.incrementSize();
		this.root = new TreeMapEntry(key, value, null);
		return true;
	}
	
	while (true) {
		if (this.comparator.compare(key,t.key) > 0) {
			if (t.right != null) {
				t = t.right;
			} else {
			    this.incrementSize();
				t.right = new TreeMapEntry(key, value, t);
				this.fixAfterInsertion(t.right);
				return true;
			}		
		} else if (this.comparator.compare(key,t.key) < 0) { 
			if (t.left != null) {
				t = t.left;
			} else {
			    this.incrementSize();
				t.left = new TreeMapEntry(key, value, t);
				this.fixAfterInsertion(t.left);
				return true;
			}			
		} else {
			t.value = value;
			return true;
		
		}
	}	
}

function TreeMap_get(key) {
	t = this.root;
	while (t != null) {
		if (this.comparator.compare(key,t.key) == 0)
			return t.value;
		else if (this.comparator.compare(key,t.key) < 0)
			t = t.left;
		else
			t = t.right;
	}
	return null;
}

function TreeMap_getEntry(key) {
	var p = this.root;
	while (p != null) {
		if (this.comparator.compare(key,p.key) == 0) {
			return p;
		} else if (this.comparator.compare(key,p.key) < 0)
			p = p.left;
		else
			p = p.right;
	}
	return null;
}
	
function TreeMap_remove(key) {
	if (this.root == null) return false;
	var p = this.getEntry(key);

    this.decrementSize();

	// If strictly internal, first swap position with successor.
	if (p.left != null && p.right != null) {
	    var s = this.successor(p);
	    this.swapPosition(s, p);
	} 

	// Start fixup at replacement node, if it exists.
	var replacement = (p.left != null ? p.left : p.right);

	if (replacement != null) {
	    // Link replacement to parent 
	    replacement.parent = p.parent;
	    if (p.parent == null)       
			this.root = replacement; 
	    else if (p == p.parent.left)  
			p.parent.left  = replacement;
	    else
			p.parent.right = replacement;

	    // Null out links so they are OK to use by fixAfterDeletion.
	    p.left = p.right = p.parent = null;
      
	    // Fix replacement
	    if (p.color == TREE_MAP_BLACK) 
			this.fixAfterDeletion(replacement);
	} else if (p.parent == null) { // return if we are the only node.
	    this.root = null;
	} else { //  No children. Use self as phantom replacement and unlink.
	    if (p.color == TREE_MAP_BLACK) 
			this.fixAfterDeletion(p);

	    if (p.parent != null) {
			if (p == p.parent.left) 
			    p.parent.left = null;
			else if (p == p.parent.right) 
			    p.parent.right = null;
			p.parent = null;
	    }
	}
}

function TreeMap_getEntries() {
	var entries = new Array(0);
	var t = this.firstEntry();
	var i = 0;
	
	while (t != null) {
		entries[i] = t;
		i++;
		t = this.successor(t);
	}
	return entries;
	
}

function TreeMap_getValues() {
	var values = new Array(0);
	var t = this.firstEntry();
	var i = 0;
	
	while (t != null) {
		values[i] = t.value;
		i++;
		t = this.successor(t);
	}
	return values;
	
}

function TreeMap_getKeys() {
	var keys = new Array(0);
	var t = this.firstEntry();
	var i = 0;
	
	while (t != null) {
		keys[i] = t.key;
		i++;
		t = this.successor(t);
	}
	return keys;
	
}

function TreeMap_rotateLeft(entry) {
	var r = entry.right;
	entry.right = r.left;
	if (r.left != null)
	    r.left.parent = entry;
	r.parent = entry.parent;
	if (entry.parent == null)
	    this.root = r;
	else if (entry.parent.left == entry)
	    entry.parent.left = r;
	else
	    entry.parent.right = r;
	r.left = entry;
	entry.parent = r;
}


function TreeMap_rotateRight(entry) {
	var l = entry.left;
	entry.left = l.right;
	if (l.right != null) 
		l.right.parent = entry;
	l.parent = entry.parent;
	if (entry.parent == null)
	    this.root = l;
	else if (entry.parent.right == entry)
	    entry.parent.right = l;
	else 
		entry.parent.left = l;
	l.right = entry;
	entry.parent = l;
}

/**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
function TreeMap_firstEntry() {
	var p = this.root;
	if (p != null)
	    while (p.left != null)
		p = p.left;
	return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
function TreeMap_lastEntry() {
	var p = this.root;
	if (p != null)
	    while (p.right != null)
		p = p.right;
	return p;
}

/**
 * Returns the successor of the specified Entry, or null if no such.
 */
function TreeMap_successor(entry) {
	if (entry == null)
	    return null;
	else if (entry.right != null) {
	    var p = entry.right;
	    while (p.left != null)
			p = p.left;
	    return p;
	} else {
	    var p = entry.parent;
	    var ch = entry;
	    while (p != null && ch == p.right) {
			ch = p;
			p = p.parent;
	    }
	    return p;
	}
}

/**
 * Returns the predecessor of the specified Entry, or null if no such.
 */
function TreeMap_predecessor(entry) {
	if (entry == null)
	    return null;
	else if (entry.left != null) {
	    var p = entry.left;
	    while (p.right != null)
			p = p.right;
	    return p;
	} else {
	    var p = entry.parent;
	    var ch = entry;
	    while (p != null && ch == p.left) {
			ch = p;
			p = p.parent;
	    }
	    return p;
	}
}

function TreeMap_incrementSize () {this.size++;}
function TreeMap_decrementSize () {this.size--;}


function TreeMap_fixAfterInsertion(entry) {
	var x = entry;
	var y = null;
	x.color = TREE_MAP_RED;

	while (x != null && x != this.root && x.parent.color == TREE_MAP_RED) {
		if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
			y = rightOf(parentOf(parentOf(x)));
			if (colorOf(y) == TREE_MAP_RED) {
				setColor(parentOf(x), TREE_MAP_BLACK);
				setColor(y, TREE_MAP_BLACK);
				setColor(parentOf(parentOf(x)), TREE_MAP_RED);
				x = parentOf(parentOf(x));
			} else {
				if (x == rightOf(parentOf(x))) {
					x = parentOf(x);
					this.rotateLeft(x);
				}
				setColor(parentOf(x), TREE_MAP_BLACK);
				setColor(parentOf(parentOf(x)), TREE_MAP_RED);
				if (parentOf(parentOf(x)) != null) 
					this.rotateRight(parentOf(parentOf(x)));
			}
		} else {
			y = leftOf(parentOf(parentOf(x)));
			if (colorOf(y) == TREE_MAP_RED) {
				setColor(parentOf(x), TREE_MAP_BLACK);
				setColor(y, TREE_MAP_BLACK);
				setColor(parentOf(parentOf(x)), TREE_MAP_RED);
				x = parentOf(parentOf(x));
			} else {
				if (x == leftOf(parentOf(x))) {
					x = parentOf(x);
					this.rotateRight(x);
				}
				setColor(parentOf(x),  TREE_MAP_BLACK);
				setColor(parentOf(parentOf(x)), TREE_MAP_RED);
				if (parentOf(parentOf(x)) != null) 
					this.rotateLeft(parentOf(parentOf(x)));
			}
		}
		
		this.root.color = TREE_MAP_BLACK;
	}
}


function TreeMap_fixAfterDeletion(entry) {
	var x = entry;
	var sib = null;
	
	while (x != this.root && colorOf(x) == TREE_MAP_BLACK) {
		if (x == leftOf(parentOf(x))) {
			sib = rightOf(parentOf(x));
	
			if (colorOf(sib) == TREE_MAP_RED) {
				setColor(sib, TREE_MAP_BLACK);
				setColor(parentOf(x), TREE_MAP_RED);
				this.rotateLeft(parentOf(x));
				sib = rightOf(parentOf(x));
			}
	
			if (colorOf(leftOf(sib))  == TREE_MAP_BLACK && 
				colorOf(rightOf(sib)) == TREE_MAP_BLACK) {
				setColor(sib,  TREE_MAP_RED);
				x = parentOf(x);
			} else {
				if (colorOf(rightOf(sib)) == TREE_MAP_BLACK) {
					setColor(leftOf(sib), TREE_MAP_BLACK);
					setColor(sib, TREE_MAP_RED);
					this.rotateRight(sib);
					sib = rightOf(parentOf(x));
				}
				setColor(sib, colorOf(parentOf(x)));
				setColor(parentOf(x), TREE_MAP_BLACK);
				setColor(rightOf(sib), TREE_MAP_BLACK);
				this.rotateLeft(parentOf(x));
				x = this.root;
			}
		} else { // symmetric
			sib = leftOf(parentOf(x));
	
			if (colorOf(sib) == TREE_MAP_RED) {
				setColor(sib, TREE_MAP_BLACK);
				setColor(parentOf(x), TREE_MAP_RED);
				this.rotateRight(parentOf(x));
				sib = leftOf(parentOf(x));
			}
	
			if (colorOf(rightOf(sib)) == TREE_MAP_BLACK && 
				colorOf(leftOf(sib)) == TREE_MAP_BLACK) {
				setColor(sib,  TREE_MAP_RED);
				x = parentOf(x);
			} else {
				if (colorOf(leftOf(sib)) == TREE_MAP_BLACK) {
					setColor(rightOf(sib), TREE_MAP_BLACK);
					setColor(sib, TREE_MAP_RED);
					this.rotateLeft(sib);
					sib = leftOf(parentOf(x));
				}
				setColor(sib, colorOf(parentOf(x)));
				setColor(parentOf(x), TREE_MAP_BLACK);
				setColor(leftOf(sib), TREE_MAP_BLACK);
				this.rotateRight(parentOf(x));
				x = this.root;
			}
		}
	}

	setColor(x, TREE_MAP_BLACK); 
}


   /**
    * Swap the linkages of two nodes in a tree.
    */
function TreeMap_swapPosition(x, y) {
	// Save initial values.
	var px = x.parent;
	var lx = x.left;
	var rx = x.right;
	
	var py = y.parent;
	var ly = y.left;
	var ry = y.right;
	
	var xWasLeftChild = px != null && x == px.left;
	var yWasLeftChild = py != null && y == py.left;
	
	// Swap, handling special cases of one being the other's parent.
	if (x == py) {  // x was y's parent
	    x.parent = y;
	    if (yWasLeftChild) { 
			y.left = x; 
			y.right = rx; 
		} else {
			y.right = x;
			y.left = lx;  
		}
	} else {
		x.parent = py; 
		if (py != null) {
			if (yWasLeftChild)
		    	py.left = x;
			else
		    	py.right = x;
		}
		y.left = lx;   
		y.right = rx;
	}
	
	if (y == px) { // y was x's parent
		y.parent = x;
		if (xWasLeftChild) { 
			x.left = y; 
			x.right = ry; 
		} else {
			x.right = y;
			x.left = ly;  
		}
	} else {
	    y.parent = px; 
	    if (px != null) {
			if (xWasLeftChild)
				px.left = y;
			else
				px.right = y;
	    }
		x.left = ly;   
		x.right = ry;  
	}
	
	// Fix children's parent pointers
	if (x.left != null)
		x.left.parent = x;
	if (x.right != null)
		x.right.parent = x;
	if (y.left != null)
		y.left.parent = y;
	if (y.right != null)
		y.right.parent = y;
	
	// Swap colors
	var c = x.color;
	x.color = y.color;
	y.color = c;
	
	// Check if root changed
	if (this.root == x)
		this.root = y;
	else if (this.root == y)
		this.root = x;
}



function TreeMapEntry(key, value, parent) {
	this.left = null;
	this.right = null;
	this.color = TREE_MAP_BLACK;
	this.parent = parent;
	this.value = value;
	this.key = key;
}








function colorOf(entry) {
	return (entry == null ? TREE_MAP_BLACK : entry.color);
}

function parentOf(entry) { 
	return (entry == null ? null: entry.parent);
}

function  setColor(entry, color) { 
	if (entry != null)  entry.color = color; 
}

function leftOf(entry) { 
	return (entry == null)? null: entry.left; 
}

function rightOf(entry) { 
	return (entry == null)? null: entry.right; 
}