[Joafip-svn] SF.net SVN: joafip:[3170] trunk/joafip-rbtree
Brought to you by:
luc_peuvrier
Menu
▾
▴
[Joafip-svn] SF.net SVN: joafip:[3170] trunk/joafip-rbtree
|
From: <luc...@us...> - 2012-11-28 12:17:52
|
Revision: 3170
http://joafip.svn.sourceforge.net/joafip/?rev=3170&view=rev
Author: luc_peuvrier
Date: 2012-11-28 12:17:40 +0000 (Wed, 28 Nov 2012)
Log Message:
-----------
red black tree management changed. foreground garbage sweep changed
Modified Paths:
--------------
trunk/joafip-rbtree/pom.xml
trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/impl/memory/entity/RBTNode.java
trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java
trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestByPosition.java
trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestDelete.java
trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestInsert.java
trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/TreeShower.java
Added Paths:
-----------
trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RBTRuntimeException.java
Modified: trunk/joafip-rbtree/pom.xml
===================================================================
--- trunk/joafip-rbtree/pom.xml 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/pom.xml 2012-11-28 12:17:40 UTC (rev 3170)
@@ -25,6 +25,13 @@
<dependency>
<groupId>net.sf.joafip</groupId>
+ <artifactId>joafip-common</artifactId>
+ <scope>test</scope>
+ <type>test-jar</type>
+ </dependency>
+
+ <dependency>
+ <groupId>net.sf.joafip</groupId>
<artifactId>joafip-log4j</artifactId>
<scope>test</scope>
</dependency>
Modified: trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/impl/memory/entity/RBTNode.java
===================================================================
--- trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/impl/memory/entity/RBTNode.java 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/impl/memory/entity/RBTNode.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -25,6 +25,7 @@
import net.sf.joafip.redblacktree.entity.IRBTNode;
import net.sf.joafip.redblacktree.service.IRBTVisitor;
import net.sf.joafip.redblacktree.service.RBTException;
+import net.sf.joafip.redblacktree.service.RBTRuntimeException;
import net.sf.joafip.redblacktree.service.RedBlackTree;
import net.sf.joafip.store.service.proxy.IInstanceFactory;
@@ -357,14 +358,29 @@
visitor.endVisit(this);
}
+ @SuppressWarnings({ "unchecked", "rawtypes" })
@Override
public boolean equals(final Object obj) {
- throw new UnsupportedOperationException();
+ final boolean equals;
+ if (obj == null) {
+ equals = false;
+ } else if (obj == this) {
+ equals = true;
+ } else if (obj instanceof RBTNode) {
+ try {
+ equals = compareTo((IRBTComparableNode) obj) == 0;
+ } catch (RBTException exception) {
+ throw new RBTRuntimeException(exception);
+ }
+ } else {
+ equals = false;
+ }
+ return equals;
}
@Override
public int hashCode() {
- throw new UnsupportedOperationException();
+ return element == null ? 0 : element.hashCode();
}
@Override
Added: trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RBTRuntimeException.java
===================================================================
--- trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RBTRuntimeException.java (rev 0)
+++ trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RBTRuntimeException.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ *
+ * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE
+ * Licensed under the LGPL License, Version 3, 29 June 2007 (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.gnu.org/licenses/lgpl.html
+ *
+ * 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 net.sf.joafip.redblacktree.service;
+
+import net.sf.joafip.NotStorableClass;
+
+@NotStorableClass
+public class RBTRuntimeException extends RuntimeException {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 7478871706595989215L;
+
+ public RBTRuntimeException() {
+ super();
+ }
+
+ public RBTRuntimeException(final String message, final Throwable cause) {
+ super(message, cause);
+ }
+
+ public RBTRuntimeException(final String message) {
+ super(message);
+ }
+
+ public RBTRuntimeException(final Throwable cause) {
+ super(cause);
+ }
+
+}
Property changes on: trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RBTRuntimeException.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
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 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/main/java/net/sf/joafip/redblacktree/service/RedBlackTree.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -23,6 +23,7 @@
import net.sf.joafip.AssertNotNull;
import net.sf.joafip.StorableClass;
import net.sf.joafip.StoreNotUseStandardSerialization;
+import net.sf.joafip.logger.JoafipLogger;
import net.sf.joafip.redblacktree.entity.IRBTNode;
import net.sf.joafip.store.service.proxy.IInstanceFactory;
@@ -46,6 +47,9 @@
// complexity
Iterable<IRBTNode<E>>, Serializable {
+ private static final JoafipLogger LOGGER = JoafipLogger
+ .getLogger(RedBlackTree.class);
+
private static final String MAX_DEPTH_REACHED = "max depth reached";
/**
@@ -1003,7 +1007,8 @@
incrementNumberOfChild(parent);
}
// Rebalance after insert.
- insertReorganize(nodeToAppend);
+ // insertReorganize(nodeToAppend);
+ insertionReorganize(nodeToAppend);
}
}
@@ -1117,96 +1122,129 @@
*
* @param nodeToDelete
* node to delete
+ * @return
* @throws RBTException
* node access error
*/
- private void privateDeleteExistingNode(final IRBTNode<E> nodeToDelete)// NOPMD
+ private IRBTNode<E> privateDeleteExistingNode(final IRBTNode<E> nodeToDelete)// NOPMD
// complexity
// ok
throws RBTException {
-
if (!manageNodeIndex) {
final int numberOfElement = getNumberOfElementInternal();
rootNumberOfChild = numberOfElement - 1;
}
- IRBTNode<E> node = nodeToDelete;
- IRBTNode<E> substitute;
- final IRBTNode<E> child;
- // search for substitute to the node to delete
- if (node.getLeft().isSentinel()) {
- // the node to be deleted has 0 or 1 child
- substitute = node;
- child = node.getRight();
- } else if (node.getRight().isSentinel()) {
- // the node to be deleted has 1 child
- substitute = node;
- child = node.getLeft();
- } else {
- /*
- * the node to delete has 2 or more children. substitute is
- * 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);
- }
- }
+ // If strictly internal, copy successor's element to p and then make p
+ // point to successor.
+ // if p has 2 children
+ if (!nodeToDelete.getLeft().isSentinel()
+ && !nodeToDelete.getRight().isSentinel()) {
+ final IRBTNode<E> successor = successor(nodeToDelete);
+ swap(nodeToDelete, successor);
+ }
- child = substitute.getLeft();
+ // Start fixup at replacement node, if it exists.
+ final IRBTNode<E> replacement = (!nodeToDelete.getLeft().isSentinel() ? nodeToDelete
+ .getLeft() : nodeToDelete.getRight());
- // swap the substitute and node to delete
- swap(node, substitute);
- final IRBTNode<E> tmp = node;
- node = substitute;
- substitute = tmp;
+ if (manageNodeIndex) {
+ decrementNumberOfChild(nodeToDelete);
}
- /*
- * Unlink substitute from the tree ( substitute became the real node to
- * detach to the tree).
- */
- final IRBTNode<E> parent = substitute.getParent();
- child.setParent(parent);
- if (parent == null) {
- // 0 or 1 node remaining.
- if (child.isSentinel()) {
- rootNode = null;// NOPMD
+ IRBTNode<E> parentOfNodeToDelete = nodeToDelete.getParent();
+ if (!replacement.isSentinel()) {
+ // Link replacement to parent
+ replacement.setParent(parentOfNodeToDelete);
+ if (parentOfNodeToDelete == null) {
+ rootNode = replacement;
+ } else if (nodeToDelete == parentOfNodeToDelete.getLeft()) {
+ parentOfNodeToDelete.setLeft(replacement);
} else {
- child.setBlack();
- rootNode = child;
- child.setNumberOfChild(0);
+ parentOfNodeToDelete.setRight(replacement);
}
- /* detach the node to the tree */
- node.detach();
+ // Null out links so they are OK to use by fixAfterDeletion.
+ // FIXMELUC __________________________see detach
+ nodeToDelete.setParent(null);
+ IRBTNode<E> newSentinel = nodeManager.newSentinel();
+ nodeToDelete.setLeft(newSentinel);
+ newSentinel.setParent(nodeToDelete);
+ newSentinel = nodeManager.newSentinel();
+ nodeToDelete.setRight(newSentinel);
+ newSentinel.setParent(nodeToDelete);
+
+ // Fix replacement
+ if (nodeToDelete.getColor() == BLACK) {
+ deletionReorganize(replacement);
+ }
+ } else if (parentOfNodeToDelete == null) {
+ // return if it is the only node.
+ rootNode = null;
} else {
- if (substitute == parent.getLeft()) {
- parent.setLeft(child);
- } else {
- parent.setRight(child);
+ // No children. Use self as phantom replacement and unlink.
+ if (nodeToDelete.getColor() == BLACK) {
+ deletionReorganize(nodeToDelete);
+ parentOfNodeToDelete = nodeToDelete.getParent();
}
- if (manageNodeIndex) {
- decrementNumberOfChild(parent);
- }
- if (substitute.isBlack()) {
- deleteReorganize(child, parent);
+ if (parentOfNodeToDelete != null) {
+ IRBTNode<E> newSentinel = nodeManager.newSentinel();
+ if (nodeToDelete == parentOfNodeToDelete.getLeft()) {
+ parentOfNodeToDelete.setLeft(newSentinel);
+ } else {
+ parentOfNodeToDelete.setRight(newSentinel);
+ }
+ newSentinel.setParent(parentOfNodeToDelete);
+ // FIXMELUC __________________________see detach
+ nodeToDelete.setParent(null);
}
-
- /* detach the node to the tree */
- substitute.detach();
}
- // assertNotAttached(nodeToDelete);
+ nodeToDelete.detach();
if (!manageNodeIndex && rootNumberOfChild != 0) {
rootNode.setNumberOfChild(rootNumberOfChild - 1);
}
+ return nodeToDelete;
}
/**
- * swap to node, the node instance and state are swaped.make able to swap
+ * Returns the successor of the specified Entry, or null if no such.
+ *
+ * @throws RBTException
+ */
+ private static <E> IRBTNode<E> successor(final IRBTNode<E> node)
+ throws RBTException {
+ if (node == null) {
+ return null;
+ // } else if (t.right != null) {
+ } else if (!node.getRight().isSentinel()) {
+ IRBTNode<E> successor = node.getRight();
+ // while (p.left != null)
+ int depth = 0;
+ while (!successor.getLeft().isSentinel()) {
+ successor = successor.getLeft();
+ if (++depth == MAX_DEPTH) {
+ throw new RBTException(MAX_DEPTH_REACHED);
+ }
+ }
+ return successor;
+ } else {
+ IRBTNode<E> successor = node.getParent();
+ IRBTNode<E> child = node;
+ // while (p != null && ch == p.right) {
+ int depth = 0;
+ while (successor != null && child == successor.getRight()) {
+ child = successor;
+ successor = successor.getParent();
+ if (++depth == MAX_DEPTH) {
+ throw new RBTException(MAX_DEPTH_REACHED);
+ }
+ }
+ return successor;
+ }
+ }
+
+ /**
+ * swap two node, the node instance and state are swaped.make able to swap
* node without acceding to its stored elements ( real implementation )
*
* @param node
@@ -1219,44 +1257,41 @@
private void swap(final IRBTNode<E> node, final IRBTNode<E> subsititute)
throws RBTException {
- IRBTNode<E> tmp;
+ final IRBTNode<E> parentOfSubstitute = subsititute.getParent();
+ final IRBTNode<E> parentOfNode = node.getParent();
- tmp = node.getParent();
- final IRBTNode<E> parent = subsititute.getParent();
-
- subsititute.setParent(tmp);
- if (tmp == null) {
+ subsititute.setParent(parentOfNode);
+ if (parentOfNode == null) {
rootNode = subsititute;
- } else if (tmp.getLeft() == node) {
- tmp.setLeft(subsititute);
+ } else if (parentOfNode.getLeft() == node) {
+ parentOfNode.setLeft(subsititute);
} else {
- tmp.setRight(subsititute);
+ parentOfNode.setRight(subsititute);
}
- if (parent == node) {// NOPMD compare instance
-
- node.setParent(subsititute);
- node.setLeft(subsititute.getLeft());
- subsititute.getLeft().setParent(node);
- subsititute.setLeft(node);
-
+ node.setParent(parentOfSubstitute);
+ if (parentOfSubstitute == null) {
+ rootNode = node;
+ } else if (parentOfSubstitute.getLeft() == subsititute) {
+ parentOfSubstitute.setLeft(node);
} else {
- node.setParent(parent);
- parent.setRight(node);
-
- tmp = subsititute.getLeft();
- subsititute.setLeft(node.getLeft());
- node.getLeft().setParent(subsititute);
- node.setLeft(tmp);
- tmp.setParent(node);
+ parentOfSubstitute.setRight(node);
}
- tmp = subsititute.getRight();
- subsititute.setRight(node.getRight());
- node.getRight().setParent(subsititute);
- node.setRight(tmp);
- tmp.setParent(node);
+ final IRBTNode<E> leftOfSubsititute = subsititute.getLeft();
+ final IRBTNode<E> leftOfNode = node.getLeft();
+ subsititute.setLeft(leftOfNode);
+ leftOfNode.setParent(subsititute);
+ node.setLeft(leftOfSubsititute);
+ leftOfSubsititute.setParent(node);
+ final IRBTNode<E> rightOfSubstitute = subsititute.getRight();
+ final IRBTNode<E> rightOfNode = node.getRight();
+ subsititute.setRight(rightOfNode);
+ rightOfNode.setParent(subsititute);
+ node.setRight(rightOfSubstitute);
+ rightOfSubstitute.setParent(node);
+
final boolean color = node.getColor();
node.setColor(subsititute.getColor());
subsititute.setColor(color);
@@ -1531,194 +1566,135 @@
return currentNode;
}
- /**
- * rebalance this red-black tree after inserting a new node.
- *
- * @param n
- * the inserted node
- * @throws RBTException
- * node access error
- */
- private void insertReorganize(final IRBTNode<E> node)// NOPMD complexity
- // ok
+ private void insertionReorganize(final IRBTNode<E> node)
throws RBTException {
- // Only need to rebalance when parent is a RED node, and while at least
- // 2 levels deep into the tree (ie: node has a grandparent). Remember
- // that nil.color == BLACK.
- 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) {
- if (currentNodeParent == currentNodeParentParent.getLeft()) {
- final IRBTNode<E> uncle = currentNodeParentParent.getRight();
- // Uncle may be nil, in which case it is BLACK.
- if (uncle.isRed()) {
- // Case 1. Uncle is RED: Change colors of parent, uncle,
- // and grandparent, and move n to grandparent.
- currentNodeParent.setBlack();
- uncle.setBlack();
- uncle.getParent().setRed();
- currentNode = uncle.getParent();
- currentNodeParent = currentNode.getParent();
+ IRBTNode<E> x = node;
+ x.setColor(RED);
+ IRBTNode<E> parentOfX = x.getParent();
+ IRBTNode<E> parentOfParentOfX = parentOf(parentOfX);
+ while (x != null && x != rootNode && parentOfX.getColor() == RED) {
+ if (parentOf(x) == leftOf(parentOfParentOfX)) {
+ IRBTNode<E> y = rightOf(parentOfParentOfX);
+ if (colorOf(y) == RED) {
+ setColor(parentOfX, BLACK);
+ setColor(y, BLACK);
+ setColor(parentOfParentOfX, RED);
+ x = parentOfParentOfX;
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
} else {
- if (currentNode == currentNodeParent.getRight()) {
- // Case 2. Uncle is BLACK and x is right child.
- // Move n to parent, and rotate n left.
- currentNode = currentNodeParent;
- // rotateLeft(n);
- leftRotation(currentNode);
- currentNodeParent = currentNode.getParent();
+ if (x == rightOf(parentOfX)) {
+ x = parentOfX;
+ leftRotation(x);
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
}
- // Case 3. Uncle is BLACK and x is left child.
- // Recolor parent, grandparent, and rotate grandparent
- // right.
- currentNodeParent.setBlack();
- currentNodeParentParent = currentNodeParent.getParent();
- currentNodeParentParent.setRed();
- rightRotation(currentNodeParentParent);
+ setColor(parentOfX, BLACK);
+ setColor(parentOfParentOfX, RED);
+ rightRotation(parentOfParentOfX);
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
}
} else {
- // Mirror image of above code.
- final IRBTNode<E> uncle = currentNodeParentParent.getLeft();
- // Uncle may be nil, in which case it is BLACK.
- if (uncle.isRed()) {
- // Case 1. Uncle is RED: Change colors of parent, uncle,
- // and grandparent, and move n to grandparent.
- currentNodeParent.setBlack();
- uncle.setBlack();
- uncle.getParent().setRed();
- currentNode = uncle.getParent();
- currentNodeParent = currentNode.getParent();
+ IRBTNode<E> y = leftOf(parentOfParentOfX);
+ if (colorOf(y) == RED) {
+ setColor(parentOfX, BLACK);
+ setColor(y, BLACK);
+ setColor(parentOfParentOfX, RED);
+ x = parentOfParentOfX;
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
+
} else {
- if (currentNode == currentNodeParent.getLeft()) {
- // Case 2. Uncle is BLACK and x is left child.
- // Move n to parent, and rotate n right.
- currentNode = currentNodeParent;
- // rotateRight(n);
- rightRotation(currentNode);
- currentNodeParent = currentNode.getParent();
+ if (x == leftOf(parentOfX)) {
+ x = parentOfX;
+ rightRotation(x);
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
+
}
- // Case 3. Uncle is BLACK and x is right child.
- // Recolor parent, grandparent, and rotate grandparent left.
- currentNodeParent.setBlack();
- currentNodeParentParent = currentNodeParent.getParent();
- currentNodeParentParent.setRed();
- leftRotation(currentNodeParentParent);
+ setColor(parentOfX, BLACK);
+ setColor(parentOfParentOfX, RED);
+ leftRotation(parentOfParentOfX);
+ // x parent
+ parentOfX = parentOf(x);
+ parentOfParentOfX = parentOf(parentOfX);
}
}
- if (++depth == MAX_DEPTH) {
- throw new RBTException(MAX_DEPTH_REACHED);
- }
}
- rootNode.setBlack();
+ rootNode.setColor(BLACK);
}
- /**
- * rebalance this red-black tree after deleting a node.
- *
- * @param node
- * the child of the node deleted, possibly sentinel
- * @param parent
- * the parent of the node deleted, never sentinel or null
- * @throws RBTException
- * node access error
- */
- private void deleteReorganize(// NOPMD complexity ok
- final IRBTNode<E> childNode, final IRBTNode<E> parentNode)
- throws RBTException {
- // ASSERTX
- 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.
- IRBTNode<E> sibling = parent.getRight();
- if (sibling.isRed()) {
- // Case 1: Sibling is red.
- // Recolor sibling and parent, and rotate parent left.
- sibling.setBlack();
- parent.setRed();
- // rotateLeft(parent);
- leftRotation(parent);
- sibling = parent.getRight();
+ private void deletionReorganize(IRBTNode<E> x) throws RBTException {
+ while (x != rootNode && colorOf(x) == BLACK) {
+ IRBTNode<E> parentOfX = parentOf(x);
+ if (x == leftOf(parentOfX)) {
+ IRBTNode<E> sib = rightOf(parentOfX);
+
+ if (colorOf(sib) == RED) {
+ setColor(sib, BLACK);
+ setColor(parentOfX, RED);
+ leftRotation(parentOfX);
+ parentOfX = parentOf(x);
+ sib = rightOf(parentOfX);
}
- final IRBTNode<E> left = sibling.getLeft();
- final IRBTNode<E> right = sibling.getRight();
- if (left.isBlack() && right.isBlack()) {
- // Case 2: Sibling has no red children.
- // Recolor sibling, and move to parent.
- sibling.setRed();
- node = parent;
- parent = parent.getParent();
+ if (colorOf(leftOf(sib)) == BLACK
+ && colorOf(rightOf(sib)) == BLACK) {
+ setColor(sib, RED);
+ x = parentOfX;
} else {
- if (right.isBlack()) {
- // Case 3: Sibling has red left child.
- // Recolor sibling and left child, rotate sibling right.
- left.setBlack();
- sibling.setRed();
- // rotateRight(sibling);
- rightRotation(sibling);
- sibling = parent.getRight();
+ if (colorOf(rightOf(sib)) == BLACK) {
+ setColor(leftOf(sib), BLACK);
+ setColor(sib, RED);
+ rightRotation(sib);
+ parentOfX = parentOf(x);
+ sib = rightOf(parentOfX);
}
- // Case 4: Sibling has red right child. Recolor sibling,
- // right child, and parent, and rotate parent left.
- sibling.setColor(parent.getColor());
- parent.setBlack();
- sibling.getRight().setBlack();
- // rotateLeft(parent);
- leftRotation(parent);
- node = rootNode; // Finished.
+ setColor(sib, colorOf(parentOfX));
+ setColor(parentOfX, BLACK);
+ setColor(rightOf(sib), BLACK);
+ leftRotation(parentOfX);
+ x = rootNode;
}
- } else {
- // Symmetric "mirror" of left-side case.
- IRBTNode<E> sibling = parent.getLeft();
- if (sibling.isRed()) {
- // Case 1: Sibling is red.
- // Recolor sibling and parent, and rotate parent right.
- sibling.setBlack();
- parent.setRed();
- rightRotation(parent);
- sibling = parent.getLeft();
+ } else { // symmetric
+ IRBTNode<E> sib = leftOf(parentOfX);
+
+ if (colorOf(sib) == RED) {
+ setColor(sib, BLACK);
+ setColor(parentOfX, RED);
+ rightRotation(parentOfX);
+ parentOfX = parentOf(x);
+ sib = leftOf(parentOfX);
}
- final IRBTNode<E> left = sibling.getLeft();
- final IRBTNode<E> right = sibling.getRight();
- if (right.isBlack() && left.isBlack()) {
- // Case 2: Sibling has no red children.
- // Recolor sibling, and move to parent.
- sibling.setRed();
- node = parent;
- parent = parent.getParent();
+ if (colorOf(rightOf(sib)) == BLACK
+ && colorOf(leftOf(sib)) == BLACK) {
+ setColor(sib, RED);
+ x = parentOfX;
} else {
- if (left.isBlack()) {
- // Case 3: Sibling has red right child.
- // Recolor sibling and right child, rotate sibling left.
- right.setBlack();
- sibling.setRed();
- // rotateLeft(sibling);
- leftRotation(sibling);
- sibling = parent.getLeft();
+ if (colorOf(leftOf(sib)) == BLACK) {
+ setColor(rightOf(sib), BLACK);
+ setColor(sib, RED);
+ leftRotation(sib);
+ parentOfX = parentOf(x);
+ sib = leftOf(parentOfX);
}
- // Case 4: Sibling has red left child. Recolor sibling,
- // left child, and parent, and rotate parent right.
- sibling.setColor(parent.getColor());
- parent.setBlack();
- sibling.getLeft().setBlack();
- rightRotation(parent);
- node = rootNode; // Finished.
+ setColor(sib, colorOf(parentOfX));
+ setColor(parentOf(x), BLACK);
+ setColor(leftOf(sib), BLACK);
+ rightRotation(parentOfX);
+ x = rootNode;
}
}
- if (++depth == MAX_DEPTH) {
- throw new RBTException(MAX_DEPTH_REACHED);
- }
}
- node.setBlack();
+
+ setColor(x, BLACK);
}
private void leftRotation(final IRBTNode<E> node) throws RBTException {
@@ -1775,15 +1751,29 @@
}
}
- private IRBTNode<E> parentOf(final IRBTNode<E> node) throws RBTException {
+ private static <E> boolean colorOf(IRBTNode<E> p) throws RBTException {
+ return (p == null ? BLACK : p.getColor());
+ }
+
+ private static <E> void setColor(IRBTNode<E> p, boolean c)
+ throws RBTException {
+ if (p != null) {
+ p.setColor(c);
+ }
+ }
+
+ private static <E> IRBTNode<E> parentOf(final IRBTNode<E> node)
+ throws RBTException {
return (node == null ? null : node.getParent());
}
- private IRBTNode<E> leftOf(final IRBTNode<E> node) throws RBTException {
+ private static <E> IRBTNode<E> leftOf(final IRBTNode<E> node)
+ throws RBTException {
return (node == null || node.isSentinel()) ? null : node.getLeft();// NOPMD
}
- private IRBTNode<E> rightOf(final IRBTNode<E> node) throws RBTException {
+ private static <E> IRBTNode<E> rightOf(final IRBTNode<E> node)
+ throws RBTException {
return (node == null || node.isSentinel()) ? null : node.getRight();// NOPMD
}
@@ -1821,7 +1811,7 @@
* the starting node having a new child
* @throws RBTException
*/
- private void incrementNumberOfChild(final IRBTNode<E> node)
+ private static <E> void incrementNumberOfChild(final IRBTNode<E> node)
throws RBTException {
IRBTNode<E> current = node;
int depth = 0;
@@ -1834,7 +1824,7 @@
}
}
- private void decrementNumberOfChild(final IRBTNode<E> node)
+ private static <E> void decrementNumberOfChild(final IRBTNode<E> node)
throws RBTException {
IRBTNode<E> current = node;
int depth = 0;
@@ -1847,7 +1837,7 @@
}
}
- private void updateNumberOfChild(final IRBTNode<E> node)
+ private static <E> void updateNumberOfChild(final IRBTNode<E> node)
throws RBTException {
final IRBTNode<E> left = node.getLeft();
final IRBTNode<E> right = node.getRight();
@@ -1880,6 +1870,11 @@
throw new RBTException(MAX_DEPTH_REACHED);
}
}
- return current == nodeManager.getRootNode();
+ final boolean attached = current == nodeManager.getRootNode();
+ if (!attached) {
+ LOGGER.error("current is: " + current.toString() + "\nroot is: "
+ + nodeManager.getRootNode().toString());
+ }
+ return attached;
}
}
Modified: trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestByPosition.java
===================================================================
--- trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestByPosition.java 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestByPosition.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -96,6 +96,8 @@
/**/new RBTNode<Integer>(beforeList[index]);// NOPMD
tree.appendAfterLast(node);
}
+ assertEquals("bad number of element", 6, tree.getNumberOfElement());
+
IRBTNode<Integer> deleted = tree.deleteByIndex(2);
assertEquals("bad element", Integer.valueOf(10), deleted.getElement());
deleted = tree.deleteByIndex(4);
Modified: trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestDelete.java
===================================================================
--- trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestDelete.java 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestDelete.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -21,6 +21,7 @@
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.TestException;
import net.sf.joafip.logger.JoafipLogger;
+import net.sf.joafip.redblacktree.entity.IRBTNode;
import net.sf.joafip.redblacktree.impl.memory.entity.RBTNode;
import net.sf.joafip.redblacktree.impl.memory.service.RBTNodeManager;
@@ -28,10 +29,10 @@
@DoNotTransform
public abstract class AbstractTestDelete extends AbstractJoafipCommonTestCase {
+ private static final String BAD_NUMBER_OF_ELEMENT = "bad number of element";
+
protected final JoafipLogger logger = JoafipLogger.getLogger(getClass());
- private final static TreeShower SHOWER = TreeShower.getInstance();
-
class IntHolder implements Comparable<IntHolder> {
private final int value;
@@ -85,6 +86,17 @@
return false;
return true;
}
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder();
+ builder.append("IntHolder [value=");
+ builder.append(value);
+ builder.append(", identifier=");
+ builder.append(identifier);
+ builder.append("]");
+ return builder.toString();
+ }
}
protected RedBlackTree<IntHolder> redBlackTree;
@@ -114,18 +126,28 @@
public void testDelete1() throws RBTException {// NOPMD assert in method
// called
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
final RBTNode<IntHolder> node = new RBTNode<IntHolder>(new IntHolder(0));
checker.checkTree();
redBlackTree.append(node);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1,
+ redBlackTree.getNumberOfElement());
+ //TreeShower treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.delete(new IntHolder(0));
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
}
public void testDelete2() throws RBTException {// NOPMD assert in method
// called
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
final RBTNode<IntHolder> node0 = new RBTNode<IntHolder>(
new IntHolder(0));
@@ -133,20 +155,31 @@
final RBTNode<IntHolder> node1 = new RBTNode<IntHolder>(
new IntHolder(1));
redBlackTree.append(node1);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 2,
+ redBlackTree.getNumberOfElement());
+ //TreeShower treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.delete(new IntHolder(0));
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.delete(new IntHolder(1));
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
}
public void testDelete3() throws RBTException {// NOPMD assert in method
// called
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
final RBTNode<IntHolder> node0 = new RBTNode<IntHolder>(
new IntHolder(0));
@@ -154,16 +187,23 @@
final RBTNode<IntHolder> node1 = new RBTNode<IntHolder>(
new IntHolder(1));
redBlackTree.append(node1);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 2,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
redBlackTree.delete(new IntHolder(1));
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
redBlackTree.delete(new IntHolder(0));
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
}
public void testDelete4() throws RBTException {// NOPMD assert in method
// called
- final TreeShower shower = TreeShower.getInstance();
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
final RBTNode<IntHolder> node0 = new RBTNode<IntHolder>(
new IntHolder(0));
@@ -174,18 +214,28 @@
final RBTNode<IntHolder> node2 = new RBTNode<IntHolder>(
new IntHolder(2));
redBlackTree.append(node2);
- shower.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 3,
+ redBlackTree.getNumberOfElement());
+ //TreeShower treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.delete(new IntHolder(1));
- shower.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 2,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.delete(new IntHolder(2));
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1,
+ redBlackTree.getNumberOfElement());
checker.checkTree();
}
public void testDelete5() throws RBTException {// NOPMD assert in method
// called
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
final RBTNode<IntHolder> node0 = new RBTNode<IntHolder>(
new IntHolder(0));
redBlackTree.append(node0);
@@ -198,14 +248,21 @@
final RBTNode<IntHolder> node3 = new RBTNode<IntHolder>(
new IntHolder(3));
redBlackTree.append(node3);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 4,
+ redBlackTree.getNumberOfElement());
+ //TreeShower treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
redBlackTree.deleteExistingNode(node1);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 3,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
}
+ @SuppressWarnings("unchecked")
public void testDelete6() throws RBTException {// NOPMD assert in method
// called
final RBTNode<IntHolder> node0 = new RBTNode<IntHolder>(
@@ -244,14 +301,96 @@
final RBTNode<IntHolder> node11 = new RBTNode<IntHolder>(new IntHolder(
11));
redBlackTree.append(node11);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 12,
+ redBlackTree.getNumberOfElement());
+ //TreeShower treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
-
+ search(redBlackTree,new RBTNode[]{node0,node1,node2,node3,node4,node5,node6,node7,node8,node9,node10,node11});
+
redBlackTree.deleteExistingNode(node5);
- SHOWER.show(redBlackTree);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 11,
+ redBlackTree.getNumberOfElement());
+ //treeShower = new TreeShower();
+ //treeShower.show(redBlackTree);
checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node0,node1,node2,node3,node4,node6,node7,node8,node9,node10,node11});
+
+ redBlackTree.deleteExistingNode(node2);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 10,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node0,node1,node3,node4,node6,node7,node8,node9,node10,node11});
+
+ redBlackTree.deleteExistingNode(node8);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 9,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node0,node1,node3,node4,node6,node7,node9,node10,node11});
+
+ redBlackTree.deleteExistingNode(node3);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 8,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node0,node1,node4,node6,node7,node9,node10,node11});
+
+ redBlackTree.deleteExistingNode(node10);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 7,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node0,node1,node4,node6,node7,node9,node11});
+
+ redBlackTree.deleteExistingNode(node0);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 6,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node1,node4,node6,node7,node9,node11});
+
+ redBlackTree.deleteExistingNode(node7);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 5,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node1,node4,node6,node9,node11});
+
+ redBlackTree.deleteExistingNode(node1);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 4,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node4,node6,node9,node11});
+
+ redBlackTree.deleteExistingNode(node9);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 3,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node4,node6,node11});
+
+ redBlackTree.deleteExistingNode(node4);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 2,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node6,node11});
+
+ redBlackTree.deleteExistingNode(node6);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+ search(redBlackTree,new RBTNode[]{node11});
+
+ redBlackTree.deleteExistingNode(node11);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 0,
+ redBlackTree.getNumberOfElement());
+ checker.checkTree();
+
}
+ private void search(final RedBlackTree<IntHolder> redBlackTree,
+ final RBTNode<IntHolder>[] rbtNodes) throws RBTException {
+ for(RBTNode<IntHolder> rbtNode:rbtNodes){
+ IRBTNode<IntHolder> found = redBlackTree.search(rbtNode.getElement());
+ assertSame("must found same node",rbtNode,found);
+ }
+ }
+
public void testDeleteRoot() throws RBTException {// NOPMD assert in
// method called
final RBTNode<IntHolder> root = new RBTNode<IntHolder>(new IntHolder(2));
@@ -260,8 +399,8 @@
redBlackTree.append(node);
node = new RBTNode<IntHolder>(new IntHolder(3));
redBlackTree.append(node);
- final TreeShower showTree = TreeShower.getInstance();
- showTree.show(redBlackTree);
+ //final TreeShower showTree = new TreeShower();
+ //showTree.show(redBlackTree);
redBlackTree.delete(new IntHolder(2));
}
@@ -271,6 +410,8 @@
for (int value = 0; value < 1024; value++) {
assertTrue("missing value " + value,
redBlackTree.delete(new IntHolder(value)));// NOPMD
+ assertEquals(BAD_NUMBER_OF_ELEMENT, 1023 - value,
+ redBlackTree.getNumberOfElement());
try {
checker.checkTree();
} catch (RBTException exception) {
@@ -291,6 +432,8 @@
final RBTNode<IntHolder> node =
/**/new RBTNode<IntHolder>(new IntHolder(function(value)));// NOPMD
redBlackTree.append(node);
+ assertEquals(BAD_NUMBER_OF_ELEMENT, value + 1,
+ redBlackTree.getNumberOfElement());
}
}
Modified: trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestInsert.java
===================================================================
--- trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestInsert.java 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/AbstractTestInsert.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -54,7 +54,7 @@
redBlackTree = new RedBlackTree<String>(nodeManager, false,
uniqueValue());
checker = new RedBlackTreeIntegrityChecker<String>(redBlackTree);
- shower = TreeShower.getInstance();
+ shower = new TreeShower();
super.setUp();
}
Modified: trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/TreeShower.java
===================================================================
--- trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/TreeShower.java 2012-11-28 12:17:20 UTC (rev 3169)
+++ trunk/joafip-rbtree/src/test/java/net/sf/joafip/redblacktree/service/TreeShower.java 2012-11-28 12:17:40 UTC (rev 3170)
@@ -30,69 +30,68 @@
*/
@SuppressWarnings("rawtypes")
@NotStorableClass
-public final class TreeShower implements IRBTVisitor {
+public class TreeShower implements IRBTVisitor {
private static final JoafipLogger LOGGER = JoafipLogger
.getLogger(TreeShower.class);
- private static final String TREE_END = "TREE END ----------------------------------------";
+ private static final String TREE_END = "TREE END ----------------------------------------\n";
- private static final String TREE_BEGIN = "TREE BEGIN ----------------------------------------";
+ private static final String TREE_BEGIN = "TREE BEGIN ----------------------------------------\n";
- private static final TreeShower INSTANCE = new TreeShower();
-
private static final String TWO_SPACE = " ";
private transient int pad;
private final transient Stack<ObjectIdentityKey> visitStack = new Stack<ObjectIdentityKey>();
+ private final StringBuilder stringBuilder = new StringBuilder();
+
private boolean fatal;
- public static TreeShower getInstance() {
- return INSTANCE;
- }
-
- private TreeShower() {
+ public TreeShower() {
super();
}
@SuppressWarnings("unchecked")
public void showFatal(final IRBTVisitable visitable) throws RBTException {
fatal = true;
- log(TREE_BEGIN);
+ stringBuilder.append(TREE_BEGIN);
pad = 0;
visitStack.clear();
visitable.accept(this);
visitStack.clear();
- log(TREE_END);
+ stringBuilder.append(TREE_END);
+ log(stringBuilder.toString());
}
@SuppressWarnings("unchecked")
public void show(final IRBTVisitable visitable) throws RBTException {
fatal = false;
- log(TREE_BEGIN);
+ stringBuilder.append(TREE_BEGIN);
pad = 0;
visitStack.clear();
visitable.accept(this);
visitStack.clear();
- log(TREE_END);
+ stringBuilder.append(TREE_END);
+ log(stringBuilder.toString());
}
public void beginVisit(final IRBTNode node) throws RBTException {
final ObjectIdentityKey item = new ObjectIdentityKey(node);
if (visitStack.contains(item)) {
- log("--> " + node.toString());
+ stringBuilder.append("--> ");
+ stringBuilder.append(node.toString());
+ stringBuilder.append('\n');
throw new RBTException("cycle in tree");
}
visitStack.push(item);
pad++;
- final StringBuilder stringBuilder = new StringBuilder();
for (int index = 0; index < pad; index++) {
stringBuilder.append(TWO_SPACE);
}
stringBuilder.append(node.toString());
- log(stringBuilder.toString());
+ stringBuilder.append('\n');
}
public void endVisit(final IRBTNode node) {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
