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.Enumeration;
016
017
018 /**
019 * This class is a generic tree. It uses TreeNode and some enumeration
020 * classes.
021 */
022 public 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 public final void setRoot(TreeNode node) {
065 node.clear(); // make sure all pointers are pointing anywhere else
066 root = node;
067 }
068
069 /**
070 * Provides an undefined enumeration over all elements in the tree
071 * @return enumeration
072 */
073 public final Enumeration<TreeNode> elements() {
074 return new TreeTopDownEnumerator(root);
075 }
076
077 /**
078 * Counts and returns the number of nodes
079 * @return the number of nodes.
080 */
081 public final int numberOfNodes() {
082 int n = 0;
083 for (Enumeration<TreeNode> e = elements(); e.hasMoreElements();) {
084 e.nextElement();
085 n++;
086 }
087 return n;
088 }
089
090 /**
091 * Provides a bottom-up enumeration over all elements in the tree
092 * @return enumeration
093 */
094 public final Enumeration<TreeNode> getBottomUpEnumerator() {
095 return new TreeBottomUpEnumerator(root);
096 }
097
098 /**
099 * Provides a top-down enumeration over all elements in the tree
100 * @return enumeration
101 */
102 public final Enumeration<TreeNode> getTopDownEnumerator() {
103 return new TreeTopDownEnumerator(root);
104 }
105
106 /**
107 * Prints the tree
108 * @return the tree as a string
109 */
110 public final String toString() {
111 StringBuffer sb = new StringBuffer();
112
113 // visit the nodes in a depth first traversal, printing the nodes
114 // as they are visited, indenting by the depth of the traversal
115 sb = DFS(sb, root, 0);
116 return sb.toString();
117 }
118
119 /**
120 * A preorder depth first traversal, printing node as visited
121 * @param sb the string buffer to insert the results
122 * @param node the node to process
123 * @param depth the current depth (root = 0) in the tree
124 */
125 private StringBuffer DFS(StringBuffer sb, TreeNode node, int depth) {
126 // indent appropriate spaces and print node
127 for (int i = 0; i < 2 * depth; i++) {
128 sb.append(" ");
129 }
130 sb.append(node).append("\n");
131
132 Enumeration<TreeNode> childEnum = node.getChildren();
133 while (childEnum.hasMoreElements()) {
134 TreeNode child = childEnum.nextElement();
135 DFS(sb, child, depth + 1);
136 }
137 return sb;
138 }
139 }