View Javadoc

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 -&gt; Node B -&gt; 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 &quot;To Delete&quot; collection to &quot;Save&quot; 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          // todo efficiency: get all relations for all nodes at once using  in [id1, id2] instead of 2 queries per node
81  
82          //Build a set of items that have no immediate external relations.
83          //Other items are put in a list to save.
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          // even if root node has relations, we will delete it
94          toSave.remove(rootToDelete);
95  
96          // we do not display existing node in list to delete
97          toDelete.remove(rootToDelete);
98  
99          saveChildrenOfSaved(toDelete, toSave, rootToDelete);
100 
101         // even if root node has relations, we will delete it
102         toSave.remove(rootToDelete);
103 
104         // we do not display existing node in list to delete
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         //Simple optimization -- if we don't have anything to delete
125         //we've eliminated it all.
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                 // save children of saved parent
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                 // recurse for ALL children, since we could find saved children at any level
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                 // we ignore any incoming from hash of all nodes in tree
171                 //
172                 if (allNodes.containsKey(adest.getSrcId())) {
173                     continue; // it is in tree--we do not include it for 'external' consideration
174                 }
175 
176                 isExternal = true;
177 
178                 break; // other relations don't matter since we have already disqualified this for deletion
179             }
180         }
181 
182         return isExternal;
183     }
184 }