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    }