DepthFirstSearch.java

/*
 *
 * The DbUnit Database Testing Framework
 * Copyright (C)2005-2008, DbUnit.org
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

package org.dbunit.util.search;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.SortedSet;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.dbunit.util.CollectionsHelper;

/**
 * Search using depth-first algorithm.<br>
 * <br>
 * An instance of this class must be used only once, as it maintains the
 * internal state of the search.<br>
 * <br>
 * 
 * @author gommma (gommma AT users.sourceforge.net)
 * @author Last changed by: $Author$
 * @version $Revision$ $Date$
 * @since 2.4.0
 */
public class DepthFirstSearch implements ISearchAlgorithm {

  // nodes that were already scanned during the search
  private Set scannedNodes;
  private Set reverseScannedNodes;

  protected final Logger logger = LoggerFactory.getLogger(getClass());
  
  // result of the search
  private LinkedHashSet result;
  
  // input of the search
  private Set nodesFrom;

  // callback used to help the search
  private ISearchCallback callback;

  // flag, as one instance cannot be used more than once
  private boolean searching = false;
  
    /**
     * The search depth to be used when recursing through the child nodes
     */
    private int searchDepth = Integer.MAX_VALUE;

  
    /**
     * Creates a new depth-first algorithm using the maximum search depth for recursing over the nodes.
     */
    public DepthFirstSearch()
    {
        super();
    }

    /**
     * Creates a new depth-first algorithm
     * @param searchDepth The search depth to be used when traversing the nodes recursively. Must be > 0.
     * @since 2.4
     */
    public DepthFirstSearch(int searchDepth)
    {
        super();
        if(searchDepth<=0){
            throw new IllegalArgumentException("The searchDepth must be > 0. Given: " + searchDepth);
        }
        this.searchDepth = searchDepth;
    }

  /**
   * Alternative option to search() that takes an array of nodes as input (instead of a Set)
   * @see ISearchAlgorithm
   */
  public Set search(Object[] nodesFrom, ISearchCallback callback)
      throws SearchException 
  {
      if(logger.isDebugEnabled())
          logger.debug("search(nodesFrom={}, callback={}) - start", nodesFrom, callback);

    return search(CollectionsHelper.objectsToSet(nodesFrom), callback);
  }
  
  /**
   * @see ISearchAlgorithm
   */
  public Set search(Set nodesFrom, ISearchCallback callback)
      throws SearchException {
      if(logger.isDebugEnabled())
          logger.debug("search(nodesFrom={}, callback={}) - start", nodesFrom, callback);

    synchronized (this) {
      if (searching) {
        throw new IllegalStateException("already searching/searched");
      }
      this.searching = true;
    }

    // set of tables that will be returned (i.e, the declared tables and its
    // dependencies)
    this.result = new LinkedHashSet();

    // callback used to help the search
    this.callback = callback;
        
    this.nodesFrom = new LinkedHashSet();
    
    int sizeNodesFromBefore = 0;
    int sizeResultBefore = 0;
    boolean keepSearching = true;
    this.scannedNodes = new HashSet();
    this.reverseScannedNodes = new HashSet();
    this.scannedNodes = new HashSet();
    do {
      
      // In a traditional depth-first search, the getEdges() method should return only
      // edges where this node is the 'from' vertex, as the graph is known in advance.
      // But in our case, the graph is built 'on the fly', so it's possible that the
      // getEdges() also returns edges where the node is the 'to' vertex. 
      // So, before we do the "real" search, we need to do a reverse search to find out
      // all the nodes that should be part of the input.
      Iterator iterator = nodesFrom.iterator();      
      while (iterator.hasNext()) {
        Object node = iterator.next();
        reverseSearch(node, 0);
      }
//        this.nodesFrom = nodesFrom;

        // now that the input is adjusted, do the search
      iterator = this.nodesFrom.iterator();
      
      while (iterator.hasNext()) {
        Object node = iterator.next();
        search(node, 0);
      }
      
      nodesFrom = new HashSet(this.result);
      
      // decides if we continue searching
      boolean sizesDontMatch = this.result.size() != this.nodesFrom.size();
      boolean resultChanged = this.result.size() != sizeResultBefore;
      boolean nodesFromChanged = this.nodesFrom.size() != sizeNodesFromBefore;
      sizeNodesFromBefore = this.nodesFrom.size();
      sizeResultBefore = this.result.size();
      keepSearching = sizesDontMatch && ( resultChanged || nodesFromChanged );
      
    } while ( keepSearching );
    
    return this.result;

  }

