/*
 * The contents of this file are subject to the terms of the Common Development and
 * Distribution License (the License). You may not use this file except in compliance with the
 * License.
 *
 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
 * specific language governing permission and limitations under the License.
 *
 * When distributing Covered Software, include this CDDL Header Notice in each file and include
 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
 * Header, with the fields enclosed by brackets [] replaced by your own identifying
 * information: "Portions copyright [year] [name of copyright owner]".
 *
 * Copyright 2013-2015 ForgeRock AS.
 */

package org.forgerock.json.resource;

import static java.util.Arrays.asList;
import static org.forgerock.http.util.Paths.*;

import java.util.Collection;
import java.util.Iterator;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.regex.Pattern;

/**
 * A relative path, or URL, to a resource. A resource path is an ordered list of
 * zero or more path elements in big-endian order. The string representation of
 * a resource path conforms to the URL path encoding rules defined in <a
 * href="http://tools.ietf.org/html/rfc3986#section-3.3">RFC 3986 section
 * 3.3</a>:
 *
 * <pre>
 * {@code
 * path          = path-abempty    ; begins with "/" or is empty
 *                 / ...
 *
 * path-abempty  = *( "/" segment )
 * segment       = *pchar
 * pchar         = unreserved / pct-encoded / sub-delims / ":" / "@"
 *
 * unreserved    = ALPHA / DIGIT / "-" / "." / "_" / "~"
 * pct-encoded   = "%" HEXDIG HEXDIG
 * sub-delims    = "!" / "$" / "&" / "'" / "(" / ")"
 *                 / "*" / "+" / "," / ";" / "="
 *
 * HEXDIG        =  DIGIT / "A" / "B" / "C" / "D" / "E" / "F"
 * ALPHA         =  %x41-5A / %x61-7A   ; A-Z / a-z
 * DIGIT         =  %x30-39             ; 0-9
 * }
 * </pre>
 *
 * The empty resource path having zero path elements may be obtained by calling
 * {@link #empty()}. Resource paths are case insensitive and empty path elements
 * are not allowed. In addition, resource paths will be automatically trimmed
 * such that any leading or trailing slashes are removed. In other words, all
 * resource paths will be considered to be "relative". At the moment the
 * relative path elements "." and ".." are not supported.
 * <p>
 * New resource paths can be created from their string representation using
 * {@link #resourcePath(String)}, or by deriving new resource paths from existing
 * values, e.g. using {@link #parent()} or {@link #child(Object)}.
 * <p>
 * Example:
 *
 * <pre>
 * ResourcePath base = ResourcePath.valueOf(&quot;commons/rest&quot;);
 * ResourcePath child = base.child(&quot;hello world&quot;);
 * child.toString(); // commons/rest/hello%20world
 *
 * ResourcePath user = base.child(&quot;users&quot;).child(123);
 * user.toString(); // commons/rest/users/123
 * </pre>
 */
public final class ResourcePath implements Comparable<ResourcePath>, Iterable<String> {
    private static final ResourcePath EMPTY = new ResourcePath();

    /**
     * Returns the empty resource path whose string representation is the empty
     * string and which has zero path elements.
     *
     * @return The empty resource path.
     */
    public static ResourcePath empty() {
        return EMPTY;
    }

    /**
     * Creates a new resource path using the provided path template and
     * unencoded path elements. This method first URL encodes each of the path
     * elements and then substitutes them into the template using
     * {@link String#format(String, Object...)}. Finally, the formatted string
     * is parsed as a resource path using {@link #resourcePath(String)}.
     * <p>
     * This method may be useful in cases where the structure of a resource path
     * is not known at compile time, for example, it may be obtained from a
     * configuration file. Example usage:
     *
     * <pre>
     * String template = "rest/users/%s"
     * ResourcePath path = ResourcePath.format(template, &quot;bjensen&quot;);
     * </pre>
     *
     * @param template
     *            The resource path template.
     * @param pathElements
     *            The path elements to be URL encoded and then substituted into
     *            the template.
     * @return The formatted template parsed as a resource path.
     * @throws IllegalArgumentException
     *             If the formatted template contains empty path elements.
     * @see org.forgerock.http.util.Paths#urlEncode(Object)
     */
    public static ResourcePath format(final String template, final Object... pathElements) {
        final String[] encodedPathElements = new String[pathElements.length];
        for (int i = 0; i < pathElements.length; i++) {
            encodedPathElements[i] = urlEncode(pathElements[i]);
        }
        return resourcePath(String.format(template, (Object[]) encodedPathElements));
    }

