openjpa-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From p..@apache.org
Subject svn commit: r544918 - in /openjpa/trunk: openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/ openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/ openjpa-lib/src/test/java/org/apache/op...
Date Wed, 06 Jun 2007 18:49:32 GMT
Author: pcl
Date: Wed Jun  6 11:49:30 2007
New Revision: 544918

URL: http://svn.apache.org/viewvc?view=rev&rev=544918
Log:
OPENJPA-235

Added:
    openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
    openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/
    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
    openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java
    openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java
    openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/package.html
    openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/
    openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
    openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestGraph.java
Modified:
    openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/JDBCConfigurationImpl.java

Modified: openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/JDBCConfigurationImpl.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/JDBCConfigurationImpl.java?view=diff&rev=544918&r1=544917&r2=544918
==============================================================================
--- openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/JDBCConfigurationImpl.java (original)
+++ openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/conf/JDBCConfigurationImpl.java Wed Jun  6 11:49:30 2007
@@ -214,9 +214,11 @@
         updateManagerPlugin = addPlugin("jdbc.UpdateManager", true);
         aliases = new String[]{
             "default",
-            "org.apache.openjpa.jdbc.kernel.OperationOrderUpdateManager",
+            "org.apache.openjpa.jdbc.kernel.ConstraintUpdateManager",
             "operation-order",
             "org.apache.openjpa.jdbc.kernel.OperationOrderUpdateManager",
+            "constraint",
+            "org.apache.openjpa.jdbc.kernel.ConstraintUpdateManager",
         };
         updateManagerPlugin.setAliases(aliases);
         updateManagerPlugin.setDefault(aliases[0]);

