001    /*
002     * This file is part of the Echo Point Project.  This project is a
003     * collection of Components that have extended the Echo Web Application
004     * Framework Version 3.
005     *
006     * Version: MPL 1.1
007     *
008     * The contents of this file are subject to the Mozilla Public License Version
009     * 1.1 (the "License"); you may not use this file except in compliance with
010     * the License. You may obtain a copy of the License at
011     * http://www.mozilla.org/MPL/
012     *
013     * Software distributed under the License is distributed on an "AS IS" basis,
014     * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
015     * for the specific language governing rights and limitations under the
016     * License.
017     */
018    
019    package echopoint.tree;
020    
021    import java.util.Enumeration;
022    import java.util.Vector;
023    import java.util.Queue;
024    import java.util.LinkedList;
025    
026    /**
027     * An enumeration that traverses the subtree rooted at
028     * a node in breadth-first order. The first node returned by the
029     * enumeration's {@code nextElement()} method is the node for which the
030     * enumeration was created.
031     *
032     * @author Brad Baker, Rakesh Vidyadharan 2009-05-29
033     * @version $Id: BreadthFirstEnumeration.java 213 2009-06-03 16:34:13Z sptrakesh $
034     */
035    public final class BreadthFirstEnumeration implements Enumeration<TreeNode>
036    {
037      protected Queue<Enumeration<TreeNode>> queue = new LinkedList<Enumeration<TreeNode>>();
038    
039      /**
040       * Create a new enumeration for the specified tree node.
041       *
042       * @param rootNode The node for which the enumeration is created.
043       */
044      public BreadthFirstEnumeration( final TreeNode rootNode )
045      {
046        final Vector<TreeNode> v = new Vector<TreeNode>( 1 );
047        v.addElement( rootNode );
048        queue.offer( v.elements() );
049      }
050    
051      /** {@inheritDoc} */
052      public boolean hasMoreElements()
053      {
054        return ( ! queue.isEmpty() ) && queue.peek().hasMoreElements();
055      }
056    
057      /** {@inheritDoc} */
058      public TreeNode nextElement()
059      {
060        final Enumeration<TreeNode> enumer = queue.poll();
061        final TreeNode node = enumer.nextElement();
062        final Enumeration<TreeNode> children = node.children();
063    
064        if ( ! enumer.hasMoreElements() )
065        {
066          queue.poll();
067        }
068    
069        if ( children.hasMoreElements() )
070        {
071          queue.offer( children );
072        }
073    
074        return node;
075      }
076    }