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 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 */
026final 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 the node to start at
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