/*
 * JBoss, Home of Professional Open Source.
 * Copyright 2014 Red Hat, Inc., and individual contributors
 * as indicated by the @author tags.
 *
 * Licensed 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.
 */

package io.undertow.util;

import io.undertow.UndertowMessages;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

Utility class that provides fast path matching of path templates. Templates are stored in a map based on the stem of the template,
and matches longest stem first.

TODO: we can probably do this faster using a trie type structure, but I think the current impl should perform ok most of the time
Author:
Stuart Douglas/**
 * Utility class that provides fast path matching of path templates. Templates are stored in a map based on the stem of the template,
 * and matches longest stem first.
 * <p>
 * TODO: we can probably do this faster using a trie type structure, but I think the current impl should perform ok most of the time
 *
 * @author Stuart Douglas
 */
public class PathTemplateMatcher<T> {

    
Map of path template stem to the path templates that share the same base.
/**
     * Map of path template stem to the path templates that share the same base.
     */
    private Map<String, Set<PathTemplateHolder>> pathTemplateMap = new CopyOnWriteMap<>();

    
lengths of all registered paths
/**
     * lengths of all registered paths
     */
    private volatile int[] lengths = {};

    public PathMatchResult<T> match(final String path) {
        final Map<String, String> params = new HashMap<>();
        int length = path.length();
        final int[] lengths = this.lengths;
        for (int i = 0; i < lengths.length; ++i) {
            int pathLength = lengths[i];
            if (pathLength == length) {
                Set<PathTemplateHolder> entry = pathTemplateMap.get(path);
                if (entry != null) {
                    PathMatchResult<T> res = handleStemMatch(entry, path, params);
                    if (res != null) {
                        return res;
                    }
                }
            } else if (pathLength < length) {
                String part = path.substring(0, pathLength);
                Set<PathTemplateHolder> entry = pathTemplateMap.get(part);
                if (entry != null) {
                    PathMatchResult<T> res = handleStemMatch(entry, path, params);
                    if (res != null) {
                        return res;
                    }
                }
            }
        }
        return null;
    }

    private PathMatchResult<T> handleStemMatch(Set<PathTemplateHolder> entry, final String path, final Map<String, String> params) {
        for (PathTemplateHolder val : entry) {
            if (val.template.matches(path, params)) {
                return new PathMatchResult<>(params, val.template.getTemplateString(), val.value);
            } else {
                params.clear();
            }
        }
        return null;
    }


    public synchronized PathTemplateMatcher<T> add(final PathTemplate template, final T value) {
        Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(template));
        Set<PathTemplateHolder> newValues;
        if (values == null) {
            newValues = new TreeSet<>();
        } else {
            newValues = new TreeSet<>(values);
        }
        PathTemplateHolder holder = new PathTemplateHolder(value, template);
        if (newValues.contains(holder)) {
            PathTemplate equivalent = null;
            for (PathTemplateHolder item : newValues) {
                if (item.compareTo(holder) == 0) {
                    equivalent = item.template;
                    break;
                }
            }
            throw UndertowMessages.MESSAGES.matcherAlreadyContainsTemplate(template.getTemplateString(), equivalent.getTemplateString());
        }
        newValues.add(holder);
        pathTemplateMap.put(trimBase(template), newValues);
        buildLengths();
        return this;
    }

    private String trimBase(PathTemplate template) {
        String retval = template.getBase();

        if (template.getBase().endsWith("/") && !template.getParameterNames().isEmpty()) {
            return retval.substring(0, retval.length() - 1);
        }
        if (retval.endsWith("*")) {
            return retval.substring(0, retval.length() - 1);
        }
        return retval;
    }

    private void buildLengths() {
        final Set<Integer> lengths = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -o1.compareTo(o2);
            }
        });
        for (String p : pathTemplateMap.keySet()) {
            lengths.add(p.length());
        }

        int[] lengthArray = new int[lengths.size()];
        int pos = 0;
        for (int i : lengths) {
            lengthArray[pos++] = i; //-1 because the base paths end with a /
        }
        this.lengths = lengthArray;
    }

    public synchronized PathTemplateMatcher<T> add(final String pathTemplate, final T value) {
        final PathTemplate template = PathTemplate.create(pathTemplate);
        return add(template, value);
    }

    public synchronized PathTemplateMatcher<T> addAll(PathTemplateMatcher<T> pathTemplateMatcher) {
        for (Entry<String, Set<PathTemplateHolder>> entry : pathTemplateMatcher.getPathTemplateMap().entrySet()) {
            for (PathTemplateHolder pathTemplateHolder : entry.getValue()) {
                add(pathTemplateHolder.template, pathTemplateHolder.value);
            }
        }
        return this;
    }

    Map<String, Set<PathTemplateHolder>> getPathTemplateMap() {
        return pathTemplateMap;
    }

    public Set<PathTemplate> getPathTemplates() {
        Set<PathTemplate> templates = new HashSet<>();
        for (Set<PathTemplateHolder> holders : pathTemplateMap.values()) {
            for (PathTemplateHolder holder: holders) {
                templates.add(holder.template);
            }
        }
        return templates;
    }

    public synchronized PathTemplateMatcher<T> remove(final String pathTemplate) {
        final PathTemplate template = PathTemplate.create(pathTemplate);
        return remove(template);
    }

    private synchronized PathTemplateMatcher<T> remove(PathTemplate template) {
        Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(template));
        Set<PathTemplateHolder> newValues;
        if (values == null) {
            return this;
        } else {
            newValues = new TreeSet<>(values);
        }
        Iterator<PathTemplateHolder> it = newValues.iterator();
        while (it.hasNext()) {
            PathTemplateHolder next = it.next();
            if (next.template.getTemplateString().equals(template.getTemplateString())) {
                it.remove();
                break;
            }
        }
        if (newValues.size() == 0) {
            pathTemplateMap.remove(trimBase(template));
        } else {
            pathTemplateMap.put(trimBase(template), newValues);
        }
        buildLengths();
        return this;
    }


    public synchronized T get(String template) {
        PathTemplate pathTemplate = PathTemplate.create(template);
        Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(pathTemplate));
        if(values == null) {
            return null;
        }
        for (PathTemplateHolder next : values) {
            if (next.template.getTemplateString().equals(template)) {
                return next.value;
            }
        }
        return null;
    }

    public static class PathMatchResult<T> extends PathTemplateMatch {
        private final T value;

        public PathMatchResult(Map<String, String> parameters, String matchedTemplate, T value) {
            super(matchedTemplate, parameters);
            this.value = value;
        }

        public T getValue() {
            return value;
        }
    }

    private final class PathTemplateHolder implements Comparable<PathTemplateHolder> {
        final T value;
        final PathTemplate template;

        private PathTemplateHolder(T value, PathTemplate template) {
            this.value = value;
            this.template = template;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null) return false;
            if (!PathTemplateHolder.class.equals(o.getClass())) return false;

            PathTemplateHolder that = (PathTemplateHolder) o;
            return template.equals(that.template);
        }

        @Override
        public int hashCode() {
            return template.hashCode();
        }

        @Override
        public int compareTo(PathTemplateHolder o) {
            return template.compareTo(o.template);
        }
    }

}