Added: openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java (added)
+++ openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,419 @@
+/*
+ * 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.jdbc.kernel;
+
+import java.sql.Connection;
+import java.sql.SQLException;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.Map;
+
+import org.apache.openjpa.jdbc.meta.ClassMapping;
+import org.apache.openjpa.jdbc.schema.Column;
+import org.apache.openjpa.jdbc.schema.ForeignKey;
+import org.apache.openjpa.jdbc.schema.Table;
+import org.apache.openjpa.jdbc.sql.PrimaryRow;
+import org.apache.openjpa.jdbc.sql.Row;
+import org.apache.openjpa.jdbc.sql.RowImpl;
+import org.apache.openjpa.jdbc.sql.RowManager;
+import org.apache.openjpa.jdbc.sql.RowManagerImpl;
+import org.apache.openjpa.jdbc.sql.SQLExceptions;
+import org.apache.openjpa.kernel.OpenJPAStateManager;
+import org.apache.openjpa.lib.graph.DepthFirstAnalysis;
+import org.apache.openjpa.lib.graph.Edge;
+import org.apache.openjpa.lib.graph.Graph;
+import org.apache.openjpa.lib.util.Localizer;
+import org.apache.openjpa.util.InternalException;
+import org.apache.openjpa.util.OpenJPAException;
+
+/**
+ * <p>Standard update manager, capable of foreign key constraint evaluation.</p>
+ *
+ * @since 1.0.0
+ */
+public class ConstraintUpdateManager
+    extends AbstractUpdateManager {
+
+    private static final Localizer _loc = Localizer.forPackage
+        (ConstraintUpdateManager.class);
+
+    public boolean orderDirty() {
+        return false;
+    }
+
+    protected PreparedStatementManager newPreparedStatementManager
+        (JDBCStore store, Connection conn) {
+        return new PreparedStatementManagerImpl(store, conn);
+    }
+
+    protected RowManager newRowManager() {
+        return new RowManagerImpl(false);
+    }
+
+    protected Collection flush(RowManager rowMgr,
+        PreparedStatementManager psMgr, Collection exceps) {
+        RowManagerImpl rmimpl = (RowManagerImpl) rowMgr;
+
+        // first take care of all secondary table deletes and 'all row' deletes
+        // (which are probably secondary table deletes), since no foreign
+        // keys ever rely on secondary table pks
+        flush(rmimpl.getAllRowDeletes(), psMgr);
+        flush(rmimpl.getSecondaryDeletes(), psMgr);
+
+        // now do any 'all row' updates
+        flush(rmimpl.getAllRowUpdates(), psMgr);
+
+        // analyze foreign keys
+        Collection inserts = rmimpl.getInserts();
+        Collection updates = rmimpl.getUpdates();
+        Collection deletes = rmimpl.getDeletes();
+        Graph[] graphs = new Graph[2];    // insert graph, delete graph
+        analyzeForeignKeys(inserts, updates, deletes, rmimpl, graphs);
+
+        // flush insert graph, if any
+        boolean autoAssign = rmimpl.hasAutoAssignConstraints();
+        try {
+            flushGraph(graphs[0], psMgr, autoAssign);
+        } catch (SQLException se) {
+            exceps = addException(exceps, SQLExceptions.getStore(se, dict));
+        } catch (OpenJPAException ke) {
+            exceps = addException(exceps, ke);
+        }
+
+        // flush the rest of the inserts and updates; inserts before updates
+        // because some update fks might reference pks that have to be inserted
+        flush(inserts, psMgr);
+        flush(updates, psMgr);
+
+        // flush the delete graph, if any
+        try {
+            flushGraph(graphs[1], psMgr, autoAssign);
+        } catch (SQLException se) {
+            exceps = addException(exceps, SQLExceptions.getStore(se, dict));
+        } catch (OpenJPAException ke) {
+            exceps = addException(exceps, ke);
+        }
+
+        // put the remainder of the deletes after updates because some updates
+        // may be nulling fks to rows that are going to be deleted
+        flush(deletes, psMgr);
+
+        // take care of all secondary table inserts and updates last, since
+        // they may rely on previous inserts or updates, but nothing relies
+        // on them
+        flush(rmimpl.getSecondaryUpdates(), psMgr);
+
+        // flush any left over prepared statements
+        psMgr.flush();
+        return exceps;
+    }
+
+    /**
+     * Analyze foreign key dependencies on the given rows
+     * and create an insert and a delete graph to execute.  The insert
+     * graph will be flushed before all other rows, and the delete graph will
+     * be flushed after them.
+     */
+    private void analyzeForeignKeys(Collection inserts, Collection updates,
+        Collection deletes, RowManagerImpl rowMgr, Graph[] graphs) {
+        // if there are any deletes, we have to map the insert objects on their
+        // oids so we'll be able to detect delete-then-insert-same-pk cases
+        Map insertMap = null;
+        OpenJPAStateManager sm;
+        if (!deletes.isEmpty() && !inserts.isEmpty()) {
+            insertMap = new HashMap((int) (inserts.size() * 1.33 + 1));
+            for (Iterator itr = inserts.iterator(); itr.hasNext();) {
+                sm = ((Row) itr.next()).getPrimaryKey();
+                if (sm != null && sm.getObjectId() != null)
+                    insertMap.put(sm.getObjectId(), sm);
+            }
+        }
+
+        // first construct the graph for deletes; this may expand to include
+        // inserts and updates as well if there are any inserts that rely on
+        // deletes (delete-then-insert-same-pk cases)
+        PrimaryRow row;
+        Row row2;
+        ForeignKey[] fks;
+        OpenJPAStateManager fkVal;
+        boolean ignoreUpdates = true;
+        for (Iterator itr = deletes.iterator(); itr.hasNext();) {
+            row = (PrimaryRow) itr.next();
+            if (!row.isValid())
+                continue;
+
+            row2 = getInsertRow(insertMap, rowMgr, row);
+            if (row2 != null) {
+                ignoreUpdates = false;
+                graphs[1] = addEdge(graphs[1], row, (PrimaryRow) row2, null);
+            }
+
+            // now check this row's fks against other deletes
+            fks = row.getTable().getForeignKeys();
+            for (int j = 0; j < fks.length; j++) {
+                // when deleting ref fks they'll just set a where value, so
+                // check both for fk updates (relation fks) and wheres (ref fks)
+                fkVal = row.getForeignKeySet(fks[j]);
+                if (fkVal == null)
+                    fkVal = row.getForeignKeyWhere(fks[j]);
+                if (fkVal == null)
+                    continue;
+
+                row2 = rowMgr.getRow(fks[j].getPrimaryKeyTable(),
+                    Row.ACTION_DELETE, fkVal, false);
+                if (row2 != null && row2.isValid() && row2 != row)
+                    graphs[1] = addEdge(graphs[1], row, (PrimaryRow) row2,
+                        fks[j]);
+            }
+        }
+
+        if (ignoreUpdates)
+            graphs[0] = analyzeAgainstInserts(inserts, rowMgr, graphs[0]);
+        else {
+            // put inserts *and updates* in the delete graph; they all rely
+            // on each other
+            graphs[1] = analyzeAgainstInserts(updates, rowMgr, graphs[1]);
+            graphs[1] = analyzeAgainstInserts(inserts, rowMgr, graphs[1]);
+        }
+    }
+
+    /**
+     * Check to see if there is an insert for for the same table and primary
+     * key values as the given delete row.
+     */
+    private Row getInsertRow(Map insertMap, RowManagerImpl rowMgr, Row row) {
+        if (insertMap == null)
+            return null;
+
+        OpenJPAStateManager sm = row.getPrimaryKey();
+        if (sm == null)
+            return null;
+
+        // look for a new object whose insert id is the same as this delete one
+        Object oid = sm.getObjectId();
+        OpenJPAStateManager nsm = (OpenJPAStateManager) insertMap.get(oid);
+        if (nsm == null)
+            return null;
+
+        // found new object; get its row
+        row = rowMgr.getRow(row.getTable(), Row.ACTION_INSERT, nsm, false);
+        return (row == null || row.isValid()) ? row : null;
+    }
+
+    /**
+     * Analyze the given rows against the inserts, placing dependencies
+     * in the given graph.
+     */
+    private Graph analyzeAgainstInserts(Collection rows, RowManagerImpl rowMgr,
+        Graph graph) {
+        PrimaryRow row;
+        Row row2;
+        ForeignKey[] fks;
+        Column[] cols;
+        for (Iterator itr = rows.iterator(); itr.hasNext();) {
+            row = (PrimaryRow) itr.next();
+            if (!row.isValid())
+                continue;
+
+            // check this row's fks against inserts; a logical fk to an auto-inc
+            // column is treated just as actual database fk because the result
+            // is the same: the pk row has to be inserted before the fk row
+            fks = row.getTable().getForeignKeys();
+            for (int j = 0; j < fks.length; j++) {
+                if (row.getForeignKeySet(fks[j]) == null)
+                    continue;
+
+                // see if this row is dependent on another.  if it's only
+                // depenent on itself, see if the fk is logical or deferred, in
+                // which case it must be an auto-inc because otherwise we
+                // wouldn't have recorded it
+                row2 = rowMgr.getRow(fks[j].getPrimaryKeyTable(),
+                    Row.ACTION_INSERT, row.getForeignKeySet(fks[j]), false);
+                if (row2 != null && row2.isValid() && (row2 != row
+                    || fks[j].isDeferred() || fks[j].isLogical()))
+                    graph = addEdge(graph, (PrimaryRow) row2, row, fks[j]);
+            }
+
+            // see if there are any relation id columns dependent on
+            // auto-inc objects
+            cols = row.getTable().getRelationIdColumns();
+            for (int j = 0; j < cols.length; j++) {
+                OpenJPAStateManager sm = row.getRelationIdSet(cols[j]);
+                if (sm == null)
+                    continue;
+
+                row2 = rowMgr.getRow(getBaseTable(sm), Row.ACTION_INSERT,
+                    sm, false);
+                if (row2 != null && row2.isValid())
+                    graph = addEdge(graph, (PrimaryRow) row2, row, cols[j]);
+            }
+        }
+        return graph;
+    }
+
+    /**
+     * Return the base table for the given instance.
+     */
+    private static Table getBaseTable(OpenJPAStateManager sm) {
+        ClassMapping cls = (ClassMapping) sm.getMetaData();
+        while (cls.getJoinablePCSuperclassMapping() != null)
+            cls = cls.getJoinablePCSuperclassMapping();
+        return cls.getTable();
+    }
+
+    /**
+     * Add an edge between the given rows in the given foreign key graph.
+     */
+    private Graph addEdge(Graph graph, PrimaryRow row1, PrimaryRow row2,
+        Object fk) {
+        // delay creation of the graph
+        if (graph == null)
+            graph = new Graph();
+
+        row1.setDependent(true);
+        row2.setDependent(true);
+        graph.addNode(row1);
+        graph.addNode(row2);
+
+        // add an edge from row1 to row2, and set the fk causing the
+        // dependency as the user object so we can retrieve it when resolving
+        // circular constraints
+        Edge edge = new Edge(row1, row2, true);
+        edge.setUserObject(fk);
+        graph.addEdge(edge);
+
+        return graph;
+    }
+
+    /**
+     * Flush the given graph of rows in the proper order.
+     * @param graph The graph of statements to be walked
+     * @param psMgr The prepared statement manager to use to issue the
+     * statements
+     * @param autoAssign Whether any of the rows in the graph have any
+     * auto-assign constraints
+     */
+    protected void flushGraph(Graph graph, PreparedStatementManager psMgr,
+        boolean autoAssign)
+        throws SQLException {
+        if (graph == null)
+            return;
+
+        DepthFirstAnalysis dfa = newDepthFirstAnalysis(graph, autoAssign);
+        Collection nodes = dfa.getSortedNodes();
+        Collection backs = dfa.getEdges(Edge.TYPE_BACK);
+
+        // handle circular constraints:
+        // - if deleted row A has a ciricular fk to deleted row B, then use an
+        //   update statement to null A's fk to B
+        // - if inserted row A has a circular fk to updated/inserted row B,
+        //   then null the fk in the B row object, and after flushing, use
+        //   an update to set the fk to back to A
+        Collection insertUpdates = null;
+        Collection deleteUpdates = null;
+        PrimaryRow row;
+        RowImpl update;
+        Edge edge;
+        ForeignKey fk;
+        Column col;
+        for (Iterator itr = backs.iterator(); itr.hasNext();) {
+            edge = (Edge) itr.next();
+            if (edge.getUserObject() == null)
+                throw new InternalException(_loc.get("del-ins-cycle"));
+
+            // use a primary row update to prevent setting pk and fk values
+            // until after flush, to get latest auto-increment values
+            row = (PrimaryRow) edge.getTo();
+            if (row.getAction() == Row.ACTION_DELETE) {
+                // copy where conditions into new update that nulls the fk
+                row = (PrimaryRow) edge.getFrom();
+                update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE,null);
+                row.copyInto(update, true);
+                if (edge.getUserObject() instanceof ForeignKey) {
+                    fk = (ForeignKey) edge.getUserObject();
+                    update.setForeignKey(fk, row.getForeignKeyIO(fk), null);
+                } else
+                    update.setNull((Column) edge.getUserObject());
+
+                if (deleteUpdates == null)
+                    deleteUpdates = new LinkedList();
+                deleteUpdates.add(update);
+            } else {
+                // copy where conditions into new update that sets the fk
+                update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE,null);
+                if (row.getAction() == Row.ACTION_INSERT) {
+                    if (row.getPrimaryKey() == null)
+                        throw new InternalException(_loc.get("ref-cycle"));
+                    update.wherePrimaryKey(row.getPrimaryKey());
+                } else
+                    row.copyInto(update, true);
+                if (edge.getUserObject() instanceof ForeignKey) {
+                    fk = (ForeignKey) edge.getUserObject();
+                    update.setForeignKey(fk, row.getForeignKeyIO(fk),
+                        row.getForeignKeySet(fk));
+                    row.clearForeignKey(fk);
+                } else {
+                    col = (Column) edge.getUserObject();
+                    update.setRelationId(col, row.getRelationIdSet(col),
+                        row.getRelationIdCallback(col));
+                    row.clearRelationId(col);
+                }
+
+                if (insertUpdates == null)
+                    insertUpdates = new LinkedList();
+                insertUpdates.add(update);
+            }
+        }
+
+        // flush delete updates to null fks, then all rows in order, then
+        // the insert updates to set circular fk values
+        if (deleteUpdates != null)
+            flush(deleteUpdates, psMgr);
+        for (Iterator itr = nodes.iterator(); itr.hasNext();)
+            psMgr.flush((RowImpl) itr.next());
+        if (insertUpdates != null)
+            flush(insertUpdates, psMgr);
+	}
+
+    /**
+     * Create a new {@link DepthFirstAnalysis} suitable for the given graph
+     * and auto-assign settings.
+     */
+    protected DepthFirstAnalysis newDepthFirstAnalysis(Graph graph,
+        boolean autoAssign) {
+        return new DepthFirstAnalysis(graph);
+    }
+
+    /**
+     * Flush the given collection of secondary rows.
+     */
+    protected void flush(Collection rows, PreparedStatementManager psMgr) {
+        if (rows.size() == 0)
+            return;
+
+        RowImpl row;
+        for (Iterator itr = rows.iterator(); itr.hasNext(); ) {
+            row = (RowImpl) itr.next();
+            if (row.isValid() && !row.isDependent())
+                psMgr.flush(row);
+        }
+    }
+}
\ No newline at end of file

