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 }