  /**
   * This is the real depth first search algorithm, which is called recursively.
   * 
   * @param node node where the search starts
   * @param currentSearchDepth the search depth in the recursion
   * @return true if the node has been already searched before
   * @throws Exception if an exception occurs while getting the edges
   */
  private boolean search(Object node, int currentSearchDepth) throws SearchException {
    if ( this.logger.isDebugEnabled() ) {
      this.logger.debug( "search:" + node );
    }
    if (this.scannedNodes.contains(node)) {
      if ( this.logger.isDebugEnabled() ) {
        this.logger.debug( "already searched; returning true" );
      }
      return true;
    }
    if (!this.callback.searchNode(node)) {
      if ( this.logger.isDebugEnabled() ) {
        this.logger.debug( "Callback handler blocked search for node " + node );
      }
      return true;
    }
    
    if ( this.logger.isDebugEnabled() ) {
      this.logger.debug("Pushing " + node);      
    }
    this.scannedNodes.add(node);

    if(currentSearchDepth < this.searchDepth) {
        // first, search the nodes the node depends on
        SortedSet edges = this.callback.getEdges(node);
        if (edges != null) {
            Iterator iterator = edges.iterator();
            while (iterator.hasNext()) {
              // and recursively search these nodes
              IEdge edge = (IEdge) iterator.next();
              Object toNode = edge.getTo();
              search(toNode, currentSearchDepth++);
            }
          }
    }

    // finally, add the node to the result
    if ( this.logger.isDebugEnabled() ) {
      this.logger.debug( "Adding node " + node + " to the final result" );
    }
    // notify the callback a node was added
    this.callback.nodeAdded(node);
    result.add(node);
    
    return false;
  }

  /**
   * Do a reverse search (i.e, searching the other way of the edges) in order
   * to adjust the input before the real search.
   * @param node node where the search starts
   * @param currentSearchDepth the search depth in the recursion
   * @return true if the node has been already reverse-searched before
   * @throws Exception if an exception occurs while getting the edges
   */
  private boolean reverseSearch(Object node, int currentSearchDepth) throws SearchException {
    if ( this.logger.isDebugEnabled() ) {
      this.logger.debug( "reverseSearch:" + node );
    }
    if (this.reverseScannedNodes.contains(node)) {
      if ( this.logger.isDebugEnabled() ) {
        this.logger.debug( "already searched; returning true" );
      }
      return true;
    }
    
    if (!this.callback.searchNode(node)) {
      if ( this.logger.isDebugEnabled() ) {
        this.logger.debug( "callback handler blocked reverse search for node " + node );
      }
      return true;
    }
    
    if ( this.logger.isDebugEnabled() ) {
      this.logger.debug("Pushing (reverse) " + node);      
    }
    this.reverseScannedNodes.add(node);

    if(currentSearchDepth < this.searchDepth) {
        // first, search the nodes the node depends on
        SortedSet edges = this.callback.getEdges(node);    
        if (edges != null) {
          Iterator iterator = edges.iterator();
          while (iterator.hasNext()) {
            // and recursively search these nodes if we find a match
            IEdge edge = (IEdge) iterator.next();
            Object toNode = edge.getTo();
            if ( toNode.equals(node) ) {
              Object fromNode = edge.getFrom();
              reverseSearch(fromNode, currentSearchDepth++);
            }
          }
        }
    }
    
    // finally, add the node to the input
    this.nodesFrom.add(node);

    return false;

  }
  
  
}