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