Added: 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?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/BreadthFirstWalk.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,145 @@
+/*
+ * 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.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;
+import java.util.Set;
+
+/**
+ * <p>Performs a breadth-first walk of a given {@link Graph},
+ * notifying visitors as it sees each node.  See the BFS algorithm
+ * in the book 'Introduction to Algorithms' by Cormen, Leiserson, and
+ * Rivest.</p>
+ * <p/>
+ * <p>Each {@link GraphVisitor} will be notified when a node
+ * is colored black (nodeVisited), edge seen (edgeVisited),
+ * and a node is seen for the first time, i.e. colored gray (nodeSeen).</p>
+ *
+ * @author Steve Kim
+ * @since 1.0.0
+ * @nojavadoc
+ */
+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();
+
+    public BreadthFirstWalk(Graph graph) {
+        _graph = graph;
+    }
+
+    /**
+     * Begins the breadth first traversal.
+     */
+    public void walk() {
+        _queue.clear();
+        _nodeInfo.clear();
+
+        Collection nodes = _graph.getNodes();
+        for (Iterator itr = nodes.iterator(); itr.hasNext();)
+            _nodeInfo.put(itr.next(), new NodeInfo());
+
+        Object node;
+        NodeInfo info;
+        for (Iterator itr = nodes.iterator(); itr.hasNext();) {
+            node = itr.next();
+            info = (NodeInfo) _nodeInfo.get(node);
+            if (info.color == NodeInfo.COLOR_WHITE)
+                enqueue(node, info);
+            processQueue();
+        }
+    }
+
+    /**
+     * 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);
+            visit(node, info);
+
+            edges = _graph.getEdgesFrom(node);
+            for (Iterator itr = edges.iterator(); itr.hasNext();) {
+                edge = (Edge) itr.next();
+                edgeVisited(edge);
+                other = edge.getOther(node);
+                otherInfo = (NodeInfo) _nodeInfo.get(other);
+                if (otherInfo.color == NodeInfo.COLOR_WHITE)
+                    enqueue(other, otherInfo);
+            }
+        }
+    }
+
+    /**
+     * Push the given node onto the queue to be processed.
+     * Notify visitors.
+     */
+    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);
+    }
+
+    /**
+     * Visit the node.  Mark the node black and notify visitors.
+     */
+    protected void visit(Object node, NodeInfo info) {
+        info.color = NodeInfo.COLOR_BLACK;
+        for (Iterator i = _visitors.iterator(); i.hasNext();)
+            ((GraphVisitor) i.next()).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);
+    }
+
+    /**
+     * add a {@link GraphVisitor} to be notified during breadth first search.
+     */
+    public void addGraphVisitor(GraphVisitor visitor) {
+        _visitors.add(visitor);
+    }
+
+    /**
+     * remove a given {@link GraphVisitor} from the listener set.
+     */
+    public void removeGraphVisitor(GraphVisitor visitor) {
+        _visitors.remove(visitor);
+    }
+}

