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        // Perform a DFS, saving nodes in preorder
046        DFS(root);
047    
048        // setup the iterator
049        iterator = list.listIterator();
050      }
051    
052      /**
053       * any elements left?
054       * @return whether there are any elements left
055       */
056      public boolean hasMoreElements() {
057        return iterator.hasNext();
058      }
059    
060      /**
061       * returns the next element in the list iterator
062       * @return the next element in the list iterator or null
063       */
064      public TreeNode nextElement() {
065        return iterator.next();
066      }
067    
068      /**
069       * A preorder depth first traversal, adding nodes to the list
070       * @param node
071       */
072      private void DFS(TreeNode node) {
073        list.add(node);
074        Enumeration<TreeNode> childEnum = node.getChildren();
075        while (childEnum.hasMoreElements()) {
076          TreeNode child = childEnum.nextElement();
077          DFS(child);
078        }
079      }
080    }
081    
082    
083