001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 The ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| You may obtain a copy of the License at                                  |
008|                                                                          |
009|    http://www.apache.org/licenses/LICENSE-2.0                            |
010|                                                                          |
011| Unless required by applicable law or agreed to in writing, software      |
012| distributed under the License is distributed on an "AS IS" BASIS,        |
013| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
014| See the License for the specific language governing permissions and      |
015| limitations under the License.                                           |
016+-------------------------------------------------------------------------*/
017package org.conqat.lib.commons.tree;
018
019import java.util.Arrays;
020import java.util.List;
021import java.util.Set;
022
023/**
024 * Utility class for tree construction.
025 * 
026 * @author deissenb
027 */
028public class TreeUtils {
029
030        /**
031         * This method creates a tree from a set of paths.
032         * 
033         * @param <T>
034         *            the node type to be created
035         * 
036         * @param <K>
037         *            the key type used by the nodes
038         * @param paths
039         *            a set of paths where each path is a list of path elements
040         *            (keys)
041         * @param handler
042         *            the handler used for creating the tree.
043         * @return The root node of the tree. The root node (as generated by
044         *         {@link ITreeNodeHandler#createRoot()} is always returned, even if
045         *         the set of paths is empty.
046         */
047        public static <T, K> T createTree(Set<List<K>> paths, ITreeNodeHandler<T, K> handler) {
048                T root = handler.createRoot();
049
050                for (List<K> path : paths) {
051                        insert(root, path, handler);
052                }
053
054                return root;
055        }
056
057        /**
058         * Utility method for creating a tree from paths described by strings.
059         * 
060         * @param <T>
061         *            the node type to be created
062         * @param paths
063         *            a set of paths where each path is described by a path
064         *            expression string, e.g. node1/node2/node3
065         * @param separator
066         *            regular expression that defines the separator between path
067         *            elements.
068         * @param handler
069         *            the handler used for creating the tree.
070         * @return The root node of the tree. The root node (as generated by
071         *         {@link ITreeNodeHandler#createRoot()} is always returned, even if
072         *         the set of paths is empty.
073         */
074        public static <T> T createTreeFromStrings(Set<String> paths, String separator,
075                        ITreeNodeHandler<T, String> handler) {
076                T root = handler.createRoot();
077
078                for (String pathDescriptor : paths) {
079                        String[] pathElements = pathDescriptor.split(separator);
080                        insert(root, Arrays.asList(pathElements), handler);
081                }
082
083                return root;
084        }
085
086        /**
087         * Create a node from a path.
088         * 
089         * @param <T>
090         *            the node type to be created
091         * @param <K>
092         *            the key type used by the nodes
093         * @param node
094         *            the reference node the new node is added to
095         * @param path
096         *            the path is a list of path elements (keys)
097         * @param handler
098         *            the handler used for creating the tree
099         */
100        private static <T, K> void insert(T node, List<K> path, ITreeNodeHandler<T, K> handler) {
101                for (K pathElement : path) {
102                        node = handler.getOrCreateChild(node, pathElement);
103                }
104        }
105}