platform/core-impl/src/com/intellij/openapi/editor/impl/RedBlackTree.java - platform/tools/idea - Git at Google

 /*
  * Copyright 2000-2010 JetBrains s.r.o.
  *
  * Licensed 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 com.intellij.openapi.editor.impl;

 import com.intellij.util.Processor;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;


 /**
  * User: cdr
  */
 public abstract class RedBlackTree<K> {
   public static boolean VERIFY = false;
   private static final int INDENT_STEP = 4;
   private int nodeSize; // number of nodes
   protected int modCount;
   protected Node<K> root;

   public RedBlackTree() {
     root = null;
     verifyProperties();
   }

   protected void rotateLeft(Node<K> n) {
     Node<K> r = n.getRight();
     replaceNode(n, r);
     n.setRight(r.getLeft());
     if (r.getLeft() != null) {
       r.getLeft().setParent(n);
     }
     r.setLeft(n);
     n.setParent(r);
   }

   protected void rotateRight(Node<K> n) {
     Node<K> l = n.getLeft();
     replaceNode(n, l);
     n.setLeft(l.getRight());
     if (l.getRight() != null) {
       l.getRight().setParent(n);
     }
     l.setRight(n);
     n.setParent(l);
   }

   protected void replaceNode(@NotNull Node<K> oldn, Node<K> newn) {
     Node<K> parent = oldn.getParent();
     if (parent == null) {
       root = newn;
     }
     else {
       if (oldn == parent.getLeft()) {
         parent.setLeft(newn);
       }
       else {
         parent.setRight(newn);
       }
     }
     if (newn != null) {
       newn.setParent(parent);
     }
     //oldn.parent = null;
     //oldn.left = null;
     //oldn.right = null;
   }

   protected void onInsertNode() {
     nodeSize++;
   }

   protected void insertCase1(Node<K> n) {
     if (n.getParent() == null) {
       n.setBlack();
     }
     else {
       insertCase2(n);
     }
   }

   private void insertCase2(Node<K> n) {
     if (!isBlack(n.getParent())) {
       insertCase3(n);
     }
     // Tree is still valid
   }

   private void insertCase3(Node<K> n) {
     if (!isBlack(n.uncle())) {
       n.getParent().setBlack();
       n.uncle().setBlack();
       n.grandparent().setRed();
       insertCase1(n.grandparent());
     }
     else {
       insertCase4(n);
     }
   }

   private void insertCase4(Node<K> n) {
     if (n == n.getParent().getRight() && n.getParent() == n.grandparent().getLeft()) {
       rotateLeft(n.getParent());
       n = n.getLeft();
     }
     else if (n == n.getParent().getLeft() && n.getParent() == n.grandparent().getRight()) {
       rotateRight(n.getParent());
       n = n.getRight();
     }
     insertCase5(n);
   }

   private void insertCase5(Node<K> n) {
     n.getParent().setBlack();
     n.grandparent().setRed();
     if (n == n.getParent().getLeft() && n.getParent() == n.grandparent().getLeft()) {
       rotateRight(n.grandparent());
     }
     else {
       assert n == n.getParent().getRight();
       assert n.getParent() == n.grandparent().getRight();
       rotateLeft(n.grandparent());
     }
   }

   private static <K> void assertParentChild(Node<K> node1) {
     assert node1 == null || node1.getParent() == null || node1.getParent().getLeft() == node1 || node1.getParent().getRight() == node1;
   }

   protected void deleteNode(@NotNull Node<K> n) {
     modCount++;

     Node<K> e = n;
     while (e.getParent() != null) e = e.getParent();
     assert e == root : e; // assert the node belongs to our tree

     if (n.getLeft() != null && n.getRight() != null) {
       // Copy key/value from predecessor and then delete it instead
       Node<K> pred = maximumNode(n.getLeft());

       //Color c = pred.color;
       //swap(n, pred);
       //assert pred.color == c;
       //pred.color = n.color;
       //n.color = c;

       n = swapWithMaxPred(n, pred);
     }

     assert n.getLeft() == null || n.getRight() == null;
     Node<K> child = n.getRight() == null ? n.getLeft() : n.getRight();
     if (isBlack(n)) {
       n.setColor(isBlack(child));
       deleteCase1(n);
     }
     replaceNode(n, child);

     if (!isBlack(root)) {
       root.setBlack();
     }

     assert nodeSize > 0 : nodeSize;
     nodeSize--;
     verifyProperties();
   }

   protected abstract Node<K> swapWithMaxPred(Node<K> nowAscendant, Node<K> nowDescendant);

   protected Node<K> maximumNode(Node<K> n) {
     assert n != null;
     while (n.getRight() != null) {
       n = n.getRight();
     }
     return n;
   }

   private void deleteCase1(Node<K> n) {
     if (n.getParent() != null) {
       deleteCase2(n);
     }
   }

   private void deleteCase2(Node<K> n) {
     if (!isBlack(n.sibling())) {
       n.getParent().setRed();
       n.sibling().setBlack();
       if (n == n.getParent().getLeft()) {
         rotateLeft(n.getParent());
       }
       else {
         rotateRight(n.getParent());
       }
     }
     deleteCase3(n);
   }

   private void deleteCase3(Node<K> n) {
     if (isBlack(n.getParent()) &&
         isBlack(n.sibling()) &&
         isBlack(n.sibling().getLeft()) &&
         isBlack(n.sibling().getRight())) {
       n.sibling().setRed();
       deleteCase1(n.getParent());
     }
     else {
       deleteCase4(n);
     }
   }

   private void deleteCase4(Node<K> n) {
     if (!isBlack(n.getParent()) &&
         isBlack(n.sibling()) &&
         isBlack(n.sibling().getLeft()) &&
         isBlack(n.sibling().getRight())) {
       n.sibling().setRed();
       n.getParent().setBlack();
     }
     else {
       deleteCase5(n);
     }
   }

   private void deleteCase5(Node<K> n) {
     if (n == n.getParent().getLeft() &&
         isBlack(n.sibling()) &&
         !isBlack(n.sibling().getLeft()) &&
         isBlack(n.sibling().getRight())) {
       n.sibling().setRed();
       n.sibling().getLeft().setBlack();
       rotateRight(n.sibling());
     }
     else if (n == n.getParent().getRight() &&
              isBlack(n.sibling()) &&
              !isBlack(n.sibling().getRight()) &&
              isBlack(n.sibling().getLeft())) {
       n.sibling().setRed();
       n.sibling().getRight().setBlack();
       rotateLeft(n.sibling());
     }
     deleteCase6(n);
   }

   private void deleteCase6(Node<K> n) {
     n.sibling().setColor(isBlack(n.getParent()));
     n.getParent().setBlack();
     if (n == n.getParent().getLeft()) {
       assert !isBlack(n.sibling().getRight());
       n.sibling().getRight().setBlack();
       rotateLeft(n.getParent());
     }
     else {
       assert !isBlack(n.sibling().getLeft());
       n.sibling().getLeft().setBlack();
       rotateRight(n.getParent());
     }
   }

   public void print() {
     printHelper(root, 0);
   }

   private static void printHelper(Node<?> n, int indent) {
     if (n == null) {
       System.err.print("<empty tree>");
       return;
     }
     if (n.getRight() != null) {
       printHelper(n.getRight(), indent + INDENT_STEP);
     }
     for (int i = 0; i < indent; i++) {
       System.err.print(" ");
     }
     if (n.isBlack()) {
       System.err.println(n);
     }
     else {
       System.err.println("<" + n + ">");
     }
     if (n.getLeft() != null) {
       printHelper(n.getLeft(), indent + INDENT_STEP);
     }
   }

   public abstract static class Node<K> {
     protected Node<K> left;
     protected Node<K> right;
     protected Node<K> parent = null;

     private volatile byte myFlags;
     protected static final int COLOR_FLAG = 0;

     protected boolean isFlagSet(int flag) {
       int state = myFlags >> flag;
       return (state & 1) != 0;
     }

     protected void setFlag(int flag, boolean value) {
       assert flag < 8;
       int state = value ? 1 : 0;
       myFlags = (byte)(myFlags & ~(1 << flag) | state << flag);
     }


     public Node<K> grandparent() {
       assert getParent() != null; // Not the root node
       assert getParent().getParent() != null; // Not child of root
       return getParent().getParent();
     }

     public Node<K> sibling() {
       Node<K> parent = getParent();
       assert parent != null; // Root node has no sibling
       return this == parent.getLeft() ? parent.getRight() : parent.getLeft();
     }

     public Node<K> uncle() {
       assert getParent() != null; // Root node has no uncle
       assert getParent().getParent() != null; // Children of root have no uncle
       return getParent().sibling();
     }

     public Node<K> getLeft() {
       return left;
     }

     public void setLeft(Node<K> left) {
       this.left = left;
     }

     public Node<K> getRight() {
       return right;
     }

     public void setRight(Node<K> right) {
       this.right = right;
     }

     public Node<K> getParent() {
       return parent;
     }

     public void setParent(Node<K> parent) {
       this.parent = parent;
     }

     public abstract boolean processAliveKeys(@NotNull Processor<? super K> processor);

     public abstract boolean hasAliveKey(boolean purgeDead);

     public boolean isBlack() {
       return isFlagSet(COLOR_FLAG);
     }
     public void setBlack() {
       setFlag(COLOR_FLAG, true);
     }
     public void setRed() {
       setFlag(COLOR_FLAG, false);
     }
     public void setColor(boolean isBlack) {
       setFlag(COLOR_FLAG, isBlack);
     }
   }

   public int size() {
     return nodeSize;
   }
   public int nodeSize() {
     return nodeSize;
   }

   public void verifyProperties() {
     //if (true) return;
     if (VERIFY) {
       verifyProperty1(root);
       verifyProperty2(root);
       // Property 3 is implicit
       verifyProperty4(root);
       verifyProperty5(root);
     }
   }

   private static void verifyProperty1(Node<?> n) {
     assert !isBlack(n) || isBlack(n);
     if (n == null) return;
     assert n.getParent() != n;
     assert n.getLeft() != n;
     assert n.getRight() != n;
     assertParentChild(n);

     verifyProperty1(n.getLeft());
     verifyProperty1(n.getRight());
   }

   private static void verifyProperty2(Node<?> root) {
     assert isBlack(root);
   }

   private static boolean isBlack(@Nullable Node<?> n) {
     return n == null || n.isBlack();
   }

   private static void verifyProperty4(Node<?> n) {
     if (!isBlack(n)) {
       assert isBlack(n.getLeft());
       assert isBlack(n.getRight());
       assert isBlack(n.getParent());
     }
     if (n == null) return;
     verifyProperty4(n.getLeft());
     verifyProperty4(n.getRight());
   }

   private static void verifyProperty5(Node<?> root) {
     verifyProperty5Helper(root, 0, -1);
   }

   private static int verifyProperty5Helper(Node<?> n, int blackCount, int pathBlackCount) {
     if (isBlack(n)) {
       blackCount++;
     }
     if (n == null) {
       if (pathBlackCount == -1) {
         pathBlackCount = blackCount;
       }
       else {
         assert blackCount == pathBlackCount;
       }
       return pathBlackCount;
     }
     pathBlackCount = verifyProperty5Helper(n.getLeft(), blackCount, pathBlackCount);
     pathBlackCount = verifyProperty5Helper(n.getRight(), blackCount, pathBlackCount);

     return pathBlackCount;
   }

   public void clear() {
     modCount++;
     root = null;
     nodeSize = 0;
   }
 }
	/*
	* Copyright 2000-2010 JetBrains s.r.o.
	*
	* Licensed 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 com.intellij.openapi.editor.impl;

	import com.intellij.util.Processor;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;


	/**
	* User: cdr
	*/
	public abstract class RedBlackTree<K> {
	public static boolean VERIFY = false;
	private static final int INDENT_STEP = 4;
	private int nodeSize; // number of nodes
	protected int modCount;
	protected Node<K> root;

	public RedBlackTree() {
	root = null;
	verifyProperties();
	}

	protected void rotateLeft(Node<K> n) {
	Node<K> r = n.getRight();
	replaceNode(n, r);
	n.setRight(r.getLeft());
	if (r.getLeft() != null) {
	r.getLeft().setParent(n);
	}
	r.setLeft(n);
	n.setParent(r);
	}

	protected void rotateRight(Node<K> n) {
	Node<K> l = n.getLeft();
	replaceNode(n, l);
	n.setLeft(l.getRight());
	if (l.getRight() != null) {
	l.getRight().setParent(n);
	}
	l.setRight(n);
	n.setParent(l);
	}

	protected void replaceNode(@NotNull Node<K> oldn, Node<K> newn) {
	Node<K> parent = oldn.getParent();
	if (parent == null) {
	root = newn;
	}
	else {
	if (oldn == parent.getLeft()) {
	parent.setLeft(newn);
	}
	else {
	parent.setRight(newn);
	}
	}
	if (newn != null) {
	newn.setParent(parent);
	}
	//oldn.parent = null;
	//oldn.left = null;
	//oldn.right = null;
	}

	protected void onInsertNode() {
	nodeSize++;
	}

	protected void insertCase1(Node<K> n) {
	if (n.getParent() == null) {
	n.setBlack();
	}
	else {
	insertCase2(n);
	}
	}

	private void insertCase2(Node<K> n) {
	if (!isBlack(n.getParent())) {
	insertCase3(n);
	}
	// Tree is still valid
	}

	private void insertCase3(Node<K> n) {
	if (!isBlack(n.uncle())) {
	n.getParent().setBlack();
	n.uncle().setBlack();
	n.grandparent().setRed();
	insertCase1(n.grandparent());
	}
	else {
	insertCase4(n);
	}
	}

	private void insertCase4(Node<K> n) {
	if (n == n.getParent().getRight() && n.getParent() == n.grandparent().getLeft()) {
	rotateLeft(n.getParent());
	n = n.getLeft();
	}
	else if (n == n.getParent().getLeft() && n.getParent() == n.grandparent().getRight()) {
	rotateRight(n.getParent());
	n = n.getRight();
	}
	insertCase5(n);
	}

	private void insertCase5(Node<K> n) {
	n.getParent().setBlack();
	n.grandparent().setRed();
	if (n == n.getParent().getLeft() && n.getParent() == n.grandparent().getLeft()) {
	rotateRight(n.grandparent());
	}
	else {
	assert n == n.getParent().getRight();
	assert n.getParent() == n.grandparent().getRight();
	rotateLeft(n.grandparent());
	}
	}

	private static <K> void assertParentChild(Node<K> node1) {
	assert node1 == null \|\| node1.getParent() == null \|\| node1.getParent().getLeft() == node1 \|\| node1.getParent().getRight() == node1;
	}

	protected void deleteNode(@NotNull Node<K> n) {
	modCount++;

	Node<K> e = n;
	while (e.getParent() != null) e = e.getParent();
	assert e == root : e; // assert the node belongs to our tree

	if (n.getLeft() != null && n.getRight() != null) {
	// Copy key/value from predecessor and then delete it instead
	Node<K> pred = maximumNode(n.getLeft());

	//Color c = pred.color;
	//swap(n, pred);
	//assert pred.color == c;
	//pred.color = n.color;
	//n.color = c;

	n = swapWithMaxPred(n, pred);
	}

	assert n.getLeft() == null \|\| n.getRight() == null;
	Node<K> child = n.getRight() == null ? n.getLeft() : n.getRight();
	if (isBlack(n)) {
	n.setColor(isBlack(child));
	deleteCase1(n);
	}
	replaceNode(n, child);

	if (!isBlack(root)) {
	root.setBlack();
	}

	assert nodeSize > 0 : nodeSize;
	nodeSize--;
	verifyProperties();
	}

	protected abstract Node<K> swapWithMaxPred(Node<K> nowAscendant, Node<K> nowDescendant);

	protected Node<K> maximumNode(Node<K> n) {
	assert n != null;
	while (n.getRight() != null) {
	n = n.getRight();
	}
	return n;
	}

	private void deleteCase1(Node<K> n) {
	if (n.getParent() != null) {
	deleteCase2(n);
	}
	}

	private void deleteCase2(Node<K> n) {
	if (!isBlack(n.sibling())) {
	n.getParent().setRed();
	n.sibling().setBlack();
	if (n == n.getParent().getLeft()) {
	rotateLeft(n.getParent());
	}
	else {
	rotateRight(n.getParent());
	}
	}
	deleteCase3(n);
	}

	private void deleteCase3(Node<K> n) {
	if (isBlack(n.getParent()) &&
	isBlack(n.sibling()) &&
	isBlack(n.sibling().getLeft()) &&
	isBlack(n.sibling().getRight())) {
	n.sibling().setRed();
	deleteCase1(n.getParent());
	}
	else {
	deleteCase4(n);
	}
	}

	private void deleteCase4(Node<K> n) {
	if (!isBlack(n.getParent()) &&
	isBlack(n.sibling()) &&
	isBlack(n.sibling().getLeft()) &&
	isBlack(n.sibling().getRight())) {
	n.sibling().setRed();
	n.getParent().setBlack();
	}
	else {
	deleteCase5(n);
	}
	}

	private void deleteCase5(Node<K> n) {
	if (n == n.getParent().getLeft() &&
	isBlack(n.sibling()) &&
	!isBlack(n.sibling().getLeft()) &&
	isBlack(n.sibling().getRight())) {
	n.sibling().setRed();
	n.sibling().getLeft().setBlack();
	rotateRight(n.sibling());
	}
	else if (n == n.getParent().getRight() &&
	isBlack(n.sibling()) &&
	!isBlack(n.sibling().getRight()) &&
	isBlack(n.sibling().getLeft())) {
	n.sibling().setRed();
	n.sibling().getRight().setBlack();
	rotateLeft(n.sibling());
	}
	deleteCase6(n);
	}

	private void deleteCase6(Node<K> n) {
	n.sibling().setColor(isBlack(n.getParent()));
	n.getParent().setBlack();
	if (n == n.getParent().getLeft()) {
	assert !isBlack(n.sibling().getRight());
	n.sibling().getRight().setBlack();
	rotateLeft(n.getParent());
	}
	else {
	assert !isBlack(n.sibling().getLeft());
	n.sibling().getLeft().setBlack();
	rotateRight(n.getParent());
	}
	}

	public void print() {
	printHelper(root, 0);
	}

	private static void printHelper(Node<?> n, int indent) {
	if (n == null) {
	System.err.print("<empty tree>");
	return;
	}
	if (n.getRight() != null) {
	printHelper(n.getRight(), indent + INDENT_STEP);
	}
	for (int i = 0; i < indent; i++) {
	System.err.print(" ");
	}
	if (n.isBlack()) {
	System.err.println(n);
	}
	else {
	System.err.println("<" + n + ">");
	}
	if (n.getLeft() != null) {
	printHelper(n.getLeft(), indent + INDENT_STEP);
	}
	}

	public abstract static class Node<K> {
	protected Node<K> left;
	protected Node<K> right;
	protected Node<K> parent = null;

	private volatile byte myFlags;
	protected static final int COLOR_FLAG = 0;

	protected boolean isFlagSet(int flag) {
	int state = myFlags >> flag;
	return (state & 1) != 0;
	}

	protected void setFlag(int flag, boolean value) {
	assert flag < 8;
	int state = value ? 1 : 0;
	myFlags = (byte)(myFlags & ~(1 << flag) \| state << flag);
	}


	public Node<K> grandparent() {
	assert getParent() != null; // Not the root node
	assert getParent().getParent() != null; // Not child of root
	return getParent().getParent();
	}

	public Node<K> sibling() {
	Node<K> parent = getParent();
	assert parent != null; // Root node has no sibling
	return this == parent.getLeft() ? parent.getRight() : parent.getLeft();
	}

	public Node<K> uncle() {
	assert getParent() != null; // Root node has no uncle
	assert getParent().getParent() != null; // Children of root have no uncle
	return getParent().sibling();
	}

	public Node<K> getLeft() {
	return left;
	}

	public void setLeft(Node<K> left) {
	this.left = left;
	}

	public Node<K> getRight() {
	return right;
	}

	public void setRight(Node<K> right) {
	this.right = right;
	}

	public Node<K> getParent() {
	return parent;
	}

	public void setParent(Node<K> parent) {
	this.parent = parent;
	}

	public abstract boolean processAliveKeys(@NotNull Processor<? super K> processor);

	public abstract boolean hasAliveKey(boolean purgeDead);

	public boolean isBlack() {
	return isFlagSet(COLOR_FLAG);
	}
	public void setBlack() {
	setFlag(COLOR_FLAG, true);
	}
	public void setRed() {
	setFlag(COLOR_FLAG, false);
	}
	public void setColor(boolean isBlack) {
	setFlag(COLOR_FLAG, isBlack);
	}
	}

	public int size() {
	return nodeSize;
	}
	public int nodeSize() {
	return nodeSize;
	}

	public void verifyProperties() {
	//if (true) return;
	if (VERIFY) {
	verifyProperty1(root);
	verifyProperty2(root);
	// Property 3 is implicit
	verifyProperty4(root);
	verifyProperty5(root);
	}
	}

	private static void verifyProperty1(Node<?> n) {
	assert !isBlack(n) \|\| isBlack(n);
	if (n == null) return;
	assert n.getParent() != n;
	assert n.getLeft() != n;
	assert n.getRight() != n;
	assertParentChild(n);

	verifyProperty1(n.getLeft());
	verifyProperty1(n.getRight());
	}

	private static void verifyProperty2(Node<?> root) {
	assert isBlack(root);
	}

	private static boolean isBlack(@Nullable Node<?> n) {
	return n == null \|\| n.isBlack();
	}

	private static void verifyProperty4(Node<?> n) {
	if (!isBlack(n)) {
	assert isBlack(n.getLeft());
	assert isBlack(n.getRight());
	assert isBlack(n.getParent());
	}
	if (n == null) return;
	verifyProperty4(n.getLeft());
	verifyProperty4(n.getRight());
	}

	private static void verifyProperty5(Node<?> root) {
	verifyProperty5Helper(root, 0, -1);
	}

	private static int verifyProperty5Helper(Node<?> n, int blackCount, int pathBlackCount) {
	if (isBlack(n)) {
	blackCount++;
	}
	if (n == null) {
	if (pathBlackCount == -1) {
	pathBlackCount = blackCount;
	}
	else {
	assert blackCount == pathBlackCount;
	}
	return pathBlackCount;
	}
	pathBlackCount = verifyProperty5Helper(n.getLeft(), blackCount, pathBlackCount);
	pathBlackCount = verifyProperty5Helper(n.getRight(), blackCount, pathBlackCount);

	return pathBlackCount;
	}

	public void clear() {
	modCount++;
	root = null;
	nodeSize = 0;
	}
	}