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 a tree in bottom-up order
022     * It guarantees that all children of a node will be visited before the parent.
023     * This is not necessarily the same as a bottom-up level walk.
024     */
025    final class TreeBottomUpEnumerator implements Enumeration<TreeNode> {
026    
027      /**
028       * List of nodes in postorder
029       */
030      private final ArrayList<TreeNode> list;
031    
032      /**
033       * an iterator of the above list
034       */
035      private final ListIterator<TreeNode> iterator;
036    
037      /**
038       * constructor: it creates the list of nodes
039       * @param root  Root of the tree whose elements are to be visited.
040       */
041      TreeBottomUpEnumerator(TreeNode root) {
042        list = new ArrayList<TreeNode>();
043    
044        if (root!=null) {
045          // Perform a DFS, saving nodes in postorder
046          DFS(root);
047        }
048    
049        iterator = list.listIterator();
050      }
051    
052      /**
053       * any elements left?
054       * @return whether there are any elements left
055       */
056      @Override
057      public boolean hasMoreElements() {
058        return iterator.hasNext();
059      }
060    
061      /**
062       * returns the next element in the list iterator
063       * @return the next element in the list iterator or {@code null}
064       */
065      @Override
066      public TreeNode nextElement() {
067        return iterator.next();
068      }
069    
070      /**
071       * A postorder depth first traversal, adding nodes to the list
072       * @param node
073       */
074      private void DFS(TreeNode node) {
075        Enumeration<TreeNode> childEnum = node.getChildren();
076        while (childEnum.hasMoreElements()) {
077          TreeNode child = childEnum.nextElement();
078          DFS(child);
079        }
080        list.add(node);
081      }
082    }