001 002 package brs; 003 004 /** 005 * Stores data and represents a non-empty state. 006 * @author Dung X. Nguyen - Copyright 2001 - All rights reserved. 007 * @author Mathias Ricken - Copyright 2008 - All rights reserved. 008 */ 009 class DatNode<T> extends ANode<T> { 010 /** 011 * Data Invariant: != null. 012 * @SBGen Variable (,left,,64) 013 */ 014 private BiTree<T> _leftTree = new BiTree<T> (); 015 /** 016 * the stored data element. 017 */ 018 private T _dat; 019 /** 020 * Data Invariant: != null. 021 * @SBGen Variable (,right,,64) 022 */ 023 private BiTree<T> _rightTree = new BiTree<T> (); 024 025 /** 026 * Initialize the data element to a given object. 027 * @param dat a given data object. 028 */ 029 DatNode(T dat) { 030 _dat = dat; 031 } 032 033 034 /** 035 * Gets the root data of the owner Tree. 036 * @param owner the BiTree holding this DatNode. 037 * @return the data element of this DatNode. 038 */ 039 T getRootDat(BiTree<T> owner) { 040 return _dat; 041 } 042 043 /** 044 * Sets the data element of this node to a given data object. 045 * @param dat a given data object. 046 * @param owner the BiTree holding this DatNode. 047 */ 048 void setRootDat(BiTree<T> owner, T dat) { 049 _dat = dat; 050 } 051 052 /** 053 * Gets the left subtree of the owner tree. 054 * @param owner the BiTree holding this DatNode. 055 * @return the left subtree of this DatNode. 056 */ 057 BiTree<T> getLeftSubTree(BiTree<T> owner) { 058 return _leftTree; 059 } 060 061 /** 062 * Gets the right subtree of the owner tree. 063 * @param owner the BiTree holding this DatNode. 064 * @return the right subtree of this DatNode. 065 */ 066 BiTree<T> getRightSubTree(BiTree<T> owner) { 067 return _rightTree; 068 } 069 070 /** 071 * Sets the left subtree of this Datnode to a given tree. 072 * Allows for growing the owner tree. 073 * @param biTree != null. Does not check for null! 074 * @param owner the BiTree holding this DatNode. 075 */ 076 void setLeftSubTree(BiTree<T> owner, BiTree<T> biTree) { 077 _leftTree = biTree; 078 } 079 080 /** 081 * Sets the right subtree of this node to a given tree. 082 * Allows for growing the owner tree. 083 * @param biTree != null. Does not check for null! 084 * @param owner the BiTree holding this DatNode. 085 */ 086 void setRightSubTree(BiTree<T> owner, BiTree<T> biTree) { 087 _rightTree = biTree; 088 } 089 090 /** 091 * Throws an IllegalStateException because the owner tree is not empty. 092 * @exception IllegaStateException. 093 */ 094 void insertRoot(BiTree<T> owner, T dat) { 095 throw new IllegalStateException ("DatNode.insertRoot()."); 096 } 097 098 /** 099 * Removes and returns the root element from the owner tree by asking the 100 * left subtree and, if necessary, the right subtree to help do the job. 101 * The subtrees help determine whether or not the root element can be removed 102 * by executing appropriate anonymous visitors. 103 * @param owner the BiTree holding this DatNode. Why is it final? 104 * @exception IllegaStateException if both subtrees of owner are non-empty. 105 */ 106 T remRoot(final BiTree<T> owner) { 107 return _leftTree.execute(new IVisitor<T,T,Void>() { 108 /** 109 * The left subtree is empty. The parent tree can simply become the 110 * right subtree. 111 */ 112 public T emptyCase(BiTree<T> host, Void... notUsed) { 113 owner.setRootNode(_rightTree.getRootNode()); 114 return _dat; 115 116 } 117 118 /** 119 * The left subtree is not empty! The right subtree must determine 120 * whether or not the parent root can be removed. 121 */ 122 public T nonEmptyCase(BiTree<T> host, Void... inp) { 123 return _rightTree.execute(new IVisitor<T,T,Void>() { 124 /** 125 * At this point both the left and right subtrees are empty. 126 */ 127 public T emptyCase(BiTree<T> h, Void... notUsed) { 128 owner.setRootNode(_leftTree.getRootNode()); 129 return _dat; 130 } 131 132 /** 133 * Both left and right subtrees are not empty! 134 * Cannot remove root! 135 */ 136 public T nonEmptyCase(BiTree<T> h, Void... notUsed) { 137 throw new IllegalStateException ("Not a leaf."); 138 } 139 }); 140 } 141 }); 142 } 143 144 /** 145 * Calls algo's nonEmptyCase() method to execute the algorithm algo. 146 * @param owner the BiTree holding this DatNode. 147 * @param algo an algorithm on owner. 148 * @param inp the vararg input algo needs. 149 * @return the output for the nonEmptyCase() of algo. 150 */ 151 <R,P> R execute(BiTree<T> owner, IVisitor<T,R,P> algo, P... inp) { 152 return algo.nonEmptyCase (owner, inp); 153 } 154 } 155