    /**
     * Compiled regular expression for splitting resource paths into path
     * elements.
     */
    private static final Pattern PATH_SPLITTER = Pattern.compile("/");

    /**
     * Parses the provided string representation of a resource path.
     *
     * @param path
     *            The URL-encoded resource path to be parsed.
     * @return The provided string representation of a resource path.
     * @throws IllegalArgumentException
     *             If the resource path contains empty path elements.
     * @see #toString()
     */
    public static ResourcePath resourcePath(final String path) {
        return valueOf(path);
    }

    /**
     * Parses the provided string representation of a resource path.
     *
     * @param path
     *            The URL-encoded resource path to be parsed.
     * @return The provided string representation of a resource path.
     * @throws IllegalArgumentException
     *             If the resource path contains empty path elements.
     * @see #toString()
     */
    public static ResourcePath valueOf(final String path) {
        if (path.isEmpty()) {
            // Fast-path.
            return EMPTY;
        }

        // Split on path separators and trim leading slash or trailing slash.
        final String[] elements = PATH_SPLITTER.split(path, -1);
        final int sz = elements.length;
        final int startIndex = elements[0].isEmpty() ? 1 : 0;
        final int endIndex = sz > 1 && elements[sz - 1].isEmpty() ? sz - 1 : sz;
        if (startIndex == endIndex) {
            return EMPTY;
        }

        // Normalize the path elements checking for empty elements.
        final StringBuilder trimmedPath = new StringBuilder(path.length());
        final StringBuilder normalizedPath = new StringBuilder(path.length());
        for (int i = startIndex; i < endIndex; i++) {
            final String element = elements[i];
            if (element.isEmpty()) {
                throw new IllegalArgumentException("Resource path '" + path
                        + "' contains empty path elements");
            }
            final String normalizedElement = normalizePathElement(element, true);
            if (i != startIndex) {
                trimmedPath.append('/');
                normalizedPath.append('/');
            }
            trimmedPath.append(element);
            normalizedPath.append(normalizedElement);
        }
        return new ResourcePath(trimmedPath.toString(), normalizedPath.toString(), endIndex - startIndex);
    }

    private static String normalizePathElement(final String element, final boolean needsDecoding) {
        if (needsDecoding) {
            return urlEncode(urlDecode(element).toLowerCase(Locale.ENGLISH));
        } else {
            return element.toLowerCase(Locale.ENGLISH);
        }
    }

    private final String path; // uri encoded
    private final String normalizedPath; // uri encoded
    private final int size;

    /**
     * Creates a new empty resource path whose string representation is the
     * empty string and which has zero path elements. This method is provided in
     * order to comply with the Java Collections Framework recommendations.
     * However, it is recommended that applications use {@link #empty()} in
     * order to avoid unnecessary memory allocation.
     */
    public ResourcePath() {
        this.path = this.normalizedPath = "";
        this.size = 0;
    }