Added: 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?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,215 @@
+/*
+ * 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.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.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 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);
+        }
+    }
+
+    /**
+     * Visit a node.  See Introduction to Algorithms book for details.
+     */
+    private int visit(Graph graph, Object node, NodeInfo info, int time) {
+        // 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
+                childTime = visit(graph, other, otherInfo, time);
+                edge.setType(Edge.TYPE_TREE);
+            } else if (otherInfo.color == NodeInfo.COLOR_GRAY) {
+                childTime = -1;
+                edge.setType(Edge.TYPE_BACK);
+            } else {
+                childTime = otherInfo.finished;
+                edge.setType(Edge.TYPE_FORWARD);
+            }
+            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_BACK} 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;
+    }
+
+    /**
+     * 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();
+
+            // reverse finished order
+            int ret = n2.finished - n1.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;
+		}
+	}
+}

Added: 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?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,189 @@
+/*
+ * 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 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;
+
+    /**
+     * 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 == node)
+            return _from;
+        if (_from == 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 == node || (!_directed && _from == 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 == node || (!_directed && _to == 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;
+    }
+
+    /**
+     * Clear traversal info.
+     */
+    public void clearTraversal() {
+        _type = 0;
+    }
+
+    public String toString() {
+        return super.toString() + "[from=" + getFrom() + ";to=" + getTo()
+            + ";directed=" + isDirected () + ";weight=" + getWeight () + "]";
+	}
+}

