content: /*
   * Resolver.java February 2001
   *
   * Copyright (C) 2001, Niall Gallagher <niallg@users.sf.net>
   *
   * 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 com.aliyun.odps.simpleframework.xml.util;
  
  import java.util.AbstractSet;
  import java.util.ArrayList;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.List;
  
  /**
   * This is used to store <code>Match</code> objects, which can then be
   * retrieved using a string by comparing that string to the pattern of
   * the <code>Match</code> objects. Patterns consist of characters
   * with either the '*' or '?' characters as wild characters. The '*'
   * character is completely wild meaning that is will match nothing or
   * a long sequence of characters. The '?' character matches a single
   * character.
   * <p>
   * If the '?' character immediately follows the '*' character then the
   * match is made as any sequence of characters up to the first match 
   * of the next character. For example "/*?/index.jsp" will match all 
   * files preceeded by only a single path. So "/pub/index.jsp" will
   * match, however "/pub/bin/index.jsp" will not, as it has two paths.
   * So, in effect the '*?' sequence will match anything or nothing up
   * to the first occurence of the next character in the pattern.
   * <p>
   * A design goal of the <code>Resolver</code> was to make it capable
   * of  high performance. In order to achieve a high performance the 
   * <code>Resolver</code> can cache the resolutions it makes so that if
   * the same text is given to the <code>Resolver.resolve</code> method 
   * a cached result can be retrived quickly which will decrease the 
   * length of time and work required to perform the match.
   * <p>
   * The semantics of the resolver are such that the last pattern added
   * with a wild string is the first one checked for a match. This means
   * that if a sequence of insertions like <code>add(x)</code> followed
   * by <code>add(y)</code> is made, then a <code>resolve(z)</code> will
   * result in a comparison to y first and then x, if z matches y then 
   * it is given as the result and if z does not match y and matches x 
   * then x is returned, remember if z matches both x and y then y will 
   * be the result due to the fact that is was the last pattern added.
   *
   * @author Niall Gallagher
   */
  public class Resolver<M extends Match> extends AbstractSet<M> {
  
     /**
      * Caches the text resolutions made to reduce the work required.
      */        
     protected final Cache cache;
  
     /**
      * Stores the matches added to the resolver in resolution order.
      */ 
     protected final Stack stack;
  
     /**
      * The default constructor will create a <code>Resolver</code>
      * without a large cache size. This is intended for use when 
      * the requests for <code>resolve</code> tend to use strings
      * that are reasonably similar. If the strings issued to this
      * instance are dramatically different then the cache tends 
      * to be an overhead rather than a bonus.
      */
     public Resolver(){
        this.stack = new Stack();
        this.cache = new Cache(); 
     }
  
     /**
      * This will search the patterns in this <code>Resolver</code> to
      * see if there is a pattern in it that matches the string given.
      * This will search the patterns from the last entered pattern to
      * the first entered. So that the last entered patterns are the
      * most searched patterns and will resolve it first if it matches.
      *
      * @param text this is the string that is to be matched by this
      *
      * @return this will return the first match within the resolver
      */
     public M resolve(String text){
        List<M> list = cache.get(text);
        
        if(list == null) {
           list = resolveAll(text);
        }
        if(list.isEmpty()) {
           return null;
        }
        return list.get(0);
     }
     
     /**
      * This will search the patterns in this <code>Resolver</code> to
      * see if there is a pattern in it that matches the string given.
      * This will search the patterns from the last entered pattern to
      * the first entered. So that the last entered patterns are the
      * most searched patterns and will resolve it first if it matches.
      *
      * @param text this is the string that is to be matched by this
      *
      * @return this will return all of the matches within the resolver
      */
     public List<M> resolveAll(String text){
        List<M> list = cache.get(text);
        
        if(list != null) {
           return list;
        }
        char[] array = text.toCharArray();
    
        if(array == null) {
           return null;
        }
        return resolveAll(text, array);
     }
     
     /**
      * This will search the patterns in this <code>Resolver</code> to
      * see if there is a pattern in it that matches the string given.
      * This will search the patterns from the last entered pattern to
      * the first entered. So that the last entered patterns are the
      * most searched patterns and will resolve it first if it matches.
      *
      * @param text this is the string that is to be matched by this
      * @param array this is the character array of the text string
      *
      * @return this will return all of the matches within the resolver
      */
     private List<M> resolveAll(String text, char[] array){
        List<M> list = new ArrayList<M>();
        
        for(M match : stack) {
           String wild = match.getPattern();
  
           if(match(array, wild.toCharArray())){
              cache.put(text, list);
              list.add(match);
           }
        }
        return list;
     }
  
     /**
      * This inserts the <code>Match</code> implementation into the set
      * so that it can be used for resolutions. The last added match is
      * the first resolved. Because this changes the state of the 
      * resolver this clears the cache as it may affect resolutions.
      *
      * @param match this is the match that is to be inserted to this
      *
      * @return returns true if the addition succeeded, always true
      */ 
     public boolean add(M match) {
        stack.push(match);
        return true;
     }
     
     /**
      * This returns an <code>Iterator</code> that iterates over the
      * matches in insertion order. So the first match added is the
      * first retrieved from the <code>Iterator</code>. This order is
      * used to ensure that resolver can be serialized properly.
      *
      * @return returns an iterator for the sequence of insertion
      */ 
     public Iterator<M> iterator() {
        return stack.sequence();
     }
  
     /**
      * This is used to remove the <code>Match</code> implementation
      * from the resolver. This clears the cache as the removal of
      * a match may affect the resoultions existing in the cache. The
      * <code>equals</code> method of the match must be implemented.
      *
      * @param match this is the match that is to be removed
      *
      * @return true of the removal of the match was successful
      */ 
     public boolean remove(M match) {
        cache.clear();
        return stack.remove(match);
     }
  
     /**
      * Returns the number of matches that have been inserted into 
      * the <code>Resolver</code>. Although this is a set, it does 
      * not mean that matches cannot used the same pattern string.
      *
      * @return this returns the number of matches within the set
      */ 
     public int size() {
        return stack.size();           
     }
     
     /**
      * This is used to clear all matches from the set. This ensures
      * that the resolver contains no matches and that the resolution 
      * cache is cleared. This is used to that the set can be reused
      * and have new pattern matches inserted into it for resolution.
      */ 
     public void clear() {
        cache.clear();      
        stack.clear();
     }
  
     /**
      * This acts as a driver to the <code>match</code> method so that
      * the offsets can be used as zeros for the start of matching for 
      * the <code>match(char[],int,char[],int)</code>. method. This is
      * also used as the initializing driver for the recursive method.
      *
      * @param text this is the buffer that is to be resolved
      * @param wild this is the pattern that will be used
      */
     private boolean match(char[] text, char[] wild){
        return match(text, 0, wild, 0);
     }
  
     /**
      * This will be used to check to see if a certain buffer matches
      * the pattern if it does then it returns <code>true</code>. This
      * is a recursive method that will attempt to match the buffers 
      * based on the wild characters '?' and '*'. If there is a match
      * then this returns <code>true</code>.
      *
      * @param text this is the buffer that is to be resolved
      * @param off this is the read offset for the text buffer
      * @param wild this is the pattern that will be used
      * @param pos this is the read offset for the wild buffer
      */
     private boolean match(char[] text, int off, char[] wild, int pos){
        while(pos < wild.length && off < text.length){ /* examine chars */
           if(wild[pos] == '*'){
              while(wild[pos] == '*'){ /* totally wild */
                 if(++pos >= wild.length) /* if finished */
                    return true;
              }
              if(wild[pos] == '?') { /* *? is special */
                 if(++pos >= wild.length)                    
                    return true;
              }
              for(; off < text.length; off++){ /* find next matching char */
                 if(text[off] == wild[pos] || wild[pos] == '?'){ /* match */
                    if(wild[pos - 1] != '?'){
                       if(match(text, off, wild, pos))
                          return true;
                    } else {
                       break;                          
                    }
                 }
              }
              if(text.length == off)
                 return false;
           }
           if(text[off++] != wild[pos++]){
              if(wild[pos-1] != '?')
                 return false; /* if not equal */
           }
        }
        if(wild.length == pos){ /* if wild is finished */
            return text.length == off; /* is text finished */
        }
        while(wild[pos] == '*'){ /* ends in all stars */
           if(++pos >= wild.length) /* if finished */
              return true;
        }
        return false;
     }
  
  
     /**
      * This is used to cache resolutions made so that the matches can
      * be acquired the next time without performing the resolution.
      * This is an LRU cache so regardless of the number of resolutions
      * made this will not result in a memory leak for the resolver.
      * 
      * @author Niall Gallagher
      */ 
     private class Cache extends LimitedCache<List<M>> {
  
        /**
         * Constructor for the <code>Cache</code> object. This is a
         * constructor that creates the linked hash map such that 
         * it will purge the entries that are oldest within the map.
         */ 
        public Cache() {      
           super(1024);              
        }
     }
  
     /**
      * This is used to store the <code>Match</code> implementations in
      * resolution order. Resolving the match objects is performed so
      * that the last inserted match object is the first used in the
      * resolution process. This gives priority to the last inserted.
      * 
      * @author Niall Gallagher
      */ 
     private class Stack extends LinkedList<M> {     
  
        /**
         * The <code>push</code> method is used to push the match to 
         * the top of the stack. This also ensures that the cache is
         * cleared so the semantics of the resolver are not affected.
         *
         * @param match this is the match to be inserted to the stack
         */            
        public void push(M match) {
           cache.clear();
           addFirst(match);                       
        }
  
        /**
         * The <code>purge</code> method is used to purge a match from
         * the provided position. This also ensures that the cache is
         * cleared so that the semantics of the resolver do not change.
         *
         * @param index the index of the match that is to be removed
         */ 
        public void purge(int index) {
           cache.clear(); 
           remove(index);         
        }
  
        /**
         * This is returned from the <code>Resolver.iterator</code> so
         * that matches can be iterated in insertion order. When a
         * match is removed from this iterator then it clears the cache
         * and removed the match from the <code>Stack</code> object.
         * 
         * @return returns an iterator to iterate in insertion order
         */ 
        public Iterator<M> sequence() {
           return new Sequence();              
        }
  
        /**
         * The is used to order the <code>Match</code> objects in the
         * insertion order. Iterating in insertion order allows the
         * resolver object to be serialized and deserialized to and
         * from an XML document without disruption resolution order.
         *
         * @author Niall Gallagher
         */
        private class Sequence implements Iterator<M> {
  
           /**
            * The cursor used to acquire objects from the stack.
            */               
           private int cursor;
  
           /**
            * Constructor for the <code>Sequence</code> object. This is
            * used to position the cursor at the end of the list so the
            * first inserted match is the first returned from this.
            */ 
           public Sequence() {
              this.cursor = size();                 
           }
  
           /**
            * This returns the <code>Match</code> object at the cursor
            * position. If the cursor has reached the start of the 
            * list then this returns null instead of the first match.
            * 
            * @return this returns the match from the cursor position
            */ 
           public M next() {
              if(hasNext()) {
                  return get(--cursor);
              }           
              return null;     
           }    
  
           /**
            * This is used to determine if the cursor has reached the
            * start of the list. When the cursor reaches the start of
            * the list then this method returns false.
            * 
            * @return this returns true if there are more matches left
            */ 
           public boolean hasNext() {
              return cursor > 0;
           }
  
           /**
            * Removes the match from the cursor position. This also
            * ensures that the cache is cleared so that resolutions
            * made before the removal do not affect the semantics.
            */ 
           public void remove() {                    
              purge(cursor);                
           }        
        }
     } 
  }
  