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.Enumeration;
016
017
018/**
019 *  This class is a generic tree.  It uses TreeNode and some enumeration
020 *  classes.
021 */
022public class Tree {
023
024  /**
025   *  A tree is simply a pointer to the root
026   */
027  private TreeNode root;
028
029  /**
030   * constructor where the root is not initially known
031   */
032  public Tree() {
033    root = null;
034  }
035
036  /**
037   * constructor where the root is initially known
038   * @param node  Root of the tree.
039   */
040  public Tree(TreeNode node) {
041    root = node;
042  }
043
044  /**
045   * Is the tree empty?
046   * @return whether the tree is empty
047   */
048  public final boolean isEmpty() {
049    return root == null;
050  }
051
052  /**
053   * Gets the root of the tree
054   * @return the root of the tree
055   */
056  public final TreeNode getRoot() {
057    return root;
058  }
059
060  /**
061   * Sets the root of the tree to be the passed node.
062   * WARNING: the tree should be empty when this occurs
063   *
064   * @param node the new root
065   */
066  public final void setRoot(TreeNode node) {
067    node.clear();  // make sure all pointers are pointing anywhere else
068    root = node;
069  }
070
071  /**
072   * @return enumeration an enumeration over all elements in the tree
073   *  in no guaranteed order
074   */
075  public final Enumeration<TreeNode> elements() {
076    return new TreeTopDownEnumerator(root);
077  }
078
079  /**
080   * Counts and returns the number of nodes
081   * @return the number of nodes.
082   */
083  public final int numberOfNodes() {
084    int n = 0;
085    if (root == null) return n;
086    for (Enumeration<TreeNode> e = elements(); e.hasMoreElements();) {
087      e.nextElement();
088      n++;
089    }
090    return n;
091  }
092
093  /**
094   * Provides a bottom-up enumeration over all elements in the tree
095   * @return enumeration
096   */
097  public final Enumeration<TreeNode> getBottomUpEnumerator() {
098    return new TreeBottomUpEnumerator(root);
099  }
100
101  /**
102   * Provides a top-down enumeration over all elements in the tree
103   * @return enumeration
104   */
105  public final Enumeration<TreeNode> getTopDownEnumerator() {
106    return new TreeTopDownEnumerator(root);
107  }
108
109  /**
110   * Prints the tree
111   * @return the tree as a string
112   */
113  @Override
114  public final String toString() {
115    StringBuilder sb = new StringBuilder();
116
117    // visit the nodes in a depth first traversal, printing the nodes
118    //  as they are visited, indenting by the depth of the traversal
119    sb = DFS(sb, root, 0);
120    return sb.toString();
121  }
122
123  /**
124   * A preorder depth first traversal, printing node as visited
125   * @param sb  the string buffer to insert the results
126   * @param node the node to process
127   * @param depth the current depth (root = 0) in the tree
128   * @return the buffer that was passed in
129   */
130  private StringBuilder DFS(StringBuilder sb, TreeNode node, int depth) {
131    // indent appropriate spaces and print node
132    for (int i = 0; i < 2 * depth; i++) {
133      sb.append(' ');
134    }
135    sb.append(node).append('\n');
136
137    Enumeration<TreeNode> childEnum = node.getChildren();
138    while (childEnum.hasMoreElements()) {
139      TreeNode child = childEnum.nextElement();
140      DFS(sb, child, depth + 1);
141    }
142    return sb;
143  }
144}