depthfirstsearch.java

采用 Java 编写的数据库系统单元测试程序。

/*
 *
 * The DbUnit Database Testing Framework
 * Copyright (C)2005, 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.Set;
import java.util.SortedSet;

import org.apache.commons.collections.set.ListOrderedSet;
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 Felipe Leme <[e-mail]>
 * @version $Revision: 554 $
 * @since Aug 25, 2005
 * 
 */
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 Set 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;

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

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

    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
    // depedencies)
    this.result = new ListOrderedSet();

    // callback used to help the search
    this.callback = callback;
        
    this.nodesFrom = new ListOrderedSet();
    
    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);
      }
          
      // now that the input is adjusted, do the search
      iterator = this.nodesFrom.iterator();
      
      while (iterator.hasNext()) {
        Object node = iterator.next();
        search(node);
      }
      
      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
   * @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) 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);

    // 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);
      }
    }

    // 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
   * @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) 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);

    // 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);
        }
      }
    }

    // finally, add the node to the input
    this.nodesFrom.add(node);

    return false;

  }
  
  
}