//
   //  ========================================================================
   //  Copyright (c) 1995-2016 Mort Bay Consulting Pty. Ltd.
   //  ------------------------------------------------------------------------
   //  All rights reserved. This program and the accompanying materials
   //  are made available under the terms of the Eclipse Public License v1.0
   //  and Apache License v2.0 which accompanies this distribution.
   //
   //      The Eclipse Public License is available at
  //      http://www.eclipse.org/legal/epl-v10.html
  //
  //      The Apache License v2.0 is available at
  //      http://www.opensource.org/licenses/apache2.0.php
  //
  //  You may elect to redistribute this code under either of these licenses.
  //  ========================================================================
  //
  
  package org.eclipse.jetty.http;
  
  import java.util.AbstractSet;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.StringTokenizer;
  
  import org.eclipse.jetty.util.ArrayTernaryTrie;
  import org.eclipse.jetty.util.IncludeExclude;
  import org.eclipse.jetty.util.Predicate;
  import org.eclipse.jetty.util.Trie;
  import org.eclipse.jetty.util.URIUtil;
  
  /* ------------------------------------------------------------ */
  /** URI path map to Object.
   * This mapping implements the path specification recommended
   * in the 2.2 Servlet API.
   *
   * Path specifications can be of the following forms:<PRE>
   * /foo/bar           - an exact path specification.
   * /foo/*             - a prefix path specification (must end '/*').
   * *.ext              - a suffix path specification.
   * /                  - the default path specification.
   * ""                 - the / path specification
   * </PRE>
   * Matching is performed in the following order <NL>
   * <LI>Exact match.
   * <LI>Longest prefix match.
   * <LI>Longest suffix match.
   * <LI>default.
   * </NL>
   * Multiple path specifications can be mapped by providing a list of
   * specifications. By default this class uses characters ":," as path
   * separators, unless configured differently by calling the static
   * method @see PathMap#setPathSpecSeparators(String)
   * <P>
   * Special characters within paths such as '?� and ';' are not treated specially
   * as it is assumed they would have been either encoded in the original URL or
   * stripped from the path.
   * <P>
   * This class is not synchronized.  If concurrent modifications are
   * possible then it should be synchronized at a higher level.
   *
   *
   */
  public class PathMap<O> extends HashMap<String,O>
  {
      /* ------------------------------------------------------------ */
      private static String __pathSpecSeparators = ":,";
  
      /* ------------------------------------------------------------ */
      /** Set the path spec separator.
       * Multiple path specification may be included in a single string
       * if they are separated by the characters set in this string.
       * By default this class uses ":," characters as path separators.
       * @param s separators
       */
      public static void setPathSpecSeparators(String s)
      {
          __pathSpecSeparators=s;
      }
  
      /* --------------------------------------------------------------- */
      Trie<MappedEntry<O>> _prefixMap=new ArrayTernaryTrie<>(false);
      Trie<MappedEntry<O>> _suffixMap=new ArrayTernaryTrie<>(false);
      final Map<String,MappedEntry<O>> _exactMap=new HashMap<>();
  
      List<MappedEntry<O>> _defaultSingletonList=null;
      MappedEntry<O> _prefixDefault=null;
      MappedEntry<O> _default=null;
      boolean _nodefault=false;
  
      /* --------------------------------------------------------------- */
      public PathMap()
      {
          this(11);
      }
 
     /* --------------------------------------------------------------- */
     public PathMap(boolean noDefault)
     {
         this(11, noDefault);
     }
 
     /* --------------------------------------------------------------- */
     public PathMap(int capacity)
     {
         this(capacity, false);
     }
 
     /* --------------------------------------------------------------- */
     private PathMap(int capacity, boolean noDefault)
     {
         super(capacity);
         _nodefault=noDefault;
     }
 
     /* --------------------------------------------------------------- */
     /** Construct from dictionary PathMap.
      */
     public PathMap(Map<String, ? extends O> m)
     {
         putAll(m);
     }
 
     /* --------------------------------------------------------------- */
     /** Add a single path match to the PathMap.
      * @param pathSpec The path specification, or comma separated list of
      * path specifications.
      * @param object The object the path maps to
      */
     @Override
     public O put(String pathSpec, O object)
     {
         if ("".equals(pathSpec.trim()))
         {
             MappedEntry<O> entry = new MappedEntry<>("",object);
             entry.setMapped("");
             _exactMap.put("", entry);
             return super.put("", object);
         }
 
         StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators);
         O old =null;
 
         while (tok.hasMoreTokens())
         {
             String spec=tok.nextToken();
 
             if (!spec.startsWith("/") && !spec.startsWith("*."))
                 throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'");
 
             old = super.put(spec,object);
 
             // Make entry that was just created.
             MappedEntry<O> entry = new MappedEntry<>(spec,object);
 
             if (entry.getKey().equals(spec))
             {
                 if (spec.equals("/*"))
                     _prefixDefault=entry;
                 else if (spec.endsWith("/*"))
                 {
                     String mapped=spec.substring(0,spec.length()-2);
                     entry.setMapped(mapped);
                     while (!_prefixMap.put(mapped,entry))
                         _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_prefixMap,1.5);
                 }
                 else if (spec.startsWith("*."))
                 {
                     String suffix=spec.substring(2);
                     while(!_suffixMap.put(suffix,entry))
                         _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5);
                 }
                 else if (spec.equals(URIUtil.SLASH))
                 {
                     if (_nodefault)
                         _exactMap.put(spec,entry);
                     else
                     {
                         _default=entry;
                         _defaultSingletonList=Collections.singletonList(_default);
                     }
                 }
                 else
                 {
                     entry.setMapped(spec);
                     _exactMap.put(spec,entry);
                 }
             }
         }
 
         return old;
     }
 
     /* ------------------------------------------------------------ */
     /** Get object matched by the path.
      * @param path the path.
      * @return Best matched object or null.
      */
     public O match(String path)
     {
         MappedEntry<O> entry = getMatch(path);
         if (entry!=null)
             return entry.getValue();
         return null;
     }
 
 
     /* --------------------------------------------------------------- */
     /** Get the entry mapped by the best specification.
      * @param path the path.
      * @return Map.Entry of the best matched  or null.
      */
     public MappedEntry<O> getMatch(String path)
     {
         if (path==null)
             return null;
 
         int l=path.length();
 
         MappedEntry<O> entry=null;
 
         //special case
         if (l == 1 && path.charAt(0)=='/')
         {
             entry = _exactMap.get("");
             if (entry != null)
                 return entry;
         }
 
         // try exact match
         entry=_exactMap.get(path);
         if (entry!=null)
             return entry;
 
         // prefix search
         int i=l;
         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
         while(i>=0)
         {
             entry=prefix_map.getBest(path,0,i);
             if (entry==null)
                 break;
             String key = entry.getKey();
             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
                 return entry;
             i=key.length()-3;
         }
 
         // Prefix Default
         if (_prefixDefault!=null)
             return _prefixDefault;
 
         // Extension search
         i=0;
         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
         while ((i=path.indexOf('.',i+1))>0)
         {
             entry=suffix_map.get(path,i+1,l-i-1);
             if (entry!=null)
                 return entry;
         }
 
         // Default
         return _default;
     }
 
     /* --------------------------------------------------------------- */
     /** Get all entries matched by the path.
      * Best match first.
      * @param path Path to match
      * @return List of Map.Entry instances key=pathSpec
      */
     public List<? extends Map.Entry<String,O>> getMatches(String path)
     {
         MappedEntry<O> entry;
         List<MappedEntry<O>> entries=new ArrayList<>();
 
         if (path==null)
             return entries;
         if (path.length()==0)
             return _defaultSingletonList;
 
         // try exact match
         entry=_exactMap.get(path);
         if (entry!=null)
             entries.add(entry);
 
         // prefix search
         int l=path.length();
         int i=l;
         final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
         while(i>=0)
         {
             entry=prefix_map.getBest(path,0,i);
             if (entry==null)
                 break;
             String key = entry.getKey();
             if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
                 entries.add(entry);
 
             i=key.length()-3;
         }
 
         // Prefix Default
         if (_prefixDefault!=null)
             entries.add(_prefixDefault);
 
         // Extension search
         i=0;
         final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
         while ((i=path.indexOf('.',i+1))>0)
         {
             entry=suffix_map.get(path,i+1,l-i-1);
             if (entry!=null)
                 entries.add(entry);
         }
 
         // root match
         if ("/".equals(path))
         {
             entry=_exactMap.get("");
             if (entry!=null)
                 entries.add(entry);
         }
             
         // Default
         if (_default!=null)
             entries.add(_default);
 
         return entries;
     }
 
 
     /* --------------------------------------------------------------- */
     /** Return whether the path matches any entries in the PathMap,
      * excluding the default entry
      * @param path Path to match
      * @return Whether the PathMap contains any entries that match this
      */
     public boolean containsMatch(String path)
     {
         MappedEntry<?> match = getMatch(path);
         return match!=null && !match.equals(_default);
     }
 
     /* --------------------------------------------------------------- */
     @Override
     public O remove(Object pathSpec)
     {
         if (pathSpec!=null)
         {
             String spec=(String) pathSpec;
             if (spec.equals("/*"))
                 _prefixDefault=null;
             else if (spec.endsWith("/*"))
                 _prefixMap.remove(spec.substring(0,spec.length()-2));
             else if (spec.startsWith("*."))
                 _suffixMap.remove(spec.substring(2));
             else if (spec.equals(URIUtil.SLASH))
             {
                 _default=null;
                 _defaultSingletonList=null;
             }
             else
                 _exactMap.remove(spec);
         }
         return super.remove(pathSpec);
     }
 
     /* --------------------------------------------------------------- */
     @Override
     public void clear()
     {
         _exactMap.clear();
         _prefixMap=new ArrayTernaryTrie<>(false);
         _suffixMap=new ArrayTernaryTrie<>(false);
         _default=null;
         _defaultSingletonList=null;
         _prefixDefault=null;
         super.clear();
     }
 
     /* --------------------------------------------------------------- */
     /**
      * @return true if match.
      */
     public static boolean match(String pathSpec, String path)
         throws IllegalArgumentException
     {
         return match(pathSpec, path, false);
     }
 
     /* --------------------------------------------------------------- */
     /**
      * @return true if match.
      */
     public static boolean match(String pathSpec, String path, boolean noDefault)
         throws IllegalArgumentException
     {
         if (pathSpec.length()==0)
             return "/".equals(path);
             
         char c = pathSpec.charAt(0);
         if (c=='/')
         {
             if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path))
                 return true;
 
             if(isPathWildcardMatch(pathSpec, path))
                 return true;
         }
         else if (c=='*')
             return path.regionMatches(path.length()-pathSpec.length()+1,
                     pathSpec,1,pathSpec.length()-1);
         return false;
     }
 
     /* --------------------------------------------------------------- */
     private static boolean isPathWildcardMatch(String pathSpec, String path)
     {
         // For a spec of "/foo/*" match "/foo" , "/foo/..." but not "/foobar"
         int cpl=pathSpec.length()-2;
         if (pathSpec.endsWith("/*") && path.regionMatches(0,pathSpec,0,cpl))
         {
             if (path.length()==cpl || '/'==path.charAt(cpl))
                 return true;
         }
         return false;
     }
 
 
     /* --------------------------------------------------------------- */
     /** Return the portion of a path that matches a path spec.
      * @return null if no match at all.
      */
     public static String pathMatch(String pathSpec, String path)
     {
         char c = pathSpec.charAt(0);
 
         if (c=='/')
         {
             if (pathSpec.length()==1)
                 return path;
 
             if (pathSpec.equals(path))
                 return path;
 
             if (isPathWildcardMatch(pathSpec, path))
                 return path.substring(0,pathSpec.length()-2);
         }
         else if (c=='*')
         {
             if (path.regionMatches(path.length()-(pathSpec.length()-1),
                     pathSpec,1,pathSpec.length()-1))
                 return path;
         }
         return null;
     }
 
     /* --------------------------------------------------------------- */
     /** Return the portion of a path that is after a path spec.
      * @return The path info string
      */
     public static String pathInfo(String pathSpec, String path)
     {
         if ("".equals(pathSpec))
             return path; //servlet 3 spec sec 12.2 will be '/'
 
         char c = pathSpec.charAt(0);
 
         if (c=='/')
         {
             if (pathSpec.length()==1)
                 return null;
 
             boolean wildcard = isPathWildcardMatch(pathSpec, path);
 
             // handle the case where pathSpec uses a wildcard and path info is "/*"
             if (pathSpec.equals(path) && !wildcard)
                 return null;
 
             if (wildcard)
             {
                 if (path.length()==pathSpec.length()-2)
                     return null;
                 return path.substring(pathSpec.length()-2);
             }
         }
         return null;
     }
 
 
     /* ------------------------------------------------------------ */
     /** Relative path.
      * @param base The base the path is relative to.
      * @param pathSpec The spec of the path segment to ignore.
      * @param path the additional path
      * @return base plus path with pathspec removed
      */
     public static String relativePath(String base,
             String pathSpec,
             String path )
     {
         String info=pathInfo(pathSpec,path);
         if (info==null)
             info=path;
 
         if( info.startsWith( "./"))
             info = info.substring( 2);
         if( base.endsWith( URIUtil.SLASH))
             if( info.startsWith( URIUtil.SLASH))
                 path = base + info.substring(1);
             else
                 path = base + info;
         else
             if( info.startsWith( URIUtil.SLASH))
                 path = base + info;
             else
                 path = base + URIUtil.SLASH + info;
         return path;
     }
 
     /* ------------------------------------------------------------ */
     /* ------------------------------------------------------------ */
     /* ------------------------------------------------------------ */
     public static class MappedEntry<O> implements Map.Entry<String,O>
     {
         private final String key;
         private final O value;
         private String mapped;
 
         MappedEntry(String key, O value)
         {
             this.key=key;
             this.value=value;
         }
 
         @Override
         public String getKey()
         {
             return key;
         }
 
         @Override
         public O getValue()
         {
             return value;
         }
 
         @Override
         public O setValue(O o)
         {
             throw new UnsupportedOperationException();
         }
 
         @Override
         public String toString()
         {
             return key+"="+value;
         }
 
         public String getMapped()
         {
             return mapped;
         }
 
         void setMapped(String mapped)
         {
             this.mapped = mapped;
         }
     }
     
     public static class PathSet extends AbstractSet<String> implements Predicate<String>
     {
         private final PathMap<Boolean> _map = new PathMap<>();
         
         @Override
         public Iterator<String> iterator()
         {
             return _map.keySet().iterator();
         }
 
         @Override
         public int size()
         {
             return _map.size();
         }
         
         @Override
         public boolean add(String item)
         {
             return _map.put(item,Boolean.TRUE)==null;
         }
         
         @Override
         public boolean remove(Object item)
         {
             return _map.remove(item)!=null;
         }
 
         @Override
         public boolean contains(Object o) 
         { 
             return _map.containsKey(o); 
         }
         
         @Override
         public boolean test(String s)
         {
             return _map.containsMatch(s);
         }
         
         public boolean containsMatch(String s) 
         { 
             return _map.containsMatch(s); 
         }
         public boolean matches(String item)
         {
             return _map.containsMatch(item);
         }
     }
 }