001 /*--------------------------------------------------------------------------+ 002 $Id: VisitorUtils.java 26283 2010-02-18 11:18:57Z juergens $ 003 | | 004 | Copyright 2005-2010 Technische Universitaet Muenchen | 005 | | 006 | Licensed under the Apache License, Version 2.0 (the "License"); | 007 | you may not use this file except in compliance with the License. | 008 | You may obtain a copy of the License at | 009 | | 010 | http://www.apache.org/licenses/LICENSE-2.0 | 011 | | 012 | Unless required by applicable law or agreed to in writing, software | 013 | distributed under the License is distributed on an "AS IS" BASIS, | 014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | 015 | See the License for the specific language governing permissions and | 016 | limitations under the License. | 017 +--------------------------------------------------------------------------*/ 018 package edu.tum.cs.commons.visitor; 019 020 import java.util.Collection; 021 import java.util.Set; 022 023 import edu.tum.cs.commons.collections.IdentityHashSet; 024 025 /** 026 * Utility class for working with visitors. 027 * 028 * @author hummelb 029 * @author $Author: juergens $ 030 * @version $Rev: 26283 $ 031 * @levd.rating GREEN Hash: 00BEBED1B01400AAA4E7790F22F6900B 032 */ 033 public class VisitorUtils { 034 035 /** 036 * Visits all nodes of a tree in pre-order, i.e. a node is visited directly 037 * before its children. 038 * 039 * @param root 040 * the root of the tree. 041 * @param walker 042 * the walker user for traversing the tree. 043 * @param visitor 044 * the visitor used for visiting the nodes. 045 */ 046 public static <T, X1 extends Exception, X2 extends Exception> void visitAllPreOrder( 047 T root, ITreeWalker<T, X1> walker, IVisitor<T, X2> visitor) 048 throws X1, X2 { 049 050 visitor.visit(root); 051 for (T child : walker.getChildren(root)) { 052 visitAllPreOrder(child, walker, visitor); 053 } 054 } 055 056 /** 057 * Visits all leaves of a tree, i.e. those nodes without children. 058 * 059 * @param root 060 * the root of the tree. 061 * @param walker 062 * the walker user for traversing the tree. 063 * @param visitor 064 * the visitor used for visiting the nodes. 065 */ 066 public static <T, X1 extends Exception, X2 extends Exception> void visitLeaves( 067 T root, ITreeWalker<T, X1> walker, IVisitor<T, X2> visitor) 068 throws X1, X2 { 069 070 Collection<T> children = walker.getChildren(root); 071 if (children.isEmpty()) { 072 visitor.visit(root); 073 } else { 074 for (T child : children) { 075 visitLeaves(child, walker, visitor); 076 } 077 } 078 } 079 080 /** 081 * Visits all elements of a mesh in depth first order. It is made sure, that 082 * each reachable element is visited exactly once, where we use equality of 083 * references to determine elements that were seen before. 084 * 085 * @param start 086 * the element to start the traversal from. 087 * @param walker 088 * the walker user for traversing the mesh. 089 * @param visitor 090 * the visitor used for visiting the elements. 091 */ 092 public static <T, X1 extends Exception, X2 extends Exception> void visitAllDepthFirst( 093 T start, IMeshWalker<T, X1> walker, IVisitor<T, X2> visitor) 094 throws X1, X2 { 095 096 IdentityHashSet<T> seen = new IdentityHashSet<T>(); 097 seen.add(start); 098 visitAllDepthFirst(start, walker, visitor, seen); 099 } 100 101 /** 102 * Helper method for 103 * {@link #visitAllDepthFirst(Object, IMeshWalker, IVisitor)}. The 104 * parameters are the same as there, only a set for storing seen elements is 105 * added. 106 */ 107 private static <T, X1 extends Exception, X2 extends Exception> void visitAllDepthFirst( 108 T start, IMeshWalker<T, X1> walker, IVisitor<T, X2> visitor, 109 Set<T> seen) throws X1, X2 { 110 visitor.visit(start); 111 for (T element : walker.getAdjacentElements(start)) { 112 if (seen.add(element)) { 113 visitAllDepthFirst(element, walker, visitor, seen); 114 } 115 } 116 } 117 }