001    /*
002     *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003     *
004     *  This file is licensed to You under the Eclipse Public License (EPL);
005     *  You may not use this file except in compliance with the License. You
006     *  may obtain a copy of the License at
007     *
008     *      http://www.opensource.org/licenses/eclipse-1.0.php
009     *
010     *  See the COPYRIGHT.txt file distributed with this work for information
011     *  regarding copyright ownership.
012     */
013    package org.jikesrvm.compilers.opt.util;
014    
015    import java.util.ArrayList;
016    import java.util.Enumeration;
017    import java.util.ListIterator;
018    
019    
020    /**
021     *  This class provides enumeration of elements of a tree in a town-down manner
022     *  It guarantees that all children of a node will only be visited after
023     *  the parent.
024     *  This is not necessarily the same as a top-down level walk.
025     */
026    final class TreeTopDownEnumerator implements Enumeration<TreeNode> {
027    
028      /**
029       * List of nodes in preorder
030       */
031      private final ArrayList<TreeNode> list;
032    
033      /**
034       * an iterator of the above list
035       */
036      private final ListIterator<TreeNode> iterator;
037    
038      /**
039       * constructor: it creates the list of nodes
040       * @param   root Root of the tree to traverse
041       */
042      TreeTopDownEnumerator(TreeNode root) {
043        list = new ArrayList<TreeNode>();
044    
045        if (root != null) {
046          // Perform a DFS, saving nodes in preorder
047          DFS(root);
048        }
049    
050        iterator = list.listIterator();
051      }
052    
053      /**
054       * any elements left?
055       * @return whether there are any elements left
056       */
057      @Override
058      public boolean hasMoreElements() {
059        return iterator.hasNext();
060      }
061    
062      /**
063       * returns the next element in the list iterator
064       * @return the next element in the list iterator or null
065       */
066      @Override
067      public TreeNode nextElement() {
068        return iterator.next();
069      }
070    
071      /**
072       * A preorder depth first traversal, adding nodes to the list
073       * @param node
074       */
075      private void DFS(TreeNode node) {
076        list.add(node);
077        Enumeration<TreeNode> childEnum = node.getChildren();
078        while (childEnum.hasMoreElements()) {
079          TreeNode child = childEnum.nextElement();
080          DFS(child);
081        }
082      }
083    }
084    
085    
086