001package org.jdesktop.swingx.tree; 002 003import java.util.ArrayDeque; 004import java.util.Deque; 005import java.util.Enumeration; 006import java.util.NoSuchElementException; 007import java.util.Queue; 008import java.util.Vector; 009import java.util.logging.Logger; 010 011import javax.swing.tree.TreeModel; 012import javax.swing.tree.TreeNode; 013import javax.swing.tree.TreePath; 014 015/** 016 * Contains convenience classes/methods for handling hierarchical Swing structures. 017 * 018 * @author Jeanette Winzenburg, Berlin 019 */ 020@SuppressWarnings({ "unchecked", "rawtypes" }) 021public class TreeUtilities { 022 023 /** 024 * An enumeration that is always empty. 025 */ 026 public static final Enumeration EMPTY_ENUMERATION 027 = new Enumeration() { 028 @Override 029 public boolean hasMoreElements() { return false; } 030 @Override 031 public Object nextElement() { 032 throw new NoSuchElementException("No more elements"); 033 } 034 }; 035 036 /** 037 * Implementation of a preorder traversal of a TreeModel. 038 */ 039 public static class PreorderModelEnumeration implements Enumeration { 040 protected Deque<Enumeration> stack; 041 protected TreeModel model; 042 // the last component is the current subtree to travers 043 private TreePath path; 044 045 /** 046 * Instantiates a preorder traversal starting from the root of the 047 * TreeModel. 048 * 049 * @param model the TreeModel to travers. 050 */ 051 public PreorderModelEnumeration(TreeModel model) { 052 this(model, model.getRoot()); 053 } 054 055 /** 056 * Instantiates a preorder traversal of the TreeModel which 057 * starts at the given node. It iterates over all nodes of the 058 * subtree, only. 059 * 060 * @param model the TreeModel to travers. 061 * @param node the node to start 062 */ 063 public PreorderModelEnumeration(TreeModel model, Object node) { 064 this.model = model; 065 stack = new ArrayDeque<Enumeration>(); 066 pushNodeAsEnumeration(node); 067 } 068 069 /** 070 * Instantiates a preorder traversal of the TreeModel which starts at the 071 * last path component of the given TreePath. It iterates over all nodes 072 * of the subtree and all of its siblings, with the same end as a traversal 073 * starting at the model's roolt would have. 074 * 075 * @param model the TreeModel to travers. 076 * @param path the TreePath to start from 077 */ 078 public PreorderModelEnumeration(TreeModel model, TreePath path) { 079 this(model, path.getLastPathComponent()); 080 this.path = path; 081 } 082 083 @Override 084 public boolean hasMoreElements() { 085 return (!stack.isEmpty() && stack.peek().hasMoreElements()); 086 } 087 088 @Override 089 public Object nextElement() { 090 Enumeration enumer = stack.peek(); 091 Object node = enumer.nextElement(); 092 Enumeration children = children(model, node); 093 094 if (!enumer.hasMoreElements()) { 095 stack.pop(); 096 } 097 if (children.hasMoreElements()) { 098 stack.push(children); 099 } 100 if (!hasMoreElements()) { 101 // check if there are more subtrees to travers 102 // and update internal state accordingly 103 updateSubtree(); 104 } 105 return node; 106 } 107 108 /** 109 * 110 */ 111 private void updateSubtree() { 112 if (path == null) return; 113 TreePath parentPath = path.getParentPath(); 114 if (parentPath == null) { 115 // root 116 path = null; 117 return; 118 } 119 Object parent = parentPath.getLastPathComponent(); 120 Object currentNode = path.getLastPathComponent(); 121 int currentIndex = model.getIndexOfChild(parent, currentNode); 122 if (currentIndex +1 < model.getChildCount(parent)) { 123 // use sibling 124 Object child = model.getChild(parent, currentIndex + 1); 125 path = parentPath.pathByAddingChild(child); 126 pushNodeAsEnumeration(child); 127 } else { 128 path = parentPath; 129 // up one level 130 updateSubtree(); 131 } 132 } 133 134 private void pushNodeAsEnumeration(Object node) { 135 // single element enum 136 Vector v = new Vector(1); 137 v.add(node); 138 stack.push(v.elements()); //children(model)); 139 } 140 141 142 } // End of class PreorderEnumeration 143 144 145 /** 146 * Implementation of a breadthFirst traversal of a subtree in a TreeModel. 147 */ 148 public static class BreadthFirstModelEnumeration implements Enumeration { 149 protected Queue<Enumeration> queue; 150 private TreeModel model; 151 152 public BreadthFirstModelEnumeration(TreeModel model) { 153 this(model, model.getRoot()); 154 } 155 156 public BreadthFirstModelEnumeration(TreeModel model, Object node) { 157 this.model = model; 158 // Vector is just used for getting an Enumeration easily 159 Vector v = new Vector(1); 160 v.addElement(node); 161 queue = new ArrayDeque<Enumeration>(); 162 queue.offer(v.elements()); 163 } 164 165 @Override 166 public boolean hasMoreElements() { 167 return !queue.isEmpty() && 168 queue.peek().hasMoreElements(); 169 } 170 171 @Override 172 public Object nextElement() { 173 // look at head 174 Enumeration enumer = queue.peek(); 175 Object node = enumer.nextElement(); 176 Enumeration children = children(model, node); 177 178 if (!enumer.hasMoreElements()) { 179 // remove head 180 queue.poll(); 181 } 182 if (children.hasMoreElements()) { 183 // add at tail 184 queue.offer(children); 185 } 186 return node; 187 } 188 189 } // End of class BreadthFirstEnumeration 190 191 192 /** 193 * Implementation of a postorder traversal of a subtree in a TreeModel. 194 */ 195 public static class PostorderModelEnumeration implements Enumeration { 196 protected TreeModel model; 197 protected Object root; 198 protected Enumeration children; 199 protected Enumeration subtree; 200 201 public PostorderModelEnumeration(TreeModel model) { 202 this(model, model.getRoot()); 203 } 204 205 public PostorderModelEnumeration(TreeModel model, Object node) { 206 this.model = model; 207 root = node; 208 children = children(model, root); 209 subtree = EMPTY_ENUMERATION; 210 } 211 212 @Override 213 public boolean hasMoreElements() { 214 return root != null; 215 } 216 217 @Override 218 public Object nextElement() { 219 Object retval; 220 221 if (subtree.hasMoreElements()) { 222 retval = subtree.nextElement(); 223 } else if (children.hasMoreElements()) { 224 subtree = new PostorderModelEnumeration(model, 225 children.nextElement()); 226 retval = subtree.nextElement(); 227 } else { 228 retval = root; 229 root = null; 230 } 231 232 return retval; 233 } 234 235 } // End of class PostorderEnumeration 236 237 /** 238 * Implementation of a preorder traversal of a subtree with nodes of type TreeNode. 239 */ 240 public static class PreorderNodeEnumeration<M extends TreeNode> implements Enumeration<M> { 241 protected Deque<Enumeration<M>> stack; 242 243 public PreorderNodeEnumeration(M rootNode) { 244 // Vector is just used for getting an Enumeration easily 245 Vector<M> v = new Vector<M>(1); 246 v.addElement(rootNode); 247 stack = new ArrayDeque<Enumeration<M>>(); 248 stack.push(v.elements()); 249 } 250 251 @Override 252 public boolean hasMoreElements() { 253 return (!stack.isEmpty() && 254 stack.peek().hasMoreElements()); 255 } 256 257 @Override 258 public M nextElement() { 259 Enumeration<M> enumer = stack.peek(); 260 M node = enumer.nextElement(); 261 Enumeration<M> children = node.children(); 262 263 if (!enumer.hasMoreElements()) { 264 stack.pop(); 265 } 266 if (children.hasMoreElements()) { 267 stack.push(children); 268 } 269 return node; 270 } 271 272 } // End of class PreorderEnumeration 273 274 /** 275 * Implementation of a postorder traversal of a subtree with nodes of type TreeNode. 276 */ 277 public static class PostorderNodeEnumeration<M extends TreeNode> implements Enumeration<M> { 278 protected M root; 279 protected Enumeration<M> children; 280 protected Enumeration<M> subtree; 281 282 public PostorderNodeEnumeration(M rootNode) { 283 super(); 284 root = rootNode; 285 children = root.children(); 286 subtree = EMPTY_ENUMERATION; 287 } 288 289 @Override 290 public boolean hasMoreElements() { 291 return root != null; 292 } 293 294 @Override 295 public M nextElement() { 296 M retval; 297 298 if (subtree.hasMoreElements()) { 299 retval = subtree.nextElement(); 300 } else if (children.hasMoreElements()) { 301 subtree = new PostorderNodeEnumeration<M>( 302 children.nextElement()); 303 retval = subtree.nextElement(); 304 } else { 305 retval = root; 306 root = null; 307 } 308 309 return retval; 310 } 311 312 } // End of class PostorderEnumeration 313 314 315 /** 316 * Implementation of a breadthFirst traversal of a subtree with nodes of type TreeNode. 317 */ 318 public static class BreadthFirstNodeEnumeration<M extends TreeNode> implements Enumeration<M> { 319 protected Queue<Enumeration<M>> queue; 320 321 public BreadthFirstNodeEnumeration(M rootNode) { 322 // Vector is just used for getting an Enumeration easily 323 Vector<M> v = new Vector<M>(1); 324 v.addElement(rootNode); 325 queue = new ArrayDeque<Enumeration<M>>(); 326 queue.offer(v.elements()); 327 } 328 329 @Override 330 public boolean hasMoreElements() { 331 return !queue.isEmpty() && 332 queue.peek().hasMoreElements(); 333 } 334 335 @Override 336 public M nextElement() { 337 // look at head 338 Enumeration<M> enumer = queue.peek(); 339 M node = enumer.nextElement(); 340 Enumeration<M> children = node.children(); 341 342 if (!enumer.hasMoreElements()) { 343 // remove head 344 queue.poll(); 345 } 346 if (children.hasMoreElements()) { 347 // add at tail 348 queue.offer(children); 349 } 350 return node; 351 } 352 353 354 } // End of class BreadthFirstEnumeration 355 356 /** 357 * Creates and returns an Enumeration across the direct children of the 358 * rootNode in the given TreeModel. 359 * 360 * @param model the TreeModel which contains parent, must not be null 361 * @return an Enumeration across the direct children of the model's root, the enumeration 362 * is empty if the root is null or contains no children 363 */ 364 public static Enumeration children(TreeModel model) { 365 return children(model, model.getRoot()); 366 } 367 368 /** 369 * Creates and returns an Enumeration across the direct children of parentNode 370 * in the given TreeModel. 371 * 372 * @param model the TreeModel which contains parent, must not be null 373 * @param parent the parent of the enumerated children 374 * @return an Enumeration across the direct children of parent, the enumeration 375 * is empty if the parent is null or contains no children 376 */ 377 public static Enumeration children(final TreeModel model, final Object parent) { 378 if (parent == null || model.isLeaf(parent)) { 379 return EMPTY_ENUMERATION; 380 } 381 Enumeration<?> e = new Enumeration() { 382 383 int currentIndex = 0; 384 @Override 385 public boolean hasMoreElements() { 386 return model.getChildCount(parent) > currentIndex; 387 } 388 389 @Override 390 public Object nextElement() { 391 return model.getChild(parent, currentIndex++); 392 } 393 394 }; 395 return e; 396 } 397 398 private TreeUtilities() {} 399 400 @SuppressWarnings("unused") 401 private static final Logger LOG = Logger.getLogger(TreeUtilities.class 402 .getName()); 403}