001    /*--------------------------------------------------------------------------+
002    $Id: TreeUtils.java 26268 2010-02-18 10:44:30Z 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.tree;
019    
020    import java.util.Arrays;
021    import java.util.List;
022    import java.util.Set;
023    
024    /**
025     * Utility class for tree construction.
026     * 
027     * @author deissenb
028     * @author $Author: juergens $
029     * @version $Rev: 26268 $
030     * @levd.rating GREEN Hash: 3CA3EEE13CB7C2935D6E01EE3AD9DA30
031     */
032    public class TreeUtils {
033    
034            /**
035             * This method creates a tree from a set of paths.
036             * 
037             * @param <T>
038             *            the node type to be created
039             * 
040             * @param <K>
041             *            the key type used by the nodes
042             * @param paths
043             *            a set of paths where each path is a list of path elements
044             *            (keys)
045             * @param handler
046             *            the handler used for creating the tree.
047             * @return The root node of the tree. The root node (as generated by
048             *         {@link ITreeNodeHandler#createRoot()} is always returned, even if
049             *         the set of paths is empty.
050             */
051            public static <T, K> T createTree(Set<List<K>> paths,
052                            ITreeNodeHandler<T, K> handler) {
053                    T root = handler.createRoot();
054    
055                    for (List<K> path : paths) {
056                            insert(root, path, handler);
057                    }
058    
059                    return root;
060            }
061    
062            /**
063             * Utility method for creating a tree from paths described by strings.
064             * 
065             * @param <T>
066             *            the node type to be created
067             * @param paths
068             *            a set of paths where each path is described by a path
069             *            expression string, e.g. node1/node2/node3
070             * @param separator
071             *            regular expression that defines the separator between path
072             *            elements.
073             * @param handler
074             *            the handler used for creating the tree.
075             * @return The root node of the tree. The root node (as generated by
076             *         {@link ITreeNodeHandler#createRoot()} is always returned, even if
077             *         the set of paths is empty.
078             */
079            public static <T> T createTreeFromStrings(Set<String> paths,
080                            String separator, ITreeNodeHandler<T, String> handler) {
081                    T root = handler.createRoot();
082    
083                    for (String pathDescriptor : paths) {
084                            String[] pathElements = pathDescriptor.split(separator);
085                            insert(root, Arrays.asList(pathElements), handler);
086                    }
087    
088                    return root;
089            }
090    
091            /**
092             * Create a node from a path.
093             * 
094             * @param <T>
095             *            the node type to be created
096             * @param <K>
097             *            the key type used by the nodes
098             * @param node
099             *            the reference node the new node is added to
100             * @param path
101             *            the path is a list of path elements (keys)
102             * @param handler
103             *            the handler used for creating the tree
104             */
105            private static <T, K> void insert(T node, List<K> path,
106                            ITreeNodeHandler<T, K> handler) {
107                    for (K pathElement : path) {
108                            node = handler.getOrCreateChild(node, pathElement);
109                    }
110            }
111    }