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 if (root == null) return n;
084 for (Enumeration<TreeNode> e = elements(); e.hasMoreElements();) {
085 e.nextElement();
086 n++;
087 }
088 return n;
089 }
090
091 /**
092 * Provides a bottom-up enumeration over all elements in the tree
093 * @return enumeration
094 */
095 public final Enumeration<TreeNode> getBottomUpEnumerator() {
096 return new TreeBottomUpEnumerator(root);
097 }
098
099 /**
100 * Provides a top-down enumeration over all elements in the tree
101 * @return enumeration
102 */
103 public final Enumeration<TreeNode> getTopDownEnumerator() {
104 return new TreeTopDownEnumerator(root);
105 }
106
107 /**
108 * Prints the tree
109 * @return the tree as a string
110 */
111 @Override
112 public final String toString() {
113 StringBuffer sb = new StringBuffer();
114
115 // visit the nodes in a depth first traversal, printing the nodes
116 // as they are visited, indenting by the depth of the traversal
117 sb = DFS(sb, root, 0);
118 return sb.toString();
119 }
120
121 /**
122 * A preorder depth first traversal, printing node as visited
123 * @param sb the string buffer to insert the results
124 * @param node the node to process
125 * @param depth the current depth (root = 0) in the tree
126 */
127 private StringBuffer DFS(StringBuffer sb, TreeNode node, int depth) {
128 // indent appropriate spaces and print node
129 for (int i = 0; i < 2 * depth; i++) {
130 sb.append(" ");
131 }
132 sb.append(node).append("\n");
133
134 Enumeration<TreeNode> childEnum = node.getChildren();
135 while (childEnum.hasMoreElements()) {
136 TreeNode child = childEnum.nextElement();
137 DFS(sb, child, depth + 1);
138 }
139 return sb;
140 }
141 }