001 /* Copyright 2000, 2001, Compaq Computer Corporation */ 002 003 package javafe.filespace; 004 005 006 import java.util.Enumeration; 007 008 009 /** 010 * A Tree is a n-ary tree with data at each node; the direct children of a 011 * node are unordered but distinguished via String labels on the edges 012 * to them.<p> 013 * 014 * All labels must be non-null.<p> 015 */ 016 017 public abstract class Tree { 018 019 /*************************************************** 020 * * 021 * Instance variables: * 022 * * 023 **************************************************/ 024 025 /** Our parent or null if we have no parent (aka, we are a root) */ 026 //@ spec_public 027 private Tree parent = null; 028 029 /** 030 * The label on the edge leading to us from our parent, or null if 031 * we have no parent. 032 */ 033 //@ invariant (label == null) == (parent == null); 034 //@ spec_public 035 private String label = null; 036 037 /* 038 * Note: the existence of these two fields implies that any given 039 * Tree has at most 1 parent and can be reached via at most 1 edge. 040 */ 041 042 /** The data, if any, associated with this node: */ 043 public Object data; 044 045 046 /*************************************************** 047 * * 048 * Creation: * 049 * * 050 **************************************************/ 051 052 /** Create a root node: */ 053 protected Tree(Object data) { 054 this.data = data; 055 } 056 057 /** Create a non-root node: */ 058 //@ requires parent != null && label != null; 059 protected Tree(Tree parent, String label, Object data) { 060 this.parent = parent; 061 this.label = label; 062 this.data = data; 063 } 064 065 066 /*************************************************** 067 * * 068 * Simple public accessors: * 069 * * 070 **************************************************/ 071 072 /** Return our parent node or null if we have no parent */ 073 public final Tree getParent() { 074 return parent; 075 } 076 077 /** 078 * Return the label on the edge to us from our parent or null if we 079 * have no parent. 080 */ 081 public final String getLabel() { 082 return label; 083 } 084 085 086 /*************************************************** 087 * * 088 * Fetching and counting children: * 089 * * 090 **************************************************/ 091 092 /** 093 * An enumeration of this node's direct children. Each child 094 * occurs exactly once in the enumeration. The order is 095 * unspecified and may differ from call to call.<p> 096 * 097 * Note: The Objects returned by the resulting enumeration's 098 * nextElement method are guaranteed to be of type Tree, 099 * non-null, and have non-null labels.<p> 100 */ 101 //@ ensures \result != null; 102 //@ ensures !\result.returnsNull; 103 //@ ensures \result.elementType == \type(Tree); 104 public abstract Enumeration children(); 105 106 107 /** 108 * Fetch our direct child along the edge labelled label. Iff there 109 * is no such child, return null. 110 */ 111 //@ requires label != null; 112 public Tree getChild(String label) { 113 /* 114 * Stupid & slow default implementation using children() 115 * enumeration: 116 */ 117 Enumeration C = children(); 118 119 while (C.hasMoreElements()) { 120 Tree next = (Tree)C.nextElement(); 121 122 if (label.equals(next.label)) 123 return next; 124 } 125 126 return null; 127 } 128 129 130 /** Return true iff we have no direct children */ 131 public boolean isLeaf() { 132 return (!children().hasMoreElements()); 133 } 134 135 136 /** Return a count of how many direct children we have: */ 137 //@ ensures \result >= 0; 138 public int getChildrenCount() { 139 /* 140 * Stupid & slow default implementation using children() 141 * enumeration: 142 */ 143 int count = 0; 144 for (Enumeration C = children(); C.hasMoreElements(); C.nextElement()) 145 count++; 146 147 return count; 148 149 } 150 151 152 /*************************************************** 153 * * 154 * Utility functions: * 155 * * 156 **************************************************/ 157 158 /** 159 * The same as getLabel, except that it returns "" instead of null 160 * for the top node. 161 */ 162 //@ ensures \result != null; 163 public final String getSimpleName() { 164 if (label == null) 165 return ""; 166 else 167 return label; 168 } 169 170 /** 171 * Return a fully qualified name for this node using a specified 172 * separator String.<p> 173 * 174 * If the sequences of labels on the edges from the root of the 175 * tree this node belongs to til this node is X, Y, ... Z, then 176 * this routine returns the string X!Y! ... !Z, where ! is the 177 * separator. Normal usage is to use "." as the separator.<p> 178 * 179 * Root nodes are thus named "" and their direct children have 180 * names of the form X, where X is their label.<p> 181 * 182 * For the resulting name to be useful, labels should never contain 183 * the separator or be the empty string.<p> 184 */ 185 //@ ensures \result != null; 186 public final String getQualifiedName(String separator) { 187 if (parent == null) 188 return ""; 189 190 if (parent.parent == null) 191 return label; 192 193 return parent.getQualifiedName(separator) + separator + label; 194 } 195 196 /** Return the root node for the tree we belong to. */ 197 public final Tree getRootNode() { 198 if (parent == null) 199 return this; 200 201 return parent.getRootNode(); 202 } 203 204 /** 205 * Return the child with a given partially qualified name or null 206 * if no such node exists; if this node is X.Y and name is Z!W, 207 * where ! is the specified separator, then this routine attempts 208 * to find the child with fully qualified name X.Y.Z.W.<p> 209 * 210 * See getQualifiedName for more information on qualified names. 211 * Name must be non-null.<p> 212 */ 213 //@ requires name != null; 214 public final Tree getQualifiedChild(String name, char separator) { 215 String[] path = StringUtil.parseList(name, separator); 216 217 Tree currentNode = this; 218 for (int i=0; i<path.length; i++) { 219 currentNode = currentNode.getChild(path[i]); 220 if (currentNode == null) 221 return null; 222 } 223 224 return currentNode; 225 } 226 227 228 /*************************************************** 229 * * 230 * Debugging functions: * 231 * * 232 **************************************************/ 233 234 /** 235 * Print out on System.out a human-readable representation of this 236 * tree.<p> 237 * 238 * Included is our fully qualified name, our data, and information 239 * about each of our children.<p> 240 */ 241 public void print(String prefix) { 242 System.out.print(prefix + "Node '" + getQualifiedName(".") + "'"); 243 printDetails(prefix + " "); 244 if (isLeaf()) 245 System.out.println(); 246 else { 247 System.out.println(":"); 248 for (Enumeration E = children(); E.hasMoreElements(); ) 249 ((Tree)E.nextElement()).print(prefix + " "); 250 } 251 } 252 253 public void printDetails(String prefix) { 254 System.out.print(", data=" + data); 255 } 256 }