View Javadoc

1   /*
2    *
3    * The DbUnit Database Testing Framework
4    * Copyright (C)2005-2008, DbUnit.org
5    *
6    * This library is free software; you can redistribute it and/or
7    * modify it under the terms of the GNU Lesser General Public
8    * License as published by the Free Software Foundation; either
9    * version 2.1 of the License, or (at your option) any later version.
10   *
11   * This library is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   * Lesser General Public License for more details.
15   *
16   * You should have received a copy of the GNU Lesser General Public
17   * License along with this library; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19   *
20   */
21  
22  package org.dbunit.util.search;
23  
24  import java.util.HashSet;
25  import java.util.Iterator;
26  import java.util.Set;
27  import java.util.SortedSet;
28  
29  import org.apache.commons.collections.set.ListOrderedSet;
30  import org.slf4j.Logger;
31  import org.slf4j.LoggerFactory;
32  import org.dbunit.util.CollectionsHelper;
33  
34  /**
35   * Search using depth-first algorithm.<br>
36   * <br>
37   * An instance of this class must be used only once, as it maintains the
38   * internal state of the search.<br>
39   * <br>
40   * 
41   * @author gommma (gommma AT users.sourceforge.net)
42   * @author Last changed by: $Author: gommma $
43   * @version $Revision: 843 $ $Date: 2008-10-26 12:06:28 +0100 (dom, 26 ott 2008) $
44   * @since 2.4.0
45   */
46  public class DepthFirstSearch implements ISearchAlgorithm {
47  
48    // nodes that were already scanned during the search
49    private Set scannedNodes;
50    private Set reverseScannedNodes;
51  
52    protected final Logger logger = LoggerFactory.getLogger(getClass());
53    
54    // result of the search
55    private ListOrderedSet result;
56    
57    // input of the search
58    private Set nodesFrom;
59  
60    // callback used to help the search
61    private ISearchCallback callback;
62  
63    // flag, as one instance cannot be used more than once
64    private boolean searching = false;
65    
66      /**
67       * The search depth to be used when recursing through the child nodes
68       */
69      private int searchDepth = Integer.MAX_VALUE;
70  
71    
72      /**
73       * Creates a new depth-first algorithm using the maximum search depth for recursing over the nodes.
74       */
75      public DepthFirstSearch()
76      {
77          super();
78      }
79  
80      /**
81       * Creates a new depth-first algorithm
82       * @param searchDepth The search depth to be used when traversing the nodes recursively. Must be > 0.
83       * @since 2.4
84       */
85      public DepthFirstSearch(int searchDepth)
86      {
87          super();
88          if(searchDepth<=0){
89              throw new IllegalArgumentException("The searchDepth must be > 0. Given: " + searchDepth);
90          }
91          this.searchDepth = searchDepth;
92      }
93  
94    /**
95     * Alternative option to search() that takes an array of nodes as input (instead of a Set)
96     * @see ISearchAlgorithm
97     */
98    public ListOrderedSet search(Object[] nodesFrom, ISearchCallback callback)
99        throws SearchException 
100   {
101       if(logger.isDebugEnabled())
102           logger.debug("search(nodesFrom={}, callback={}) - start", nodesFrom, callback);
103 
104     return search(CollectionsHelper.objectsToSet(nodesFrom), callback);
105   }
106   
107   /**
108    * @see ISearchAlgorithm
109    */
110   public ListOrderedSet search(Set nodesFrom, ISearchCallback callback)
111       throws SearchException {
112       if(logger.isDebugEnabled())
113           logger.debug("search(nodesFrom={}, callback={}) - start", nodesFrom, callback);
114 
115     synchronized (this) {
116       if (searching) {
117         throw new IllegalStateException("already searching/searched");
118       }
119       this.searching = true;
120     }
121 
122     // set of tables that will be returned (i.e, the declared tables and its
123     // dependencies)
124     this.result = new ListOrderedSet();
125 
126     // callback used to help the search
127     this.callback = callback;
128         
129     this.nodesFrom = new ListOrderedSet();
130     
131     int sizeNodesFromBefore = 0;
132     int sizeResultBefore = 0;
133     boolean keepSearching = true;
134     this.scannedNodes = new HashSet();
135     this.reverseScannedNodes = new HashSet();
136     this.scannedNodes = new HashSet();
137     do {
138       
139       // In a traditional depth-first search, the getEdges() method should return only
140       // edges where this node is the 'from' vertex, as the graph is known in advance.
141       // But in our case, the graph is built 'on the fly', so it's possible that the
142       // getEdges() also returns edges where the node is the 'to' vertex. 
143       // So, before we do the "real" search, we need to do a reverse search to find out
144       // all the nodes that should be part of the input.
145       Iterator iterator = nodesFrom.iterator();      
146       while (iterator.hasNext()) {
147         Object node = iterator.next();
148         reverseSearch(node, 0);
149       }
150 //        this.nodesFrom = nodesFrom;
151 
152         // now that the input is adjusted, do the search
153       iterator = this.nodesFrom.iterator();
154       
155       while (iterator.hasNext()) {
156         Object node = iterator.next();
157         search(node, 0);
158       }
159       
160       nodesFrom = new HashSet(this.result);
161       
162       // decides if we continue searching
163       boolean sizesDontMatch = this.result.size() != this.nodesFrom.size();
164       boolean resultChanged = this.result.size() != sizeResultBefore;
165       boolean nodesFromChanged = this.nodesFrom.size() != sizeNodesFromBefore;
166       sizeNodesFromBefore = this.nodesFrom.size();
167       sizeResultBefore = this.result.size();
168       keepSearching = sizesDontMatch && ( resultChanged || nodesFromChanged );
169       
170     } while ( keepSearching );
171     
172     return this.result;
173 
174   }
175 
176   /**
177    * This is the real depth first search algorithm, which is called recursively.
178    * 
179    * @param node node where the search starts
180    * @param currentSearchDepth the search depth in the recursion
181    * @return true if the node has been already searched before
182    * @throws Exception if an exception occurs while getting the edges
183    */
184   private boolean search(Object node, int currentSearchDepth) throws SearchException {
185     if ( this.logger.isDebugEnabled() ) {
186       this.logger.debug( "search:" + node );
187     }
188     if (this.scannedNodes.contains(node)) {
189       if ( this.logger.isDebugEnabled() ) {
190         this.logger.debug( "already searched; returning true" );
191       }
192       return true;
193     }
194     if (!this.callback.searchNode(node)) {
195       if ( this.logger.isDebugEnabled() ) {
196         this.logger.debug( "Callback handler blocked search for node " + node );
197       }
198       return true;
199     }
200     
201     if ( this.logger.isDebugEnabled() ) {
202       this.logger.debug("Pushing " + node);      
203     }
204     this.scannedNodes.add(node);
205 
206     if(currentSearchDepth < this.searchDepth) {
207         // first, search the nodes the node depends on
208         SortedSet edges = this.callback.getEdges(node);
209         if (edges != null) {
210             Iterator iterator = edges.iterator();
211             while (iterator.hasNext()) {
212               // and recursively search these nodes
213               IEdge edge = (IEdge) iterator.next();
214               Object toNode = edge.getTo();
215               search(toNode, currentSearchDepth++);
216             }
217           }
218     }
219 
220     // finally, add the node to the result
221     if ( this.logger.isDebugEnabled() ) {
222       this.logger.debug( "Adding node " + node + " to the final result" );
223     }
224     // notify the callback a node was added
225     this.callback.nodeAdded(node);
226     result.add(node);
227     
228     return false;
229   }
230 
231   /**
232    * Do a reverse search (i.e, searching the other way of the edges) in order
233    * to adjust the input before the real search.
234    * @param node node where the search starts
235    * @param currentSearchDepth the search depth in the recursion
236    * @return true if the node has been already reverse-searched before
237    * @throws Exception if an exception occurs while getting the edges
238    */
239   private boolean reverseSearch(Object node, int currentSearchDepth) throws SearchException {
240     if ( this.logger.isDebugEnabled() ) {
241       this.logger.debug( "reverseSearch:" + node );
242     }
243     if (this.reverseScannedNodes.contains(node)) {
244       if ( this.logger.isDebugEnabled() ) {
245         this.logger.debug( "already searched; returning true" );
246       }
247       return true;
248     }
249     
250     if (!this.callback.searchNode(node)) {
251       if ( this.logger.isDebugEnabled() ) {
252         this.logger.debug( "callback handler blocked reverse search for node " + node );
253       }
254       return true;
255     }
256     
257     if ( this.logger.isDebugEnabled() ) {
258       this.logger.debug("Pushing (reverse) " + node);      
259     }
260     this.reverseScannedNodes.add(node);
261 
262     if(currentSearchDepth < this.searchDepth) {
263         // first, search the nodes the node depends on
264         SortedSet edges = this.callback.getEdges(node);    
265         if (edges != null) {
266           Iterator iterator = edges.iterator();
267           while (iterator.hasNext()) {
268             // and recursively search these nodes if we find a match
269             IEdge edge = (IEdge) iterator.next();
270             Object toNode = edge.getTo();
271             if ( toNode.equals(node) ) {
272               Object fromNode = edge.getFrom();
273               reverseSearch(fromNode, currentSearchDepth++);
274             }
275           }
276         }
277     }
278     
279     // finally, add the node to the input
280     this.nodesFrom.add(node);
281 
282     return false;
283 
284   }
285   
286   
287 }