001/*
002 * Copyright (C) 2009-2011 Mathias Doenitz
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.parboiled.trees;
018
019import org.parboiled.common.Preconditions;
020
021/**
022 * General utility methods for operating on tree, i.e. graphs consisting of {@link TreeNode}s.
023 */
024public final class TreeUtils {
025
026    private TreeUtils() {}
027
028    /**
029     * Returns the root of the tree the given node is part of.
030     *
031     * @param node the node to get the root of
032     * @return the root or null if the given node is null
033     */
034    public static <T extends TreeNode<T>> T getRoot(T node) {
035        if (node == null) return null;
036        if (node.getParent() != null) return getRoot(node.getParent());
037        return node;
038    }
039
040    /**
041     * Adds a new child node to a given MutableTreeNode parent.
042     *
043     * @param parent the parent node
044     * @param child  the child node to add
045     */
046    public static <T extends MutableTreeNode<T>> void addChild(T parent, T child) {
047        Preconditions.checkArgNotNull(parent, "parent");
048        parent.addChild(parent.getChildren().size(), child);
049    }
050
051    /**
052     * Removes the given child from the given parent node.
053     *
054     * @param parent the parent node
055     * @param child  the child node
056     */
057    public static <T extends MutableTreeNode<T>> void removeChild(T parent, T child) {
058        Preconditions.checkArgNotNull(parent, "parent");
059        int index = parent.getChildren().indexOf(child);
060        Preconditions.checkElementIndex(index, parent.getChildren().size());
061        parent.removeChild(index);
062    }
063
064    /**
065     * Performs the following transformation on the given MutableBinaryTreeNode:
066     * <pre>
067     *        o1                    o2
068     *       / \                   / \
069     *      A   o2     ====>     o1   C
070     *         / \              / \
071     *        B   C            A   B
072     * </pre>
073     *
074     * @param node the node to transform
075     * @return the new root after the transformation, which is either the right sub node of the original root
076     *         or the original root, if the right sub node is null
077     */
078    public static <N extends MutableBinaryTreeNode<N>> N toLeftAssociativity(N node) {
079        Preconditions.checkArgNotNull(node, "node");
080        N right = node.right();
081        if (right == null) return node;
082
083        node.setRight(right.left());
084        right.setLeft(node);
085        return right;
086    }
087}