    /**
     * Creates a new resource path having the provided path elements.
     *
     * @param pathElements
     *            The unencoded path elements.
     */
    public ResourcePath(final Collection<? extends Object> pathElements) {
        int i = 0;
        final StringBuilder pathBuilder = new StringBuilder();
        final StringBuilder normalizedPathBuilder = new StringBuilder();
        for (final Object element : pathElements) {
            final String s = element.toString();
            if (i > 0) {
                pathBuilder.append('/');
                normalizedPathBuilder.append('/');
            }
            final String encodedPathElement = urlEncode(s);
            pathBuilder.append(encodedPathElement);
            final String normalizedPathElement = normalizePathElement(s, false);
            normalizedPathBuilder.append(urlEncode(normalizedPathElement));
            i++;
        }
        this.path = pathBuilder.toString();
        this.normalizedPath = normalizedPathBuilder.toString();
        this.size = pathElements.size();
    }

    /**
     * Creates a new resource path having the provided path elements.
     *
     * @param pathElements
     *            The unencoded path elements.
     */
    public ResourcePath(final Object... pathElements) {
        this(asList(pathElements));
    }

    private ResourcePath(final String path, final String normalizedPath, final int size) {
        this.path = path;
        this.normalizedPath = normalizedPath;
        this.size = size;
    }

    /**
     * Creates a new resource path which is a child of this resource path. The
     * returned resource path will have the same path elements as this resource
     * path and, in addition, the provided path element.
     *
     * @param pathElement
     *            The unencoded child path element.
     * @return A new resource path which is a child of this resource path.
     */
    public ResourcePath child(final Object pathElement) {
        final String s = pathElement.toString();
        final String encodedPathElement = urlEncode(s);
        final String normalizedPathElement = normalizePathElement(s, false);
        final String normalizedEncodedPathElement = urlEncode(normalizedPathElement);
        if (isEmpty()) {
            return new ResourcePath(encodedPathElement, normalizedEncodedPathElement, 1);
        } else {
            final String newPath = path + "/" + encodedPathElement;
            final String newNormalizedPath = normalizedPath + "/" + normalizedEncodedPathElement;
            return new ResourcePath(newPath, newNormalizedPath, size + 1);
        }
    }

    /**
     * Compares this resource path with the provided resource path. Resource
     * paths are compared case sensitively and ancestors sort before
     * descendants.
     *
     * @param o
     *            {@inheritDoc}
     * @return {@inheritDoc}
     */
    @Override
    public int compareTo(final ResourcePath o) {
        return normalizedPath.compareTo(o.normalizedPath);
    }

    /**
     * Creates a new resource path which is a descendant of this resource path.
     * The returned resource path will have be formed of the concatenation of
     * this resource path and the provided resource path.
     *
     * @param suffix
     *            The resource path to be appended to this resource path.
     * @return A new resource path which is a descendant of this resource path.
     */
    public ResourcePath concat(final ResourcePath suffix) {
        if (isEmpty()) {
            return suffix;
        } else if (suffix.isEmpty()) {
            return this;
        } else {
            final String newPath = path + "/" + suffix.path;
            final String newNormalizedPath = normalizedPath + "/" + suffix.normalizedPath;
            return new ResourcePath(newPath, newNormalizedPath, size + suffix.size);
        }
    }

    /**
     * Creates a new resource path which is a descendant of this resource path.
     * The returned resource path will have be formed of the concatenation of
     * this resource path and the provided resource path.
     *
     * @param suffix
     *            The resource path to be appended to this resource path.
     * @return A new resource path which is a descendant of this resource path.
     * @throws IllegalArgumentException
     *             If the the suffix contains empty path elements.
     */
    public ResourcePath concat(final String suffix) {
        return concat(resourcePath(suffix));
    }

    /**
     * Returns {@code true} if {@code obj} is a resource path having the exact
     * same elements as this resource path.
     *
     * @param obj
     *            The object to be compared.
     * @return {@code true} if {@code obj} is a resource path having the exact
     *         same elements as this resource path.
     */
    @Override
    public boolean equals(final Object obj) {
        if (this == obj) {
            return true;
        } else if (obj instanceof ResourcePath) {
            return normalizedPath.equals(((ResourcePath) obj).normalizedPath);
        } else {
            return false;
        }
    }

