openjpa-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mik...@apache.org
Subject svn commit: r757280 [8/23] - in /openjpa/branches/1.0.x: openjpa-examples/src/main/java/hellojpa/ openjpa-examples/src/main/java/relations/ openjpa-jdbc-5/src/main/java/org/apache/openjpa/jdbc/meta/strats/ openjpa-jdbc/src/main/java/org/apache/openjpa/...
Date Sun, 22 Mar 2009 23:45:35 GMT
Modified: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
URL: http://svn.apache.org/viewvc/openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java?rev=757280&r1=757279&r2=757280&view=diff
==============================================================================
--- openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java (original)
+++ openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java Sun Mar 22 23:45:15 2009
@@ -1,358 +1,358 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.openjpa.lib.graph;
-
-import org.apache.openjpa.lib.util.Localizer;
-
-import java.util.AbstractList;
-import java.util.ArrayList;
-import java.util.Arrays;
-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;
-
-/**
- * <p>Performs a depth-first analysis of a given {@link Graph}, caching
- * information about the graph's nodes and edges.  See the DFS algorithm
- * in the book 'Introduction to Algorithms' by Cormen, Leiserson, and
- * Rivest.  The algorithm has been modified to group sibling nodes without
- * connections together during the topological sort.</p>
- *
- * @author Abe White
- * @since 1.0.0
- * @nojavadoc
- */
-public class DepthFirstAnalysis {
-
-    private static final Localizer _loc = Localizer.forPackage
-        (DepthFirstAnalysis.class);
-
-    private final Graph _graph;
-    private final Map _nodeInfo = new HashMap();
-    private Comparator _comp;
-
-    /**
-     * Constructor.  Performs the analysis on the given graph and caches
-     * the resulting information.
-     */
-    public DepthFirstAnalysis(Graph graph) {
-        _graph = graph;
-
-        // initialize node infos
-        Collection nodes = graph.getNodes();
-        for (Iterator itr = nodes.iterator(); itr.hasNext();)
-            _nodeInfo.put(itr.next(), 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);
-            if (info.color == NodeInfo.COLOR_WHITE)
-                visit(graph, node, info, 0, new LinkedList());
-        }
-    }
-
-    /**
-     * Visit a node.  See Introduction to Algorithms book for details.
-     */
-    private int visit(Graph graph, Object node, NodeInfo info, int time, 
-        List 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;
-        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);
-            if (otherInfo.color == NodeInfo.COLOR_WHITE) {
-                // undiscovered node; recurse into it
-                path.add(edge);
-                childTime = visit(graph, other, otherInfo, time, path);
-                path.remove(edge);
-                edge.setType(Edge.TYPE_TREE);
-            } else if (otherInfo.color == NodeInfo.COLOR_GRAY) {
-                childTime = -1;
-                edge.setType(Edge.TYPE_BACK);
-                // calculate the cycle including this edge
-                edge.setCycle(cycleForBackEdge(edge, path));
-            } else {
-                childTime = otherInfo.finished;
-                edge.setType(Edge.TYPE_FORWARD);
-                // find the cycle including this edge
-                List cycle = new LinkedList();
-                cycle.add(edge);
-                if (cycleForForwardEdge(graph, other, node, cycle)) {
-                    edge.setCycle(cycle);
-                }
-            }
-            maxChildTime = Math.max(maxChildTime, childTime);
-        }
-
-        // finished with node
-        info.color = NodeInfo.COLOR_BLACK;
-        info.finished = maxChildTime + 1;
-        return info.finished;
-    }
-
-    /**
-     * Set the comparator that should be used for ordering groups of nodes
-     * with the same dependencies.
-     */
-    public void setNodeComparator(Comparator comp) {
-        _comp = comp;
-    }
-
-    /**
-     * Return the nodes in topologically-sorted order.  This is often used
-     * to order dependencies.  If each graph edge (u, v) represents a
-     * dependency of v on u, then this method will return the nodes in the
-     * order that they should be evaluated to satisfy all dependencies.  Of
-     * course, if the graph is cyclic (has back edges), then no such ordering
-     * 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()]);
-        Arrays.sort(entries, new NodeInfoComparator(_comp));
-        return new NodeList(entries);
-    }
-
-    /**
-     * Return all edges of the given type.  This method can be used to
-     * 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();
-                if (edge.getType() == type) {
-                    if (typed == null)
-                        typed = new ArrayList();
-                    typed.add(edge);
-                }
-            }
-        }
-        return (typed == null) ? Collections.EMPTY_LIST : typed;
-    }
-
-    /**
-     * Return the logical time that the given node was finished in
-     * 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);
-        if (info == null)
-            return -1;
-        return info.finished;
-    }
-
-    /**
-     * Returns a list of graph edges forming a cycle. The cycle begins 
-     * with a type {@link Edge#TYPE_BACK} edge.
-     * @param backEdge "Starting" edge of the cycle
-     * @param path Continuous list of graph edges, may be null
-     * @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) {
-        int length = path != null ? path.size() - pos : 0;
-        List cycle = new ArrayList(length + 1);
-        cycle.add(0, backEdge);
-        for (int i = 0; i < length; i++) {
-            cycle.add(i + 1, path.get(pos + i));
-        }
-        return cycle;
-    }
-
-    /**
-     * Computes the list of edges forming a cycle. The cycle always exists for
-     * a type {@link Edge#TYPE_BACK} edge. This method should only be called 
-     * for type {@link Edge#TYPE_BACK} edges. 
-     * @param edge Edge where the cycle was detected
-     * @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) {
-        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
-            pos = findNodeInPath(edge.getTo(), path);
-            assert (pos >= 0): _loc.get("node-not-on-path", edge, edge.getTo()); 
-        } else {
-            assert (edge.getFrom().equals(edge.getTo())): 
-                _loc.get("edge-no-loop", edge).getMessage();
-            path = null;
-        }
-        cycle = buildCycle(edge, path, pos); 
-        assert (cycle != null): _loc.get("cycle-null", edge).getMessage();
-        return cycle;
-    }
-
-    /**
-     * Computes the cycle of edges including node cycleTo. The cycle must not 
-     * necessarily exist. This method should only be called for type 
-     * {@link Edge#TYPE_FORWARD} edges.
-     * @param graph Graph
-     * @param node Current node
-     * @param cycleTo End node for loop
-     * @param path Path from loop end node to current node
-     * @return True if a cycle has been found. The cycle will be contained in
-     * the <code>path</code> parameter.
-     */
-    private boolean cycleForForwardEdge(Graph graph, Object node,
-        Object cycleTo, List path) {                   
-        boolean found = false;
-        Collection edges = graph.getEdgesFrom(node);
-        for (Iterator itr = edges.iterator(); !found && itr.hasNext();) {
-            Edge edge = (Edge) itr.next();
-            Object other = edge.getOther(node);
-            // Single edge loops are ignored
-            if (!node.equals(other)) {
-                if (other.equals(cycleTo)) {
-                    // Cycle complete
-                    path.add(edge);
-                    found = true;
-                } else if (!path.contains(edge)){
-                    // Walk this edge
-                    path.add(edge);
-                    found = cycleForForwardEdge(graph, other, cycleTo, path);
-                    if (!found) {
-                        // Remove edge again
-                        path.remove(edge);                    
-                    }
-                }
-            }
-        }
-        return found;
-    }
-    
-    /**
-     * Finds the position of the edge starting from a particular node in the 
-     * continuous list of edges.
-     * @param node Node on the cycle.
-     * @param path Continuous list of graph edges.
-     * @return Edge index if found, -1 otherwise.
-     */
-    private int findNodeInPath(Object node, List path) {
-        int pos = -1;
-        if (path != null) {
-            for (int i = 0; i < path.size(); i++) {
-                if (((Edge)path.get(i)).getFrom().equals(node)) {
-                    pos = i;
-                }
-            }
-        }
-        return pos;
-    }
-
-    /**
-     * Test, if the analysis didn't find cycles.
-     */
-    public boolean hasNoCycles() {
-        // a) there must not be any back edges
-        if (!getEdges(Edge.TYPE_BACK).isEmpty()) {
-            return false;
-        }
-        // b) there might be forward edges
-        // make sure these don't indicate cycles
-        Collection edges = getEdges(Edge.TYPE_FORWARD);
-        if (!edges.isEmpty()) {
-            for (Iterator itr = edges.iterator(); itr.hasNext();) {
-                Edge edge = (Edge) itr.next();
-                if (edge.getCycle() != null)  {
-                    return false;
-                }
-            }
-        }
-        return true;
-    }
-    
-    /**
-     * Comparator for toplogically sorting entries in the node info map.
-     */
-    private static class NodeInfoComparator
-        implements Comparator {
-
-        private final Comparator _subComp;
-
-        public NodeInfoComparator(Comparator 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();
-
-            // sort by finished order
-            int ret = n1.finished - n2.finished;
-            if (ret == 0 && _subComp != null)
-                ret = _subComp.compare(e1.getKey(), e2.getKey());
-            return ret;
-        }
-    }
-
-    /**
-     *	List of node-to-nodeinfo entries that exposes just the nodes.
-     */
-    private static class NodeList
-        extends AbstractList {
-
-        private final Map.Entry[] _entries;
-
-        public NodeList(Map.Entry[] entries) {
-            _entries = entries;
-        }
-
-        public Object get(int idx) {
-            return _entries[idx].getKey();
-        }
-
-        public int size() {
-            return _entries.length;
-		}
-	}
-}
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.lib.graph;
+
+import org.apache.openjpa.lib.util.Localizer;
+
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.Arrays;
+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;
+
+/**
+ * <p>Performs a depth-first analysis of a given {@link Graph}, caching
+ * information about the graph's nodes and edges.  See the DFS algorithm
+ * in the book 'Introduction to Algorithms' by Cormen, Leiserson, and
+ * Rivest.  The algorithm has been modified to group sibling nodes without
+ * connections together during the topological sort.</p>
+ *
+ * @author Abe White
+ * @since 1.0.0
+ * @nojavadoc
+ */
+public class DepthFirstAnalysis {
+
+    private static final Localizer _loc = Localizer.forPackage
+        (DepthFirstAnalysis.class);
+
+    private final Graph _graph;
+    private final Map _nodeInfo = new HashMap();
+    private Comparator _comp;
+
+    /**
+     * Constructor.  Performs the analysis on the given graph and caches
+     * the resulting information.
+     */
+    public DepthFirstAnalysis(Graph graph) {
+        _graph = graph;
+
+        // initialize node infos
+        Collection nodes = graph.getNodes();
+        for (Iterator itr = nodes.iterator(); itr.hasNext();)
+            _nodeInfo.put(itr.next(), 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);
+            if (info.color == NodeInfo.COLOR_WHITE)
+                visit(graph, node, info, 0, new LinkedList());
+        }
+    }
+
+    /**
+     * Visit a node.  See Introduction to Algorithms book for details.
+     */
+    private int visit(Graph graph, Object node, NodeInfo info, int time, 
+        List 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;
+        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);
+            if (otherInfo.color == NodeInfo.COLOR_WHITE) {
+                // undiscovered node; recurse into it
+                path.add(edge);
+                childTime = visit(graph, other, otherInfo, time, path);
+                path.remove(edge);
+                edge.setType(Edge.TYPE_TREE);
+            } else if (otherInfo.color == NodeInfo.COLOR_GRAY) {
+                childTime = -1;
+                edge.setType(Edge.TYPE_BACK);
+                // calculate the cycle including this edge
+                edge.setCycle(cycleForBackEdge(edge, path));
+            } else {
+                childTime = otherInfo.finished;
+                edge.setType(Edge.TYPE_FORWARD);
+                // find the cycle including this edge
+                List cycle = new LinkedList();
+                cycle.add(edge);
+                if (cycleForForwardEdge(graph, other, node, cycle)) {
+                    edge.setCycle(cycle);
+                }
+            }
+            maxChildTime = Math.max(maxChildTime, childTime);
+        }
+
+        // finished with node
+        info.color = NodeInfo.COLOR_BLACK;
+        info.finished = maxChildTime + 1;
+        return info.finished;
+    }
+
+    /**
+     * Set the comparator that should be used for ordering groups of nodes
+     * with the same dependencies.
+     */
+    public void setNodeComparator(Comparator comp) {
+        _comp = comp;
+    }
+
+    /**
+     * Return the nodes in topologically-sorted order.  This is often used
+     * to order dependencies.  If each graph edge (u, v) represents a
+     * dependency of v on u, then this method will return the nodes in the
+     * order that they should be evaluated to satisfy all dependencies.  Of
+     * course, if the graph is cyclic (has back edges), then no such ordering
+     * 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()]);
+        Arrays.sort(entries, new NodeInfoComparator(_comp));
+        return new NodeList(entries);
+    }
+
+    /**
+     * Return all edges of the given type.  This method can be used to
+     * 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();
+                if (edge.getType() == type) {
+                    if (typed == null)
+                        typed = new ArrayList();
+                    typed.add(edge);
+                }
+            }
+        }
+        return (typed == null) ? Collections.EMPTY_LIST : typed;
+    }
+
+    /**
+     * Return the logical time that the given node was finished in
+     * 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);
+        if (info == null)
+            return -1;
+        return info.finished;
+    }
+
+    /**
+     * Returns a list of graph edges forming a cycle. The cycle begins 
+     * with a type {@link Edge#TYPE_BACK} edge.
+     * @param backEdge "Starting" edge of the cycle
+     * @param path Continuous list of graph edges, may be null
+     * @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) {
+        int length = path != null ? path.size() - pos : 0;
+        List cycle = new ArrayList(length + 1);
+        cycle.add(0, backEdge);
+        for (int i = 0; i < length; i++) {
+            cycle.add(i + 1, path.get(pos + i));
+        }
+        return cycle;
+    }
+
+    /**
+     * Computes the list of edges forming a cycle. The cycle always exists for
+     * a type {@link Edge#TYPE_BACK} edge. This method should only be called 
+     * for type {@link Edge#TYPE_BACK} edges. 
+     * @param edge Edge where the cycle was detected
+     * @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) {
+        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
+            pos = findNodeInPath(edge.getTo(), path);
+            assert (pos >= 0): _loc.get("node-not-on-path", edge, edge.getTo()); 
+        } else {
+            assert (edge.getFrom().equals(edge.getTo())): 
+                _loc.get("edge-no-loop", edge).getMessage();
+            path = null;
+        }
+        cycle = buildCycle(edge, path, pos); 
+        assert (cycle != null): _loc.get("cycle-null", edge).getMessage();
+        return cycle;
+    }
+
+    /**
+     * Computes the cycle of edges including node cycleTo. The cycle must not 
+     * necessarily exist. This method should only be called for type 
+     * {@link Edge#TYPE_FORWARD} edges.
+     * @param graph Graph
+     * @param node Current node
+     * @param cycleTo End node for loop
+     * @param path Path from loop end node to current node
+     * @return True if a cycle has been found. The cycle will be contained in
+     * the <code>path</code> parameter.
+     */
+    private boolean cycleForForwardEdge(Graph graph, Object node,
+        Object cycleTo, List path) {                   
+        boolean found = false;
+        Collection edges = graph.getEdgesFrom(node);
+        for (Iterator itr = edges.iterator(); !found && itr.hasNext();) {
+            Edge edge = (Edge) itr.next();
+            Object other = edge.getOther(node);
+            // Single edge loops are ignored
+            if (!node.equals(other)) {
+                if (other.equals(cycleTo)) {
+                    // Cycle complete
+                    path.add(edge);
+                    found = true;
+                } else if (!path.contains(edge)){
+                    // Walk this edge
+                    path.add(edge);
+                    found = cycleForForwardEdge(graph, other, cycleTo, path);
+                    if (!found) {
+                        // Remove edge again
+                        path.remove(edge);                    
+                    }
+                }
+            }
+        }
+        return found;
+    }
+    
+    /**
+     * Finds the position of the edge starting from a particular node in the 
+     * continuous list of edges.
+     * @param node Node on the cycle.
+     * @param path Continuous list of graph edges.
+     * @return Edge index if found, -1 otherwise.
+     */
+    private int findNodeInPath(Object node, List path) {
+        int pos = -1;
+        if (path != null) {
+            for (int i = 0; i < path.size(); i++) {
+                if (((Edge)path.get(i)).getFrom().equals(node)) {
+                    pos = i;
+                }
+            }
+        }
+        return pos;
+    }
+
+    /**
+     * Test, if the analysis didn't find cycles.
+     */
+    public boolean hasNoCycles() {
+        // a) there must not be any back edges
+        if (!getEdges(Edge.TYPE_BACK).isEmpty()) {
+            return false;
+        }
+        // b) there might be forward edges
+        // make sure these don't indicate cycles
+        Collection edges = getEdges(Edge.TYPE_FORWARD);
+        if (!edges.isEmpty()) {
+            for (Iterator itr = edges.iterator(); itr.hasNext();) {
+                Edge edge = (Edge) itr.next();
+                if (edge.getCycle() != null)  {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+    
+    /**
+     * Comparator for toplogically sorting entries in the node info map.
+     */
+    private static class NodeInfoComparator
+        implements Comparator {
+
+        private final Comparator _subComp;
+
+        public NodeInfoComparator(Comparator 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();
+
+            // sort by finished order
+            int ret = n1.finished - n2.finished;
+            if (ret == 0 && _subComp != null)
+                ret = _subComp.compare(e1.getKey(), e2.getKey());
+            return ret;
+        }
+    }
+
+    /**
+     *	List of node-to-nodeinfo entries that exposes just the nodes.
+     */
+    private static class NodeList
+        extends AbstractList {
+
+        private final Map.Entry[] _entries;
+
+        public NodeList(Map.Entry[] entries) {
+            _entries = entries;
+        }
+
+        public Object get(int idx) {
+            return _entries[idx].getKey();
+        }
+
+        public int size() {
+            return _entries.length;
+		}
+	}
+}

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
URL: http://svn.apache.org/viewvc/openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java?rev=757280&r1=757279&r2=757280&view=diff
==============================================================================
--- openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java (original)
+++ openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java Sun Mar 22 23:45:15 2009
@@ -1,222 +1,222 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.openjpa.lib.graph;
-
-import java.util.List;
-
-/**
- * <p>A graph edge.  Includes the from and to nodes, an arbitrary user object,
- * and a weight.  Edges can be either directed or undirected.</p>
- *
- * @author Abe White
- * @since 1.0.0
- * @nojavadoc
- */
-public class Edge {
-
-    /**
-     * An edge (u, v) is a tree edge if node v was first discovered by
-     * traversing the edge.
-     */
-    public static final int TYPE_TREE = 1;
-
-    /**
-     * An edge (u, v) is a back edge if it creates a cycle back to an
-     * ancestor in the graph.
-     */
-    public static final int TYPE_BACK = 2;
-
-    /**
-     * An edge (u, v) is a forward edge if it is not a tree or back edge.
-     */
-    public static final int TYPE_FORWARD = 3;
-
-    private final Object _from;
-    private final Object _to;
-    private final boolean _directed;
-
-    private int _type = 0;
-    private double _weight = 0;
-    private Object _userObj = null;
-    private List _cycle = null;
-    private boolean _removedFromGraph = false;
-
-    /**
-     * Constructor.
-     *
-     * @param    from        the node the edge comes from
-     * @param    to            the node the edge goes to
-     * @param    directed    whether the edge is directed
-     */
-    public Edge(Object from, Object to, boolean directed) {
-        if (from == null)
-            throw new NullPointerException("from == null");
-        if (to == null)
-            throw new NullPointerException("to == null");
-        _from = from;
-        _to = to;
-        _directed = directed;
-    }
-
-    /**
-     * Constructor.
-     *
-     * @param    from        the node the edge comes from
-     * @param    to            the node the edge goes to
-     * @param    directed    whether the edge is directed
-     * @param    userObject    an associated object
-     */
-    public Edge(Object from, Object to, boolean directed, Object userObject) {
-        this(from, to, directed);
-        _userObj = userObject;
-    }
-
-    /**
-     * Return the node the edge links from.
-     */
-    public Object getFrom() {
-        return _from;
-    }
-
-    /**
-     * Return the node the edge links to.
-     */
-    public Object getTo() {
-        return _to;
-    }
-
-    /**
-     * Return the node on the opposite end of the given one, or null if the
-     * given node is not part of this edge.
-     */
-    public Object getOther(Object node) {
-        if (_to.equals(node))
-            return _from;
-        if (_from.equals(node))
-            return _to;
-        return null;
-    }
-
-    /**
-     * Return true if this edge links to the given node.  For undirected edges,
-     * this method returns true if either side is equal to the given node.
-     */
-    public boolean isTo(Object node) {
-        return _to.equals(node) || (!_directed && _from.equals(node));
-    }
-
-    /**
-     * Return true if this edge links from the given node.  For undirected
-     * edges, this method returns true if either side is equal to the given
-     * node.
-     */
-    public boolean isFrom(Object node) {
-        return _from.equals(node) || (!_directed && _to.equals(node));
-    }
-
-    /**
-     * Return whether the edge is directed.
-     */
-    public boolean isDirected() {
-        return _directed;
-    }
-
-    /**
-     * Return the weight of the edge.
-     */
-    public double getWeight() {
-        return _weight;
-    }
-
-    /**
-     * Set the weight of the edge.
-     */
-    public void setWeight(double weight) {
-        _weight = weight;
-    }
-
-    /**
-     * Arbitrary user object associated with the edge.
-     */
-    public Object getUserObject() {
-        return _userObj;
-    }
-
-    /**
-     * Arbitrary user object associated with the edge.
-     */
-    public void setUserObject(Object obj) {
-        _userObj = obj;
-    }
-
-    /**
-     * Traversal bookkeeping info.
-     */
-    public int getType() {
-        return _type;
-    }
-
-    /**
-     * Traversal bookkeeping info.
-     */
-    public void setType(int type) {
-        _type = type;
-    }
-
-    /**
-     * List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD edges.
-     */
-    public List getCycle() {
-        return _cycle;
-    }
-    
-    /**
-     * List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD edges.
-     */
-    public void setCycle(List cycle) {
-        _cycle = cycle;
-    }
-
-    /**
-     * Returns if this edge is (still) part of the graph.
-     */
-    public boolean isRemovedFromGraph() {
-        return _removedFromGraph;
-    }
-
-    /**
-     * Mark this edge as removed from the graph.
-     */
-    public void setRemovedFromGraph() {
-        this._removedFromGraph = true;
-    }
-
-    /**
-     * Clear traversal info.
-     */
-    public void clearTraversal() {
-        _type = 0;
-        _cycle = null;
-    }
-
-    public String toString() {
-        return super.toString() + "[from=" + getFrom() + ";to=" + getTo()
-            + ";directed=" + isDirected () + ";weight=" + getWeight () + "]";
-	}
-}
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.lib.graph;
+
+import java.util.List;
+
+/**
+ * <p>A graph edge.  Includes the from and to nodes, an arbitrary user object,
+ * and a weight.  Edges can be either directed or undirected.</p>
+ *
+ * @author Abe White
+ * @since 1.0.0
+ * @nojavadoc
+ */
+public class Edge {
+
+    /**
+     * An edge (u, v) is a tree edge if node v was first discovered by
+     * traversing the edge.
+     */
+    public static final int TYPE_TREE = 1;
+
+    /**
+     * An edge (u, v) is a back edge if it creates a cycle back to an
+     * ancestor in the graph.
+     */
+    public static final int TYPE_BACK = 2;
+
+    /**
+     * An edge (u, v) is a forward edge if it is not a tree or back edge.
+     */
+    public static final int TYPE_FORWARD = 3;
+
+    private final Object _from;
+    private final Object _to;
+    private final boolean _directed;
+
+    private int _type = 0;
+    private double _weight = 0;
+    private Object _userObj = null;
+    private List _cycle = null;
+    private boolean _removedFromGraph = false;
+
+    /**
+     * Constructor.
+     *
+     * @param    from        the node the edge comes from
+     * @param    to            the node the edge goes to
+     * @param    directed    whether the edge is directed
+     */
+    public Edge(Object from, Object to, boolean directed) {
+        if (from == null)
+            throw new NullPointerException("from == null");
+        if (to == null)
+            throw new NullPointerException("to == null");
+        _from = from;
+        _to = to;
+        _directed = directed;
+    }
+
+    /**
+     * Constructor.
+     *
+     * @param    from        the node the edge comes from
+     * @param    to            the node the edge goes to
+     * @param    directed    whether the edge is directed
+     * @param    userObject    an associated object
+     */
+    public Edge(Object from, Object to, boolean directed, Object userObject) {
+        this(from, to, directed);
+        _userObj = userObject;
+    }
+
+    /**
+     * Return the node the edge links from.
+     */
+    public Object getFrom() {
+        return _from;
+    }
+
+    /**
+     * Return the node the edge links to.
+     */
+    public Object getTo() {
+        return _to;
+    }
+
+    /**
+     * Return the node on the opposite end of the given one, or null if the
+     * given node is not part of this edge.
+     */
+    public Object getOther(Object node) {
+        if (_to.equals(node))
+            return _from;
+        if (_from.equals(node))
+            return _to;
+        return null;
+    }
+
+    /**
+     * Return true if this edge links to the given node.  For undirected edges,
+     * this method returns true if either side is equal to the given node.
+     */
+    public boolean isTo(Object node) {
+        return _to.equals(node) || (!_directed && _from.equals(node));
+    }
+
+    /**
+     * Return true if this edge links from the given node.  For undirected
+     * edges, this method returns true if either side is equal to the given
+     * node.
+     */
+    public boolean isFrom(Object node) {
+        return _from.equals(node) || (!_directed && _to.equals(node));
+    }
+
+    /**
+     * Return whether the edge is directed.
+     */
+    public boolean isDirected() {
+        return _directed;
+    }
+
+    /**
+     * Return the weight of the edge.
+     */
+    public double getWeight() {
+        return _weight;
+    }
+
+    /**
+     * Set the weight of the edge.
+     */
+    public void setWeight(double weight) {
+        _weight = weight;
+    }
+
+    /**
+     * Arbitrary user object associated with the edge.
+     */
+    public Object getUserObject() {
+        return _userObj;
+    }
+
+    /**
+     * Arbitrary user object associated with the edge.
+     */
+    public void setUserObject(Object obj) {
+        _userObj = obj;
+    }
+
+    /**
+     * Traversal bookkeeping info.
+     */
+    public int getType() {
+        return _type;
+    }
+
+    /**
+     * Traversal bookkeeping info.
+     */
+    public void setType(int type) {
+        _type = type;
+    }
+
+    /**
+     * List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD edges.
+     */
+    public List getCycle() {
+        return _cycle;
+    }
+    
+    /**
+     * List of edges forming a cycle. Only set for TYPE_BACK and TYPE_FORWARD edges.
+     */
+    public void setCycle(List cycle) {
+        _cycle = cycle;
+    }
+
+    /**
+     * Returns if this edge is (still) part of the graph.
+     */
+    public boolean isRemovedFromGraph() {
+        return _removedFromGraph;
+    }
+
+    /**
+     * Mark this edge as removed from the graph.
+     */
+    public void setRemovedFromGraph() {
+        this._removedFromGraph = true;
+    }
+
+    /**
+     * Clear traversal info.
+     */
+    public void clearTraversal() {
+        _type = 0;
+        _cycle = null;
+    }
+
+    public String toString() {
+        return super.toString() + "[from=" + getFrom() + ";to=" + getTo()
+            + ";directed=" + isDirected () + ";weight=" + getWeight () + "]";
+	}
+}

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
URL: http://svn.apache.org/viewvc/openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java?rev=757280&r1=757279&r2=757280&view=diff
==============================================================================
--- openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java (original)
+++ openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java Sun Mar 22 23:45:15 2009
@@ -1,202 +1,202 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.openjpa.lib.graph;
-
-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;
-
-/**
- * <p>Graph representation using the adjacency list form.  See the book
- * 'Introduction to Algorithms' by Cormen, Leiserson, and Rivest.</p>
- *
- * @author Abe White
- * @since 1.0.0
- * @nojavadoc
- */
-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();
-
-    /**
-     * Clear the graph.
-     */
-    public void clear() {
-        _nodes.clear();
-    }
-
-    /**
-     * Return true if the graph contains the given node.
-     */
-    public boolean containsNode(Object node) {
-        return _nodes.containsKey(node);
-    }
-
-    /**
-     * Return a view of all nodes in the graph.
-     */
-    public Collection getNodes() {
-        return _nodes.keySet();
-    }
-
-    /**
-     * Add a node to the graph.  Adding a node a second time has no effect.
-     */
-    public void addNode(Object node) {
-        if (node == null)
-            throw new NullPointerException("node = null");
-        if (!containsNode(node))
-            _nodes.put(node, null);
-    }
-
-    /**
-     * Remove a node from the graph.  All edges to and from the node
-     * will be cleared.
-     *
-     * @return true if the node was removed, false otherwise
-     */
-    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());
-            _nodes.remove(node);
-        }
-        return rem;
-    }
-
-    /**
-     * 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);
-        }
-        return all;
-    }
-
-    /**
-     * 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;
-    }
-
-    /**
-     * 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;
-    }
-
-    /**
-     * 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();
-            if (edge.isTo(to))
-                matches.add(edge);
-        }
-        return matches;
-    }
-
-    /**
-     * Add an edge to the graph.
-     */
-    public void addEdge(Edge edge) {
-        if (!containsNode(edge.getTo()))
-            throw new IllegalArgumentException(edge.getTo().toString());
-        if (!containsNode(edge.getFrom()))
-            throw new IllegalArgumentException(edge.getFrom().toString());
-
-        Collection from = (Collection) _nodes.get(edge.getFrom());
-        if (from == null) {
-            from = new ArrayList(3);
-            _nodes.put(edge.getFrom(), from);
-        }
-        from.add(edge);
-
-        if (!edge.isDirected() && !edge.getFrom().equals(edge.getTo())) {
-            Collection to = (Collection) _nodes.get(edge.getTo());
-            if (to == null) {
-                to = new ArrayList(3);
-                _nodes.put(edge.getTo(), to);
-            }
-            to.add(edge);
-        }
-    }
-
-    /**
-     * Remove an edge from the 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());
-        if (edges == null)
-            return false;
-        boolean rem = edges.remove(edge);
-        if (rem && !edge.isDirected()) {
-            edges = (Collection) _nodes.get(edge.getTo());
-            if (edges != null)
-                edges.remove(edge);
-        }
-        return rem;
-    }
-
-    /**
-     *	Clear all nodes and edges of the bookkeeping information from their
-     *	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 ();
-		}
-	}
-}
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.lib.graph;
+
+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;
+
+/**
+ * <p>Graph representation using the adjacency list form.  See the book
+ * 'Introduction to Algorithms' by Cormen, Leiserson, and Rivest.</p>
+ *
+ * @author Abe White
+ * @since 1.0.0
+ * @nojavadoc
+ */
+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();
+
+    /**
+     * Clear the graph.
+     */
+    public void clear() {
+        _nodes.clear();
+    }
+
+    /**
+     * Return true if the graph contains the given node.
+     */
+    public boolean containsNode(Object node) {
+        return _nodes.containsKey(node);
+    }
+
+    /**
+     * Return a view of all nodes in the graph.
+     */
+    public Collection getNodes() {
+        return _nodes.keySet();
+    }
+
+    /**
+     * Add a node to the graph.  Adding a node a second time has no effect.
+     */
+    public void addNode(Object node) {
+        if (node == null)
+            throw new NullPointerException("node = null");
+        if (!containsNode(node))
+            _nodes.put(node, null);
+    }
+
+    /**
+     * Remove a node from the graph.  All edges to and from the node
+     * will be cleared.
+     *
+     * @return true if the node was removed, false otherwise
+     */
+    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());
+            _nodes.remove(node);
+        }
+        return rem;
+    }
+
+    /**
+     * 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);
+        }
+        return all;
+    }
+
+    /**
+     * 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;
+    }
+
+    /**
+     * 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;
+    }
+
+    /**
+     * 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();
+            if (edge.isTo(to))
+                matches.add(edge);
+        }
+        return matches;
+    }
+
+    /**
+     * Add an edge to the graph.
+     */
+    public void addEdge(Edge edge) {
+        if (!containsNode(edge.getTo()))
+            throw new IllegalArgumentException(edge.getTo().toString());
+        if (!containsNode(edge.getFrom()))
+            throw new IllegalArgumentException(edge.getFrom().toString());
+
+        Collection from = (Collection) _nodes.get(edge.getFrom());
+        if (from == null) {
+            from = new ArrayList(3);
+            _nodes.put(edge.getFrom(), from);
+        }
+        from.add(edge);
+
+        if (!edge.isDirected() && !edge.getFrom().equals(edge.getTo())) {
+            Collection to = (Collection) _nodes.get(edge.getTo());
+            if (to == null) {
+                to = new ArrayList(3);
+                _nodes.put(edge.getTo(), to);
+            }
+            to.add(edge);
+        }
+    }
+
+    /**
+     * Remove an edge from the 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());
+        if (edges == null)
+            return false;
+        boolean rem = edges.remove(edge);
+        if (rem && !edge.isDirected()) {
+            edges = (Collection) _nodes.get(edge.getTo());
+            if (edges != null)
+                edges.remove(edge);
+        }
+        return rem;
+    }
+
+    /**
+     *	Clear all nodes and edges of the bookkeeping information from their
+     *	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 ();
+		}
+	}
+}

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java
URL: http://svn.apache.org/viewvc/openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java?rev=757280&r1=757279&r2=757280&view=diff
==============================================================================
--- openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java (original)
+++ openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java Sun Mar 22 23:45:15 2009
@@ -1,47 +1,47 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.openjpa.lib.graph;
-
-/**
- * <p>A helper interface that allows third parties to be notified of
- * graph events during graph traversals</p>
- *
- * @author Steve Kim
- * @since 1.0.0
- * @nojavadoc
- */
-public interface GraphVisitor {
-
-    /**
-     * May not be called.  The meaning of this method is dependent
-     * on the traversal being used.  See each appropriate graph
-     * walker for details.
-     */
-    public void nodeSeen(Object node);
-
-    /**
-     * will only be called once per node
-     */
-    public void nodeVisited(Object node);
-
-    /**
-     * may visit the node twice (both sides)
-     */
-    public void edgeVisited(Edge edge);
-}
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.lib.graph;
+
+/**
+ * <p>A helper interface that allows third parties to be notified of
+ * graph events during graph traversals</p>
+ *
+ * @author Steve Kim
+ * @since 1.0.0
+ * @nojavadoc
+ */
+public interface GraphVisitor {
+
+    /**
+     * May not be called.  The meaning of this method is dependent
+     * on the traversal being used.  See each appropriate graph
+     * walker for details.
+     */
+    public void nodeSeen(Object node);
+
+    /**
+     * will only be called once per node
+     */
+    public void nodeVisited(Object node);
+
+    /**
+     * may visit the node twice (both sides)
+     */
+    public void edgeVisited(Edge edge);
+}

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java
URL: http://svn.apache.org/viewvc/openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java?rev=757280&r1=757279&r2=757280&view=diff
==============================================================================
--- openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java (original)
+++ openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java Sun Mar 22 23:45:15 2009
@@ -1,35 +1,35 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied.  See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.openjpa.lib.graph;
-
-/**
- * <p>Struct used to track graph node information during traversal.</p>
- *
- * @author Abe White
- * @since 1.0.0
- */
-class NodeInfo {
-
-    public static final int COLOR_WHITE = 0;
-    public static final int COLOR_GRAY = 1;
-    public static final int COLOR_BLACK = 2;
-
-    public int finished = 0;
-    public int color = COLOR_WHITE;
-}
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.lib.graph;
+
+/**
+ * <p>Struct used to track graph node information during traversal.</p>
+ *
+ * @author Abe White
+ * @since 1.0.0
+ */
+class NodeInfo {
+
+    public static final int COLOR_WHITE = 0;
+    public static final int COLOR_GRAY = 1;
+    public static final int COLOR_BLACK = 2;
+
+    public int finished = 0;
+    public int color = COLOR_WHITE;
+}

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/AbstractJDBCListener.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/ConfiguringConnectionDecorator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/ConnectionDecorator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/DataSourceLogs.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/DecoratingDataSource.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/DelegatingCallableStatement.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/DelegatingConnection.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: openjpa/branches/1.0.x/openjpa-lib/src/main/java/org/apache/openjpa/lib/jdbc/DelegatingDataSource.java
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message