You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mnemonic.apache.org by ga...@apache.org on 2017/07/18 06:07:42 UTC
incubator-mnemonic git commit: MNEMONIC-305: Implement Remove
operation for Durable Trees
Repository: incubator-mnemonic
Updated Branches:
refs/heads/master 3d5465cef -> 48b37676b
MNEMONIC-305: Implement Remove operation for Durable Trees
Project: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/commit/48b37676
Tree: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/tree/48b37676
Diff: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/diff/48b37676
Branch: refs/heads/master
Commit: 48b37676bb1413cc902bea45666c7d8084891392
Parents: 3d5465c
Author: Johnu George <jo...@apache.org>
Authored: Thu Jul 13 14:40:15 2017 -0700
Committer: Johnu George <jo...@apache.org>
Committed: Mon Jul 17 17:27:11 2017 -0700
----------------------------------------------------------------------
.../mnemonic/collections/DurableTree.java | 13 ++
.../mnemonic/collections/DurableTreeImpl.java | 121 ++++++++++++++++++-
.../mnemonic/collections/DurableTreeNGTest.java | 59 ++++++++-
3 files changed, 190 insertions(+), 3 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/48b37676/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
index 18266cf..8fc4c6c 100644
--- a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
@@ -105,6 +105,19 @@ public abstract class DurableTree<E> implements Durable, Iterable<E> {
public abstract void insert(E item);
/**
+ * removes a specific element from the tree
+ *
+ * @param item
+ * the item to be removed
+ *
+ * @param destroy
+ * destroy the item to be removed
+ *
+ * @return true if element is removed
+ */
+ public abstract boolean remove(E item, boolean destroy);
+
+ /**
* print tree
*
*/
http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/48b37676/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
index e3a3108..b345e9f 100644
--- a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
@@ -183,6 +183,125 @@ public class DurableTreeImpl<A extends RestorableAllocator<A>, E extends Compara
}
}
+ /**
+ * removes a specific element from the tree
+ *
+ * @param item
+ * the item to be removed
+ *
+ * @return true if element is removed
+ */
+ public boolean remove(E item, boolean destroy) {
+ TreeNode<E> currentNode = findNode(item);
+ if (null == currentNode) {
+ return false;
+ }
+ TreeNode<E> tmp, ref = currentNode;
+ boolean col = ref.getColor();
+ if (null == currentNode.getLeft()) {
+ tmp = currentNode.getRight();
+ replace(currentNode, currentNode.getRight());
+ } else if (null == currentNode.getRight()) {
+ tmp = currentNode.getLeft();
+ replace(currentNode, currentNode.getLeft());
+ } else {
+ ref = findMinimum(currentNode.getRight());
+ col = ref.getColor();
+ tmp = ref.getRight();
+ if (ref.getParent().equals(currentNode)) {
+ tmp.setParent(ref, false);
+ } else {
+ replace(ref, ref.getRight());
+ ref.setRight(currentNode.getRight(), false);
+ ref.getRight().setParent(ref, false);
+ }
+ replace(currentNode, ref);
+ ref.setLeft(currentNode.getLeft(), false);
+ ref.getLeft().setParent(ref, false);
+ ref.setColor(currentNode.getColor());
+ }
+ if (col == BLACK && tmp != null) {
+ fixDelete(tmp);
+ }
+ if (destroy) {
+ currentNode.setLeft(null, false);
+ currentNode.setRight(null, false);
+ currentNode.setParent(null, false);
+ currentNode.destroy();
+ }
+ return true;
+ }
+
+ protected void fixDelete(TreeNode<E> currentNode) {
+ while (!currentNode.equals(root) && currentNode.getColor() == BLACK) {
+ if (currentNode.equals(currentNode.getParent().getLeft())) {
+ TreeNode<E> other = currentNode.getParent().getRight();
+ if (other.getColor() == RED) {
+ other.setColor(BLACK);
+ currentNode.getParent().setColor(RED);
+ rotateLeft(currentNode.getParent());
+ other = currentNode.getParent().getRight();
+ }
+ if (other.getLeft().getColor() == BLACK && other.getRight().getColor() == BLACK) {
+ other.setColor(RED);
+ currentNode = currentNode.getParent();
+ continue;
+ } else if (other.getRight().getColor() == BLACK) {
+ other.getLeft().setColor(BLACK);
+ other.setColor(RED);
+ rotateRight(other);
+ other = currentNode.getParent().getRight();
+ }
+ if (other.getRight().getColor() == RED) {
+ other.setColor(currentNode.getParent().getColor());
+ currentNode.getParent().setColor(BLACK);
+ other.getRight().setColor(BLACK);
+ rotateLeft(currentNode.getParent());
+ currentNode = root;
+ }
+ } else {
+ TreeNode other = currentNode.getParent().getLeft();
+ if (other.getColor() == RED) {
+ other.setColor(BLACK);
+ currentNode.getParent().setColor(RED);
+ rotateRight(currentNode.getParent());
+ other = currentNode.getParent().getLeft();
+ }
+ if (other.getRight().getColor() == BLACK && other.getLeft().getColor() == BLACK) {
+ other.setColor(RED);
+ currentNode = currentNode.getParent();
+ continue;
+ } else if (other.getLeft().getColor() == BLACK) {
+ other.getRight().setColor(BLACK);
+ other.setColor(RED);
+ rotateLeft(other);
+ other = currentNode.getParent().getLeft();
+ }
+ if (other.getLeft().getColor() == RED) {
+ other.setColor(currentNode.getParent().getColor());
+ currentNode.getParent().setColor(BLACK);
+ other.getLeft().setColor(BLACK);
+ rotateRight(currentNode.getParent());
+ currentNode = root;
+ }
+ }
+ }
+ currentNode.setColor(BLACK);
+ }
+
+ protected void replace(TreeNode<E> first, TreeNode<E> second) {
+ if (null == first.getParent()) {
+ root = second;
+ unsafe.putLong(holder.get(), root.getHandler());
+ } else if (first.equals(first.getParent().getLeft())) {
+ first.getParent().setLeft(second, false);
+ } else {
+ first.getParent().setRight(second, false);
+ }
+ if (second != null) {
+ second.setParent(first.getParent(), false);
+ }
+ }
/**
* checks if tree contains the specified element
@@ -190,7 +309,7 @@ public class DurableTreeImpl<A extends RestorableAllocator<A>, E extends Compara
* @param item
* the item to be set
*
- * @return tree if set contains the element
+ * @return true if tree contains the element
*/
public boolean contains(E item) {
return findNode(item) == null ? false : true;
http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/48b37676/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java b/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
index 2327050..e8c657f 100644
--- a/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
+++ b/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
@@ -114,6 +114,20 @@ public class DurableTreeNGTest {
AssertJUnit.assertEquals(tree.predecessor(7).intValue(), 6);
AssertJUnit.assertNull(tree.successor(7));
+ AssertJUnit.assertTrue(tree.contains(3));
+ tree.remove(3, true);
+ AssertJUnit.assertFalse(tree.contains(3));
+ AssertJUnit.assertEquals(tree.successor(1).intValue(), 4);
+ AssertJUnit.assertEquals(tree.predecessor(4).intValue(), 1);
+ AssertJUnit.assertTrue(tree.isValidTree());
+ tree.remove(7, true);
+ AssertJUnit.assertFalse(tree.contains(7));
+ AssertJUnit.assertNull(tree.successor(6));
+ AssertJUnit.assertTrue(tree.isValidTree());
+
+ tree.insert(3);
+ tree.insert(7);
+
DurableTree<Integer> restoredTree = DurableTreeFactory.restore(m_act, null, gtypes, handler, false);
AssertJUnit.assertTrue(restoredTree.isValidTree());
@@ -131,8 +145,7 @@ public class DurableTreeNGTest {
AssertJUnit.assertNull(restoredTree.successor(7));
restoredTree.insert(10);
- restoredTree.insert(2);
- AssertJUnit.assertEquals(restoredTree.successor(1).intValue(), 2);
+ AssertJUnit.assertEquals(restoredTree.successor(1).intValue(), 3);
AssertJUnit.assertEquals(restoredTree.predecessor(10).intValue(), 7);
restoredTree.destroy();
@@ -166,6 +179,13 @@ public class DurableTreeNGTest {
AssertJUnit.assertEquals(tree.predecessor("Fun"), "Ele");
AssertJUnit.assertNull(tree.successor("bob"));
+ tree.remove("Cat", true);
+ AssertJUnit.assertEquals(tree.predecessor("Dog"), "Alice");
+ AssertJUnit.assertEquals(tree.successor("Alice"), "Dog");
+ AssertJUnit.assertTrue(tree.isValidTree());
+ tree.remove("Alice", true);
+ AssertJUnit.assertNull(tree.predecessor("Dog"));
+
tree.destroy();
}
@@ -185,6 +205,41 @@ public class DurableTreeNGTest {
}
@Test(enabled = true)
+ public void testInsertRemoveBigTrees() {
+ DurableType gtypes[] = {DurableType.INTEGER};
+ DurableTree<Integer> tree = DurableTreeFactory.create(m_act, null, gtypes, false);
+
+ Long handler = tree.getHandler();
+ for (int i = 0; i < 10 * 1024; i++) {
+ tree.insert(i);
+ AssertJUnit.assertTrue(tree.contains(i));
+ }
+
+ AssertJUnit.assertTrue(tree.isValidTree());
+
+ for (int i = 0; i < 5 * 1024; i++) {
+ AssertJUnit.assertTrue(tree.remove(i, true));
+ }
+ AssertJUnit.assertTrue(tree.isValidTree());
+
+ for (int i = 0; i < 10 * 1024; i++) {
+ if (i < 5 * 1024) {
+ AssertJUnit.assertFalse(tree.contains(i));
+ tree.insert(i);
+ } else {
+ AssertJUnit.assertTrue(tree.contains(i));
+ }
+ }
+
+ for (int i = 0; i < 10 * 1024; i++) {
+ AssertJUnit.assertTrue(tree.contains(i));
+ }
+ AssertJUnit.assertTrue(tree.isValidTree());
+
+ tree.destroy();
+ }
+
+ @Test(enabled = true)
public void testInsertDurable() {
DurableType gtypes[] = {DurableType.DURABLE};
EntityFactoryProxy efproxies[] = {new EntityFactoryProxy() {