[Joafip-svn] SF.net SVN: joafip:[2942] trunk/joafip-rbtree/src/main/java/net/sf/joafip/ redblacktree/service/RedBlackTree.java

[<luc...@us...>]

Revision: 2942
          http://joafip.svn.sourceforge.net/joafip/?rev=2942&view=rev
Author:   luc_peuvrier
Date:     2011-10-28 03:13:13 +0000 (Fri, 28 Oct 2011)
Log Message:
-----------
to break infinite loop in case of problems

Modified Paths:
--------------
    trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java

Modified: trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java
===================================================================
--- trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java	2011-10-27 01:46:02 UTC (rev 2941)
+++ trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java	2011-10-28 03:13:13 UTC (rev 2942)
@@ -46,11 +46,15 @@
 		// complexity
 		Iterable<IRBTNode<E>>, Serializable {
 
+	private static final String MAX_DEPTH_REACHED = "max depth reached";
+
 	/**
 	 * 
 	 */
 	private static final long serialVersionUID = -3573347853060581283L;
 
+	private static final int MAX_DEPTH = 64;
+
 	private static final String INDEX_OUT_OF_BOUND = "index out of bound";
 
 	public static final boolean BLACK = true;
@@ -177,6 +181,7 @@
 		IRBTNode<E> current = rootNode = nodeManager.getRootNode();
 		IRBTNode<E> found = null;
 		if (current != null) {
+			int depth = 0;
 			while (!current.isSentinel() && (!uniqueValue || found == null)) {
 				final int compareTo = current.compareTo(referenceElement);
 				if (compareTo == 0) {
@@ -187,6 +192,9 @@
 				} else {
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		return found;
@@ -201,6 +209,7 @@
 		IRBTNode<E> current = rootNode = nodeManager.getRootNode();
 		IRBTNode<E> found = null;
 		if (current != null) {
+			int depth = 0;
 			while (!current.isSentinel() && (!uniqueValue || found == null)) {
 				final int compareTo = current.compareTo(referenceElement);
 				if (compareTo == 0) {
@@ -211,6 +220,9 @@
 				} else {
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		return found;
@@ -232,6 +244,7 @@
 		IRBTNode<E> closestGreater = null;
 		boolean found = false;
 		if (current != null) {
+			int depth = 0;
 			int compareTo;
 			while (!found && !current.isSentinel()) {
 				compareTo = current.compareTo(referenceElement);
@@ -245,6 +258,9 @@
 				} else {
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 			if (!uniqueValue && found) {
 				while (!current.isSentinel()) {
@@ -257,6 +273,9 @@
 					} else {
 						current = current.getRight();
 					}
+					if (++depth == MAX_DEPTH) {
+						throw new RBTException(MAX_DEPTH_REACHED);
+					}
 				}
 			}
 		}
@@ -278,6 +297,7 @@
 		IRBTNode<E> current = nodeManager.getRootNode();
 		IRBTNode<E> strictlyGreater = null;
 		if (current != null) {
+			int depth = 0;
 			while (!current.isSentinel()) {
 				final int compareTo = current.compareTo(referenceElement);
 				if (compareTo > 0) {
@@ -286,6 +306,9 @@
 				} else {
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		rootNode = null;// NOPMD unreference
@@ -311,10 +334,14 @@
 			if (current.isSentinel()) {
 				current = null;// NOPMD
 			} else {
+				int depth = 0;
 				IRBTNode<E> right = current.getRight();
 				while (!right.isSentinel()) {
 					current = right;
 					right = current.getRight();
+					if (++depth == MAX_DEPTH) {
+						throw new RBTException(MAX_DEPTH_REACHED);
+					}
 				}
 			}
 		}
@@ -358,10 +385,14 @@
 			if (current.isSentinel()) {
 				current = null;// NOPMD
 			} else {
+				int depth = 0;
 				IRBTNode<E> left = current.getLeft();
 				while (!left.isSentinel()) {
 					current = left;
 					left = current.getLeft();
+					if (++depth == MAX_DEPTH) {
+						throw new RBTException(MAX_DEPTH_REACHED);
+					}
 				}
 			}
 		}
@@ -401,6 +432,7 @@
 		IRBTNode<E> current = nodeManager.getRootNode();
 		IRBTNode<E> closestLess = null;
 		if (current != null) {
+			int depth = 0;
 			boolean found = false;
 			int compareTo;
 			while (!found && !current.isSentinel()) {
@@ -415,6 +447,9 @@
 					closestLess = current;
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 			if (!uniqueValue && found) {
 				while (!current.isSentinel()) {
@@ -427,6 +462,9 @@
 					} else {
 						current = current.getRight();
 					}
+					if (++depth == MAX_DEPTH) {
+						throw new RBTException(MAX_DEPTH_REACHED);
+					}
 				}
 			}
 		}
@@ -447,6 +485,7 @@
 		IRBTNode<E> current = nodeManager.getRootNode();
 		IRBTNode<E> strictlyLess = null;
 		if (current != null) {
+			int depth = 0;
 			while (!current.isSentinel()) {
 				final int compareTo = current.compareTo(referenceElement);
 				if (compareTo >= 0) {
@@ -455,6 +494,9 @@
 					strictlyLess = current;
 					current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		return strictlyLess;
@@ -482,6 +524,7 @@
 		int comparison = 0;
 		// search for new node's parent.
 		if (current != null) {
+			int depth = 0;
 			while (!current.isSentinel()) {
 				parent = current;
 				comparison = nodeToAppend.compareTo(current);
@@ -494,6 +537,9 @@
 				} else if (comparison < 0) {
 					current = current.getLeft();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		if (exist && uniqueValue) {
@@ -535,6 +581,7 @@
 		int comparison = 0;
 		// search for new node's parent.
 		if (current != null) {
+			int depth = 0;
 			while (!toReplace && !current.isSentinel()) {
 				parent = current;
 				comparison = nodeToAppendOrSubstitute.compareTo(current);
@@ -549,6 +596,9 @@
 					toReplace = true;
 					// current = current.getRight();
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 
@@ -621,6 +671,7 @@
 		int comparison = 0;
 		// search for new node's parent.
 		if (current != null) {
+			int depth = 0;
 			while (toAppend && !current.isSentinel()) {
 				parent = current;
 				comparison = nodeToAppend.compareTo(current);
@@ -635,6 +686,9 @@
 					 */
 					toAppend = false;
 				}
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 		}
 		final boolean appendToRight = comparison >= 0;
@@ -699,9 +753,13 @@
 			if (child != null && !child.isSentinel()) {// NOPMD
 				parent = child;
 				child = parent.getRight();
+				int depth = 0;
 				while (child != null && !child.isSentinel()) {
 					parent = child;
 					child = parent.getRight();
+					if (++depth == MAX_DEPTH) {
+						throw new RBTException(MAX_DEPTH_REACHED);
+					}
 				}
 				appendInternal(nodeToInsert, parent, true);
 			} else {
@@ -742,9 +800,13 @@
 		if (child != null && !child.isSentinel()) {// NOPMD
 			parent = child;
 			child = parent.getLeft();
+			int depth = 0;
 			while (child != null && !child.isSentinel()) {
 				parent = child;
 				child = parent.getLeft();
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 			appendInternal(nodeToInsert, parent, false);
 		} else {
@@ -985,8 +1047,12 @@
 			 * predecessor of the node to delete.
 			 */
 			substitute = node.getLeft();
+			int depth = 0;
 			while (!substitute.getRight().isSentinel()) {
 				substitute = substitute.getRight();
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 
 			child = substitute.getLeft();
@@ -1116,10 +1182,14 @@
 		if (node.getLeft().isSentinel()) {
 			IRBTNode<E> currentNode = node;
 			IRBTNode<E> parent = currentNode.getParent();
+			int depth = 0;
 			while (parent != null && !parent.isSentinel()
 					&& currentNode == parent.getLeft()) {
 				currentNode = parent;
 				parent = currentNode.getParent();
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 			previous = parent;
 		} else {
@@ -1143,10 +1213,14 @@
 		if (node.getRight().isSentinel()) {
 			IRBTNode<E> currentNode = node;
 			IRBTNode<E> parent = currentNode.getParent();
+			int depth = 0;
 			while (parent != null && !parent.isSentinel()
 					&& currentNode == parent.getRight()) {
 				currentNode = parent;
 				parent = currentNode.getParent();
+				if (++depth == MAX_DEPTH) {
+					throw new RBTException(MAX_DEPTH_REACHED);
+				}
 			}
 			next = parent;
 		} else {
@@ -1177,8 +1251,12 @@
 			throws RBTException {
 		IRBTNode<E> currentNode = node;
 		IRBTNode<E> left;
+		int depth = 0;
 		while (!(left = currentNode.getLeft()).isSentinel()) {// NOPMD
 			currentNode = left;
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		return currentNode;
 	}
@@ -1187,8 +1265,12 @@
 			throws RBTException {
 		IRBTNode<E> currentNode = node;
 		IRBTNode<E> right;
+		int depth = 0;
 		while (!(right = currentNode.getRight()).isSentinel()) { // NOPMD
 			currentNode = right;
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		return currentNode;
 	}
@@ -1235,6 +1317,7 @@
 		final IRBTNode<E> left = current.getLeft();
 		index = left.isSentinel() ? 0 : (left.getNumberOfChild() + 1);
 		IRBTNode<E> parent = current.getParent();
+		int depth = 0;
 		while (parent != null) {
 			if (parent.getRight() == current) {
 				final IRBTNode<E> parentLeft = parent.getLeft();
@@ -1243,6 +1326,9 @@
 			}
 			current = parent;
 			parent = parent.getParent();
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		rootNode = null;// NOPMD unreference
 		return index;
@@ -1286,6 +1372,7 @@
 		currentNodeIndex = currentLeft.isSentinel() ? 0 : (currentLeft
 				.getNumberOfChild() + 1);
 
+		int depth = 0;
 		while (index != currentNodeIndex) {
 			if (index < currentNodeIndex) {
 				/*
@@ -1312,6 +1399,9 @@
 				currentNodeIndex += (currentLeft.isSentinel() ? 0
 						: (currentLeft.getNumberOfChild() + 1)) + 1;
 			}
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		return currentNode;
 	}
@@ -1333,6 +1423,7 @@
 		IRBTNode<E> currentNode = node;
 		IRBTNode<E> currentNodeParent = currentNode.getParent();
 		IRBTNode<E> currentNodeParentParent;
+		int depth = 0;
 		while (currentNodeParent != null // NOPMD
 				&& currentNodeParent.isRed()
 				&& (currentNodeParentParent = currentNodeParent.getParent()) != null) {
@@ -1393,6 +1484,9 @@
 					leftRotation(currentNodeParentParent);
 				}
 			}
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		rootNode.setBlack();
 	}
@@ -1414,6 +1508,7 @@
 		assert parentNode != null && !parentNode.isSentinel() : "parent node can not be null nor sentinel";
 		IRBTNode<E> node = childNode;
 		IRBTNode<E> parent = parentNode;
+		int depth = 0;
 		while (node != rootNode && node.isBlack()) {// NOPMD
 			if (node == parent.getLeft()) {
 				// Rebalance left side.
@@ -1494,6 +1589,9 @@
 					node = rootNode; // Finished.
 				}
 			}
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		node.setBlack();
 	}
@@ -1601,18 +1699,26 @@
 	private void incrementNumberOfChild(final IRBTNode<E> node)
 			throws RBTException {
 		IRBTNode<E> current = node;
+		int depth = 0;
 		while (current != null) {
 			current.setNumberOfChild(current.getNumberOfChild() + 1);
 			current = current.getParent();
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 	}
 
 	private void decrementNumberOfChild(final IRBTNode<E> node)
 			throws RBTException {
 		IRBTNode<E> current = node;
+		int depth = 0;
 		while (current != null) {
 			current.setNumberOfChild(current.getNumberOfChild() - 1);
 			current = current.getParent();
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 	}
 
@@ -1641,9 +1747,13 @@
 			throws RBTException {
 		IRBTNode<E> current = node;
 		IRBTNode<E> parent = node.getParent();
+		int depth = 0;
 		while (parent != null) {
 			current = parent;
 			parent = current.getParent();
+			if (++depth == MAX_DEPTH) {
+				throw new RBTException(MAX_DEPTH_REACHED);
+			}
 		}
 		return current == nodeManager.getRootNode();
 	}

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.