aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorFlorian Waibel2011-10-21 10:56:31 (EDT)
committerChristopher Frost2011-10-21 10:56:31 (EDT)
commit42d62d5f8e5dd3564bad384119004d254d939636 (patch)
treebe872549b5d9a40952ebd3b47450b2109720c6ad
parentd20cb4ac98babd960c3a7b91d4e00efab3677c47 (diff)
downloadorg.eclipse.virgo.util-42d62d5f8e5dd3564bad384119004d254d939636.zip
org.eclipse.virgo.util-42d62d5f8e5dd3564bad384119004d254d939636.tar.gz
org.eclipse.virgo.util-42d62d5f8e5dd3564bad384119004d254d939636.tar.bz2
ASSIGNED - bug 358697: [Subsystems] DAG interface and implementation https://bugs.eclipse.org/bugs/show_bug.cgi?id=358697 - DirectedAcyclicGraph and GraphNode ready for contribution.
-rw-r--r--org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java54
-rw-r--r--org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java160
-rw-r--r--org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java161
-rw-r--r--org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java382
-rw-r--r--org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java346
-rw-r--r--org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java601
6 files changed, 1704 insertions, 0 deletions
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
new file mode 100644
index 0000000..12e4391
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
@@ -0,0 +1,54 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.List;
+
+/**
+ * {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
+ * to each other in a way that it is impossible to start at a node n and follow a child relationship that loops back to
+ * n. The DAG may have multiple root nodes (nodes with no parents) and nodes may share children.
+ * <p />
+ * Once created a root node can become a non-root node by adding the node as a child to another node. This can be done
+ * by calling the method addChild on a node. All nodes of a DAG are reachable from its root nodes.
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * Implementations of this interface may or may not be thread safe.
+ *
+ * @param <V> type of values in the {@link GraphNode}s.
+ */
+public interface DirectedAcyclicGraph<V> {
+
+ /**
+ * Create a new {@link GraphNode} and add it to this {@link DirectedAcyclicGraph}'s root nodes. The value is not
+ * copied.
+ *
+ * @param value of the node to create
+ * @return a node with the given value
+ */
+ GraphNode<V> createRootNode(V value);
+
+ /**
+ * Removes the occurrence of the given {@link GraphNode} from this {@link DirectedAcyclicGraph}'s root nodes.
+ * Returns <code>true</code> if the node was found and removed, otherwise <code>false</code>.
+ *
+ * <strong>Note</strong>: Removal is only allowed if the root node has no children.
+ *
+ * @param node the node to remove
+ * @throws IllegalArgumentException if the given node is not a root node (the node has one or more parents)
+ * @throws IllegalArgumentException if the given node has children
+ * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+ * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+ * @see java.util.List#remove
+ */
+ boolean deleteRootNode(GraphNode<V> node);
+
+ /**
+ * Returns a list of this {@link DirectedAcyclicGraph}'s root nodes (not copies of the nodes). If the graph has no
+ * root nodes (and is therefore empty), returns an empty list. Never returns <code>null</code>.
+ *
+ * @return this graph's root nodes
+ */
+ List<GraphNode<V>> getRootNodes();
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java
new file mode 100644
index 0000000..598e51c
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java
@@ -0,0 +1,160 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.List;
+
+/**
+ * {@link GraphNode} is a node in a {@link DirectedAcyclicGraph}. Each node has a value.
+ * <p />
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * Implementations of this interface may or may not be thread safe.
+ *
+ * @param <V> type of values in the graph nodes.
+ */
+public interface GraphNode<V> {
+
+ /**
+ * {@link DirectedAcyclicGraphVisitor} is used to visit a node and, at the option of the visitor, its subgraphs
+ * recursively. <strong>Note</strong>: Shared nodes are only visited once.
+ * <p />
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * Implementations of this interface should be thread safe when used with a thread safe
+ * <code>DirectedAcyclicGraph</code> implementation.
+ *
+ * @param <V> type of values in graph nodes
+ */
+ interface DirectedAcyclicGraphVisitor<V> {
+
+ /**
+ * Visits the given {@link GraphNode}. The return value determines whether or not any subgraphs of the given
+ * node are visited.
+ *
+ * @param node the <code>GraphNode</code> to be visited
+ * @return <code>true</code> if and only if the subgraphs of the given node should be visited.
+ */
+ boolean visit(GraphNode<V> node);
+
+ }
+
+ /**
+ * An <code>ExceptionThrowingDirectedAcyclicGraphVisitor</code> is used to visit a node and, at the option of the
+ * visitor, its subgraphs recursively if the {@link #visit(GraphNode)} implementation needs to be able to throw a
+ * checked {@link Exception}. <strong>Note</strong>: Shared nodes are only visited once.
+ * <p />
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * Implementations of this interface should be thread safe when used with a thread safe
+ * <code>DirectedAcyclicGraph</code> implementation.
+ *
+ * @param <V> type of values in graph nodes
+ * @param <E> type of exceptions possibly thrown
+ */
+ interface ExceptionThrowingDirectedAcyclicGraphVisitor<V, E extends Exception> {
+
+ /**
+ * Visits the given {@link GraphNode}. The return value determines whether or not any subgraphs of the given
+ * node are visited.
+ *
+ * @param node the <code>GraphNode</code> to be visited
+ * @throws E if an error occurs when visiting the given node
+ * @return <code>true</code> if and only if the subgraphs of the given node should be visited.
+ */
+ boolean visit(GraphNode<V> node) throws E;
+
+ }
+
+ /**
+ * Returns the node's value. If there is no value associated with this node, returns <code>null</code>.
+ *
+ * @return the value, which may be <code>null</code>
+ */
+ V getValue();
+
+ /**
+ * Returns a list of this node's children (not copies of the children). If the node has no children, returns an
+ * empty list. Never returns <code>null</code> .
+ *
+ * @return this node's children
+ */
+ List<GraphNode<V>> getChildren();
+
+ /**
+ * Adds the given node as child to this node. The child node is <strong>not</strong> copied.
+ *
+ * @param child the node to add
+ * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+ * @throws IllegalArgumentException if the given node is already a child of this node.
+ */
+ void addChild(GraphNode<V> child);
+
+ /**
+ * Removes the occurrence of the given node from this node's children. Returns <code>true</code> if the child was
+ * found and removed, otherwise <code>false</code>.
+ *
+ * @param child the node to remove
+ * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+ * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+ * @see java.util.List#remove
+ */
+ boolean removeChild(GraphNode<V> child);
+
+ /**
+ * Returns a list of this node's parents (not copies of the parents). If this node does not have any parents,
+ * returns an empty list. Never returns <code>null</code>.
+ *
+ * @return this node's parents
+ */
+ List<GraphNode<V>> getParents();
+
+ /**
+ * Traverse this {@link GraphNode} in preorder (see below) and call the visit method of the given
+ * {@link DirectedAcyclicGraphVisitor} at each node. The visitor determines whether the subgraphs of each visited
+ * node should also be visited. <strong>Note</strong>: Shared nodes are only visited once.
+ * <p/>
+ * Preorder traversal visits the node and then visits, in preorder, each subgraph of the node.
+ *
+ * @param visitor a {@link DirectedAcyclicGraphVisitor}
+ */
+ void visit(DirectedAcyclicGraphVisitor<V> visitor);
+
+ /**
+ * Traverse this {@link GraphNode} in preorder (see below) and call the visit method of the given
+ * {@link ExceptionThrowingDirectedAcyclicGraphVisitor} at each node. The visitor determines whether the subgraph of
+ * each visited node should also be visited. <strong>Note</strong>: Shared nodes are only visited once.
+ * <p/>
+ * Preorder traversal visits the node and then visits, in preorder, each subgraph of the node.
+ *
+ * @param <E> type of exception possibly thrown
+ * @param visitor a {@link ExceptionThrowingDirectedAcyclicGraphVisitor}
+ * @throws E if an error occurs when visiting the node
+ */
+ <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor) throws E;
+
+ /**
+ * Returns the number of nodes in the subgraph of this node. The subgraph includes the node itself as the only root
+ * node.
+ *
+ * <p />
+ * <strong>Note</strong>: Nodes may be shared and shared nodes are counted only once.
+ *
+ * <p />
+ * If there are more than <tt>Integer.MAX_VALUE</tt> nodes, the return value is undefined and the user should seek
+ * professional help.
+ *
+ * @return the number of nodes in the subgraph
+ */
+ int size();
+
+ /**
+ * Check if this node is a root node (a node without parents).
+ *
+ * @return <code>true</code> if the node has no parents. Otherwise <code>false</code>.
+ */
+ boolean isRootNode();
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
new file mode 100644
index 0000000..7b827c8
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
@@ -0,0 +1,161 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
+ * to each other in a way that it is impossible to start at a node n and follow a child relationship that loops back to
+ * n. The DAG may have multiple root nodes (nodes with no parents) and nodes may share children.
+ * <p />
+ * Once created a root node can become a non-root node by adding the node as a child to another node. This can be done
+ * by calling the method addChild on a node. All nodes of a DAG are reachable from its root nodes.
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * This class is thread safe.
+ *
+ * @param <V> type of values in the graph
+ */
+public class ThreadSafeDirectedAcyclicGraph<V> implements DirectedAcyclicGraph<V> {
+
+ private final Object monitor = new Object();
+
+ private static final Object tieMonitor = new Object();
+
+ private final List<ThreadSafeGraphNode<V>> nodes = new ArrayList<ThreadSafeGraphNode<V>>();
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public ThreadSafeGraphNode<V> createRootNode(V value) {
+ synchronized (this.monitor) {
+ ThreadSafeGraphNode<V> node = new ThreadSafeGraphNode<V>(value, this.monitor);
+ this.nodes.add(node);
+ return node;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean deleteRootNode(GraphNode<V> node) {
+ assertTypeAndMembership(node);
+ synchronized (this.monitor) {
+ Assert.isTrue(node.getChildren().isEmpty(), "Cannot delete node '%s'. Node has children. Please remove the children first.", node);
+ Assert.isTrue(node.getParents().isEmpty(),
+ "Cannot delete node '%s'. Node is still in use. Please remove it from the other node(s) first.", node);
+ boolean removed = this.nodes.remove(node);
+ return removed;
+ }
+ }
+
+ private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
+ Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
+ ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+ Assert.isTrue(concreteChild.belongsToSameGraph(this.monitor), "The node '%s' does not belong to the graph '%s'", concreteChild, this);
+ return concreteChild;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public List<GraphNode<V>> getRootNodes() {
+ List<GraphNode<V>> rootNodes = new ArrayList<GraphNode<V>>();
+ synchronized (this.monitor) {
+ for (GraphNode<V> node : this.nodes) {
+ if (node.isRootNode()) {
+ rootNodes.add(node);
+ }
+ }
+ return rootNodes;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ StringBuffer result = new StringBuffer();
+ result.append("<");
+ synchronized (this.monitor) {
+ boolean first = true;
+ for (GraphNode<V> child : getRootNodes()) {
+ if (!first) {
+ result.append(", ");
+ }
+ result.append(child.toString());
+ first = false;
+ }
+ }
+ result.append(">");
+ return result.toString();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode() {
+ synchronized (this.monitor) {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + this.nodes.hashCode();
+ return result;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
+ if (getClass() != obj.getClass()) {
+ return false;
+ }
+ ThreadSafeDirectedAcyclicGraph<V> other = (ThreadSafeDirectedAcyclicGraph<V>) obj;
+ int thisHash = System.identityHashCode(this);
+ int otherHash = System.identityHashCode(other);
+ if (thisHash < otherHash) {
+ synchronized (this.monitor) {
+ synchronized (other.monitor) {
+ if (!this.nodes.equals(other.nodes)) {
+ return false;
+ }
+ }
+ }
+ } else if (thisHash > otherHash) {
+ synchronized (other.monitor) {
+ synchronized (this.monitor) {
+ if (!this.nodes.equals(other.nodes)) {
+ return false;
+ }
+ }
+ }
+ } else {
+ synchronized (tieMonitor) {
+ synchronized (this.monitor) {
+ synchronized (other.monitor) {
+ if (!this.nodes.equals(other.nodes)) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ return true;
+ }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java
new file mode 100644
index 0000000..7b7a221
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java
@@ -0,0 +1,382 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * {@link GraphNode} is a node in a {@link DirectedAcyclicGraph}. Each node has a value.
+ * <p />
+ *
+ * <strong>Concurrent Semantics</strong><br />
+ *
+ * This class is thread safe.
+ *
+ * @param <V> type of values in the graph
+ */
+class ThreadSafeGraphNode<V> implements GraphNode<V> {
+
+ private final V value;
+
+ private final Object monitor;
+
+ private static final Object tieMonitor = new Object();
+
+ private final List<ThreadSafeGraphNode<V>> children = new ArrayList<ThreadSafeGraphNode<V>>();
+
+ private final List<ThreadSafeGraphNode<V>> parents = new ArrayList<ThreadSafeGraphNode<V>>();
+
+ /**
+ * Construct a {@link ThreadSafeGraphNode} with the given value, which may be <code>null</code>.
+ *
+ * @param value the value of the node, which may be <code>null</code>
+ * @param monitor the shared monitor of the graph
+ */
+ ThreadSafeGraphNode(V value, Object monitor) {
+ this.value = value;
+ this.monitor = monitor;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V getValue() {
+ return this.value;
+ }
+
+ /**
+ * Returns a list of this node's children (not copies of the children). If the node has no children, returns an
+ * empty list. Never returns <code>null</code> .
+ * <p/>
+ * The returned list is synchronized to preserve thread safety, but may still result in
+ * ConcurrentModificationException being thrown.
+ *
+ * @return this node's children
+ */
+ @Override
+ public List<GraphNode<V>> getChildren() {
+ synchronized (this.monitor) {
+ return new SynchronizedList<GraphNode<V>>(this.children, this.monitor);
+ }
+ }
+
+ /**
+ * Adds the given node as child to this node. The child node is <strong>not</strong> copied.
+ *
+ * @param child the node to add
+ * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+ * @throws IllegalArgumentException if the given node is already a child of this node.
+ * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
+ */
+ @Override
+ public void addChild(GraphNode<V> child) {
+ ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
+ synchronized (this.monitor) {
+ Assert.isFalse(this.children.contains(child), "The node '%s' is already a child of '%s'", child, this);
+ doCycleCheck(concreteChild);
+ this.children.add(concreteChild);
+ concreteChild.parents.add(this);
+ }
+ }
+
+ private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
+ Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
+ ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+ Assert.isTrue(belongsToSameGraph(concreteChild), "The node '%s' does not belong to the same graph as '%s'", concreteChild, this);
+ return concreteChild;
+ }
+
+ private boolean belongsToSameGraph(ThreadSafeGraphNode<V> other) {
+ return this.monitor == other.monitor;
+ }
+
+ protected boolean belongsToSameGraph(Object monitor) {
+ return this.monitor == monitor;
+ }
+
+ // check for cycles when adding a new child to a parent (is this node a descendant of the new child?).
+ private void doCycleCheck(GraphNode<V> child) {
+ synchronized (this.monitor) {
+ DescendentChecker<V> descendentChecker = new DescendentChecker<V>(this);
+ child.visit(descendentChecker);
+ Assert.isFalse(descendentChecker.isDescendent(), "Can't add '%s'. This node is a descendent of the new child.", child);
+ }
+ }
+
+ /**
+ * Removes the occurrence of the given node from this node's children. Returns <code>true</code> if the child was
+ * found and removed, otherwise <code>false</code>.
+ *
+ * @param child the node to remove
+ * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+ * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
+ * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+ * @see java.util.List#remove
+ */
+ @Override
+ public boolean removeChild(GraphNode<V> child) {
+ ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
+ synchronized (this.monitor) {
+ boolean removed = this.children.remove(concreteChild);
+ if (removed) {
+ removeParent(child, this);
+ }
+ return removed;
+ }
+ }
+
+ /*
+ * All the children in this.children share this.monitor.
+ */
+ private void removeParent(GraphNode<V> child, GraphNode<V> parent) {
+ synchronized (this.monitor) {
+ if (child instanceof ThreadSafeGraphNode<?>) {
+ ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+ concreteChild.parents.remove(parent);
+ }
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void visit(DirectedAcyclicGraphVisitor<V> visitor) {
+ visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
+ }
+
+ private void visitInternal(DirectedAcyclicGraphVisitor<V> visitor, Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) {
+ if (visitedFlags.containsKey(this)) {
+ return;
+ }
+ visitedFlags.put(this, Boolean.TRUE);
+ if (visitor.visit(this)) {
+ for (int i = 0; i < numChildren(); i++) {
+ ThreadSafeGraphNode<V> nextChild = getChild(i);
+ if (nextChild != null) {
+ nextChild.visitInternal(visitor, visitedFlags);
+ } else {
+ break;
+ }
+ }
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor) throws E {
+ visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
+ }
+
+ private <E extends Exception> void visitInternal(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor,
+ Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) throws E {
+ if (visitedFlags.containsKey(this)) {
+ return;
+ }
+ visitedFlags.put(this, Boolean.TRUE);
+ if (visitor.visit(this)) {
+ for (int i = 0; i < numChildren(); i++) {
+ ThreadSafeGraphNode<V> nextChild = getChild(i);
+ if (nextChild != null) {
+ nextChild.visitInternal(visitor, visitedFlags);
+ } else {
+ break;
+ }
+ }
+ }
+ }
+
+ private ThreadSafeGraphNode<V> getChild(int i) {
+ synchronized (this.monitor) {
+ try {
+ return this.children.get(i);
+ } catch (IndexOutOfBoundsException e) {
+ return null;
+ }
+ }
+ }
+
+ private int numChildren() {
+ synchronized (this.monitor) {
+ return this.children.size();
+ }
+ }
+
+ private static class DescendentChecker<V> implements DirectedAcyclicGraphVisitor<V> {
+
+ private final ThreadSafeGraphNode<V> prospect;
+
+ private boolean descendent = false;
+
+ public DescendentChecker(ThreadSafeGraphNode<V> prospect) {
+ this.prospect = prospect;
+ }
+
+ @Override
+ public boolean visit(GraphNode<V> node) {
+ if (this.descendent) {
+ return false;
+ }
+ if (this.prospect == node) {
+ this.descendent = true;
+ return false;
+ }
+ return true;
+ }
+
+ public boolean isDescendent() {
+ return this.descendent;
+ }
+
+ }
+
+ private static class SizeVisitor<V> implements DirectedAcyclicGraphVisitor<V> {
+
+ private int size;
+
+ @Override
+ public boolean visit(GraphNode<V> dag) {
+ this.size += 1;
+ return true;
+ }
+
+ public int getSize() {
+ return this.size;
+ }
+ };
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int size() {
+ SizeVisitor<V> sizeVisitor = new SizeVisitor<V>();
+ visit(sizeVisitor);
+ return sizeVisitor.getSize();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode() {
+ synchronized (this.monitor) {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + this.children.hashCode();
+ result = prime * result + (this.value == null ? 0 : this.value.hashCode());
+ return result;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ // TODO TSGN.equals regards nodes as equal which have different sets of parents.
+ // TODO TSGN.equals regards distinct nodes with no children (no parents once the todo above is fixed) and the same
+ // value as equal. These nodes were created separately, possibly even from distinct DAGs as currently coded.
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
+ if (getClass() != obj.getClass()) {
+ return false;
+ }
+ ThreadSafeGraphNode<V> other = (ThreadSafeGraphNode<V>) obj;
+ int thisHash = System.identityHashCode(this);
+ int otherHash = System.identityHashCode(other);
+ if (thisHash < otherHash) {
+ synchronized (this.monitor) {
+ synchronized (other.monitor) {
+ if (!this.children.equals(other.children)) {
+ return false;
+ }
+ }
+ }
+ } else if (thisHash > otherHash) {
+ synchronized (other.monitor) {
+ synchronized (this.monitor) {
+ if (!this.children.equals(other.children)) {
+ return false;
+ }
+ }
+ }
+ } else {
+ synchronized (tieMonitor) {
+ synchronized (this.monitor) {
+ synchronized (other.monitor) {
+ if (!this.children.equals(other.children)) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ if (this.value == null) {
+ if (other.value != null) {
+ return false;
+ }
+ } else if (!this.value.equals(other.value)) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString() {
+ StringBuffer result = new StringBuffer();
+ result.append(this.value != null ? this.value : "null").append("<");
+ synchronized (this.monitor) {
+ boolean first = true;
+ for (ThreadSafeGraphNode<V> child : this.children) {
+ if (!first) {
+ result.append(", ");
+ }
+ result.append(child.toString());
+ first = false;
+ }
+ }
+ result.append(">");
+ return result.toString();
+ }
+
+ /**
+ * Returns a list of this graph's parents (not copies of the parents). If the graph has no parents, returns an empty
+ * list. Never returns <code>null</code> .
+ * <p/>
+ * The returned list is synchronized to preserve thread safety, but may still result in
+ * ConcurrentModificationException being thrown.
+ *
+ * @return this graph's parents
+ */
+ // TODO TSGN.getParents share its monitor with return values of getParents and getChildren. It feels as if the user
+ // might get some surprising deadlocks.
+ @Override
+ public List<GraphNode<V>> getParents() {
+ synchronized (this.monitor) {
+ return new SynchronizedList<GraphNode<V>>(this.parents, this.monitor);
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean isRootNode() {
+ return this.parents.isEmpty();
+ }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
new file mode 100644
index 0000000..69e36f0
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
@@ -0,0 +1,346 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2010 VMware Inc.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VMware Inc. - initial contribution
+ *******************************************************************************/
+
+package org.eclipse.virgo.util.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.concurrent.CyclicBarrier;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class ThreadSafeAcyclicDirectedGraphTests {
+
+ private DirectedAcyclicGraph<String> graph;
+
+ private static DirectedAcyclicGraph<String> getDAG() {
+ return getDAG("We");
+ }
+
+ private static DirectedAcyclicGraph<String> getDAG(String rootValue) {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ // shared nodes
+ GraphNode<String> lo = graph.createRootNode("Lo");
+ GraphNode<String> fi = graph.createRootNode("Fi");
+
+ // We.add(Pa)
+ GraphNode<String> we = graph.createRootNode("We");
+ GraphNode<String> pa = graph.createRootNode("Pa");
+ we.addChild(pa);
+ // Pa.add(Cr)
+ GraphNode<String> cr = graph.createRootNode("Cr");
+ pa.addChild(cr);
+ // Cr.add(B1,Lo,Fi)
+ cr.addChild(graph.createRootNode("B1"));
+ cr.addChild(lo);
+ cr.addChild(fi);
+
+ // Pa.add(Cu)
+ GraphNode<String> cu = graph.createRootNode("Cu");
+ pa.addChild(cu);
+ cu.addChild(graph.createRootNode("B2"));
+ cu.addChild(lo);
+ cu.addChild(fi);
+
+ // Pa.add(B3)
+ pa.addChild(graph.createRootNode("B3"));
+ // Pa.add(Lo)
+ pa.addChild(lo);
+
+ return graph;
+ }
+
+ @Before
+ public void setUp() {
+ this.graph = getDAG();
+ }
+
+ @Test
+ public void testEmptyGraph() throws Exception {
+ DirectedAcyclicGraph<String> emptyGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ assertNotNull(emptyGraph);
+ assertNotNull(emptyGraph.getRootNodes());
+ assertEquals("<>", emptyGraph.toString());
+ assertTrue(emptyGraph.getRootNodes().isEmpty());
+ }
+
+ @Test
+ public void testGraphWithSingleRootNode() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = smallGraph.createRootNode("root");
+
+ assertEquals("<root<>>", smallGraph.toString());
+ assertEquals(1, smallGraph.getRootNodes().size());
+
+ smallGraph.deleteRootNode(rootNode);
+
+ assertEquals(0, smallGraph.getRootNodes().size());
+ }
+
+ @Test
+ public void testGraphWithSingleNullRootNode() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = smallGraph.createRootNode(null);
+
+ assertEquals("<null<>>", smallGraph.toString());
+ assertEquals(1, smallGraph.getRootNodes().size());
+
+ smallGraph.deleteRootNode(rootNode);
+
+ assertEquals(0, smallGraph.getRootNodes().size());
+ }
+
+ @Test
+ public void testGraphWithOnlyChildren() throws Exception {
+ DirectedAcyclicGraph<String> onlyChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = onlyChildGraph.createRootNode("root");
+ assertEquals("<root<>>", onlyChildGraph.toString());
+ assertEquals(1, onlyChildGraph.getRootNodes().size());
+
+ GraphNode<String> child = onlyChildGraph.createRootNode("child");
+ rootNode.addChild(child);
+ assertEquals("<root<child<>>>", onlyChildGraph.toString());
+
+ GraphNode<String> grandchild = onlyChildGraph.createRootNode("grandchild");
+ child.addChild(grandchild);
+ assertEquals("<root<child<grandchild<>>>>", onlyChildGraph.toString());
+ assertEquals(1, onlyChildGraph.getRootNodes().size());
+
+ assertTrue(child.removeChild(grandchild));
+ onlyChildGraph.deleteRootNode(grandchild);
+ assertTrue(rootNode.removeChild(child));
+ onlyChildGraph.deleteRootNode(child);
+ onlyChildGraph.deleteRootNode(rootNode);
+ assertEquals(0, onlyChildGraph.getRootNodes().size());
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDirectCycle() throws Exception {
+ DirectedAcyclicGraph<Integer> smallGraph = new ThreadSafeDirectedAcyclicGraph<Integer>();
+ GraphNode<Integer> root = smallGraph.createRootNode(Integer.valueOf(42));
+
+ root.addChild(root);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testParentNodeIsNotADescendantOfTheNewChild() throws Exception {
+ DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> rootNode = dag.createRootNode("root");
+ GraphNode<String> child = dag.createRootNode("child");
+
+ rootNode.addChild(child);
+ child.addChild(rootNode);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testParentIsNotADescendantOfTheNewChildDistanceTwo() throws Exception {
+ DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> rootNode = dag.createRootNode("root");
+
+ GraphNode<String> child = dag.createRootNode("child");
+ rootNode.addChild(child);
+ GraphNode<String> child2 = dag.createRootNode("child2");
+ rootNode.addChild(child2);
+ GraphNode<String> grandchild = dag.createRootNode("grandchild");
+ child.addChild(grandchild);
+
+ grandchild.addChild(rootNode);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDeleteRootNodeFromOtherGraph() {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+
+ this.graph.deleteRootNode(r1);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDeleteRootNodeOfWrongType() {
+ this.graph.deleteRootNode(new ThreadSafeGraphNodeTests.NoopGraphNode());
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDeleteRootNodeWithChildren() {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+ GraphNode<String> c1 = smallGraph.createRootNode("C1");
+ r1.addChild(c1);
+
+ this.graph.deleteRootNode(r1);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDeleteNonRootNode() {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+ GraphNode<String> c1 = smallGraph.createRootNode("C1");
+ r1.addChild(c1);
+
+ this.graph.deleteRootNode(c1);
+ }
+
+ @Test
+ public void testAddSharedChildWithMultipleThreads() throws Exception {
+
+ final DirectedAcyclicGraph<String> sharedChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ final int THREAD_COUNT = 150;
+ final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
+ final GraphNode<String> sharedChild = sharedChildGraph.createRootNode("shared child");
+ assertEquals(0, sharedChild.getParents().size());
+ assertEquals(1, sharedChildGraph.getRootNodes().size());
+
+ class AddChildThread extends Thread {
+
+ private final int counter;
+
+ public AddChildThread(int counter) {
+ this.counter = counter;
+ }
+
+ @Override
+ public void run() {
+ try {
+ barrier.await(); // 1
+ GraphNode<String> root = sharedChildGraph.createRootNode("root" + this.counter);
+ root.addChild(sharedChild);
+ barrier.await(); // 2
+ barrier.await();
+ assertTrue(root.removeChild(sharedChild));
+ barrier.await(); // 3
+ barrier.await();
+ sharedChildGraph.deleteRootNode(root);
+ barrier.await();
+ } catch (Exception e) {
+ fail();
+ }
+ }
+ }
+
+ for (int i = 0; i < THREAD_COUNT; i++) {
+ new AddChildThread(i).start();
+ }
+ barrier.await(); // 1 - wait for all threads to be ready
+ barrier.await(); // 2 - wait for all threads to create and add the nodes
+ assertEquals(THREAD_COUNT, sharedChild.getParents().size());
+ assertEquals(THREAD_COUNT, sharedChildGraph.getRootNodes().size());
+ barrier.await(); //
+ barrier.await(); // 3 - wait for all threads to be finish
+ assertEquals(0, sharedChild.getParents().size());
+ assertEquals(THREAD_COUNT + 1, sharedChildGraph.getRootNodes().size());
+ barrier.await(); // wait for all threads to be finish
+ assertEquals(0, sharedChild.getParents().size());
+ }
+
+ @Test
+ public void testGraphWithSharedNodes() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+ GraphNode<String> c1 = smallGraph.createRootNode("C1");
+ GraphNode<String> c2 = smallGraph.createRootNode("C2");
+ smallGraph.createRootNode("C3");
+ assertEquals(4, smallGraph.getRootNodes().size());
+ assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
+
+ r1.addChild(c1);
+ assertEquals(3, smallGraph.getRootNodes().size());
+ r1.addChild(c2);
+ assertEquals(2, smallGraph.getRootNodes().size());
+ assertEquals("<R1<C1<>, C2<>>, C3<>>", smallGraph.toString());
+
+ GraphNode<String> r2 = smallGraph.createRootNode("R2");
+ assertEquals(3, smallGraph.getRootNodes().size());
+ assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
+
+ r2.addChild(c1);
+ assertEquals(3, smallGraph.getRootNodes().size());
+ assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
+ }
+
+ @Test
+ public void testDisassembleGraphWithSharedNodes() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+ GraphNode<String> c1 = smallGraph.createRootNode("C1");
+ GraphNode<String> c2 = smallGraph.createRootNode("C2");
+ GraphNode<String> c3 = smallGraph.createRootNode("C3");
+ r1.addChild(c1);
+ r1.addChild(c2);
+ GraphNode<String> r2 = smallGraph.createRootNode("R2");
+ r2.addChild(c1);
+ assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
+ assertEquals(3, smallGraph.getRootNodes().size());
+
+ // remove shared node
+ assertTrue(r2.removeChild(c1));
+ assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
+ assertEquals(3, smallGraph.getRootNodes().size());
+ assertTrue(r1.removeChild(c2));
+ assertEquals(4, smallGraph.getRootNodes().size());
+ assertTrue(r1.removeChild(c1));
+ assertEquals(5, smallGraph.getRootNodes().size());
+ assertEquals("<R1<>, C1<>, C2<>, C3<>, R2<>>", smallGraph.toString());
+ assertTrue(smallGraph.deleteRootNode(r2));
+ assertEquals(4, smallGraph.getRootNodes().size());
+ assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
+ assertTrue(smallGraph.deleteRootNode(r1));
+ assertEquals(3, smallGraph.getRootNodes().size());
+ assertEquals("<C1<>, C2<>, C3<>>", smallGraph.toString());
+ smallGraph.deleteRootNode(smallGraph.getRootNodes().get(0));
+ assertEquals(2, smallGraph.getRootNodes().size());
+ assertEquals("<C2<>, C3<>>", smallGraph.toString());
+ assertTrue(smallGraph.deleteRootNode(c2));
+ assertEquals(1, smallGraph.getRootNodes().size());
+ assertTrue(smallGraph.deleteRootNode(c3));
+ assertTrue(smallGraph.getRootNodes().isEmpty());
+ }
+
+ @Test
+ public void testRemovalOfAnAlreadyRemovedRootNode() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createRootNode("R1");
+
+ assertTrue(smallGraph.deleteRootNode(r1));
+
+ assertFalse(smallGraph.deleteRootNode(r1));
+ }
+
+ @Test
+ public void testHashCodeEquals() {
+ assertFalse(this.graph.equals(null));
+
+ assertFalse(this.graph.equals(new Object()));
+
+ DirectedAcyclicGraph<String> graph2 = getDAG();
+ assertEquals(this.graph.hashCode(), graph2.hashCode());
+ assertEquals(this.graph, this.graph);
+ assertEquals(graph2, this.graph);
+ assertEquals(this.graph, graph2);
+
+ DirectedAcyclicGraph<String> g1 = new ThreadSafeDirectedAcyclicGraph<String>();
+ assertFalse(this.graph.equals(g1));
+ assertFalse(g1.equals(this.graph));
+
+ assertTrue(new ThreadSafeDirectedAcyclicGraph<String>().equals(new ThreadSafeDirectedAcyclicGraph<String>()));
+ }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
new file mode 100644
index 0000000..8c9dc76
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
@@ -0,0 +1,601 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2010 VMware Inc.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VMware Inc. - initial contribution
+ *******************************************************************************/
+
+package org.eclipse.virgo.util.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.CyclicBarrier;
+
+import org.eclipse.virgo.util.common.GraphNode.DirectedAcyclicGraphVisitor;
+import org.eclipse.virgo.util.common.GraphNode.ExceptionThrowingDirectedAcyclicGraphVisitor;
+import org.junit.Test;
+
+public class ThreadSafeGraphNodeTests {
+
+ private static void add(List<String> l, String... s) {
+ for (String string : s) {
+ l.add(string);
+ }
+ }
+
+ private static final List<String> EXPECTED_VISITS = new ArrayList<String>();
+
+ static {
+ add(EXPECTED_VISITS, "We", "Pa", "Cr", "B1", "Lo", "Fi", "Cu", "B2", "B3");
+ }
+
+ private GraphNode<String> buildTestGraphAndReturnRootNode() {
+ return buildTestGraphAndReturnRootNode(new ThreadSafeDirectedAcyclicGraph<String>());
+ }
+
+ private GraphNode<String> buildTestGraphAndReturnRootNode(DirectedAcyclicGraph<String> graph) {
+ return buildTestGraphAndReturnRootNode(graph, "We");
+ }
+
+ private GraphNode<String> buildTestGraphAndReturnRootNode(DirectedAcyclicGraph<String> graph, String rootValue) {
+ GraphNode<String> top = graph.createRootNode(rootValue);
+
+ // shared nodes
+ GraphNode<String> lo = graph.createRootNode("Lo");
+ GraphNode<String> fi = graph.createRootNode("Fi");
+
+ // We.add(Pa)
+ top.addChild(graph.createRootNode("Pa"));
+ GraphNode<String> pa = top.getChildren().get(0);
+ // Pa.add(Cr)
+ pa.addChild(graph.createRootNode("Cr"));
+ GraphNode<String> cr = pa.getChildren().get(0);
+ cr.addChild(graph.createRootNode("B1"));
+ cr.addChild(lo);
+ cr.addChild(fi);
+
+ // Pa.add(Cu)
+ pa.addChild(graph.createRootNode("Cu"));
+ GraphNode<String> cu = pa.getChildren().get(1);
+ cu.addChild(graph.createRootNode("B2"));
+ cu.addChild(lo);
+ cu.addChild(fi);
+
+ // Pa.add(B3)
+ pa.addChild(graph.createRootNode("B3"));
+ // Pa.add(Lo)
+ pa.addChild(lo);
+
+ return top;
+ }
+
+ private GraphNode<String> addFluffyToGraph(DirectedAcyclicGraph<String> graph) {
+ GraphNode<String> body = graph.createRootNode("Fluffy's body");
+ for (int i = 0; i < 3; i++) {
+ GraphNode<String> head = graph.createRootNode("head " + i);
+ head.addChild(body);
+ }
+ return body;
+ }
+
+ @Test
+ public void testEmptyNode() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> nullGraph = graph.createRootNode(null);
+
+ assertNull(nullGraph.getValue());
+ assertEquals("null<>", nullGraph.toString());
+ }
+
+ @Test
+ public void testDepthTwo() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> root = graph.createRootNode("root");
+
+ root.addChild(graph.createRootNode("C1"));
+ root.addChild(graph.createRootNode("C2"));
+
+ assertEquals("root<C1<>, C2<>>", root.toString());
+ }
+
+ @Test
+ public void testDepthThree() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> we = graph.createRootNode("We");
+ GraphNode<String> pa = graph.createRootNode("Pa");
+ GraphNode<String> cr = graph.createRootNode("Cr");
+
+ we.addChild(pa);
+ pa.addChild(cr);
+
+ assertEquals("We<Pa<Cr<>>>", we.toString());
+ }
+
+ @Test
+ public void testToString() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ assertEquals("null<>", graph.createRootNode(null).toString());
+
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ assertEquals("We<Pa<Cr<B1<>, Lo<>, Fi<>>, Cu<B2<>, Lo<>, Fi<>>, B3<>, Lo<>>>", top.toString());
+ }
+
+ @Test
+ public void testHashCodeEquals() {
+ DirectedAcyclicGraph<String> graphA = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> topA = graphA.createRootNode("root");
+
+ assertFalse(topA.equals(null));
+ assertFalse(topA.equals(new Object()));
+
+ DirectedAcyclicGraph<String> graphB = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> topB = graphB.createRootNode("root");
+
+ assertEquals(topA.hashCode(), topB.hashCode());
+ assertEquals(topB.hashCode(), topA.hashCode());
+
+ assertEquals(topA, topB);
+ assertEquals(topB, topA);
+
+ GraphNode<String> t1 = graphA.createRootNode("a");
+ {
+ GraphNode<String> a = t1;
+ assertFalse(topA.equals(a));
+ assertFalse(a.equals(topA));
+ }
+
+ {
+ GraphNode<String> a = graphA.createRootNode(null);
+ a.hashCode();
+ assertFalse(topA.equals(a));
+ assertFalse(a.equals(topA));
+ }
+
+ assertTrue(graphA.createRootNode(null).equals(graphA.createRootNode(null)));
+ assertFalse(graphA.createRootNode(null).equals(graphA.createRootNode("a")));
+ assertFalse(graphA.createRootNode("a").equals(graphA.createRootNode(null)));
+
+ GraphNode<String> t2 = graphA.createRootNode("b");
+ assertFalse(t1.equals(t2));
+ assertFalse(t2.equals(t1));
+ }
+
+ @Test
+ public void testSize() {
+ GraphNode<String> top = buildTestGraphAndReturnRootNode();
+
+ // (+1) Web shop application
+ // (+1) Payment application
+ // (+1) Credit card application
+ // (+3) B1, Logging Bundle, Financial Utils (Lo and Fi first time)
+ // (+1) Currency conversion application
+ // (+1) B2, Logging Bundle, Financial Utils (B2 only)
+ // (+1) B3
+ // (+0) Logging Bundle
+ assertEquals(9, top.size());
+ }
+
+ @Test
+ public void testSizeWithNullNodes() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> graphWithNullNodes = graph.createRootNode("with null values");
+ assertEquals(1, graphWithNullNodes.size());
+
+ graphWithNullNodes.addChild(graph.createRootNode("first"));
+ assertEquals(2, graphWithNullNodes.size());
+
+ graphWithNullNodes.addChild(graph.createRootNode(null));
+ assertEquals(3, graphWithNullNodes.size());
+
+ graphWithNullNodes.addChild(graph.createRootNode("third"));
+ assertEquals(4, graphWithNullNodes.size());
+ }
+
+ @Test
+ public void testSizeWithMultipleRoots() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> fluffy = addFluffyToGraph(graph);
+
+ assertEquals(1, fluffy.size());
+
+ List<GraphNode<String>> parents = fluffy.getParents();
+ for (GraphNode<String> parent : parents) {
+ assertEquals(2, parent.size());
+ }
+ }
+
+ @Test
+ public void testChildren() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ List<GraphNode<String>> children = top.getChildren();
+ assertEquals(1, children.size());
+ GraphNode<String> newChild = graph.createRootNode("newChild");
+
+ top.addChild(newChild);
+ assertEquals(2, children.size());
+ assertEquals(newChild, children.get(1));
+ }
+
+ @Test
+ public void testDAGWithNoChilds() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> solo = graph.createRootNode("solo");
+
+ assertNotNull(solo.getChildren());
+ assertTrue(solo.getChildren().isEmpty());
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testInstanceOfChild() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> child = new NoopGraphNode();
+
+ graph.createRootNode("foo").addChild(child);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDuplicateInsertionOfAChild() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ buildTestGraphAndReturnRootNode(graph);
+
+ GraphNode<String> node = graph.getRootNodes().get(0);
+ GraphNode<String> child = graph.createRootNode("child");
+
+ node.addChild(child);
+ node.addChild(child);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testAddChildFromOtherDAG() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+
+ top.addChild(alienNode);
+ }
+
+ @Test
+ public void testAddSharedChild() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> cr = graph.createRootNode("cr");
+ GraphNode<String> cu = graph.createRootNode("cu");
+ GraphNode<String> lo = graph.createRootNode("lo");
+
+ cr.addChild(lo);
+ cu.addChild(lo);
+
+ assertEquals(2, lo.getParents().size());
+ assertTrue(lo.getParents().contains(cr));
+ assertTrue(lo.getParents().contains(cu));
+
+ // Ensure parents are correctly set up in both root nodes.
+ checkParents(Collections.singletonList(cr));
+ checkParents(Collections.singletonList(cu));
+ }
+
+ @Test
+ public void testAddSharedChildWithMultipleThreads() throws Exception {
+
+ final int THREAD_COUNT = 150;
+ final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
+ final DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ final GraphNode<String> sharedChild = graph.createRootNode("shared child");
+
+ class AddChildThread extends Thread {
+
+ private final int counter;
+
+ public AddChildThread(int counter) {
+ this.counter = counter;
+ }
+
+ @Override
+ public void run() {
+ try {
+ barrier.await();
+ GraphNode<String> root = graph.createRootNode("root" + this.counter);
+ root.addChild(sharedChild);
+ barrier.await();
+ } catch (Exception e) {
+ fail();
+ }
+ }
+ }
+
+ for (int i = 0; i < THREAD_COUNT; i++) {
+ new AddChildThread(i).start();
+ }
+ barrier.await(); // wait for all threads to be ready
+ barrier.await(); // wait for all threads to be finish
+
+ assertEquals(THREAD_COUNT, sharedChild.getParents().size());
+ }
+
+ private void checkParents(List<GraphNode<String>> parents) {
+ for (GraphNode<String> parent : parents) {
+ List<GraphNode<String>> children = parent.getChildren();
+ for (GraphNode<String> child : children) {
+ assertTrue(child.getParents().contains(parent));
+ checkParents(Collections.singletonList(child));
+ }
+ }
+ }
+
+ @Test
+ public void testChildrenListModification() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ List<GraphNode<String>> children = top.getChildren();
+ assertEquals(1, children.size());
+
+ GraphNode<String> newChild = buildTestGraphAndReturnRootNode(graph, "newChild");
+ children.add(newChild);
+ assertEquals(2, children.size());
+ assertEquals(newChild, children.get(1));
+ }
+
+ @Test
+ public void testGetValue() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ assertEquals("We", top.getValue());
+ }
+
+ @Test
+ public void testRemoveChild() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ List<GraphNode<String>> children = top.getChildren();
+ assertTrue(top.removeChild(children.get(0)));
+
+ assertEquals(1, top.size());
+ assertFalse(top.removeChild(buildTestGraphAndReturnRootNode(graph, "unknownChild")));
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testRemoveWrongInstanceOfChild() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> child = new NoopGraphNode();
+
+ graph.createRootNode("foo").removeChild(child);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testRemoveChildFromOtherDAG() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+
+ top.removeChild(alienNode);
+ }
+
+ @Test
+ public void testParent() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ List<GraphNode<String>> children = top.getChildren();
+ assertNotNull(top.getParents());
+ assertTrue(top.getParents().isEmpty());
+
+ GraphNode<String> child = children.get(0);
+ assertEquals(Collections.singletonList(top), child.getParents());
+ assertSame(top, child.getParents().get(0));
+
+ top.removeChild(child);
+ assertNotNull(child.getParents());
+ assertTrue(child.getParents().isEmpty());
+ }
+
+ @Test
+ public void testNormalVisit() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+ top.visit(visitor);
+ assertTrue(EXPECTED_VISITS.equals(visitor.getVisited()));
+ }
+
+ @Test
+ public void testSkippedVisit() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+ GraphNode<String> t = graph.createRootNode("-");
+ t.visit(visitor);
+ List<String> visited = visitor.getVisited();
+
+ assertEquals(1, visited.size());
+ assertEquals("-", visited.get(0));
+ }
+
+ @Test
+ public void testPartiallySkippedVisit() {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+ top.addChild(graph.createRootNode("-"));
+ GraphNode<String> t = top.getChildren().get(1);
+ t.addChild(graph.createRootNode("foo"));
+ t.addChild(graph.createRootNode("bar"));
+ assertEquals(12, top.size());
+
+ top.visit(visitor);
+
+ assertEquals(10, visitor.getVisited().size());
+ }
+
+ @Test
+ public void testNormalExceptionVisit() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+ top.visit(visitor);
+
+ assertEquals(EXPECTED_VISITS, visitor.getVisited());
+ }
+
+ @Test
+ public void testSkippedExceptionVisit() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+ GraphNode<String> t = graph.createRootNode("-");
+ t.visit(visitor);
+
+ List<String> visited = visitor.getVisited();
+ assertEquals(1, visited.size());
+ assertEquals("-", visited.get(0));
+ }
+
+ @Test
+ public void testPartiallySkippedDueToStopExceptionVisit() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+ top.addChild(graph.createRootNode("-"));
+ GraphNode<String> t = top.getChildren().get(1);
+ t.addChild(graph.createRootNode("foo"));
+ t.addChild(graph.createRootNode("bar"));
+ assertEquals(12, top.size());
+
+ top.visit(visitor);
+
+ assertEquals(10, visitor.getVisited().size());
+ }
+
+ @Test(expected = Exception.class)
+ public void testPartiallySkippedDueToExceptionExceptionVisit() throws Exception {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+ TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+ top.addChild(graph.createRootNode("*"));
+ GraphNode<String> t = top.getChildren().get(1);
+ t.addChild(graph.createRootNode("foo"));
+ t.addChild(graph.createRootNode("bar"));
+
+ assertEquals(12, top.size());
+ try {
+ top.visit(visitor);
+ } finally {
+ assertEquals(10, visitor.getVisited().size());
+ }
+ }
+
+ private static class TestDirectedAcyclicGraphVisitor implements DirectedAcyclicGraphVisitor<String> {
+
+ private final List<String> visited = new ArrayList<String>();
+
+ @Override
+ public boolean visit(GraphNode<String> dag) {
+ String value = dag.getValue();
+ this.visited.add(value);
+ return !value.startsWith("-");
+ }
+
+ public List<String> getVisited() {
+ return this.visited;
+ }
+ }
+
+ private static class TestExceptionThrowingDirectedAcyclicGraphVisitor implements ExceptionThrowingDirectedAcyclicGraphVisitor<String, Exception> {
+
+ private final List<String> visited = new ArrayList<String>();
+
+ @Override
+ public boolean visit(GraphNode<String> dag) throws Exception {
+ String value = dag.getValue();
+ this.visited.add(value);
+ if (value.startsWith("*")) {
+ throw new Exception();
+ }
+ return !value.startsWith("-");
+ }
+
+ public List<String> getVisited() {
+ return this.visited;
+ }
+ }
+
+ protected static class NoopGraphNode implements GraphNode<String> {
+
+ @Override
+ public void visit(DirectedAcyclicGraphVisitor<String> visitor) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<String, E> visitor) throws E {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void addChild(GraphNode<String> child) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public int size() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean removeChild(GraphNode<String> child) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public List<GraphNode<String>> getChildren() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public List<GraphNode<String>> getParents() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public String getValue() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean isRootNode() {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+}