Added: 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?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Graph.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,199 @@
+/*
+ * 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.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+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
+    private final Map _nodes = new HashMap();
+
+    /**
+     * 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 ();
+		}
+	}
+}

Added: openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/GraphVisitor.java Wed Jun  6 11:49:30 2007
@@ -0,0 +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);
+}

Added: openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/NodeInfo.java Wed Jun  6 11:49:30 2007
@@ -0,0 +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;
+}

Added: openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/package.html
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/package.html?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/package.html (added)
+++ openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/package.html Wed Jun  6 11:49:30 2007
@@ -0,0 +1,27 @@
+<!--
+ 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.
+-->
+<html>
+<body>
+<p><strong>Graph Abstraction</strong></p>
+
+<p>
+    This package provides a graph abstraction and graph-related algorithms.
+</p>
+</body>
+</html>

Added: openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java (added)
+++ openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,80 @@
+/*
+ * 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.Collection;
+import java.util.Iterator;
+
+import org.apache.openjpa.lib.test.AbstractTestCase;
+
+/**
+ * <p>Tests the {@link DepthFirstAnalysis} type.</p>
+ *
+ * @author Abe White
+ */
+public class TestDepthFirstAnalysis
+    extends AbstractTestCase {
+
+    private DepthFirstAnalysis _dfa = null;
+
+    public void setUp() {
+        Graph graph = new Graph();
+        Object node1 = new Object();
+        Object node2 = new Object();
+        Object node3 = new Object();
+        Object node4 = new Object();
+        graph.addNode(node1);
+        graph.addNode(node2);
+        graph.addNode(node3);
+        graph.addNode(node4);
+        graph.addEdge(new Edge(node1, node2, true));
+        graph.addEdge(new Edge(node2, node3, true));
+        graph.addEdge(new Edge(node3, node1, true));
+        graph.addEdge(new Edge(node3, node4, true));
+        graph.addEdge(new Edge(node2, node2, true));
+        _dfa = new DepthFirstAnalysis(graph);
+    }
+
+    public void testNodeSorting() {
+        Collection nodes = _dfa.getSortedNodes();
+        assertEquals(4, nodes.size());
+
+        int time = Integer.MAX_VALUE;
+        Object node;
+        for (Iterator itr = nodes.iterator(); itr.hasNext();) {
+            node = itr.next();
+            assertTrue(time >= _dfa.getFinishedTime(node));
+            time = _dfa.getFinishedTime(node);
+        }
+    }
+
+    public void testEdgeTyping() {
+        Collection edges = _dfa.getEdges(Edge.TYPE_BACK);
+        assertEquals(2, edges.size());
+        Iterator itr = edges.iterator();
+        Edge edge0 = (Edge) itr.next();
+        Edge edge1 = (Edge) itr.next();
+        assertTrue((edge0.getTo() == edge0.getFrom())
+            || edge1.getTo() == edge1.getFrom());
+    }
+
+    public static void main(String[] args) {
+        main(TestDepthFirstAnalysis.class);
+    }
+}

