uimaj-2.3.0-incubating/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/RBTNode.java - uima-uimaj - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 package org.apache.uima.internal.util.rb_trees;

 import org.apache.uima.internal.util.BinaryTree;

 /**
  * Red-Black Tree node. Not for public use. Use the interface in RedBlackTree instead. This should
  * probably be an internal class to RedBlackTree, but it's easier to read in a seperate file. See
  * comments in RedBlackTree.
  *
  */
 class RBTNode<T> {

   // The colors.
   private static final boolean RED = true;

   private static final boolean BLACK = false;

   private int key; // The key of the node.

   private boolean color; // The color of the node.

   // A pointer to the parent node. This will be null if this is the
   // root of a tree.
   private RBTNode<T> parent;

   // The following variables are package private so they can be
   // accessed from RedBlackTree.

   RBTNode<T> left; // The left daughter.

   RBTNode<T> right; // The right daughter.

   T element; // The element contained in the node.

   // For the debugging print functions.
   private static final int indentInc = 2;

   /**
    * The real constructor, used only internally.
    */
   private RBTNode(int key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right,
           T element) {
     this.key = key;
     this.color = color;
     this.parent = parent;
     this.left = left;
     this.right = right;
     this.element = element;
   }

   /**
    * The standard constructor as used by RedBlackTree.
    *
    * @param key
    *          The key to be inserted.
    * @param element
    *          The value to be inserted.
    */
   RBTNode(int key, T element) {
     // The default color is completely arbitrary.
     this(key, BLACK, null, null, null, element);
   }

   /**
    * Find a node with a certain key. Returns null if no such node exists.
    */
   static final <T> RBTNode<T> find(RBTNode<T> x, int key) {
     while (x != null && x.key != key) {
       if (key < x.key) {
         x = x.left;
       } else {
         x = x.right;
       }
     }
     return x;
   }

   /**
    * Find the successor node to this.
    */
   final RBTNode<T> successor() {
     RBTNode<T> x = this;
     // If this has a right daughter, then the successor will be the
     // leftmost daughter of this.right, if it exists, and x.right,
     // else.
     if (x.right != null) {
       x = x.right;
       while (x.left != null) {
         x = x.left;
       }
       return x;
     }
     // If this does not have a right daughter, we need to move up in
     // the tree until we hit a node we're the left daughter of. That
     // will be the successor.
     RBTNode<T> y = x.parent;
     while (y != null && x == y.right) {
       x = y;
       y = x.parent;
     }
     return y;
   }

   /**
    * Insert a node into a tree. See CLR.
    */
   static final <T> boolean insert(RedBlackTree<T> tree, RBTNode<T> x) {
     if (!treeInsert(tree, x)) {
       // A node with the same key as x already existed in the tree, so
       // there is nothing left to do.
       return false;
     }
     RBTNode<T> y;
     x.color = RED;
     while (x != tree.root && x.parent.color == RED) {
       if (x.parent == x.parent.parent.left) {
         y = x.parent.parent.right;
         if (colorOf(y) == RED) {
           x.parent.color = BLACK;
           setColor(y, BLACK);
           x.parent.parent.color = RED;
           x = x.parent.parent;
         } else {
           if (x == x.parent.right) {
             x = x.parent;
             x.leftRotate(tree);
           }
           x.parent.color = BLACK;
           x.parent.parent.color = RED;
           x.parent.parent.rightRotate(tree);
         }
       } else {
         y = x.parent.parent.left;
         if (colorOf(y) == RED) {
           x.parent.color = BLACK;
           setColor(y, BLACK);
           x.parent.parent.color = RED;
           x = x.parent.parent;
         } else {
           if (x == x.parent.left) {
             x = x.parent;
             x.rightRotate(tree);
           }
           x.parent.color = BLACK;
           x.parent.parent.color = RED;
           x.parent.parent.leftRotate(tree);
         }
       }
     }
     tree.root.color = BLACK;
     return true;
   }

   /** Auxiliary function for insert(). See CLR. */
   private static final <T> boolean treeInsert(RedBlackTree<T> tree, RBTNode<T> z) {
     RBTNode<T> y = null;
     RBTNode<T> x = tree.root;
     while (x != null) {
       y = x;
       if (z.key < x.key) {
         x = x.left;
       } else if (z.key > x.key) {
         x = x.right;
       } else { // z.key == x.key
         x.element = z.element;
         // No node was actually inserted.
         return false;
       }
     }
     z.parent = y;
     if (y == null) {
       tree.root = z;
     } else if (z.key < y.key) {
       y.left = z;
     } else {
       y.right = z;
     }
     return true;
   }

   /** Left rotation, used to keep the tree balanced. See CLR. */
   private final void leftRotate(RedBlackTree<T> tree) {
     RBTNode<T> y = this.right;
     this.right = y.left;
     if (y.left != null) {
       y.left.parent = this;
     }
     y.parent = this.parent;
     if (this.parent == null) {
       tree.root = y;
     } else if (this == this.parent.left) {
       this.parent.left = y;
     } else {
       this.parent.right = y;
     }
     y.left = this;
     this.parent = y;
     return;
   }

   /** Right rotation, used to keep the tree balanced. See CLR. */
   private final void rightRotate(RedBlackTree<T> tree) {
     RBTNode<T> y = this.left;
     this.left = y.right;
     if (y.right != null) {
       y.right.parent = this;
     }
     y.parent = this.parent;
     if (this.parent == null) {
       tree.root = y;
     } else if (this == this.parent.right) {
       this.parent.right = y;
     } else {
       this.parent.left = y;
     }
     y.right = this;
     this.parent = y;
     return;
   }

   /**
    * Delete a given node from the tree. The node must be contained in the tree! Our code is more
    * complicated than CLR because we don't use a NIL sentinel.
    */
   static final <T> void delete(RedBlackTree<T> tree, RBTNode<T> z) {
     RBTNode<T> x;
     RBTNode<T> y;
     RBTNode<T> xParent = null;

     if (z.left == null || z.right == null) {
       y = z;
     } else {
       y = z.successor();
     }
     if (y.left != null) {
       x = y.left;
     } else {
       x = y.right;
     }
     if (x != null) {
       x.parent = y.parent;
     } else {
       xParent = y.parent;
     }
     if (y.parent == null) {
       tree.root = x;
     } else {
       if (y == y.parent.left) {
         y.parent.left = x;
       } else {
         y.parent.right = x;
       }
     }
     if (y != z) {
       z.key = y.key;
       z.element = y.element;
     }
     if (y.color == BLACK) {
       if (x == null) {
         deleteFixupNull(tree, xParent);
       } else {
         deleteFixup(tree, x);
       }
     }
   }

   /**
    * From CLR. x must not be null.
    */
   private static final <T> void deleteFixup(RedBlackTree<T> tree, RBTNode<T> x) {
     RBTNode<T> w;
     while (x != tree.root && x.color == BLACK) {
       if (x == x.parent.left) {
         w = x.parent.right;
         if (w.color == RED) {
           w.color = BLACK;
           x.parent.color = RED;
           x.parent.leftRotate(tree);
           w = x.parent.right;
         }
         if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
           w.color = RED;
           x = x.parent;
         } else {
           if (colorOf(rightOf(w)) == BLACK) {
             w.color = RED;
             w.rightRotate(tree);
             w = x.parent.right;
           }
           w.color = x.parent.color;
           x.parent.color = BLACK;
           if (w.right != null) {
             w.right.color = BLACK;
           }
           x.parent.leftRotate(tree);
           x = tree.root;
         }
       } else {
         w = x.parent.left;
         if (w.color == RED) {
           w.color = BLACK;
           x.parent.color = RED;
           x.parent.rightRotate(tree);
           w = x.parent.left;
         }
         if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
           w.color = RED;
           x = x.parent;
         } else {
           if (colorOf(leftOf(w)) == BLACK) {
             w.color = RED;
             w.leftRotate(tree);
             w = x.parent.left;
           }
           w.color = x.parent.color;
           x.parent.color = BLACK;
           if (w.left != null) {
             w.left.color = BLACK;
           }
           x.parent.rightRotate(tree);
           x = tree.root;
         }
       }
     }
     x.color = BLACK;
   }

   /**
    * Like deleteFixup(), only that the node we should be working on is null, and we actually hand in
    * the node's mother. Special case because we don't use sentinels.
    */
   private static final <T> void deleteFixupNull(RedBlackTree<T> tree, RBTNode<T> x) {
     // if x == null, we just deleted the only node in the tree
     if (x == null) {
       return;
     }

     RBTNode<T> w;

     if (x.left == null) {
       w = x.right;
       if (w.color == RED) {
         w.color = BLACK;
         x.color = RED;
         x.leftRotate(tree);
         w = x.right;
       }
       if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
         w.color = RED;
       } else {
         if (colorOf(rightOf(w)) == BLACK) {
           w.color = RED;
           w.rightRotate(tree);
           w = x.right;
         }
         w.color = x.color;
         x.color = BLACK;
         if (w.right != null) {
           w.right.color = BLACK;
         }
         x.leftRotate(tree);
         x = tree.root;
       }
     } else {
       w = x.left;
       if (w.color == RED) {
         w.color = BLACK;
         x.color = RED;
         x.rightRotate(tree);
         w = x.left;
       }
       if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
         w.color = RED;
       } else {
         if (colorOf(leftOf(w)) == BLACK) {
           w.color = RED;
           w.leftRotate(tree);
           w = x.left;
         }
         w.color = x.color;
         x.color = BLACK;
         if (w.left != null) {
           w.left.color = BLACK;
         }
         x.rightRotate(tree);
         x = tree.root;
       }
     }
     while (x != tree.root && x.color == BLACK) {
       if (x == x.parent.left) {
         w = x.parent.right;
         if (w.color == RED) {
           w.color = BLACK;
           x.parent.color = RED;
           x.parent.leftRotate(tree);
           w = x.parent.right;
         }
         if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
           w.color = RED;
           x = x.parent;
         } else {
           if (colorOf(rightOf(w)) == BLACK) {
             w.color = RED;
             w.rightRotate(tree);
             w = x.parent.right;
           }
           w.color = x.parent.color;
           x.parent.color = BLACK;
           if (w.right != null) {
             w.right.color = BLACK;
           }
           x.parent.leftRotate(tree);
           x = tree.root;
         }
       } else {
         w = x.parent.left;
         if (w.color == RED) {
           w.color = BLACK;
           x.parent.color = RED;
           x.parent.rightRotate(tree);
           w = x.parent.left;
         }
         if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
           w.color = RED;
           x = x.parent;
         } else {
           if (colorOf(leftOf(w)) == BLACK) {
             w.color = RED;
             w.leftRotate(tree);
             w = x.parent.left;
           }
           w.color = x.parent.color;
           x.parent.color = BLACK;
           if (w.left != null) {
             w.left.color = BLACK;
           }
           x.parent.rightRotate(tree);
           x = tree.root;
         }
       }
     }
     x.color = BLACK;
   }

   /**
    * Fill an array with the keys contained in the tree. The array must at least have the size of the
    * tree! Returns the size of the tree, for internal reasons.
    */
   int keys(int pos, int[] keys) {
     int cur = pos;
     if (this.left != null) {
       cur = this.left.keys(cur, keys);
     }
     keys[cur] = this.key;
     ++cur;
     if (this.right != null) {
       cur = this.right.keys(cur, keys);
     }
     return cur;
   }

   // Use as accessor when node might be null.
   private static final <T> boolean colorOf(RBTNode<T> x) {
     return (x == null) ? BLACK : x.color;
   }

   // Below some accessor functions to be used when the node might be
   // null.

   // Use when node might be null.
   private static final <T> void setColor(RBTNode<T> x, boolean c) {
     if (x != null) {
       x.color = c;
     }
   }

   // Use when node might be null.
   private static final <T> RBTNode<T> leftOf(RBTNode<T> x) {
     return (x == null) ? null : x.left;
   }

   // Use when node might be null.
   private static final <T> RBTNode<T> rightOf(RBTNode<T> x) {
     return (x == null) ? null : x.right;
   }

   // Debugging aid.
   public void printKeys(int indent) {
     for (int i = 0; i < indent; i++) {
       System.out.print(' ');
     }
     System.out.print(this.key);
     System.out.print(":");
     if (this.color == RED) {
       System.out.println("red");
     } else {
       System.out.println("black");
     }
     indent += indentInc;
     if (this.left != null) {
       this.left.printKeys(indent);
     }
     if (this.right != null) {
       this.right.printKeys(indent);
     }
     return;
   }

   // Debugging aid.
   public void printElements(int indent) {
     for (int i = 0; i < indent; i++) {
       System.out.print(' ');
     }
     System.out.println(this.element.toString());
     indent += indentInc;
     if (this.left != null) {
       this.left.printElements(indent);
     }
     if (this.right != null) {
       this.right.printElements(indent);
     }
     return;
   }

   void getBinaryTree(BinaryTree tree) {
     tree.setValue(new RBTKeyValuePair(this.key, this.element));
     if (this.left != null) {
       BinaryTree newLeft = tree.newLeftDtr();
       this.left.getBinaryTree(newLeft);
     }
     if (this.right != null) {
       BinaryTree newRight = tree.newRightDtr();
       this.right.getBinaryTree(newRight);
     }
   }

   // public class PreorderIterator implements Iterator {

   // private RBTNode current;

   // private PreorderIterator() {
   // this.current = null;
   // }

   // PreorderIterator(RBTNode node) {
   // this.current = node;
   // }

   // public boolean hasNext() {
   // return (this.current == null);
   // }

   // public Object next() {
   // if (this.current == null) {
   // throw new java.util.NoSuchElementException();
   // }
   // RBTNode node = this.current;
   // // Return this at the end.
   // final RBTKeyValuePair rv = new RBTKeyValuePair(node.key, node.element);
   // // Find the next value.
   // if (node.left != null) {
   // // Go down left branch if it exists.
   // node = node.left;
   // } else if (node.right != null) {
   // // Else, go down right branch, if it exists.
   // node = node.right;
   // } else {
   // // Else, back up the tree.
   // while (node.parent != null) {
   // if (node == node.parent.right || node.parent.right == null) {
   // // This is a right dtr or an only child, continue backing
   // // up the tree.
   // node = node.parent;
   // } else {
   // // This is a left dtr and a right dtr exists, so this is
   // // our next candidate.
   // node = node.parent.right;
   // break;
   // }
   // }
   // if (node.parent == null) {
   // this.current = null;
   // } else {
   // this.current = node;
   // }
   // }
   // return rv;
   // }

   // public void remove() {
   // throw new java.lang.UnsupportedOperationException();
   // }
   // }

   // java.util.Iterator preorderIterator() {
   // return new PreorderIterator(this);
   // }

 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	package org.apache.uima.internal.util.rb_trees;

	import org.apache.uima.internal.util.BinaryTree;

	/**
	* Red-Black Tree node. Not for public use. Use the interface in RedBlackTree instead. This should
	* probably be an internal class to RedBlackTree, but it's easier to read in a seperate file. See
	* comments in RedBlackTree.
	*
	*/
	class RBTNode<T> {

	// The colors.
	private static final boolean RED = true;

	private static final boolean BLACK = false;

	private int key; // The key of the node.

	private boolean color; // The color of the node.

	// A pointer to the parent node. This will be null if this is the
	// root of a tree.
	private RBTNode<T> parent;

	// The following variables are package private so they can be
	// accessed from RedBlackTree.

	RBTNode<T> left; // The left daughter.

	RBTNode<T> right; // The right daughter.

	T element; // The element contained in the node.

	// For the debugging print functions.
	private static final int indentInc = 2;

	/**
	* The real constructor, used only internally.
	*/
	private RBTNode(int key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right,
	T element) {
	this.key = key;
	this.color = color;
	this.parent = parent;
	this.left = left;
	this.right = right;
	this.element = element;
	}

	/**
	* The standard constructor as used by RedBlackTree.
	*
	* @param key
	* The key to be inserted.
	* @param element
	* The value to be inserted.
	*/
	RBTNode(int key, T element) {
	// The default color is completely arbitrary.
	this(key, BLACK, null, null, null, element);
	}

	/**
	* Find a node with a certain key. Returns null if no such node exists.
	*/
	static final <T> RBTNode<T> find(RBTNode<T> x, int key) {
	while (x != null && x.key != key) {
	if (key < x.key) {
	x = x.left;
	} else {
	x = x.right;
	}
	}
	return x;
	}

	/**
	* Find the successor node to this.
	*/
	final RBTNode<T> successor() {
	RBTNode<T> x = this;
	// If this has a right daughter, then the successor will be the
	// leftmost daughter of this.right, if it exists, and x.right,
	// else.
	if (x.right != null) {
	x = x.right;
	while (x.left != null) {
	x = x.left;
	}
	return x;
	}
	// If this does not have a right daughter, we need to move up in
	// the tree until we hit a node we're the left daughter of. That
	// will be the successor.
	RBTNode<T> y = x.parent;
	while (y != null && x == y.right) {
	x = y;
	y = x.parent;
	}
	return y;
	}

	/**
	* Insert a node into a tree. See CLR.
	*/
	static final <T> boolean insert(RedBlackTree<T> tree, RBTNode<T> x) {
	if (!treeInsert(tree, x)) {
	// A node with the same key as x already existed in the tree, so
	// there is nothing left to do.
	return false;
	}
	RBTNode<T> y;
	x.color = RED;
	while (x != tree.root && x.parent.color == RED) {
	if (x.parent == x.parent.parent.left) {
	y = x.parent.parent.right;
	if (colorOf(y) == RED) {
	x.parent.color = BLACK;
	setColor(y, BLACK);
	x.parent.parent.color = RED;
	x = x.parent.parent;
	} else {
	if (x == x.parent.right) {
	x = x.parent;
	x.leftRotate(tree);
	}
	x.parent.color = BLACK;
	x.parent.parent.color = RED;
	x.parent.parent.rightRotate(tree);
	}
	} else {
	y = x.parent.parent.left;
	if (colorOf(y) == RED) {
	x.parent.color = BLACK;
	setColor(y, BLACK);
	x.parent.parent.color = RED;
	x = x.parent.parent;
	} else {
	if (x == x.parent.left) {
	x = x.parent;
	x.rightRotate(tree);
	}
	x.parent.color = BLACK;
	x.parent.parent.color = RED;
	x.parent.parent.leftRotate(tree);
	}
	}
	}
	tree.root.color = BLACK;
	return true;
	}

	/** Auxiliary function for insert(). See CLR. */
	private static final <T> boolean treeInsert(RedBlackTree<T> tree, RBTNode<T> z) {
	RBTNode<T> y = null;
	RBTNode<T> x = tree.root;
	while (x != null) {
	y = x;
	if (z.key < x.key) {
	x = x.left;
	} else if (z.key > x.key) {
	x = x.right;
	} else { // z.key == x.key
	x.element = z.element;
	// No node was actually inserted.
	return false;
	}
	}
	z.parent = y;
	if (y == null) {
	tree.root = z;
	} else if (z.key < y.key) {
	y.left = z;
	} else {
	y.right = z;
	}
	return true;
	}

	/** Left rotation, used to keep the tree balanced. See CLR. */
	private final void leftRotate(RedBlackTree<T> tree) {
	RBTNode<T> y = this.right;
	this.right = y.left;
	if (y.left != null) {
	y.left.parent = this;
	}
	y.parent = this.parent;
	if (this.parent == null) {
	tree.root = y;
	} else if (this == this.parent.left) {
	this.parent.left = y;
	} else {
	this.parent.right = y;
	}
	y.left = this;
	this.parent = y;
	return;
	}

	/** Right rotation, used to keep the tree balanced. See CLR. */
	private final void rightRotate(RedBlackTree<T> tree) {
	RBTNode<T> y = this.left;
	this.left = y.right;
	if (y.right != null) {
	y.right.parent = this;
	}
	y.parent = this.parent;
	if (this.parent == null) {
	tree.root = y;
	} else if (this == this.parent.right) {
	this.parent.right = y;
	} else {
	this.parent.left = y;
	}
	y.right = this;
	this.parent = y;
	return;
	}

	/**
	* Delete a given node from the tree. The node must be contained in the tree! Our code is more
	* complicated than CLR because we don't use a NIL sentinel.
	*/
	static final <T> void delete(RedBlackTree<T> tree, RBTNode<T> z) {
	RBTNode<T> x;
	RBTNode<T> y;
	RBTNode<T> xParent = null;

	if (z.left == null \|\| z.right == null) {
	y = z;
	} else {
	y = z.successor();
	}
	if (y.left != null) {
	x = y.left;
	} else {
	x = y.right;
	}
	if (x != null) {
	x.parent = y.parent;
	} else {
	xParent = y.parent;
	}
	if (y.parent == null) {
	tree.root = x;
	} else {
	if (y == y.parent.left) {
	y.parent.left = x;
	} else {
	y.parent.right = x;
	}
	}
	if (y != z) {
	z.key = y.key;
	z.element = y.element;
	}
	if (y.color == BLACK) {
	if (x == null) {
	deleteFixupNull(tree, xParent);
	} else {
	deleteFixup(tree, x);
	}
	}
	}

	/**
	* From CLR. x must not be null.
	*/
	private static final <T> void deleteFixup(RedBlackTree<T> tree, RBTNode<T> x) {
	RBTNode<T> w;
	while (x != tree.root && x.color == BLACK) {
	if (x == x.parent.left) {
	w = x.parent.right;
	if (w.color == RED) {
	w.color = BLACK;
	x.parent.color = RED;
	x.parent.leftRotate(tree);
	w = x.parent.right;
	}
	if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	x = x.parent;
	} else {
	if (colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	w.rightRotate(tree);
	w = x.parent.right;
	}
	w.color = x.parent.color;
	x.parent.color = BLACK;
	if (w.right != null) {
	w.right.color = BLACK;
	}
	x.parent.leftRotate(tree);
	x = tree.root;
	}
	} else {
	w = x.parent.left;
	if (w.color == RED) {
	w.color = BLACK;
	x.parent.color = RED;
	x.parent.rightRotate(tree);
	w = x.parent.left;
	}
	if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	x = x.parent;
	} else {
	if (colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	w.leftRotate(tree);
	w = x.parent.left;
	}
	w.color = x.parent.color;
	x.parent.color = BLACK;
	if (w.left != null) {
	w.left.color = BLACK;
	}
	x.parent.rightRotate(tree);
	x = tree.root;
	}
	}
	}
	x.color = BLACK;
	}

	/**
	* Like deleteFixup(), only that the node we should be working on is null, and we actually hand in
	* the node's mother. Special case because we don't use sentinels.
	*/
	private static final <T> void deleteFixupNull(RedBlackTree<T> tree, RBTNode<T> x) {
	// if x == null, we just deleted the only node in the tree
	if (x == null) {
	return;
	}

	RBTNode<T> w;

	if (x.left == null) {
	w = x.right;
	if (w.color == RED) {
	w.color = BLACK;
	x.color = RED;
	x.leftRotate(tree);
	w = x.right;
	}
	if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	} else {
	if (colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	w.rightRotate(tree);
	w = x.right;
	}
	w.color = x.color;
	x.color = BLACK;
	if (w.right != null) {
	w.right.color = BLACK;
	}
	x.leftRotate(tree);
	x = tree.root;
	}
	} else {
	w = x.left;
	if (w.color == RED) {
	w.color = BLACK;
	x.color = RED;
	x.rightRotate(tree);
	w = x.left;
	}
	if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	} else {
	if (colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	w.leftRotate(tree);
	w = x.left;
	}
	w.color = x.color;
	x.color = BLACK;
	if (w.left != null) {
	w.left.color = BLACK;
	}
	x.rightRotate(tree);
	x = tree.root;
	}
	}
	while (x != tree.root && x.color == BLACK) {
	if (x == x.parent.left) {
	w = x.parent.right;
	if (w.color == RED) {
	w.color = BLACK;
	x.parent.color = RED;
	x.parent.leftRotate(tree);
	w = x.parent.right;
	}
	if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	x = x.parent;
	} else {
	if (colorOf(rightOf(w)) == BLACK) {
	w.color = RED;
	w.rightRotate(tree);
	w = x.parent.right;
	}
	w.color = x.parent.color;
	x.parent.color = BLACK;
	if (w.right != null) {
	w.right.color = BLACK;
	}
	x.parent.leftRotate(tree);
	x = tree.root;
	}
	} else {
	w = x.parent.left;
	if (w.color == RED) {
	w.color = BLACK;
	x.parent.color = RED;
	x.parent.rightRotate(tree);
	w = x.parent.left;
	}
	if (colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	x = x.parent;
	} else {
	if (colorOf(leftOf(w)) == BLACK) {
	w.color = RED;
	w.leftRotate(tree);
	w = x.parent.left;
	}
	w.color = x.parent.color;
	x.parent.color = BLACK;
	if (w.left != null) {
	w.left.color = BLACK;
	}
	x.parent.rightRotate(tree);
	x = tree.root;
	}
	}
	}
	x.color = BLACK;
	}

	/**
	* Fill an array with the keys contained in the tree. The array must at least have the size of the
	* tree! Returns the size of the tree, for internal reasons.
	*/
	int keys(int pos, int[] keys) {
	int cur = pos;
	if (this.left != null) {
	cur = this.left.keys(cur, keys);
	}
	keys[cur] = this.key;
	++cur;
	if (this.right != null) {
	cur = this.right.keys(cur, keys);
	}
	return cur;
	}

	// Use as accessor when node might be null.
	private static final <T> boolean colorOf(RBTNode<T> x) {
	return (x == null) ? BLACK : x.color;
	}

	// Below some accessor functions to be used when the node might be
	// null.

	// Use when node might be null.
	private static final <T> void setColor(RBTNode<T> x, boolean c) {
	if (x != null) {
	x.color = c;
	}
	}

	// Use when node might be null.
	private static final <T> RBTNode<T> leftOf(RBTNode<T> x) {
	return (x == null) ? null : x.left;
	}

	// Use when node might be null.
	private static final <T> RBTNode<T> rightOf(RBTNode<T> x) {
	return (x == null) ? null : x.right;
	}

	// Debugging aid.
	public void printKeys(int indent) {
	for (int i = 0; i < indent; i++) {
	System.out.print(' ');
	}
	System.out.print(this.key);
	System.out.print(":");
	if (this.color == RED) {
	System.out.println("red");
	} else {
	System.out.println("black");
	}
	indent += indentInc;
	if (this.left != null) {
	this.left.printKeys(indent);
	}
	if (this.right != null) {
	this.right.printKeys(indent);
	}
	return;
	}

	// Debugging aid.
	public void printElements(int indent) {
	for (int i = 0; i < indent; i++) {
	System.out.print(' ');
	}
	System.out.println(this.element.toString());
	indent += indentInc;
	if (this.left != null) {
	this.left.printElements(indent);
	}
	if (this.right != null) {
	this.right.printElements(indent);
	}
	return;
	}

	void getBinaryTree(BinaryTree tree) {
	tree.setValue(new RBTKeyValuePair(this.key, this.element));
	if (this.left != null) {
	BinaryTree newLeft = tree.newLeftDtr();
	this.left.getBinaryTree(newLeft);
	}
	if (this.right != null) {
	BinaryTree newRight = tree.newRightDtr();
	this.right.getBinaryTree(newRight);
	}
	}

	// public class PreorderIterator implements Iterator {

	// private RBTNode current;

	// private PreorderIterator() {
	// this.current = null;
	// }

	// PreorderIterator(RBTNode node) {
	// this.current = node;
	// }

	// public boolean hasNext() {
	// return (this.current == null);
	// }

	// public Object next() {
	// if (this.current == null) {
	// throw new java.util.NoSuchElementException();
	// }
	// RBTNode node = this.current;
	// // Return this at the end.
	// final RBTKeyValuePair rv = new RBTKeyValuePair(node.key, node.element);
	// // Find the next value.
	// if (node.left != null) {
	// // Go down left branch if it exists.
	// node = node.left;
	// } else if (node.right != null) {
	// // Else, go down right branch, if it exists.
	// node = node.right;
	// } else {
	// // Else, back up the tree.
	// while (node.parent != null) {
	// if (node == node.parent.right \|\| node.parent.right == null) {
	// // This is a right dtr or an only child, continue backing
	// // up the tree.
	// node = node.parent;
	// } else {
	// // This is a left dtr and a right dtr exists, so this is
	// // our next candidate.
	// node = node.parent.right;
	// break;
	// }
	// }
	// if (node.parent == null) {
	// this.current = null;
	// } else {
	// this.current = node;
	// }
	// }
	// return rv;
	// }

	// public void remove() {
	// throw new java.lang.UnsupportedOperationException();
	// }
	// }

	// java.util.Iterator preorderIterator() {
	// return new PreorderIterator(this);
	// }

	}