    /**
     * Returns the path element at the specified position in this resource path.
     * The path element at position 0 is the top level element (closest to
     * root).
     *
     * @param index
     *            The index of the path element to be returned, where 0 is the
     *            top level element.
     * @return The path element at the specified position in this resource path.
     * @throws IndexOutOfBoundsException
     *             If the index is out of range (index &lt; 0 || index &gt;= size()).
     */
    public String get(final int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int startIndex = 0;
        int endIndex = nextElementEndIndex(path, 0);
        for (int i = 0; i < index; i++) {
            startIndex = endIndex + 1;
            endIndex = nextElementEndIndex(path, startIndex);
        }
        return urlDecode(path.substring(startIndex, endIndex));
    }

    /**
     * Returns a hash code for this resource path.
     *
     * @return A hash code for this resource path.
     */
    @Override
    public int hashCode() {
        return normalizedPath.hashCode();
    }

    /**
     * Returns a resource path which is a subsequence of the path elements
     * contained in this resource path beginning with the first element (0) and
     * ending with the element at position {@code endIndex-1}. The returned
     * resource path will therefore have the size {@code endIndex}. Calling this
     * method is equivalent to:
     *
     * <pre>
     * subSequence(0, endIndex);
     * </pre>
     *
     * @param endIndex
     *            The end index, exclusive.
     * @return A resource path which is a subsequence of the path elements
     *         contained in this resource path.
     * @throws IndexOutOfBoundsException
     *             If {@code endIndex} is bigger than {@code size()}.
     */
    public ResourcePath head(final int endIndex) {
        return subSequence(0, endIndex);
    }

    /**
     * Returns {@code true} if this resource path contains no path elements.
     *
     * @return {@code true} if this resource path contains no path elements.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns an iterator over the path elements in this resource path. The
     * returned iterator will not support the {@link Iterator#remove()} method
     * and will return path elements starting with index 0, then 1, then 2, etc.
     *
     * @return An iterator over the path elements in this resource path.
     */
    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            private int startIndex = 0;
            private int endIndex = nextElementEndIndex(path, 0);

            @Override
            public boolean hasNext() {
                return startIndex < path.length();
            }