Added: openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestGraph.java
URL: http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestGraph.java?view=auto&rev=544918
==============================================================================
--- openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestGraph.java (added)
+++ openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestGraph.java Wed Jun  6 11:49:30 2007
@@ -0,0 +1,148 @@
+/*
+ * 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.Collection;
+import java.util.Iterator;
+
+import org.apache.openjpa.lib.test.AbstractTestCase;
+
+/**
+ * <p>Tests the {@link Graph} type, and in so doing implicitly tests the
+ * {@link Edge} as well.</p>
+ *
+ * @author Abe White
+ */
+public class TestGraph
+    extends AbstractTestCase {
+
+    private Graph _graph = new Graph();
+    private Object _node1 = new Object();
+    private Object _node2 = new Object();
+    private Object _node3 = new Object();
+    private Edge _edge1 = new Edge(_node1, _node2, true);
+    private Edge _edge2 = new Edge(_node2, _node3, true);
+    private Edge _edge3 = new Edge(_node1, _node3, false);
+    private Edge _edge4 = new Edge(_node2, _node2, false);
+
+    public void setUp() {
+        _graph.addNode(_node1);
+        _graph.addNode(_node2);
+        _graph.addNode(_node3);
+        _graph.addEdge(_edge1);
+        _graph.addEdge(_edge2);
+        _graph.addEdge(_edge3);
+        _graph.addEdge(_edge4);
+    }
+
+    /**
+     * Tests adding and retrieving nodes and edges.
+     */
+    public void testAddRetrieve() {
+        assertEquals(3, _graph.getNodes().size());
+        assertEquals(4, _graph.getEdges().size());
+
+        Collection edges = _graph.getEdgesFrom(_node1);
+        assertEquals(2, edges.size());
+        Iterator itr = edges.iterator();
+        Edge edge0 = (Edge) itr.next();
+        Edge edge1 = (Edge) itr.next();
+        assertTrue((edge0 == _edge1 && edge1 == _edge3)
+            || (edge0 == _edge3 && edge1 == _edge1));
+
+        edges = _graph.getEdgesTo(_node1);
+        assertEquals(1, edges.size());
+        assertEquals(_edge3, edges.iterator().next());
+
+        edges = _graph.getEdges(_node1, _node3);
+        assertEquals(1, edges.size());
+        assertEquals(_edge3, edges.iterator().next());
+        edges = _graph.getEdges(_node3, _node1);
+        assertEquals(1, edges.size());
+        assertEquals(_edge3, edges.iterator().next());
+
+        edges = _graph.getEdgesFrom(_node2);
+        assertEquals(2, edges.size());
+        itr = edges.iterator();
+        edge0 = (Edge) itr.next();
+        edge1 = (Edge) itr.next();
+        assertTrue((edge0 == _edge2 && edge1 == _edge4)
+            || (edge0 == _edge4 && edge1 == _edge2));
+
+        edges = _graph.getEdgesTo(_node2);
+        assertEquals(2, edges.size());
+        itr = edges.iterator();
+        edge0 = (Edge) itr.next();
+        edge1 = (Edge) itr.next();
+        assertTrue((edge0 == _edge1 && edge1 == _edge4)
+            || (edge0 == _edge4 && edge1 == _edge1));
+
+        edges = _graph.getEdges(_node2, _node2);
+        assertEquals(1, edges.size());
+        assertEquals(_edge4, edges.iterator().next());
+
+        edges = _graph.getEdgesFrom(_node3);
+        assertEquals(1, edges.size());
+        assertEquals(_edge3, edges.iterator().next());
+    }
+
+    /**
+     * Test removing edges.
+     */
+    public void testRemoveEdges() {
+        assertTrue(_graph.removeEdge(_edge2));
+        Collection edges = _graph.getEdgesFrom(_node2);
+        assertEquals(1, edges.size());
+        assertEquals(_edge4, edges.iterator().next());
+
+        assertTrue(_graph.removeEdge(_edge3));
+        edges = _graph.getEdgesFrom(_node1);
+        assertEquals(1, edges.size());
+        assertEquals(_edge1, edges.iterator().next());
+        edges = _graph.getEdgesTo(_node1);
+        assertEquals(0, edges.size());
+        edges = _graph.getEdgesTo(_node3);
+        assertEquals(0, edges.size());
+        edges = _graph.getEdgesFrom(_node3);
+        assertEquals(0, edges.size());
+    }
+
+    /**
+     * Test removing nodes.
+     */
+    public void testRemoveNodes() {
+        assertTrue(_graph.removeNode(_node3));
+        Collection edges = _graph.getEdges();
+        assertEquals(2, edges.size());
+        Iterator itr = edges.iterator();
+        Edge edge0 = (Edge) itr.next();
+        Edge edge1 = (Edge) itr.next();
+        assertTrue((edge0 == _edge1 && edge1 == _edge4)
+            || (edge0 == _edge4 && edge1 == _edge1));
+        edges = _graph.getEdgesFrom(_node1);
+        assertEquals(1, edges.size());
+        assertEquals(_edge1, edges.iterator().next());
+        edges = _graph.getEdgesTo(_node1);
+        assertEquals(0, edges.size());
+    }
+
+    public static void main(String[] args) {
+        main(TestGraph.class);
+	}
+}



Mime
View raw message