tuscany-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From lrese...@apache.org
Subject svn commit: r652897 - /incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java
Date Fri, 02 May 2008 20:34:32 GMT
Author: lresende
Date: Fri May  2 13:34:32 2008
New Revision: 652897

URL: http://svn.apache.org/viewvc?rev=652897&view=rev
Log:
TUSCANY-2288 - Patch from Florian Pinal with updates to  MappingWrapper.getInsertOrder() algorithm

Modified:
    incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java

Modified: incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java
URL: http://svn.apache.org/viewvc/incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java?rev=652897&r1=652896&r2=652897&view=diff
==============================================================================
--- incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java
(original)
+++ incubator/tuscany/java/das/rdb/src/main/java/org/apache/tuscany/das/rdb/config/wrapper/MappingWrapper.java
Fri May  2 13:34:32 2008
@@ -22,9 +22,11 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.Vector;
 
 import org.apache.log4j.Logger;
@@ -51,6 +53,12 @@
     private final Logger logger = Logger.getLogger(MappingWrapper.class);
 
     private Config config;
+    
+	// TUSCANY-2288
+	private List insertOrder;
+	private List deleteOrder;
+	// --
+
 
     public MappingWrapper() {
         config = FACTORY.createConfig();
@@ -600,57 +608,143 @@
         return results;
     }
 
