Author: mikedd
Date: Wed Jun 22 13:54:05 2011
New Revision: 1138467
URL: http://svn.apache.org/viewvc?rev=1138467&view=rev
Log:
OPENJPA-1875: Add generics to graph code.
Submitted By: Guy Korland
M
openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java
M
openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
M openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
M openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java?rev=1138467&r1=1138466&r2=1138467&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java
Wed Jun 22 13:54:05 2011
@@ -21,7 +21,6 @@ package org.apache.openjpa.lib.graph;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
-import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -44,9 +43,9 @@ import java.util.Set;
public class BreadthFirstWalk {
private final Graph _graph;
- private final Set _visitors = new HashSet();
- private final List _queue = new LinkedList();
- private final Map _nodeInfo = new HashMap();
+ private final Set<GraphVisitor> _visitors = new HashSet<GraphVisitor>();
+ private final List<Object> _queue = new LinkedList<Object>();
+ private final Map<Object, NodeInfo> _nodeInfo = new HashMap<Object,
NodeInfo>();
public BreadthFirstWalk(Graph graph) {
_graph = graph;
@@ -59,15 +58,13 @@ public class BreadthFirstWalk {
_queue.clear();
_nodeInfo.clear();
- Collection nodes = _graph.getNodes();
- for (Iterator itr = nodes.iterator(); itr.hasNext();)
- _nodeInfo.put(itr.next(), new NodeInfo());
+ Collection<Object> nodes = _graph.getNodes();
+ for (Object node: nodes)
+ _nodeInfo.put(node, new NodeInfo());
- Object node;
NodeInfo info;
- for (Iterator itr = nodes.iterator(); itr.hasNext();) {
- node = itr.next();
- info = (NodeInfo) _nodeInfo.get(node);
+ for (Object node : nodes){
+ info = _nodeInfo.get(node);
if (info.color == NodeInfo.COLOR_WHITE)
enqueue(node, info);
processQueue();
@@ -78,23 +75,16 @@ public class BreadthFirstWalk {
* Process the queue to see what data needs to be obtained.
*/
private void processQueue() {
- Object node;
- Object other;
- NodeInfo info;
- NodeInfo otherInfo;
- Collection edges;
- Edge edge;
while (_queue.size() > 0) {
- node = _queue.remove(0);
- info = (NodeInfo) _nodeInfo.get(node);
+ Object node = _queue.remove(0);
+ NodeInfo info = _nodeInfo.get(node);
visit(node, info);
- edges = _graph.getEdgesFrom(node);
- for (Iterator itr = edges.iterator(); itr.hasNext();) {
- edge = (Edge) itr.next();
+ Collection<Edge> edges = _graph.getEdgesFrom(node);
+ for (Edge edge : edges) {
edgeVisited(edge);
- other = edge.getOther(node);
- otherInfo = (NodeInfo) _nodeInfo.get(other);
+ Object other = edge.getOther(node);
+ NodeInfo otherInfo = _nodeInfo.get(other);
if (otherInfo.color == NodeInfo.COLOR_WHITE)
enqueue(other, otherInfo);
}
@@ -108,8 +98,8 @@ public class BreadthFirstWalk {
protected void enqueue(Object node, NodeInfo info) {
_queue.add(node);
info.color = NodeInfo.COLOR_GRAY;
- for (Iterator i = _visitors.iterator(); i.hasNext();)
- ((GraphVisitor) i.next()).nodeSeen(node);
+ for (GraphVisitor visitor : _visitors)
+ visitor.nodeSeen(node);
}
/**
@@ -117,16 +107,16 @@ public class BreadthFirstWalk {
*/
protected void visit(Object node, NodeInfo info) {
info.color = NodeInfo.COLOR_BLACK;
- for (Iterator i = _visitors.iterator(); i.hasNext();)
- ((GraphVisitor) i.next()).nodeVisited(node);
+ for (GraphVisitor visitor : _visitors)
+ visitor.nodeVisited(node);
}
/**
* An edge is seen. Notify visitors.
*/
protected void edgeVisited(Edge edge) {
- for (Iterator i = _visitors.iterator(); i.hasNext();)
- ((GraphVisitor) i.next()).edgeVisited(edge);
+ for (GraphVisitor visitor : _visitors)
+ visitor.edgeVisited(edge);
}
/**
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java?rev=1138467&r1=1138466&r2=1138467&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
Wed Jun 22 13:54:05 2011
@@ -27,7 +27,6 @@ import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
-import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -49,8 +48,8 @@ public class DepthFirstAnalysis {
(DepthFirstAnalysis.class);
private final Graph _graph;
- private final Map _nodeInfo = new HashMap();
- private Comparator _comp;
+ private final Map<Object, NodeInfo> _nodeInfo = new HashMap<Object,
NodeInfo>();
+ private Comparator<Object> _comp;
/**
* Constructor. Performs the analysis on the given graph and caches
@@ -60,18 +59,16 @@ public class DepthFirstAnalysis {
_graph = graph;
// initialize node infos
- Collection nodes = graph.getNodes();
- for (Iterator itr = nodes.iterator(); itr.hasNext();)
- _nodeInfo.put(itr.next(), new NodeInfo());
+ Collection<Object> nodes = graph.getNodes();
+ for (Object node : nodes)
+ _nodeInfo.put(node, new NodeInfo());
// visit all nodes -- see intro to algo's book
NodeInfo info;
- Object node;
- for (Iterator itr = nodes.iterator(); itr.hasNext();) {
- node = itr.next();
- info = (NodeInfo) _nodeInfo.get(node);
+ for (Object node : nodes) {
+ info = _nodeInfo.get(node);
if (info.color == NodeInfo.COLOR_WHITE)
- visit(graph, node, info, 0, new LinkedList());
+ visit(graph, node, info, 0, new LinkedList<Edge>());
}
}
@@ -79,21 +76,17 @@ public class DepthFirstAnalysis {
* Visit a node. See Introduction to Algorithms book for details.
*/
private int visit(Graph graph, Object node, NodeInfo info, int time,
- List path) {
+ List<Edge> path) {
// discover node
info.color = NodeInfo.COLOR_GRAY;
// explore all vertices from that node depth first
- Collection edges = graph.getEdgesFrom(node);
- Edge edge;
- Object other;
- NodeInfo otherInfo;
+ Collection<Edge> edges = graph.getEdgesFrom(node);
int maxChildTime = time - 1;
int childTime;
- for (Iterator itr = edges.iterator(); itr.hasNext();) {
- edge = (Edge) itr.next();
- other = edge.getOther(node);
- otherInfo = (NodeInfo) _nodeInfo.get(other);
+ for (Edge edge : edges) {
+ Object other = edge.getOther(node);
+ NodeInfo otherInfo = _nodeInfo.get(other);
if (otherInfo.color == NodeInfo.COLOR_WHITE) {
// undiscovered node; recurse into it
path.add(edge);
@@ -109,7 +102,7 @@ public class DepthFirstAnalysis {
childTime = otherInfo.finished;
edge.setType(Edge.TYPE_FORWARD);
// find the cycle including this edge
- List cycle = new LinkedList();
+ List<Edge> cycle = new LinkedList<Edge>();
cycle.add(edge);
if (cycleForForwardEdge(graph, other, node, cycle)) {
edge.setCycle(cycle);
@@ -128,7 +121,7 @@ public class DepthFirstAnalysis {
* Set the comparator that should be used for ordering groups of nodes
* with the same dependencies.
*/
- public void setNodeComparator(Comparator comp) {
+ public void setNodeComparator(Comparator<Object> comp) {
_comp = comp;
}
@@ -141,9 +134,9 @@ public class DepthFirstAnalysis {
* is possible, though this method will still return the correct order
* as if edges creating the cycles did not exist.
*/
- public List getSortedNodes() {
- Map.Entry[] entries = (Map.Entry[]) _nodeInfo.entrySet().
- toArray(new Map.Entry[_nodeInfo.size()]);
+ public List<Object> getSortedNodes() {
+ Map.Entry<Object,NodeInfo>[] entries =
+ _nodeInfo.entrySet().toArray(new Map.Entry[_nodeInfo.size()]);
Arrays.sort(entries, new NodeInfoComparator(_comp));
return new NodeList(entries);
}
@@ -153,23 +146,21 @@ public class DepthFirstAnalysis {
* discover all edges that cause cycles in the graph by passing it
* the {@link Edge#TYPE_BACK} or {@link Edge#TYPE_FORWARD} edge type.
*/
- public Collection getEdges(int type) {
- Collection typed = null;
- Edge edge;
- Object node;
- for (Iterator nodes = _graph.getNodes().iterator(); nodes.hasNext();) {
- node = nodes.next();
- for (Iterator itr = _graph.getEdgesFrom(node).iterator();
- itr.hasNext();) {
- edge = (Edge) itr.next();
+ public Collection<Edge> getEdges(int type) {
+ Collection<Edge> typed = null;
+ for (Object node : _graph.getNodes()) {
+ for (Edge edge : _graph.getEdgesFrom(node)) {
if (edge.getType() == type) {
if (typed == null)
- typed = new ArrayList();
+ typed = new ArrayList<Edge>();
typed.add(edge);
}
}
}
- return (typed == null) ? Collections.EMPTY_LIST : typed;
+ if(typed == null ) {
+ typed = Collections.emptyList();
+ }
+ return typed;
}
/**
@@ -177,7 +168,7 @@ public class DepthFirstAnalysis {
* the graph walk, or -1 if the node is not part of the graph.
*/
public int getFinishedTime(Object node) {
- NodeInfo info = (NodeInfo) _nodeInfo.get(node);
+ NodeInfo info = _nodeInfo.get(node);
if (info == null)
return -1;
return info.finished;
@@ -191,9 +182,9 @@ public class DepthFirstAnalysis {
* @param pos Index of the first edge in path continuing the cycle
* @return Cycle starting with a type {@link Edge#TYPE_BACK} edge
*/
- private List buildCycle(Edge backEdge, List path, int pos) {
+ private List<Edge> buildCycle(Edge backEdge, List<Edge> path, int pos) {
int length = path != null ? path.size() - pos : 0;
- List cycle = new ArrayList(length + 1);
+ List<Edge> cycle = new ArrayList<Edge>(length + 1);
cycle.add(0, backEdge);
for (int i = 0; i < length; i++) {
cycle.add(i + 1, path.get(pos + i));
@@ -209,12 +200,11 @@ public class DepthFirstAnalysis {
* @param path Path consisting of edges to the edge's starting node
* @return Cycle starting with a type {@link Edge#TYPE_BACK} edge
*/
- private List cycleForBackEdge(Edge edge, List path) {
+ private List<Edge> cycleForBackEdge(Edge edge, List<Edge> path) {
if (edge.getType() != Edge.TYPE_BACK) {
return null;
}
- List cycle;
int pos = 0;
if (path != null && !edge.getFrom().equals(edge.getTo())) {
// Not a single edge loop
@@ -225,7 +215,7 @@ public class DepthFirstAnalysis {
_loc.get("edge-no-loop", edge).getMessage();
path = null;
}
- cycle = buildCycle(edge, path, pos);
+ List<Edge> cycle = buildCycle(edge, path, pos);
assert (cycle != null): _loc.get("cycle-null", edge).getMessage();
return cycle;
}
@@ -242,11 +232,10 @@ public class DepthFirstAnalysis {
* the <code>path</code> parameter.
*/
private boolean cycleForForwardEdge(Graph graph, Object node,
- Object cycleTo, List path) {
+ Object cycleTo, List<Edge> path) {
boolean found = false;
- Collection edges = graph.getEdgesFrom(node);
- for (Iterator itr = edges.iterator(); !found && itr.hasNext();) {
- Edge edge = (Edge) itr.next();
+ Collection<Edge> edges = graph.getEdgesFrom(node);
+ for (Edge edge : edges) {
Object other = edge.getOther(node);
// Single edge loops are ignored
if (!node.equals(other)) {
@@ -275,11 +264,11 @@ public class DepthFirstAnalysis {
* @param path Continuous list of graph edges.
* @return Edge index if found, -1 otherwise.
*/
- private int findNodeInPath(Object node, List path) {
+ private int findNodeInPath(Object node, List<Edge> path) {
int pos = -1;
if (path != null) {
for (int i = 0; i < path.size(); i++) {
- if (((Edge)path.get(i)).getFrom().equals(node)) {
+ if ( path.get(i).getFrom().equals(node)) {
pos = i;
}
}
@@ -297,10 +286,9 @@ public class DepthFirstAnalysis {
}
// b) there might be forward edges
// make sure these don't indicate cycles
- Collection edges = getEdges(Edge.TYPE_FORWARD);
+ Collection<Edge> edges = getEdges(Edge.TYPE_FORWARD);
if (!edges.isEmpty()) {
- for (Iterator itr = edges.iterator(); itr.hasNext();) {
- Edge edge = (Edge) itr.next();
+ for (Edge edge : edges) {
if (edge.getCycle() != null) {
return false;
}
@@ -310,22 +298,20 @@ public class DepthFirstAnalysis {
}
/**
- * Comparator for toplogically sorting entries in the node info map.
+ * Comparator for topologically sorting entries in the node info map.
*/
private static class NodeInfoComparator
- implements Comparator {
+ implements Comparator<Map.Entry<Object,NodeInfo>> {
- private final Comparator _subComp;
+ private final Comparator<Object> _subComp;
- public NodeInfoComparator(Comparator subComp) {
+ public NodeInfoComparator(Comparator<Object> subComp) {
_subComp = subComp;
}
- public int compare(Object o1, Object o2) {
- Map.Entry e1 = (Map.Entry) o1;
- Map.Entry e2 = (Map.Entry) o2;
- NodeInfo n1 = (NodeInfo) e1.getValue();
- NodeInfo n2 = (NodeInfo) e2.getValue();
+ public int compare(Map.Entry<Object,NodeInfo> e1,
Map.Entry<Object,NodeInfo> e2) {
+ NodeInfo n1 = e1.getValue();
+ NodeInfo n2 = e2.getValue();
// sort by finished order
int ret = n1.finished - n2.finished;
@@ -339,11 +325,11 @@ public class DepthFirstAnalysis {
* List of node-to-nodeinfo entries that exposes just the nodes.
*/
private static class NodeList
- extends AbstractList {
+ extends AbstractList<Object> {
- private final Map.Entry[] _entries;
+ private final Map.Entry<Object, NodeInfo>[] _entries;
- public NodeList(Map.Entry[] entries) {
+ public NodeList(Map.Entry<Object, NodeInfo>[] entries) {
_entries = entries;
}
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java?rev=1138467&r1=1138466&r2=1138467&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
Wed Jun 22 13:54:05 2011
@@ -54,7 +54,7 @@ public class Edge {
private int _type = 0;
private double _weight = 0;
private Object _userObj = null;
- private List _cycle = null;
+ private List<Edge> _cycle = null;
private boolean _removedFromGraph = false;
/**
@@ -183,7 +183,7 @@ public class Edge {
* List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD
* edges.
*/
- public List getCycle() {
+ public List<Edge> getCycle() {
return _cycle;
}
@@ -191,7 +191,7 @@ public class Edge {
* List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD
* edges.
*/
- public void setCycle(List cycle) {
+ public void setCycle(List<Edge> cycle) {
_cycle = cycle;
}
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java?rev=1138467&r1=1138466&r2=1138467&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
Wed Jun 22 13:54:05 2011
@@ -22,7 +22,6 @@ import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
-import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
@@ -40,7 +39,7 @@ public class Graph {
* Map each node to list of edges from that node.
* Using a LinkedHashMap to ensure order of iterator processing.
*/
- private final Map _nodes = new LinkedHashMap();
+ private final Map<Object, Collection<Edge>> _nodes = new
LinkedHashMap<Object, Collection<Edge>>();
/**
* Clear the graph.
@@ -59,7 +58,7 @@ public class Graph {
/**
* Return a view of all nodes in the graph.
*/
- public Collection getNodes() {
+ public Collection<Object> getNodes() {
return _nodes.keySet();
}
@@ -82,9 +81,9 @@ public class Graph {
public boolean removeNode(Object node) {
boolean rem = containsNode(node);
if (rem) {
- Collection edges = getEdgesTo(node);
- for (Iterator itr = edges.iterator(); itr.hasNext();)
- removeEdge((Edge) itr.next());
+ Collection<Edge> edges = getEdgesTo(node);
+ for (Edge edge : edges)
+ removeEdge( edge);
_nodes.remove(node);
}
return rem;
@@ -93,13 +92,11 @@ public class Graph {
/**
* Return all edges in the graph.
*/
- public Collection getEdges() {
- Collection all = new HashSet();
- Collection edges;
- for (Iterator itr = _nodes.values().iterator(); itr.hasNext();) {
- edges = (Collection) itr.next();
- if (edges != null)
- all.addAll(edges);
+ public Collection<Edge> getEdges() {
+ Collection<Edge> all = new HashSet<Edge>();
+ for (Collection<Edge> edges : _nodes.values()) {
+ if (edges != null)
+ all.addAll(edges);
}
return all;
}
@@ -107,35 +104,34 @@ public class Graph {
/**
* Return all the edges from a particular node.
*/
- public Collection getEdgesFrom(Object node) {
- Collection edges = (Collection) _nodes.get(node);
- return (edges == null) ? Collections.EMPTY_LIST : edges;
+ public Collection<Edge> getEdgesFrom(Object node) {
+ Collection<Edge> edges = _nodes.get(node);
+ if(edges == null ) {
+ edges = Collections.emptyList();
+ }
+ return edges;
}
/**
* Return all the edges to a particular node.
*/
- public Collection getEdgesTo(Object node) {
- Collection edges = getEdges();
- Collection to = new ArrayList();
- Edge edge;
- for (Iterator itr = edges.iterator(); itr.hasNext();) {
- edge = (Edge) itr.next();
- if (edge.isTo(node))
- to.add(edge);
- }
- return to;
+ public Collection<Edge> getEdgesTo(Object node) {
+ Collection<Edge> edges = getEdges();
+ Collection<Edge> to = new ArrayList<Edge>();
+ for (Edge edge : edges) {
+ if (edge.isTo(node))
+ to.add(edge);
+ }
+ return to;
}
/**
* Return all the edges from one node to another.
*/
- public Collection getEdges(Object from, Object to) {
- Collection edges = getEdgesFrom(from);
- Collection matches = new ArrayList(edges.size());
- Edge edge;
- for (Iterator itr = edges.iterator(); itr.hasNext();) {
- edge = (Edge) itr.next();
+ public Collection<Edge> getEdges(Object from, Object to) {
+ Collection<Edge> edges = getEdgesFrom(from);
+ Collection<Edge> matches = new ArrayList<Edge>(edges.size());
+ for (Edge edge : edges) {
if (edge.isTo(to))
matches.add(edge);
}
@@ -151,17 +147,17 @@ public class Graph {
if (!containsNode(edge.getFrom()))
throw new IllegalArgumentException(edge.getFrom().toString());
- Collection from = (Collection) _nodes.get(edge.getFrom());
+ Collection<Edge> from = _nodes.get(edge.getFrom());
if (from == null) {
- from = new ArrayList(3);
+ from = new ArrayList<Edge>(3);
_nodes.put(edge.getFrom(), from);
}
from.add(edge);
if (!edge.isDirected() && !edge.getFrom().equals(edge.getTo())) {
- Collection to = (Collection) _nodes.get(edge.getTo());
+ Collection<Edge> to = _nodes.get(edge.getTo());
if (to == null) {
- to = new ArrayList(3);
+ to = new ArrayList<Edge>(3);
_nodes.put(edge.getTo(), to);
}
to.add(edge);
@@ -174,12 +170,12 @@ public class Graph {
* @return true if the edge was removed, false if not in the graph
*/
public boolean removeEdge(Edge edge) {
- Collection edges = (Collection) _nodes.get(edge.getFrom());
+ Collection<Edge> edges = _nodes.get(edge.getFrom());
if (edges == null)
return false;
boolean rem = edges.remove(edge);
if (rem && !edge.isDirected()) {
- edges = (Collection) _nodes.get(edge.getTo());
+ edges = _nodes.get(edge.getTo());
if (edges != null)
edges.remove(edge);
}
@@ -191,12 +187,10 @@ public class Graph {
* last traversal.
*/
public void clearTraversal() {
- Collection edges;
- for (Iterator vals = _nodes.values().iterator(); vals.hasNext();) {
- edges = (Collection) vals.next();
- if (edges != null)
- for (Iterator ed = edges.iterator(); ed.hasNext();)
- ((Edge) ed.next()).clearTraversal ();
- }
- }
+ for (Collection<Edge> edges : _nodes.values()) {
+ if (edges != null)
+ for (Edge edge : edges)
+ edge.clearTraversal();
+ }
+ }
}
