/*

     This file is part of Combean.

     Combean is free software; you can redistribute it and/or modify

     it under the terms of the GNU General Public License as published by

     the Free Software Foundation; either version 2 of the License, or

     (at your option) any later version.

     Combean 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 General Public License for more details.

     You should have received a copy of the GNU General Public License

     along with Combean; if not, write to the Free Software

     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

 /*

  * Created on 20.08.2005

  *

  */

 package net.sourceforge.combean.graph.alg.traversal;

 import org.apache.commons.logging.Log;

 import org.apache.commons.logging.LogFactory;

 import net.sourceforge.combean.graph.containers.ListAsNodeQueue;

 import net.sourceforge.combean.interfaces.graph.Edge;

 import net.sourceforge.combean.interfaces.graph.EdgeIterator;

 import net.sourceforge.combean.interfaces.graph.Node;

 import net.sourceforge.combean.interfaces.graph.alg.traverse.BreadthFirstSearch;

 import net.sourceforge.combean.interfaces.graph.containers.NodeQueue;

 /**

  * @author schickin

  *

  */

 public class BreadthFirstSearchImpl extends AbstractGraphTraversalAlg

 implements BreadthFirstSearch {

     private static Log log = LogFactory.getLog(BreadthFirstSearchImpl.class);

     NodeQueue queue = null;

     /**

      * constructor 

      */

     public BreadthFirstSearchImpl() {

         super();

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.graph.alg.traversal.AbstractGraphTraversalAlg#runTraversalWithSingleStartNode(net.sourceforge.combean.interfaces.graph.Node)

      */

     protected void runTraversalWithSingleStartNode(Node startNode) {

         this.queue.enqueue(startNode);

         while (!this.queue.isEmpty()) {

             Node v = this.queue.dequeue();

             if (log.isDebugEnabled()) {

                 log.debug("visit: " + v);

             }

             getVisitor().visitNode(v);

                     EdgeIterator it = getNeighborIterator(v);

                     while (it.hasNext()) {

                             Edge e = it.next();

                             Node w = getNeighborhood().getOtherNode(e, v);

                             boolean notYetVisited = getVisitedNodes().add(w);

                             if (notYetVisited) {

                                     getVisitor().openNeighbor(e, v);

                                     this.queue.enqueue(w);

                                     if (log.isTraceEnabled()) {

                                         log.debug("enqueue: " + e);

                                     }

                             }

                             else {

                                     getVisitor().reopenNeighbor(e, v);

                             }

                     }

         }

     }

     /**

      * @param queue The queue to set.

      */

     public final void setQueue(NodeQueue queue) {

         this.queue = queue;

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.graph.alg.traversal.AbstractGraphTraversalAlg#init()

      */

     protected void init() {

          super.init();

          if (this.queue == null) {

              this.queue = new ListAsNodeQueue();

          }

          this.queue.clear();

     }

 }