You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@openjpa.apache.org by pc...@apache.org on 2007/06/06 20:49:32 UTC
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...
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);
+ }
+}