You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cayenne.apache.org by aa...@apache.org on 2015/11/16 21:07:03 UTC
cayenne git commit: modernizing syntax, no change
Repository: cayenne
Updated Branches:
refs/heads/master 46aee4828 -> d252bf37b
modernizing syntax, no change
Project: http://git-wip-us.apache.org/repos/asf/cayenne/repo
Commit: http://git-wip-us.apache.org/repos/asf/cayenne/commit/d252bf37
Tree: http://git-wip-us.apache.org/repos/asf/cayenne/tree/d252bf37
Diff: http://git-wip-us.apache.org/repos/asf/cayenne/diff/d252bf37
Branch: refs/heads/master
Commit: d252bf37bfb4a0149ae8b72bf438fe55ad9427c1
Parents: 46aee48
Author: aadamchik <aa...@apache.org>
Authored: Mon Nov 16 14:33:40 2015 -0500
Committer: aadamchik <aa...@apache.org>
Committed: Mon Nov 16 15:06:49 2015 -0500
----------------------------------------------------------------------
.../cayenne/ashwood/graph/DepthFirstSearch.java | 76 +-
.../ashwood/graph/DepthFirstStampSearch.java | 97 ++-
.../cayenne/ashwood/graph/MapDigraph.java | 697 ++++++++++---------
.../cayenne/ashwood/graph/StrongConnection.java | 320 ++++-----
4 files changed, 612 insertions(+), 578 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cayenne/blob/d252bf37/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstSearch.java
----------------------------------------------------------------------
diff --git a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstSearch.java b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstSearch.java
index 6806e20..9aecb1e 100644
--- a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstSearch.java
+++ b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstSearch.java
@@ -70,45 +70,51 @@ import org.apache.commons.collections.ArrayStack;
*/
public class DepthFirstSearch<E> implements Iterator<E> {
- protected DigraphIteration<E, ?> factory;
- protected E firstVertex;
+ protected DigraphIteration<E, ?> factory;
+ protected E firstVertex;
+ protected ArrayStack stack;
+ protected Set<E> seen;
- protected ArrayStack stack = new ArrayStack();
- protected Set<E> seen = new HashSet<E>();
+ public DepthFirstSearch(DigraphIteration<E, ?> factory, E firstVertex) {
- public DepthFirstSearch(DigraphIteration<E, ?> factory, E firstVertex) {
- this.factory = factory;
- this.firstVertex = firstVertex;
- stack.push(factory.outgoingIterator(firstVertex));
- seen.add(firstVertex);
- }
+ this.stack = new ArrayStack();
+ this.seen = new HashSet<>();
+ this.factory = factory;
+ this.firstVertex = firstVertex;
- public void reset(E newFirstVertex) {
- stack.clear();
- seen.clear();
- firstVertex = newFirstVertex;
- stack.push(factory.outgoingIterator(firstVertex));
- seen.add(firstVertex);
- }
+ stack.push(factory.outgoingIterator(firstVertex));
+ seen.add(firstVertex);
+ }
- public boolean hasNext() {
- return !stack.isEmpty();
- }
+ public void reset(E newFirstVertex) {
+ stack.clear();
+ seen.clear();
+ firstVertex = newFirstVertex;
+ stack.push(factory.outgoingIterator(firstVertex));
+ seen.add(firstVertex);
+ }
- public E next() {
- ArcIterator<E, ?> i = (ArcIterator<E, ?>) stack.pop();
- Object origin = i.getOrigin();
- while (i.hasNext()) {
- i.next();
- E dst = i.getDestination();
- if (seen.add(dst)) {
- stack.push(factory.outgoingIterator(dst));
- }
- }
- return (E) origin;
- }
+ @Override
+ public boolean hasNext() {
+ return !stack.isEmpty();
+ }
- public void remove() {
- throw new UnsupportedOperationException("Method remove() not supported.");
- }
+ @Override
+ public E next() {
+ ArcIterator<E, ?> i = (ArcIterator<E, ?>) stack.pop();
+ E origin = i.getOrigin();
+ while (i.hasNext()) {
+ i.next();
+ E dst = i.getDestination();
+ if (seen.add(dst)) {
+ stack.push(factory.outgoingIterator(dst));
+ }
+ }
+ return origin;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("Method remove() not supported.");
+ }
}
http://git-wip-us.apache.org/repos/asf/cayenne/blob/d252bf37/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstStampSearch.java
----------------------------------------------------------------------
diff --git a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstStampSearch.java b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstStampSearch.java
index f4060a0..cc8321e 100644
--- a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstStampSearch.java
+++ b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/DepthFirstStampSearch.java
@@ -64,58 +64,55 @@ package org.apache.cayenne.ashwood.graph;
*/
public class DepthFirstStampSearch<E> extends DepthFirstSearch<E> {
- public static final int UNDEFINED_STAMP = -1;
- public static final int GROW_DEPTH_STAMP = 0;
- public static final int GROW_BREADTH_STAMP = 1;
- public static final int SHRINK_STAMP = 2;
- public static final int LEAF_STAMP = 3;
+ public static final int UNDEFINED_STAMP = -1;
+ public static final int GROW_DEPTH_STAMP = 0;
+ public static final int GROW_BREADTH_STAMP = 1;
+ public static final int SHRINK_STAMP = 2;
+ public static final int LEAF_STAMP = 3;
- private int stamp = UNDEFINED_STAMP;
+ private int stamp = UNDEFINED_STAMP;
- public DepthFirstStampSearch(DigraphIteration<E, ?> factory, E firstVertex) {
- super(factory, firstVertex);
- }
+ public DepthFirstStampSearch(DigraphIteration<E, ?> factory, E firstVertex) {
+ super(factory, firstVertex);
+ }
- public int getStamp() {
- return stamp;
- }
+ public int getStamp() {
+ return stamp;
+ }
- @Override
- public E next() {
- ArcIterator<E, ?> i = (ArcIterator<E, ?>) stack.peek();
- E origin = i.getOrigin();
- E dst = i.getDestination();
- if (dst == null) {
- if (i.hasNext()) {
- i.next();
- dst = i.getDestination();
- }
- else {
- stack.pop();
- // shrink
- stamp = LEAF_STAMP;
- return origin;
- }
- }
- if (seen.add(dst)) {
- stack.push(factory.outgoingIterator(dst));
- // grow depth
- stamp = GROW_DEPTH_STAMP;
- if (i.hasNext())
- i.next();
- }
- else {
- if (i.hasNext()) {
- i.next();
- // grow breadth
- stamp = GROW_BREADTH_STAMP;
- }
- else {
- stack.pop();
- // shrink
- stamp = SHRINK_STAMP;
- }
- }
- return origin;
- }
+ @Override
+ public E next() {
+ ArcIterator<E, ?> i = (ArcIterator<E, ?>) stack.peek();
+ E origin = i.getOrigin();
+ E dst = i.getDestination();
+ if (dst == null) {
+ if (i.hasNext()) {
+ i.next();
+ dst = i.getDestination();
+ } else {
+ stack.pop();
+ // shrink
+ stamp = LEAF_STAMP;
+ return origin;
+ }
+ }
+ if (seen.add(dst)) {
+ stack.push(factory.outgoingIterator(dst));
+ // grow depth
+ stamp = GROW_DEPTH_STAMP;
+ if (i.hasNext())
+ i.next();
+ } else {
+ if (i.hasNext()) {
+ i.next();
+ // grow breadth
+ stamp = GROW_BREADTH_STAMP;
+ } else {
+ stack.pop();
+ // shrink
+ stamp = SHRINK_STAMP;
+ }
+ }
+ return origin;
+ }
}
http://git-wip-us.apache.org/repos/asf/cayenne/blob/d252bf37/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/MapDigraph.java
----------------------------------------------------------------------
diff --git a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/MapDigraph.java b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/MapDigraph.java
index d477187..2402261 100644
--- a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/MapDigraph.java
+++ b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/MapDigraph.java
@@ -70,338 +70,369 @@ import java.util.Map.Entry;
*/
public class MapDigraph<E, V> implements Digraph<E, V> {
- private Map<E, Map<E, V>> graph;
- private int size;
-
- public MapDigraph() {
- graph = new HashMap<E, Map<E, V>>();
- }
-
- public boolean addVertex(E vertex) {
- if (graph.containsKey(vertex)) {
- return false;
- }
-
- graph.put(vertex, new HashMap<E, V>());
- return true;
- }
-
- public boolean addAllVertices(Collection<? extends E> vertices) {
- if (graph.keySet().containsAll(vertices)) {
- return false;
- }
-
- for (E vertex : vertices) {
- addVertex(vertex);
- }
-
- return true;
- }
-
- public V putArc(E origin, E destination, V arc) {
- Map<E, V> destinations = graph.get(origin);
- if (destinations == null) {
- destinations = new HashMap<E, V>();
- graph.put(origin, destinations);
- }
-
- addVertex(destination);
- V oldArc = destinations.put(destination, arc);
- if (oldArc == null) {
- size++;
- }
-
- return oldArc;
- }
-
- public V getArc(Object origin, Object destination) {
- Map<E, V> destinations = graph.get(origin);
- if (destinations == null) {
- return null;
- }
-
- return destinations.get(destination);
- }
-
- public boolean removeVertex(E vertex) {
- Map<E, V> destination = graph.remove(vertex);
- if (destination != null)
- size -= destination.size();
- else
- return false;
-
- removeIncoming(vertex);
- return true;
- }
-
- public boolean removeAllVertices(Collection<? extends E> vertices) {
- boolean modified = false;
-
- for (E vertex : vertices) {
- modified |= removeVertex(vertex);
- }
-
- return modified;
- }
-
- public Object removeArc(E origin, E destination) {
- Map<E, V> destinations = graph.get(origin);
- if (destinations == null) {
- return null;
- }
-
- V arc = destinations.remove(destination);
- if (arc != null)
- size--;
-
- return arc;
- }
-
- public boolean removeIncoming(E vertex) {
- boolean modified = false;
-
- for (Map<E, V> destinations : graph.values()) {
- Object arc = destinations.remove(vertex);
- if (arc != null)
- size--;
- modified |= (arc != null);
- }
-
- return modified;
- }
-
- public boolean removeOutgoing(E vertex) {
-
- Map<E, V> destinations = graph.remove(vertex);
- if (destinations != null)
- size -= destinations.size();
- else
- return false;
- boolean modified = !destinations.isEmpty();
- destinations.clear();
- return modified;
- }
-
- public Iterator<E> vertexIterator() {
- return graph.keySet().iterator();
- }
-
- public ArcIterator<E, V> arcIterator() {
- return new AllArcIterator();
- }
-
- public ArcIterator<E, V> outgoingIterator(E vertex) {
- if (!containsVertex(vertex)) {
- return ArcIterator.EMPTY_ITERATOR;
- }
-
- return new OutgoingArcIterator(vertex);
- }
-
- public ArcIterator<E, V> incomingIterator(E vertex) {
- if (!containsVertex(vertex))
- return ArcIterator.EMPTY_ITERATOR;
- return new IncomingArcIterator(vertex);
- }
-
- public int order() {
- return graph.size();
- }
-
- public int size() {
- return size;
- }
-
- public int outgoingSize(E vertex) {
- Map<E, V> destinations = graph.get(vertex);
- if (destinations == null)
- return 0;
- else
- return destinations.size();
- }
-
- public int incomingSize(E vertex) {
- int count = 0;
- if (!graph.containsKey(vertex))
- return 0;
-
- for (Map<E, V> destinations : graph.values()) {
- count += (destinations.containsKey(vertex) ? 1 : 0);
- }
-
- return count;
- }
-
- public boolean containsVertex(E vertex) {
- return graph.containsKey(vertex);
- }
-
- public boolean containsAllVertices(Collection<? extends E> vertices) {
- return graph.keySet().containsAll(vertices);
- }
-
- public boolean hasArc(E origin, E destination) {
- Map<E, V> destinations = graph.get(origin);
- if (destinations == null)
- return false;
- return destinations.containsKey(destination);
- }
-
- public boolean isEmpty() {
- return graph.isEmpty();
- }
-
- public boolean isOutgoingEmpty(E vertex) {
- return outgoingSize(vertex) == 0;
- }
-
- public boolean isIncomingEmpty(E vertex) {
- return incomingSize(vertex) == 0;
- }
-
- private class AllArcIterator implements ArcIterator<E, V> {
-
- private Iterator<Entry<E, Map<E, V>>> originIterator;
- private Iterator<Entry<E, V>> destinationIterator;
- private E origin, nextOrigin;
- private E destination, nextDst;
- private V arc, nextArc;
-
- private AllArcIterator() {
- originIterator = graph.entrySet().iterator();
- next();
- }
-
- public E getOrigin() {
- return origin;
- }
-
- public E getDestination() {
- return destination;
- }
-
- public boolean hasNext() {
- return nextArc != null;
- }
-
- public V next() {
- origin = nextOrigin;
- destination = nextDst;
- arc = nextArc;
- if (destinationIterator == null || !destinationIterator.hasNext()) {
- nextOrigin = null;
- nextDst = null;
- nextArc = null;
-
- while (originIterator.hasNext()) {
- Entry<E, Map<E, V>> entry = originIterator.next();
- destinationIterator = entry.getValue().entrySet().iterator();
- if (destinationIterator.hasNext()) {
- nextOrigin = entry.getKey();
- Entry<E, V> entry1 = destinationIterator.next();
- nextDst = entry1.getKey();
- nextArc = entry1.getValue();
- break;
- }
- }
- }
- else {
- Entry<E, V> entry1 = destinationIterator.next();
- nextDst = entry1.getKey();
- nextArc = entry1.getValue();
- }
-
- return arc;
- }
-
- public void remove() {
- throw new UnsupportedOperationException(
- "Method remove() not yet implemented.");
- }
- }
-
- private class OutgoingArcIterator implements ArcIterator<E, V> {
-
- private E origin;
- private Iterator<Entry<E, V>> dstIt;
- private Entry<E, V> entry;
-
- private OutgoingArcIterator(E vertex) {
- origin = vertex;
- dstIt = graph.get(vertex).entrySet().iterator();
- }
-
- public E getOrigin() {
- return origin;
- }
-
- public E getDestination() {
- if (entry == null)
- return null;
- return entry.getKey();
- }
-
- public boolean hasNext() {
- return dstIt.hasNext();
- }
-
- public V next() {
- entry = dstIt.next();
- return entry.getValue();
- }
-
- public void remove() {
- throw new UnsupportedOperationException(
- "Method remove() not yet implemented.");
- }
- }
-
- private class IncomingArcIterator implements ArcIterator<E, V> {
-
- private E dst;
- private E origin, nextOrigin;
- private V arc, nextArc;
- private Iterator<Entry<E, Map<E, V>>> graphIt;
-
- private IncomingArcIterator(E vertex) {
- dst = vertex;
- graphIt = graph.entrySet().iterator();
- next();
- }
-
- public E getOrigin() {
- return origin;
- }
-
- public E getDestination() {
- return dst;
- }
-
- public boolean hasNext() {
- return (nextArc != null);
- }
-
- public V next() {
- origin = nextOrigin;
- arc = nextArc;
- nextArc = null;
- nextOrigin = null;
- while (graphIt.hasNext()) {
- Entry<E, Map<E, V>> entry = graphIt.next();
- Map<E, V> destinations = entry.getValue();
- nextArc = destinations.get(dst);
- if (nextArc != null) {
- nextOrigin = entry.getKey();
- break;
- }
- }
- return arc;
- }
-
- public void remove() {
- throw new java.lang.UnsupportedOperationException(
- "Method remove() not yet implemented.");
- }
- }
+ private Map<E, Map<E, V>> graph;
+ private int size;
+
+ public MapDigraph() {
+ graph = new HashMap<E, Map<E, V>>();
+ }
+
+ @Override
+ public boolean addVertex(E vertex) {
+ if (graph.containsKey(vertex)) {
+ return false;
+ }
+
+ graph.put(vertex, new HashMap<E, V>());
+ return true;
+ }
+
+ @Override
+ public boolean addAllVertices(Collection<? extends E> vertices) {
+ if (graph.keySet().containsAll(vertices)) {
+ return false;
+ }
+
+ for (E vertex : vertices) {
+ addVertex(vertex);
+ }
+
+ return true;
+ }
+
+ @Override
+ public V putArc(E origin, E destination, V arc) {
+ Map<E, V> destinations = graph.get(origin);
+ if (destinations == null) {
+ destinations = new HashMap<E, V>();
+ graph.put(origin, destinations);
+ }
+
+ addVertex(destination);
+ V oldArc = destinations.put(destination, arc);
+ if (oldArc == null) {
+ size++;
+ }
+
+ return oldArc;
+ }
+
+ @Override
+ public V getArc(Object origin, Object destination) {
+ Map<E, V> destinations = graph.get(origin);
+ if (destinations == null) {
+ return null;
+ }
+
+ return destinations.get(destination);
+ }
+
+ @Override
+ public boolean removeVertex(E vertex) {
+ Map<E, V> destination = graph.remove(vertex);
+ if (destination != null)
+ size -= destination.size();
+ else
+ return false;
+
+ removeIncoming(vertex);
+ return true;
+ }
+
+ @Override
+ public boolean removeAllVertices(Collection<? extends E> vertices) {
+ boolean modified = false;
+
+ for (E vertex : vertices) {
+ modified |= removeVertex(vertex);
+ }
+
+ return modified;
+ }
+
+ @Override
+ public Object removeArc(E origin, E destination) {
+ Map<E, V> destinations = graph.get(origin);
+ if (destinations == null) {
+ return null;
+ }
+
+ V arc = destinations.remove(destination);
+ if (arc != null)
+ size--;
+
+ return arc;
+ }
+
+ @Override
+ public boolean removeIncoming(E vertex) {
+ boolean modified = false;
+
+ for (Map<E, V> destinations : graph.values()) {
+ Object arc = destinations.remove(vertex);
+ if (arc != null)
+ size--;
+ modified |= (arc != null);
+ }
+
+ return modified;
+ }
+
+ @Override
+ public boolean removeOutgoing(E vertex) {
+
+ Map<E, V> destinations = graph.remove(vertex);
+ if (destinations != null)
+ size -= destinations.size();
+ else
+ return false;
+ boolean modified = !destinations.isEmpty();
+ destinations.clear();
+ return modified;
+ }
+
+ @Override
+ public Iterator<E> vertexIterator() {
+ return graph.keySet().iterator();
+ }
+
+ @Override
+ public ArcIterator<E, V> arcIterator() {
+ return new AllArcIterator();
+ }
+
+ @Override
+ public ArcIterator<E, V> outgoingIterator(E vertex) {
+ if (!containsVertex(vertex)) {
+ return ArcIterator.EMPTY_ITERATOR;
+ }
+
+ return new OutgoingArcIterator(vertex);
+ }
+
+ @Override
+ public ArcIterator<E, V> incomingIterator(E vertex) {
+ if (!containsVertex(vertex)) {
+ return ArcIterator.EMPTY_ITERATOR;
+ }
+
+ return new IncomingArcIterator(vertex);
+ }
+
+ @Override
+ public int order() {
+ return graph.size();
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public int outgoingSize(E vertex) {
+ Map<E, V> destinations = graph.get(vertex);
+ if (destinations == null)
+ return 0;
+ else
+ return destinations.size();
+ }
+
+ @Override
+ public int incomingSize(E vertex) {
+ int count = 0;
+ if (!graph.containsKey(vertex))
+ return 0;
+
+ for (Map<E, V> destinations : graph.values()) {
+ count += (destinations.containsKey(vertex) ? 1 : 0);
+ }
+
+ return count;
+ }
+
+ @Override
+ public boolean containsVertex(E vertex) {
+ return graph.containsKey(vertex);
+ }
+
+ @Override
+ public boolean containsAllVertices(Collection<? extends E> vertices) {
+ return graph.keySet().containsAll(vertices);
+ }
+
+ @Override
+ public boolean hasArc(E origin, E destination) {
+ Map<E, V> destinations = graph.get(origin);
+ if (destinations == null)
+ return false;
+ return destinations.containsKey(destination);
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return graph.isEmpty();
+ }
+
+ @Override
+ public boolean isOutgoingEmpty(E vertex) {
+ return outgoingSize(vertex) == 0;
+ }
+
+ @Override
+ public boolean isIncomingEmpty(E vertex) {
+ return incomingSize(vertex) == 0;
+ }
+
+ private class AllArcIterator implements ArcIterator<E, V> {
+
+ private Iterator<Entry<E, Map<E, V>>> originIterator;
+ private Iterator<Entry<E, V>> destinationIterator;
+ private E origin, nextOrigin;
+ private E destination, nextDst;
+ private V arc, nextArc;
+
+ private AllArcIterator() {
+ originIterator = graph.entrySet().iterator();
+ next();
+ }
+
+ @Override
+ public E getOrigin() {
+ return origin;
+ }
+
+ @Override
+ public E getDestination() {
+ return destination;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return nextArc != null;
+ }
+
+ @Override
+ public V next() {
+ origin = nextOrigin;
+ destination = nextDst;
+ arc = nextArc;
+ if (destinationIterator == null || !destinationIterator.hasNext()) {
+ nextOrigin = null;
+ nextDst = null;
+ nextArc = null;
+
+ while (originIterator.hasNext()) {
+ Entry<E, Map<E, V>> entry = originIterator.next();
+ destinationIterator = entry.getValue().entrySet().iterator();
+ if (destinationIterator.hasNext()) {
+ nextOrigin = entry.getKey();
+ Entry<E, V> entry1 = destinationIterator.next();
+ nextDst = entry1.getKey();
+ nextArc = entry1.getValue();
+ break;
+ }
+ }
+ } else {
+ Entry<E, V> entry1 = destinationIterator.next();
+ nextDst = entry1.getKey();
+ nextArc = entry1.getValue();
+ }
+
+ return arc;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("Method remove() not yet implemented.");
+ }
+ }
+
+ private class OutgoingArcIterator implements ArcIterator<E, V> {
+
+ private E origin;
+ private Iterator<Entry<E, V>> dstIt;
+ private Entry<E, V> entry;
+
+ private OutgoingArcIterator(E vertex) {
+ origin = vertex;
+ dstIt = graph.get(vertex).entrySet().iterator();
+ }
+
+ @Override
+ public E getOrigin() {
+ return origin;
+ }
+
+ @Override
+ public E getDestination() {
+ if (entry == null)
+ return null;
+ return entry.getKey();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return dstIt.hasNext();
+ }
+
+ @Override
+ public V next() {
+ entry = dstIt.next();
+ return entry.getValue();
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("Method remove() not yet implemented.");
+ }
+ }
+
+ private class IncomingArcIterator implements ArcIterator<E, V> {
+
+ private E dst;
+ private E origin, nextOrigin;
+ private V arc, nextArc;
+ private Iterator<Entry<E, Map<E, V>>> graphIt;
+
+ private IncomingArcIterator(E vertex) {
+ dst = vertex;
+ graphIt = graph.entrySet().iterator();
+ next();
+ }
+
+ public E getOrigin() {
+ return origin;
+ }
+
+ public E getDestination() {
+ return dst;
+ }
+
+ public boolean hasNext() {
+ return (nextArc != null);
+ }
+
+ public V next() {
+ origin = nextOrigin;
+ arc = nextArc;
+ nextArc = null;
+ nextOrigin = null;
+ while (graphIt.hasNext()) {
+ Entry<E, Map<E, V>> entry = graphIt.next();
+ Map<E, V> destinations = entry.getValue();
+ nextArc = destinations.get(dst);
+ if (nextArc != null) {
+ nextOrigin = entry.getKey();
+ break;
+ }
+ }
+ return arc;
+ }
+
+ public void remove() {
+ throw new java.lang.UnsupportedOperationException("Method remove() not yet implemented.");
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/cayenne/blob/d252bf37/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/StrongConnection.java
----------------------------------------------------------------------
diff --git a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/StrongConnection.java b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/StrongConnection.java
index e8d7348..62dbddd 100644
--- a/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/StrongConnection.java
+++ b/cayenne-server/src/main/java/org/apache/cayenne/ashwood/graph/StrongConnection.java
@@ -78,164 +78,164 @@ import org.apache.commons.collections.functors.TruePredicate;
*/
public class StrongConnection<E, V> implements Iterator<Collection<E>> {
- private DigraphIteration<E, V> digraph;
- private DigraphIteration<E, V> reverseDigraph;
- private DigraphIteration<E, V> filteredDigraph;
- private DepthFirstStampSearch<E> directDfs;
- private DepthFirstSearch<E> reverseDfs;
- private Set<E> seen = new HashSet<E>();
- private Iterator<E> vertexIterator;
- private ArrayStack dfsStack = new ArrayStack();
- private DFSSeenVerticesPredicate reverseDFSFilter = new DFSSeenVerticesPredicate();
-
- public StrongConnection(DigraphIteration<E, V> digraph) {
- this.digraph = digraph;
- filteredDigraph = new FilterIteration<E, V>(
- digraph,
- new NotSeenPredicate(),
- TruePredicate.INSTANCE);
- reverseDigraph = new FilterIteration<E, V>(
- new ReversedIteration<E, V>(digraph),
- reverseDFSFilter,
- TruePredicate.INSTANCE);
- vertexIterator = filteredDigraph.vertexIterator();
- runDirectDFS();
- }
-
- public boolean hasNext() {
- return !dfsStack.isEmpty();
- }
-
- public Collection<E> next() {
- Collection<E> component = buildStronglyConnectedComponent();
- if (dfsStack.isEmpty())
- runDirectDFS();
- return component;
- }
-
- public void remove() {
- throw new UnsupportedOperationException("Method remove() not supported.");
- }
-
- public Digraph<Collection<E>, Collection<V>> contract(
- Digraph<Collection<E>, Collection<V>> contractedDigraph) {
-
- Collection<Collection<E>> components = new ArrayList<Collection<E>>();
- CollectionUtils.addAll(components, this);
-
- Map<E, Collection<E>> memberToComponent = new HashMap<E, Collection<E>>();
-
- for (Collection<E> c : components) {
- for (E e : c) {
- memberToComponent.put(e, c);
- }
- }
-
- for (Collection<E> origin : components) {
-
- contractedDigraph.addVertex(origin);
-
- for (E member : origin) {
-
- for (ArcIterator<E, V> k = digraph.outgoingIterator(member); k.hasNext();) {
- V arc = k.next();
- E dst = k.getDestination();
- if (origin.contains(dst))
- continue;
- Collection<E> destination = memberToComponent.get(dst);
-
- Collection<V> contractedArc = contractedDigraph.getArc(
- origin,
- destination);
- if (contractedArc == null) {
- contractedArc = Collections.singletonList(arc);
- contractedDigraph.putArc(origin, destination, contractedArc);
- }
- else {
- if (contractedArc.size() == 1) {
- Collection<V> tmp = contractedArc;
- contractedArc = new ArrayList<V>();
- contractedArc.addAll(tmp);
- contractedDigraph.putArc(origin, destination, contractedArc);
- }
- contractedArc.add(arc);
- }
-
- }
- }
- }
- return contractedDigraph;
- }
-
- private E nextDFSRoot() {
- return vertexIterator.hasNext() ? vertexIterator.next() : null;
- }
-
- private boolean runDirectDFS() {
- dfsStack.clear();
- reverseDFSFilter.seenVertices.clear();
- E root = nextDFSRoot();
- if (root == null)
- return false;
- if (directDfs == null)
- directDfs = new DepthFirstStampSearch<E>(filteredDigraph, root);
- else
- directDfs.reset(root);
- int stamp;
- E vertex;
- while (directDfs.hasNext()) {
- vertex = directDfs.next();
- stamp = directDfs.getStamp();
- if (stamp == DepthFirstStampSearch.SHRINK_STAMP
- || stamp == DepthFirstStampSearch.LEAF_STAMP) {
- // if (seen.add(vertex)) {
- dfsStack.push(vertex);
- reverseDFSFilter.seenVertices.add(vertex);
- // }
- }
- }
- seen.addAll(dfsStack);
- return true;
- }
-
- private Collection<E> buildStronglyConnectedComponent() {
- E root = (E) dfsStack.pop();
- Collection<E> component = Collections.singletonList(root);
- boolean singleton = true;
- if (reverseDfs == null)
- reverseDfs = new DepthFirstSearch<E>(reverseDigraph, root);
- else
- reverseDfs.reset(root);
- while (reverseDfs.hasNext()) {
- E vertex = reverseDfs.next();
- if (vertex != root) {
- if (singleton) {
- Collection<E> tmp = component;
- component = new ArrayList<E>();
- component.addAll(tmp);
- singleton = false;
- }
- component.add(vertex);
- dfsStack.remove(vertex);
- }
- }
- reverseDFSFilter.seenVertices.removeAll(component);
- return component;
- }
-
- private class DFSSeenVerticesPredicate implements Predicate {
-
- private Set<E> seenVertices = new HashSet<E>();
-
- public boolean evaluate(Object vertex) {
- return seenVertices.contains(vertex);
- }
- }
-
- private class NotSeenPredicate implements Predicate {
-
- public boolean evaluate(Object vertex) {
- return !seen.contains(vertex);
- }
- }
+ private DigraphIteration<E, V> digraph;
+ private DigraphIteration<E, V> reverseDigraph;
+ private DigraphIteration<E, V> filteredDigraph;
+ private DepthFirstStampSearch<E> directDfs;
+ private DepthFirstSearch<E> reverseDfs;
+ private Set<E> seen = new HashSet<E>();
+ private Iterator<E> vertexIterator;
+ private ArrayStack dfsStack;
+ private DFSSeenVerticesPredicate reverseDFSFilter;
+
+ public StrongConnection(DigraphIteration<E, V> digraph) {
+
+ this.dfsStack = new ArrayStack();
+ this.reverseDFSFilter = new DFSSeenVerticesPredicate();
+ this.digraph = digraph;
+ this.filteredDigraph = new FilterIteration<>(digraph, new NotSeenPredicate(), TruePredicate.INSTANCE);
+ this.reverseDigraph = new FilterIteration<>(new ReversedIteration<>(digraph), reverseDFSFilter,
+ TruePredicate.INSTANCE);
+ this.vertexIterator = filteredDigraph.vertexIterator();
+
+ runDirectDFS();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return !dfsStack.isEmpty();
+ }
+
+ @Override
+ public Collection<E> next() {
+ Collection<E> component = buildStronglyConnectedComponent();
+ if (dfsStack.isEmpty()) {
+ runDirectDFS();
+ }
+ return component;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("Method remove() not supported.");
+ }
+
+ public Digraph<Collection<E>, Collection<V>> contract(Digraph<Collection<E>, Collection<V>> contractedDigraph) {
+
+ Collection<Collection<E>> components = new ArrayList<>();
+ CollectionUtils.addAll(components, this);
+
+ Map<E, Collection<E>> memberToComponent = new HashMap<>();
+
+ for (Collection<E> c : components) {
+ for (E e : c) {
+ memberToComponent.put(e, c);
+ }
+ }
+
+ for (Collection<E> origin : components) {
+
+ contractedDigraph.addVertex(origin);
+
+ for (E member : origin) {
+
+ for (ArcIterator<E, V> k = digraph.outgoingIterator(member); k.hasNext();) {
+ V arc = k.next();
+ E dst = k.getDestination();
+ if (origin.contains(dst))
+ continue;
+ Collection<E> destination = memberToComponent.get(dst);
+
+ Collection<V> contractedArc = contractedDigraph.getArc(origin, destination);
+ if (contractedArc == null) {
+ contractedArc = Collections.singletonList(arc);
+ contractedDigraph.putArc(origin, destination, contractedArc);
+ } else {
+ if (contractedArc.size() == 1) {
+ Collection<V> tmp = contractedArc;
+ contractedArc = new ArrayList<V>();
+ contractedArc.addAll(tmp);
+ contractedDigraph.putArc(origin, destination, contractedArc);
+ }
+ contractedArc.add(arc);
+ }
+
+ }
+ }
+ }
+ return contractedDigraph;
+ }
+
+ private E nextDFSRoot() {
+ return vertexIterator.hasNext() ? vertexIterator.next() : null;
+ }
+
+ private boolean runDirectDFS() {
+ dfsStack.clear();
+ reverseDFSFilter.seenVertices.clear();
+ E root = nextDFSRoot();
+ if (root == null)
+ return false;
+ if (directDfs == null)
+ directDfs = new DepthFirstStampSearch<>(filteredDigraph, root);
+ else
+ directDfs.reset(root);
+ int stamp;
+ E vertex;
+ while (directDfs.hasNext()) {
+ vertex = directDfs.next();
+ stamp = directDfs.getStamp();
+ if (stamp == DepthFirstStampSearch.SHRINK_STAMP || stamp == DepthFirstStampSearch.LEAF_STAMP) {
+ // if (seen.add(vertex)) {
+ dfsStack.push(vertex);
+ reverseDFSFilter.seenVertices.add(vertex);
+ // }
+ }
+ }
+ seen.addAll(dfsStack);
+ return true;
+ }
+
+ private Collection<E> buildStronglyConnectedComponent() {
+ E root = (E) dfsStack.pop();
+ Collection<E> component = Collections.singletonList(root);
+ boolean singleton = true;
+ if (reverseDfs == null)
+ reverseDfs = new DepthFirstSearch<E>(reverseDigraph, root);
+ else
+ reverseDfs.reset(root);
+ while (reverseDfs.hasNext()) {
+ E vertex = reverseDfs.next();
+ if (vertex != root) {
+ if (singleton) {
+ Collection<E> tmp = component;
+ component = new ArrayList<E>();
+ component.addAll(tmp);
+ singleton = false;
+ }
+ component.add(vertex);
+ dfsStack.remove(vertex);
+ }
+ }
+ reverseDFSFilter.seenVertices.removeAll(component);
+ return component;
+ }
+
+ private class DFSSeenVerticesPredicate implements Predicate {
+
+ private Set<E> seenVertices = new HashSet<E>();
+
+ @Override
+ public boolean evaluate(Object vertex) {
+ return seenVertices.contains(vertex);
+ }
+ }
+
+ private class NotSeenPredicate implements Predicate {
+
+ @Override
+ public boolean evaluate(Object vertex) {
+ return !seen.contains(vertex);
+ }
+ }
}