package org.apache.torque.generator.source;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;
import java.util.StringTokenizer;

import org.apache.torque.generator.GeneratorException;

/**
 * Methods for traversing a source tree.
 */
public final class SourcePath
{
    /**
     * The separator between different levels in the path.
     */
    private static final String PATH_LEVEL_SEPARATOR = "/";

    /**
     * The token denoting the current element.
     */
    private static final String THIS_TOKEN = ".";

    /**
     * The token denoting the parent element.
     */
    private static final String PARENT_TOKEN = "..";

    /**
     * The token denoting the parent element.
     */
    private static final String ANY_ELEMENT_TOKEN = "*";

    /**
     * Private constructor for utility class.
     */
    private SourcePath()
    {
    }

    /**
     * Returns whether children with the given name exist.
     *
     * @param sourceElement the start element, not null.
     * @param name the name of the child element, not null.
     *
     * @return true if children with the given name exist, false otherwise.
     *
     * @throws NullPointerException if name is null.
     */
    public static boolean hasChild(SourceElement sourceElement, String name)
    {
        if (name == null)
        {
            throw new NullPointerException("name must not be null");
        }
        if (sourceElement == null)
        {
            throw new NullPointerException("sourceElement must not be null");
        }
        for (SourceElement child : sourceElement.getChildren())
        {
            if (name.equals(child.getName()))
            {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns whether a following element exists as a child of the parent of
     * this element.
     *
     * @param sourceElement the start element, not null.
     *
     * @return true if a following element exists, false if not.
     */
    public static boolean hasFollowing(SourceElement sourceElement)
    {
        return !getFollowing(sourceElement, null).isEmpty();
    }

    /**
     * Returns whether an preceding exists as a child of the parent of
     * this element.
     *
     * @param sourceElement the start element, not null.
     *
     * @return true if a preceding element exists, false if not.
     */
    public static boolean hasPreceding(SourceElement sourceElement)
    {
        return !getPreceding(sourceElement, sourceElement.getName()).isEmpty();
    }

    /**
     * Returns whether a following element exists as a child of the parent of
     * this element, which has the same name as this source element.
     *
     * @param sourceElement the start element, not null.
     *
     * @return true if a following sibling exists, false if not.
     */
    public static boolean hasFollowingSibling(SourceElement sourceElement)
    {
        return !getFollowing(sourceElement, sourceElement.getName()).isEmpty();
    }

    /**
     * Returns whether an preceding exists as a child of the parent of
     * this element, which has the same name as this source element.
     *
     * @param sourceElement the start element, not null.
     *
     * @return true if a preceding sibling exists, false if not.
     */
    public static boolean hasPrecedingSibling(SourceElement sourceElement)
    {
        return !getPreceding(sourceElement, sourceElement.getName()).isEmpty();
    }

    /**
     * Returns all the preceding elements before this element
     * with the given name.
     * If name is null, all preceding elements are returned.
     * If this element has no parent, an empty list is returned.
     *
     * @param sourceElement the start element, not null.
     * @param name the name of the preceding elements to select,
     *        or null to select all preceding elements.
     *
     * @return a list containing the preceding elements with the given name,
     *         never null.
     *
     * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
     */
    public static List<SourceElement> getPreceding(
            SourceElement sourceElement,
            String name)
    {
        if (sourceElement == null)
        {
            throw new NullPointerException("sourceElement must not be null");
        }

        List<SourceElement> result = new ArrayList<SourceElement>();
        ListIterator<SourceElement> sameLevelIt
                = getSiblingIteratorPositionedOnSelf(sourceElement);
        if (sameLevelIt == null)
        {
            return result;
        }
        boolean first = true;
        while (sameLevelIt.hasPrevious())
        {
            SourceElement sameLevelElement = sameLevelIt.previous();
            // skip first iterated element because it is input element,
            // but we want to begin before the input element.
            if (first)
            {
                first = false;
                continue;
            }
            if (name == null || name.equals(sameLevelElement.getName()))
            {
                result.add(sameLevelElement);
            }
        }
        return result;

    }

    /**
     * Returns all the following elements after this element
     * with the given name.
     * If name is null, all following elements are returned.
     * If this element has no parent, an empty list is returned.
     *
     * @param sourceElement the start element, not null.
     * @param name the name of the following elements to select,
     *        or null to select all following elements.
     *
     * @return a list containing the following elements with the given name,
     *         never null.
     *
     * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
     */
    public static List<SourceElement> getFollowing(
            SourceElement sourceElement,
            String name)
    {
        if (sourceElement == null)
        {
            throw new NullPointerException("sourceElement must not be null");
        }
        List<SourceElement> result = new ArrayList<SourceElement>();

        ListIterator<SourceElement> sameLevelIt
                = getSiblingIteratorPositionedOnSelf(sourceElement);
        if (sameLevelIt == null)
        {
            return result;
        }
        while (sameLevelIt.hasNext())
        {
            SourceElement sameLevelElement = sameLevelIt.next();
            if (name == null || name.equals(sameLevelElement.getName()))
            {
                result.add(sameLevelElement);
            }
        }
        return result;
    }

    /**
     * Returns a ListIterator of the siblings of the input source element.
     * The iterator is positioned such that the next method returns
     * the element after the input element, and the previous method returns
     * the input element.
     *
     * @param sourceElement the source element for which the sibling iterator
     *        should be created, not null.
     *
     * @return the sibling iterator, or null if the input source element has
     *         no parent.
     *
     * @throws IllegalArgumentException if the element cannot be found in the
     *         list of children of its parent.
     */
    private static ListIterator<SourceElement> getSiblingIteratorPositionedOnSelf(
            SourceElement sourceElement)
    {
        SourceElement parent = sourceElement.getParent();
        if (parent == null)
        {
            return null;
        }
        ListIterator<SourceElement> sameLevelIt
                = parent.getChildren().listIterator();

        boolean found = false;
        while (sameLevelIt.hasNext())
        {
            SourceElement sameLevelElement = sameLevelIt.next();
            if (sameLevelElement == sourceElement)
            {
                found = true;
                break;
            }
        }
        if (!found)
        {
            throw new IllegalArgumentException("Inconsistent source tree: "
                    + "Source element " + sourceElement.getName()
                    + " not found in the list of the children of its parent");
        }
        return sameLevelIt;
    }

    /**
     * Gets the elements which can be reached from the start element by a given
     * path.
     *
     * @param sourceElement the start element, not null.
     * @param path the path to use, not null.
     *
     * @return the list of matching source elements, not null, may be empty.
     *
     * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
     */
    public static List<SourceElement> getElements(
            SourceElement sourceElement,
            String path)
    {
        if (sourceElement == null)
        {
            throw new NullPointerException("sourceElement must not be null");
        }

        if (path.equals(THIS_TOKEN))
        {
            List<SourceElement> result = new ArrayList<SourceElement>(1);
            result.add(sourceElement);
            return result;
        }
        StringTokenizer selectionPathTokenizer
            = new StringTokenizer(path, PATH_LEVEL_SEPARATOR);
        List<SourceElement> currentSelection = new ArrayList<SourceElement>();
        currentSelection.add(sourceElement);
        while (selectionPathTokenizer.hasMoreTokens())
        {
            String childName = selectionPathTokenizer.nextToken();
            List<SourceElement> nextSelection = new ArrayList<SourceElement>();
            for (SourceElement currentElement : currentSelection)
            {
                if (childName.equals(PARENT_TOKEN))
                {
                    SourceElement parent = currentElement.getParent();
                    if (parent != null && !nextSelection.contains(parent))
                    {
                        nextSelection.add(parent);
                    }
                }
                else if (ANY_ELEMENT_TOKEN.equals(childName))
                {
                    for (SourceElement child
                            : currentElement.getChildren())
                    {
                        nextSelection.add(child);
                    }
                }
                {
                    for (SourceElement child
                            : currentElement.getChildren(childName))
                    {
                        nextSelection.add(child);
                    }
                }
            }
            currentSelection = nextSelection;
        }
        return currentSelection;
    }

    /**
     * Gets the elements which can be reached from the root element by a given
     * path. The name of the root element must appear first in the path,
     * otherwise nothing is selected.
     *
     * @param rootElement the root element of the source tree, not null.
     * @param path the path to use, null selects the root element.
     *
     * @return the list of matching source elements, not null, may be empty.
     *
     * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
     */
    public static List<SourceElement> getElementsFromRoot(
            SourceElement rootElement,
            String path)
    {
        if (rootElement == null)
        {
            throw new NullPointerException("rootElement must not be null");
        }

        if (path == null
                || "".equals(path.trim())
                || PATH_LEVEL_SEPARATOR.equals(path.trim()))
        {
            // use root element
            List<SourceElement> result = new ArrayList<SourceElement>(1);
            result.add(rootElement);
            return result;
        }

        path = path.trim();
        // remove leading slash
        if (path.startsWith(PATH_LEVEL_SEPARATOR))
        {
            path = path.substring(1);
        }
        int firstSeparatorPos = path.indexOf(PATH_LEVEL_SEPARATOR);
        String firstElementName;
        if (firstSeparatorPos == -1)
        {
            firstElementName = path;
            path = THIS_TOKEN;
        }
        else
        {
            firstElementName = path.substring(0, firstSeparatorPos);
            path = path.substring(firstSeparatorPos + 1);
        }
        if (!ANY_ELEMENT_TOKEN.equals(firstElementName)
                && !rootElement.getName().equals(firstElementName))
        {
            return new ArrayList<SourceElement>();
        }
        return SourcePath.getElements(rootElement, path);
    }


    /**
     * Gets a single source element which can be reached from the start element
     * by a given path.
     *
     * @param sourceElement the start element, not null.
     * @param path the path to use, not null.
     * @param acceptEmpty whether no match is an error(acceptEmpty=false)
     *        or not (acceptEmpty=true)
     *
     * @return the single matching source elements, may be null only if
     *         acceptEmpty=true.
     *
     * @throws GeneratorException if more than one source element matches,
     *       or if no source element matches and acceptEmpty=false
     * @see <a href="http://www.w3.org/TR/xpath#axes">xpath axes</a>
     */
    public static SourceElement getElement(
            SourceElement sourceElement,
            String path,
            boolean acceptEmpty)
        throws GeneratorException
    {
        List<SourceElement> sourceElements
                = SourcePath.getElements(sourceElement, path);
        if (sourceElements.isEmpty())
        {
            if (acceptEmpty)
            {
                return null;
            }
            else
            {
                throw new GeneratorException(
                        "Source element path "
                        + path
                        + " selects no element on source element "
                        + sourceElement.getName());
            }
        }
        if (sourceElements.size() > 1)
        {
            throw new GeneratorException(
                    "Source element path "
                    + path
                    + " selects more than a single element on source element "
                    + sourceElement.getName());
        }
        return sourceElements.get(0);
    }

    /**
     * Returns the path from the root element to the source element.
     * The element names are separated by slashes.
     * Example: root/firstLevelElement/secondLevelElement/currentNode
     *
     * @param sourceElement the element to output, not null.
     *
     * @return the path from root, not null.
     *
     * @throws GeneratorException if the parent chain contains a closed loop.
     */
    public static String getPathAsString(SourceElement sourceElement)
        throws GeneratorException
    {
        StringBuilder result = new StringBuilder();
        getParentPath(sourceElement, new HashSet<SourceElement>(), result);
        result.append(sourceElement.getName());
        return result.toString();
    }

    /**
     * Gets the path to the parent of a source element.
     * @param toProcess the source element for which parent the path should be
     *        calculated.
     * @param alreadyProcessed the elements which are already processed
     *        by this method.
     * @param result the path to the parent, ends with a slash if any parents
     *        are present.
     *
     * @throws GeneratorException if the parent is contained in alreadyProcessed
     *         or if the parent chain contains a closed loop.
     */
    private static void getParentPath(
            SourceElement toProcess,
            Set<SourceElement> alreadyProcessed,
            StringBuilder result)
        throws GeneratorException
    {
        SourceElement parent = toProcess.getParent();
        if (alreadyProcessed.contains(parent))
        {
            throw new GeneratorException(
                    "getParentPath(): invoked on a closed loop");
        }
        if (parent == null)
        {
            return;
        }
        result.insert(0, parent.getName() + "/");
        alreadyProcessed.add(parent);
        getParentPath(parent, alreadyProcessed, result);
    }
}