            @Override
            public String next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                final String element = path.substring(startIndex, endIndex);
                startIndex = endIndex + 1;
                endIndex = nextElementEndIndex(path, startIndex);
                return urlDecode(element);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }

        };
    }

    /**
     * Returns the last path element in this resource path. Calling this method
     * is equivalent to:
     *
     * <pre>
     * resourcePath.get(resourcePath.size() - 1);
     * </pre>
     *
     * @return The last path element in this resource path.
     */
    public String leaf() {
        return get(size() - 1);
    }

    /**
     * Returns the resource path which is the immediate parent of this resource
     * path, or {@code null} if this resource path is empty.
     *
     * @return The resource path which is the immediate parent of this resource
     *         path, or {@code null} if this resource path is empty.
     */
    public ResourcePath parent() {
        switch (size()) {
        case 0:
            return null;
        case 1:
            return EMPTY;
        default:
            final String newPath = path.substring(0, path.lastIndexOf('/') /* safe */);
            final String newNormalizedPath =
                    normalizedPath.substring(0, normalizedPath.lastIndexOf('/') /* safe */);
            return new ResourcePath(newPath, newNormalizedPath, size - 1);
        }
    }

    /**
     * Returns the number of elements in this resource path, or 0 if it is
     * empty.
     *
     * @return The number of elements in this resource path, or 0 if it is
     *         empty.
     */
    public int size() {
        return size;
    }

    /**
     * Returns {@code true} if this resource path is equal to or begins with the
     * provided resource resource path.
     *
     * @param prefix
     *            The resource path prefix.
     * @return {@code true} if this resource path is equal to or begins with the
     *         provided resource resource path.
     */
    public boolean startsWith(final ResourcePath prefix) {
        if (size == prefix.size) {
            return equals(prefix);
        } else if (size < prefix.size) {
            return false;
        } else if (prefix.size == 0) {
            return true;
        } else {
            return normalizedPath.startsWith(prefix.normalizedPath)
                    && normalizedPath.charAt(prefix.normalizedPath.length()) == '/';
        }
    }

    /**
     * Returns {@code true} if this resource path is equal to or begins with the
     * provided resource resource path.
     *
     * @param prefix
     *            The resource path prefix.
     * @return {@code true} if this resource path is equal to or begins with the
     *         provided resource resource path.
     * @throws IllegalArgumentException
     *             If the the prefix contains empty path elements.
     */
    public boolean startsWith(final String prefix) {
        return startsWith(resourcePath(prefix));
    }

    /**
     * Returns a resource path which is a subsequence of the path elements
     * contained in this resource path beginning with the element at position
     * {@code beginIndex} and ending with the element at position
     * {@code endIndex-1}. The returned resource path will therefore have the
     * size {@code endIndex - beginIndex}.
     *
     * @param beginIndex
     *            The beginning index, inclusive.
     * @param endIndex
     *            The end index, exclusive.
     * @return A resource path which is a subsequence of the path elements
     *         contained in this resource path.
     * @throws IndexOutOfBoundsException
     *             If {@code beginIndex} is negative, or {@code endIndex} is
     *             bigger than {@code size()}, or if {@code beginIndex} is
     *             bigger than {@code endIndex}.
     */
    public ResourcePath subSequence(final int beginIndex, final int endIndex) {
        if (beginIndex < 0 || endIndex > size || beginIndex > endIndex) {
            throw new IndexOutOfBoundsException();
        }
        if (beginIndex == 0 && endIndex == size) {
            return this;
        }
        if (endIndex - beginIndex == 0) {
            return EMPTY;
        }
        final String subPath = subPath(path, beginIndex, endIndex);
        final String subNormalizedPath = subPath(normalizedPath, beginIndex, endIndex);
        return new ResourcePath(subPath, subNormalizedPath, endIndex - beginIndex);
    }

    /**
     * Returns a resource path which is a subsequence of the path elements
     * contained in this resource path beginning with the element at position
     * {@code beginIndex} and ending with the last element in this resource
     * path. The returned resource path will therefore have the size
     * {@code size() - beginIndex}. Calling this method is equivalent to:
     *
     * <pre>
     * subSequence(beginIndex, size());
     * </pre>
     *
     * @param beginIndex
     *            The beginning index, inclusive.
     * @return A resource path which is a subsequence of the path elements
     *         contained in this resource path.
     * @throws IndexOutOfBoundsException
     *             If {@code beginIndex} is negative, or if {@code beginIndex}
     *             is bigger than {@code size()}.
     */
    public ResourcePath tail(final int beginIndex) {
        return subSequence(beginIndex, size);
    }

    /**
     * Returns the URL path encoded string representation of this resource path.
     *
     * @return The URL path encoded string representation of this resource path.
     * @see #resourcePath(String)
     */
    @Override
    public String toString() {
        return path;
    }

    private int nextElementEndIndex(final String s, final int startIndex) {
        final int index = s.indexOf('/', startIndex);
        return index < 0 ? s.length() : index;
    }

    private String subPath(final String s, final int beginIndex, final int endIndex) {
        int startCharIndex = 0;
        int endCharIndex = nextElementEndIndex(s, 0);
        for (int i = 0; i < beginIndex; i++) {
            startCharIndex = endCharIndex + 1;
            endCharIndex = nextElementEndIndex(s, startCharIndex);
        }
        int tmpStartCharIndex;
        for (int i = beginIndex + 1; i < endIndex; i++) {
            tmpStartCharIndex = endCharIndex + 1;
            endCharIndex = nextElementEndIndex(s, tmpStartCharIndex);
        }
        return s.substring(startCharIndex, endCharIndex);
    }
}