-    // TODO optimize
-    public List getInsertOrder() {
-        if (this.logger.isDebugEnabled()) {
-            this.logger.debug("Getting insert order");
-        }
-
-        List inserts = new ArrayList();
-        Map parentToChild = new HashMap();
-
-        List parents = new ArrayList();
-        List children = new ArrayList();
-        if (config != null) {
-            Iterator i = getConfig().getRelationship().iterator();
-            while (i.hasNext()) {
-                Relationship r = (Relationship) i.next();
-                parents.add(r.getPrimaryKeyTable());
-                children.add(r.getForeignKeyTable());
-                parentToChild.put(r.getPrimaryKeyTable(), r.getForeignKeyTable());
-            }
-            while (parents.size() > 0) {
-                String parent = (String) parents.get(0);
-                if (!children.contains(parent)) {
-                    if (!inserts.contains(parent)) {
-                        inserts.add(parent);
-                    }
-                    String child = (String) parentToChild.get(parent);
-                    if (!inserts.contains(child)) {
-                        inserts.add(child);
-                    }
-                    parents.remove(parent);
-                    children.remove(child);
-                } else {
-                    parents.add(parents.remove(0));
-                }
-            }
-            inserts.addAll(children);
-        }
-
-        if (this.logger.isDebugEnabled()) {
-            this.logger.debug(inserts);
-        }
+	// TUSCANY-2288
+	public List getInsertOrder() {
+		if (this.logger.isDebugEnabled()) {
+			this.logger.debug("Getting insert order");
+		}
+		if (insertOrder == null) {
+			insertOrder = new ArrayList();
+			if (config == null) return insertOrder;
+			// correct insert order: tables sorted by ascending depth
+			// parse all relationships
+			Set allParents = new HashSet();
+			Set allChildren = new HashSet();
+			Map parentToChild = new HashMap();
+			Iterator i = getConfig().getRelationship().iterator();
+			while (i.hasNext()) {
+				Relationship r = (Relationship) i.next();
+				String parent = r.getPrimaryKeyTable();
+				String child = r.getForeignKeyTable();
+				if (parent.equals(child)) {
+					// self-relationship
+					// do not add to parent to child map to avoid loops
+					// do not add to all children list to allow root detection
+					allParents.add(parent);
+				} else {
+					allParents.add(parent);
+					allChildren.add(child);
+					Set children = (Set) parentToChild.get(parent);
+					if (children == null) {
+						children = new HashSet();
+						parentToChild.put(parent, children);
+					}
+					children.add(child);
+				}
+			}
+			// build list of tables ordered by depth
+			List depthList = new ArrayList();
+			// find roots (depth 0)
+			// roots are tables that are present in the parents set, but not in the children set
+			Set roots = new HashSet();
+			for (Iterator itParents = allParents.iterator(); itParents.hasNext(); ) {
+				String parent = (String) itParents.next();
+				if (!allChildren.contains(parent)) {
+					roots.add(parent);
+				}
+			}
+			// traverse table graph to populate depth list
+			traverseTableGraph(roots, 0, parentToChild, depthList, new ArrayList());
+			// build insert order from depth list
+			for (Iterator itDepths = depthList.iterator(); itDepths.hasNext(); ) {
+				Set tables = (Set) itDepths.next();
+				insertOrder.addAll(tables);
+			}
+		}
+		if (this.logger.isDebugEnabled()) {
+			this.logger.debug(insertOrder);
+		}
+		return insertOrder;
+	}
+
+	private void traverseTableGraph(Set parents, int parentDepth, Map parentToChild, List depthList,
List branch) {
+		int childDepth = parentDepth + 1;
+		// expand depth list if necessary
+		for (int i = depthList.size() - 1; i < parentDepth; i++) {
+			Set tables = new HashSet();
+			depthList.add(tables);
+		}
+		// loop thru parents
+		for (Iterator itParents = parents.iterator(); itParents.hasNext(); ) {
+			String parent = (String) itParents.next();
+			if (branch.contains(parent)) {
+				// we found a cycle
+				// we don't handle cycles
+				// stop traversing branch to avoid infinite loop
+				break;
+			}
+			// add parent to depth list
+			addTableToDepthList(parent, parentDepth, depthList);
+			// make recursive call on children
+			Set children = (Set) parentToChild.get(parent);
+			if (children != null && children.size() > 0) {
+				List parentBranch = new ArrayList();
+				parentBranch.addAll(branch);
+				parentBranch.add(parent);
+				traverseTableGraph(children, childDepth, parentToChild, depthList, parentBranch);
+			}
+		}
+	}
+
+	private void addTableToDepthList(String table, int depth, List depthList) {
+		// in this method, keep in mind that the same table can appear multiple times at multiple
depths inside the table graph
+		// check if table is already somewhere in depth list
+		int currentDepth = getTableDepth(table, depthList);
+		if (currentDepth == -1) {
+			// table not in depth list
+			// add it
+			Set tables = (Set) depthList.get(depth);
+			tables.add(table);
+		} else if (currentDepth < depth) {
+			// table already in depth list, at a lower depth
+			// the table should only be present once, at the greatest possible depth
+			// replace table at the new depth
+			Set tables = (Set) depthList.get(currentDepth);
+			tables.remove(table);
+			tables = (Set) depthList.get(depth);
+			tables.add(table);
+		} else {
+			// table already in depth list, at a greater or same depth
+			// nothing to do, since the table should only be present once, at the greatest possible
depth
+		}
+	}
+
+	private int getTableDepth(String table, List depthList) {
+		int depth = -1;
+		// loop thru depth list
+		int count = depthList.size();
+		for (int i = 0; i < count; i++) {
+			Set tables = (Set) depthList.get(i);
+			if (tables != null && tables.contains(table)) {
+				depth = i;
+				break;
+			}
+		}
+		return depth;
+	}
+
+
+	public List getDeleteOrder() {
+		if (deleteOrder == null) {
+			deleteOrder = new ArrayList();
+			deleteOrder.addAll(getInsertOrder());
+			Collections.reverse(deleteOrder);
+		}
+		return deleteOrder;
+	}
 
-        return inserts;
-    }
+	// --
 
-    public List getDeleteOrder() {
-        List deleteOrder = new ArrayList();
-        deleteOrder.addAll(getInsertOrder());
-        Collections.reverse(deleteOrder);
-        return deleteOrder;
-    }
 
     //JIRA-952
     public void addConverter(String name, String converter) {



Mime
View raw message