001
002 package brs;
003
004 /**
005 * Models the binary tree structure using the state pattern and the visitor
006 * pattern. Provides only structural behaviors and a hook to execute any
007 * visitor algorithm.
008 * Exercise: Override the toString() method anonymous inner visitor classes.
009 * @author Dung X. Nguyen - Copyright 2002 - All rights reserved.
010 * @author Mathias Ricken - Copyright 2008 - All rights reserved.
011 */
012 public class BiTree<T> {
013 /**
014 * the state of this BiTree.
015 */
016 private ANode<T> _rootNode;
017
018 /** Visitor to generate string representation. */
019 private ToString<T> _toString = new ToString<T>();
020
021 /**
022 * Initializes this BiTree to the empty state.
023 */
024 public BiTree() {
025 _rootNode = new EmptyNode<T>();
026 }
027
028 /**
029 * Gets the root data of this BiTree if it exists.
030 * @return the root data element of this BiTree if it exists.
031 * @exception NoSuchElementException if this BiTree is empty.
032 */
033 public T getRootDat() {
034 return _rootNode.getRootDat (this);
035 }
036
037 /**
038 * Sets the root data element to a given object.
039 * @param dat the new root data.
040 * @exception NoSuchElementException if this BiTree is empty.
041 */
042 public void setRootDat(T dat) {
043 _rootNode.setRootDat (this, dat);
044 }
045
046 /**
047 * Gets the left subtree of this BiTree if it exists.
048 * @return the left subtree of this BiTree if it exists.
049 * @exception NoSuchElementException if this BiTree is empty.
050 */
051 public BiTree<T> getLeftSubTree() {
052 return _rootNode.getLeftSubTree (this);
053 }
054
055 /**
056 * Gets the right subtree of this BiTree if it exsists.
057 * @return the right subtree of this BiTree if it exists.
058 * @exception NoSuchElementException if this BiTree is empty.
059 */
060 public BiTree<T> getRightSubTree() {
061 return _rootNode.getRightSubTree (this);
062 }
063
064 /**
065 * Attaches a new left subtree to the left of this BiTree, allowing this
066 * BiTree to grow to the left.
067 * @param biTree to replace the current left subtree.
068 * @exception NoSuchElementException if this BiTree is empty.
069 */
070 public void setLeftSubTree(BiTree<T> biTree) {
071 _rootNode.setLeftSubTree(this, biTree);
072 }
073
074 /**
075 * Attaches a new right subtree to the left of this BiTree, allowing this
076 * BiTree to grow to the right.
077 * @param biTree to replace the current right subtree.
078 * @exception NoSuchElementException if this BiTree is empty.
079 */
080 public void setRightSubTree(BiTree<T> biTree) {
081 _rootNode.setRightSubTree(this, biTree);
082 }
083
084 /**
085 * Inserts a root element to this BiTree.
086 * Allows for state change from empty to non-empty.
087 * @param dat the new root data.
088 * @exception IllegalStateException if this BiTree has more than one element.
089 */
090 public void insertRoot(T dat) {
091 _rootNode.insertRoot(this, dat);
092 }
093
094 /**
095 * Removes and returns the root data element of this BiTree.
096 * @return the root data element of this BiTree.
097 * @exception NoSuchElementException if this BiTree is empty.
098 * @exception IllegalStateException if one of the subtrees is not empty.
099 */
100 public T remRoot() {
101 return _rootNode.remRoot(this);
102 }
103
104 /**
105 * Hook to execute any algorithm that presents itself as a visitor to this
106 * BiTree.
107 * @param algo a visitor to a BiTree.
108 * @param inp the vararg input for the algo visitor.
109 * @return the output for the execution of algo.
110 */
111 public <R,P> R execute(IVisitor<T,R,P> algo, P... inp) {
112 return _rootNode.execute(this, algo, inp);
113 }
114
115 public String toString () {
116 return (String)execute(_toString);
117 // EXERCISE FOR STUDENTS: The above line of code does not conform to the
118 // state pattern because it does not forward the request to the state.
119 // Rewrite the code to conform to the state pattern. You will need to add
120 // appropriate methods to the states. Review what we did with toString()
121 // for linear recursive structures.
122 }
123
124 /**
125 * Changes this BiTree to a given new node (i.e. state).
126 * @param node a new root node (i.e.state) for this BiTree.
127 */
128 final void setRootNode(ANode<T> node) {
129 _rootNode = node;
130 }
131
132 /**
133 * Returns the current node (i.e. state) of this BiTree.
134 * @return the current root node (state) of this BiTree.
135 */
136 final ANode<T> getRootNode() {
137 return _rootNode;
138 }
139 }