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 */
013package org.jikesrvm.compilers.opt.util;
014
015import java.util.ArrayList;
016import java.util.Enumeration;
017import 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 */
025final 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 the node to start at
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}