1 package com.sri.emo.dbobj.selectiontree;
2
3 import java.util.Collection;
4 import java.util.Iterator;
5 import java.util.Map;
6 import com.jcorporate.expresso.core.db.DBException;
7 import com.sri.emo.dbobj.Node;
8 import com.sri.emo.dbobj.Relation;
9
10 /***
11 * Helps with the the selection of nodes in an association tree.
12 *
13 * Depends on all nodes having attributes set that indicate their immediate
14 * chilren, from TreeSlectionFactory.
15 * The general
16 * algorithm for selecting necessary nodes is this:
17 * <h4>Step 1: Build Tree</h4>
18 * <p>Get a list of all nodes that belong in the tree via strong relations
19 * </p>
20 * <h4>Step 2: Trim Nodes with External Links</h4>
21 * <p>Trim the bulk of the tree by finding any nodes that are the destinations
22 * via any strong relations of nodes outside the tree.
23 * <p>The algorithm for this step is:</p>
24 * <p/>
25 * <pre>
26 * for each node N in allNodesInTree
27 * if N is destination of strong relation not in allNodesTree
28 * save N (Mark as do not delete)
29 * end if
30 * end for
31 * </pre>
32 * </p>
33 * <h4>Step 3: save children of any parent that is saved.</h4>
34 * <p>The situation here arises when <tt>External Link -> Node B -> Node A</tt>
35 * Node A won't register any external links, and will be marked for deletion
36 * when it shouldn't be. We use the following algorithm to trim transitive
37 * associations, where "ROOT DOWN ORDER" means from the root of the tree to the leaves:</p>
38 * <p><pre>
39 * for each node N IN ROOT DOWN ORDER
40 * if N is saved, and is parent of node to be deleted
41 * move child nodes from "To Delete" collection to "Save" collection
42 * recurse down from each child
43 * end if
44 * end for.
45 * </pre></p>
46 *
47 * @author Michael Rimov, Larry Hamel
48 */
49 public class TreeDeletionSelector {
50
51 /***
52 * A map of all nodes in a tree marked for deletion
53 * keyed by ID pointing to nodes.
54 */
55 private final Map allNodes;
56
57 /***
58 * Build the selector with all nodes in the tree to delete.
59 *
60 * @param allNodes Map
61 */
62 public TreeDeletionSelector(Map allNodes) {
63 this.allNodes = allNodes;
64 }
65
66 /***
67 * After step 1 is completed (see class-level javadoc), this function
68 * performs the remaining deletion steps.
69 *
70 * @param rootToDelete The root of the tree to delete. It is best
71 * to use a collection that can have speedy iteration and deletions.
72 * @param toSave A collection to be built of objects to save. It is
73 * better to use a collection that can have speedy lookups and insertions.
74 * @param toDelete A collection to be built of objects to delete.
75 * @throws DBException upon Expresso database error.
76 */
77 public void determineDeletionTree(final Node rootToDelete, final Collection toSave,
78 final Collection toDelete) throws DBException {
79
80
81
82
83
84 for (Iterator i = allNodes.values().iterator(); i.hasNext();) {
85 Node eachNode = (Node) i.next();
86 if (isDestOfExternal(eachNode)) {
87 toSave.add(eachNode);
88 } else {
89 toDelete.add(eachNode);
90 }
91 }
92
93
94 toSave.remove(rootToDelete);
95
96
97 toDelete.remove(rootToDelete);
98
99 saveChildrenOfSaved(toDelete, toSave, rootToDelete);
100
101
102 toSave.remove(rootToDelete);
103
104
105 toDelete.remove(rootToDelete);
106 }
107
108 /***
109 * traverse tree from root down, and
110 * save any children of parents that are saved
111 *
112 * @param toDelete A collection of items marked for deletion. Fast iteration
113 * is better for this object's instance selection.
114 * @param toSave A collection of items marked to save. For efficiency's sake,
115 * it is recommended to use a collection that can handle object lookup quickly (such
116 * as a HashSet).
117 * @throws DBException upon Expresso database error.
118 */
119 private void saveChildrenOfSaved(
120 final Collection toDelete,
121 final Collection toSave,
122 Node root) throws DBException {
123
124
125
126 if (toDelete.size() == 0) {
127 return;
128 }
129
130 Node[] children = (Node[]) root.getAttribute(TreeSelectionFactory.IS_PARENT_OF);
131 if (children != null) {
132 for (int i = 0; i < children.length; i++) {
133 Node child = children[i];
134
135
136
137 if (toSave.contains(root) && !toSave.contains(child)) {
138 toSave.add(child);
139 if (toDelete.contains(child)) {
140 toDelete.remove(child);
141 }
142 }
143
144
145 saveChildrenOfSaved(toDelete, toSave, child);
146 }
147 }
148 }
149
150 /***
151 * is this node the destination of any strong relation
152 * that has a source node outside our tree?
153 *
154 * @param n The node to be examine.
155 * @return true if this node the destination of any strong relation with source node outside our tree
156 * @throws DBException
157 */
158 private boolean isDestOfExternal(final Node n) throws DBException {
159 boolean isExternal = false;
160
161
162 Relation[] destRels = n.getDestRelations();
163
164 for (int i = 0; (i < destRels.length); i++) {
165
166 Relation adest = destRels[i];
167
168 if (adest.isStrong()) {
169
170
171
172 if (allNodes.containsKey(adest.getSrcId())) {
173 continue;
174 }
175
176 isExternal = true;
177
178 break;
179 }
180 }
181
182 return isExternal;
183 }
184 }