001 /* Copyright 2000, 2001, Compaq Computer Corporation */ 002 003 package javafe.filespace; 004 005 006 import java.util.*; 007 import java.io.File; 008 009 010 /** 011 * This class provides a way to enumerate all the nodes of a 012 * given Tree in depth-first pre-order using lexical ordering on 013 * siblings. I.e., X preceeds X.A, which in turn preceeds X.B. 014 * The first node in the list will be the root note of the Tree. 015 * It also allows enumerating a Tree's direct children in sorted order 016 * (based on their labels).<p> 017 * 018 * Guarantee: Returned elements are always non-null Trees.<p> 019 */ 020 021 public final class TreeWalker extends LookAheadEnum { 022 023 /*************************************************** 024 * * 025 * Instance variables: * 026 * * 027 **************************************************/ 028 029 //@ invariant elementType == \type(Tree); 030 //@ invariant !returnsNull; 031 032 033 /** 034 * The remaining children we have yet to start processing: 035 */ 036 //@ invariant remainingChildren != null; 037 //@ invariant !remainingChildren.returnsNull; 038 //@ invariant remainingChildren.elementType == \type(Tree); 039 protected Enumeration remainingChildren; 040 041 /** 042 * The remaining nodes from the child we are currently 043 * processing: 044 */ 045 //@ invariant remainingNodes != null; 046 //@ invariant !remainingNodes.returnsNull; 047 //@ invariant remainingNodes.elementType == \type(Tree); 048 protected Enumeration remainingNodes; 049 050 051 /*************************************************** 052 * * 053 * Creation: * 054 * * 055 **************************************************/ 056 057 /** 058 * From a Tree create an enumeration that enumerates 059 * all of the Tree's nodes (including the root node first). 060 * The nodes are produced in depth-first lexical pre-order. 061 */ 062 //@ requires T != null; 063 public TreeWalker(Tree T) { 064 // First element is the tree itself: 065 super(T); 066 067 remainingChildren = sortedChildren(T); 068 remainingNodes = new EmptyEnum(); 069 //@ set remainingNodes.elementType = \type(Tree); 070 071 //@ set elementType = \type(Tree); 072 //@ set returnsNull = false; 073 } 074 075 076 /*************************************************** 077 * * 078 * Calculating the next element: * 079 * * 080 **************************************************/ 081 082 /* 083 * This returns the next element in the enumeration or null if there 084 * are no more nodes left. 085 */ 086 //@ also 087 //@ assignable remainingNodes; 088 protected Object calcNextElement() { 089 for (;;) { 090 // First exhaust the nodes from the current child: 091 if (remainingNodes.hasMoreElements()) 092 return remainingNodes.nextElement(); 093 094 // Advance to next child: 095 if (!remainingChildren.hasMoreElements()) 096 return null; // no nodes left... 097 Tree nextChild = (Tree)remainingChildren.nextElement(); 098 099 // Process all of its nodes: 100 remainingNodes = new TreeWalker(nextChild); 101 } 102 } 103 104 105 /*************************************************** 106 * * 107 * Enumerating children in order: * 108 * * 109 **************************************************/ 110 111 /** 112 * Enumerate a Tree's direct children in sorted order (of labels).<p> 113 * 114 * Guarantee: The resulting enumeration never yields null as an 115 * element.<p> 116 */ 117 //@ requires T != null; 118 //@ ensures \result != null; 119 //@ ensures !\result.returnsNull; 120 //@ ensures \result.elementType == \type(Tree); 121 //@ ensures ((Object)\result).owner == null; 122 public static Enumeration sortedChildren(Tree T) { 123 return new TreeWalker_ArrayEnum(getSortedChildren(T)); 124 } 125 126 127 /** Return a sorted list of a Tree's direct children: */ 128 //@ requires T != null; 129 //@ ensures \result != null; 130 //@ ensures \elemtype(\typeof(\result)) == \type(Tree); 131 private static Tree[] getSortedChildren(Tree T) { 132 Tree[] directChildren = new Tree[T.getChildrenCount()]; 133 134 // Copy list of T's direct children into an array: 135 int c = 0; 136 for (Enumeration C=T.children(); C.hasMoreElements(); ) { 137 directChildren[c++] = (Tree)C.nextElement(); //@nowarn IndexTooBig; 138 } 139 //@ assume \nonnullelements(directChildren); 140 141 // Sort the array then return it: 142 sort(directChildren); 143 return directChildren; 144 } 145 146 /* 147 * A simple, stupid (aka slow) sorting routine. 148 * 149 * precondition: a[i] is not a root node. 150 */ 151 //@ requires \nonnullelements(a); 152 private static void sort(Tree[] a) { 153 // Only arrays of length>2 need to be sorted: 154 if (a.length<2) 155 return; 156 157 // Bubble sort... 158 for (;;) { 159 boolean sorted = true; 160 for (int i=0; i<a.length-1; i++) { 161 if (a[i].getLabel().compareTo //@ nowarn Null; 162 (a[i+1].getLabel())>0) { //@ nowarn NonNull; 163 Tree tmp = a[i]; 164 a[i] = a[i+1]; 165 a[i+1] = tmp; 166 sorted = false; 167 } 168 } 169 if (sorted) 170 return; 171 } 172 } 173 174 175 /*************************************************** 176 * * 177 * Debugging: * 178 * * 179 **************************************************/ 180 181 /** A simple test driver. */ 182 //@ requires \nonnullelements(args); 183 public static void main(String[] args) { 184 if (args.length != 1) { 185 System.out.println("usage: TreeWalker <pathname>"); 186 return; 187 } 188 String treeName = args[0]; 189 190 // Find the tree in question: 191 Tree top = new FileTree(new File(treeName)); 192 193 // Enumerate its subtrees: 194 for (Enumeration E = new TreeWalker(top); E.hasMoreElements();) { 195 Tree subtree = (Tree)E.nextElement(); 196 System.out.println(subtree.getQualifiedName(".") + ":"); 197 } 198 } 199 } 200 201 202 /** 203 * A Enumeration for enumerating the members of an array of Objects. 204 * 205 * This filter is for the use of the TreeWalker class only; if inner 206 * classes were available, it would be expressed as an anonymous class. 207 */ 208 class TreeWalker_ArrayEnum extends LookAheadEnum { 209 210 //@ private invariant list != null; 211 //@ private invariant \elemtype(\typeof(list)) == elementType; 212 private Object[] list; 213 214 //@ private invariant index+1>=0; 215 private int index = -1; 216 217 218 //@ private normal_behavior 219 //@ requires list != null; 220 //@ assignable \not_specified; 221 //@ ensures elementType == \elemtype(\typeof(list)); 222 TreeWalker_ArrayEnum(Object[] list) { 223 this.list = list; 224 225 //@ set elementType = \elemtype(\typeof(list)); 226 } 227 228 //@ also private normal_behavior 229 //@ assignable index; 230 public Object calcNextElement() { 231 if (++index>=list.length) 232 return null; 233 else 234 return list[index]; 235 } 236 }