[Unicode]   Common Locale Data Repository : Bug Tracking Home | Site Map | Search
 

Changeset 9530


Ignore:
Timestamp:
12/03/13 10:57:04 (5 years ago)
Author:
jali01
Message:

cldrbug 6838: store regex's in a tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/tools/java/org/unicode/cldr/util/RegexLookup.java

    r9490 r9530  
    33import java.util.ArrayList; 
    44import java.util.Collections; 
     5import java.util.Comparator; 
    56import java.util.Iterator; 
    67import java.util.LinkedHashMap; 
    78import java.util.List; 
    89import java.util.Map; 
     10import java.util.Map.Entry; 
    911import java.util.Set; 
     12import java.util.TreeSet; 
    1013import java.util.regex.Matcher; 
    1114import java.util.regex.Pattern; 
     
    1619import org.unicode.cldr.util.RegexLookup.Finder; 
    1720 
    18 import com.ibm.icu.impl.Row; 
    19 import com.ibm.icu.impl.Row.R2; 
    2021import com.ibm.icu.text.Transform; 
    2122import com.ibm.icu.util.Output; 
     
    3031    private VariableReplacer variables = new VariableReplacer(); 
    3132    private static final boolean DEBUG = true; 
    32     private final Map<Finder, T> entries = new LinkedHashMap<Finder, T>(); 
     33    public final RegexTree entries = new RegexTree(); 
    3334    private Transform<String, ? extends Finder> patternTransform = RegexFinderTransform; 
    3435    private Transform<String, ? extends T> valueTransform; 
     
    8182        @Override 
    8283        public boolean equals(Object obj) { 
    83             return toString().equals(obj.toString()); 
     84            if(obj == null) { 
     85                return false; 
     86            } else { 
     87                return toString().equals(obj.toString()); 
     88            } 
    8489        } 
    8590 
     
    9297        public int getFailPoint(String source) { 
    9398            return RegexUtilities.findMismatch(matcher, source); 
     99        } 
     100    } 
     101     
     102    public class RegexTree{ 
     103        private RTNode root; 
     104        private int _size; 
     105        private RTNodeRankComparator rankComparator = new RTNodeRankComparator(); 
     106         
     107        public RegexTree(){ 
     108            root = new RTNode("", null); 
     109            _size = 0; 
     110        } 
     111         
     112        public int size(){ 
     113            return _size; 
     114        } 
     115         
     116        public void put(Finder pattern, T value){ 
     117            root.put(new RTNode(pattern, value, _size)); 
     118            _size++; 
     119        } 
     120         
     121        public T get(Finder finder){ 
     122            return root.get(finder); 
     123        } 
     124         
     125        public List<T> getAll(String pattern, Object context, List<Finder> matcherList) { 
     126            List<RTNode> list = new ArrayList<RTNode>(); 
     127            List<T> retList = new ArrayList<T>(); 
     128             
     129            root.addToList(pattern, context, list); 
     130            Collections.sort(list, rankComparator); 
     131             
     132            for( RTNode n: list ) { 
     133                retList.add(n._val); 
     134                if(matcherList != null){ 
     135                    matcherList.add(n._finder); 
     136                } 
     137            } 
     138             
     139            return retList; 
     140        } 
     141         
     142        public T get(String pattern, Object context, Output<String[]> arguments, Output<Finder> matcherFound) { 
     143            List<Finder> matcherList = new ArrayList<Finder>(); 
     144            List<T> matches = getAll(pattern, context, matcherList);  //need to get whole list because we want value that was entered first 
     145            if (arguments != null) { 
     146                arguments.value = (matcherList.size() > 0) ? matcherList.get(0).getInfo() : null; 
     147            } 
     148            if(matcherFound != null) { 
     149                matcherFound.value = (matcherList.size() > 0) ? matcherList.get(0) : null; 
     150            } 
     151            return (matches.size() > 0) ? matches.get(0) : null; 
     152        } 
     153         
     154        public Set<Entry<Finder,T>> entrySet(){ 
     155            LinkedHashMap<Finder, T> ret = new LinkedHashMap<Finder, T>(); 
     156            TreeSet<RTNode> s = new TreeSet<RTNode>(rankComparator); 
     157            root.addToEntrySet(s); 
     158             
     159            for( RTNode n : s ){ 
     160                ret.put(n._finder, n._val); 
     161            } 
     162             
     163            return ret.entrySet(); 
     164        } 
     165         
     166        public class RTNode{ 
     167            Finder _finder; 
     168            T _val; 
     169            List<RTNode> _children = new ArrayList<RTNode>(); 
     170            int _rank;      //rank -1 means the node was not inserted, but only used for structural purposes 
     171             
     172            //constructor for regular nodes with a Finder 
     173            public RTNode(Finder finder, T val, int rank){ 
     174                _finder = finder; 
     175                _val = val; 
     176                _rank = rank; 
     177            } 
     178             
     179            //constructors for nodes without a Finder 
     180            public RTNode(String key, T val){ 
     181                _finder = new RegexFinder(key); 
     182                _val = val; 
     183                _rank = -1; 
     184            } 
     185             
     186            public void put(RTNode node){ 
     187                if(_children.size() == 0){ 
     188                    _children.add(node); 
     189                } else { 
     190                    String maxSimilarChars = "";  //most similar characters up to the last similar directory 
     191                    int insertIndex = 0; 
     192                    for(int i = 0; i < _children.size(); i++){ 
     193                        RTNode child = _children.get(i); 
     194                        String childFinderPattern = child._finder.toString(); 
     195                        if( childFinderPattern.length() > 0 && childFinderPattern.charAt(childFinderPattern.length()-1) == '$'){ 
     196                            childFinderPattern = childFinderPattern.substring(0, childFinderPattern.length() - 1);  //takes into account the added "$" 
     197                        } 
     198                        else if( child._rank == -1 ){ 
     199                            childFinderPattern = childFinderPattern.substring(0, childFinderPattern.length() - 2);  //takes into account the added ".*" 
     200                        } 
     201                         
     202                        //check if child has the same Finder as node to insert, then replace it 
     203                        if(node._finder.equals(child._finder)){ 
     204                            child._finder = node._finder; 
     205                            child._val = node._val; 
     206                            if(child._rank == -1) { 
     207                                child._rank = node._rank; 
     208                            } else { 
     209                                _size--; 
     210                            } 
     211                            return; 
     212                        } 
     213                         
     214                        //check if child is the parent of node 
     215                        if(child._rank == -1 && node._finder.toString().startsWith(childFinderPattern)){ 
     216                            child.put(node); 
     217                            return; 
     218                        } 
     219                         
     220                        //if not parent then check if candidate for most similar RTNode 
     221                        String gcp = greatestCommonPrefix(childFinderPattern, node._finder.toString()); 
     222                        gcp = removeExtraChars(gcp); 
     223                        if(gcp.length() > maxSimilarChars.length()){ 
     224                            maxSimilarChars = gcp; 
     225                            insertIndex = i; 
     226                        } 
     227                    } 
     228                     
     229                    String finderPattern = this._finder.toString(); 
     230                    if( finderPattern.length() > 0 && finderPattern.charAt(finderPattern.length()-1) == '$'){ 
     231                        finderPattern = finderPattern.substring(0, finderPattern.length() - 1);  //takes into account the added "$" 
     232                    } 
     233                    else if( !(finderPattern.equals("")) && this._rank == -1 ){ 
     234                        finderPattern = finderPattern.substring(0, finderPattern.length() - 2);  //takes into account the added ".*" 
     235                    } 
     236                     
     237                    if((maxSimilarChars).equals(finderPattern)){  //add under this if no similar children 
     238                        _children.add(node); 
     239                    } else { 
     240                        //create the common parent of the chosen candidate above and node, then add to the insert index 
     241                        RTNode newParent = new RTNode(maxSimilarChars + ".*", null); 
     242                        newParent._children.add(this._children.get(insertIndex)); 
     243                        newParent._children.add(node); 
     244                        this._children.remove(insertIndex); 
     245                        this._children.add(insertIndex, newParent); 
     246                    } 
     247                } 
     248            } 
     249             
     250            //takes a string in a directory regex form and removes all characters up to the last full directory 
     251            private String removeExtraChars( String input ){ 
     252                String ret = input.substring(0, Math.max(0, input.lastIndexOf('/')) ); 
     253                while( (ret.lastIndexOf('(') != -1 && ret.lastIndexOf('(') > ret.lastIndexOf(')')) || 
     254                       (ret.lastIndexOf('[') != -1 && ret.lastIndexOf('[') > ret.lastIndexOf(']')) || 
     255                       (ret.lastIndexOf('{') != -1 && ret.lastIndexOf('{') > ret.lastIndexOf('}'))) { 
     256                    ret = ret.substring(0, Math.max(0, ret.lastIndexOf('/')) ); 
     257                } 
     258                return ret; 
     259            } 
     260             
     261            //traverse tree to get value 
     262            public T get(Finder finder){ 
     263                T ret = null;  //return value 
     264                 
     265                if(_children.size() == 0){ 
     266                    return null; 
     267                } else { 
     268                    for(RTNode child : _children){ 
     269                         
     270                        //check if child is the node 
     271                        if(child._rank != -1 && finder.equals(child._finder)){ 
     272                            return child._val; 
     273                        } 
     274                         
     275                        String childFinderPattern = child._finder.toString(); 
     276                         
     277                        if( childFinderPattern.length() > 0 && childFinderPattern.charAt(childFinderPattern.length()-1) == '$'){ 
     278                            childFinderPattern = childFinderPattern.substring(0, childFinderPattern.length() - 1);  //takes into account the added "$" 
     279                        } 
     280                        else if( child._rank == -1 ){ 
     281                            childFinderPattern = childFinderPattern.substring(0, childFinderPattern.length() - 2);  //takes into account the added ".*" 
     282                        } 
     283                         
     284                        //check if child is the parent of node 
     285                        if(finder.toString().startsWith(childFinderPattern)){ 
     286                            ret = child.get(finder); 
     287                            if(ret != null){ 
     288                                break; 
     289                            } 
     290                        } 
     291                    } 
     292                     
     293                    return ret; 
     294                } 
     295            } 
     296             
     297            //traverse tree to get an entry set 
     298            public void addToEntrySet(TreeSet<RTNode> s){ 
     299                if(_children.size() == 0){ 
     300                    return; 
     301                } else { 
     302                    for(RTNode child : _children){ 
     303                        if( child._rank != -1 ) { 
     304                            s.add(child); 
     305                        } 
     306                        child.addToEntrySet(s); 
     307                    } 
     308                } 
     309            } 
     310             
     311            //traverse tree to get list of all values who's key matcher matches pattern 
     312            public void addToList( String pattern, Object context, List<RTNode> list ){ 
     313                if(_children.size() == 0){ 
     314                    return; 
     315                } else { 
     316                    for(RTNode child : _children){ 
     317                         
     318                        boolean found; 
     319                        synchronized(child._finder){ 
     320                            found = child._finder.find(pattern, context); 
     321                        } 
     322                         
     323                        //check if child matches pattern 
     324                        if(found){ 
     325                            if(child._rank != -1){ 
     326                                list.add(child); 
     327                            } 
     328                             
     329                            //check if child is the parent of node then enter that node 
     330                            child.addToList(pattern, context, list); 
     331                        } 
     332                    } 
     333                } 
     334            } 
     335             
     336            public String toString() { 
     337                return this._finder.toString(); 
     338            } 
     339             
     340            //greatest common prefix between two strings 
     341            public String greatestCommonPrefix(String a, String b) { 
     342                int minLength = Math.min(a.length(), b.length()); 
     343                for (int i = 0; i < minLength; i++) { 
     344                    if (a.charAt(i) != b.charAt(i)) { 
     345                        return a.substring(0, i); 
     346                    } 
     347                } 
     348                return a.substring(0, minLength); 
     349            } 
     350        } 
     351         
     352        class RTNodeRankComparator implements Comparator<RTNode>{ 
     353            public int compare(RTNode a, RTNode b) { 
     354                if(a == b){ 
     355                    return 0; 
     356                } else if(a == null) { 
     357                    return -1; 
     358                } else if(b == null) { 
     359                    return 1; 
     360                } else if(a._rank == b._rank) { 
     361                    return 0; 
     362                } else if(a._rank > b._rank) { 
     363                    return 1; 
     364                } else { 
     365                    return -1; 
     366                } 
     367            } 
    94368        } 
    95369    } 
     
    156430    public T get(String source, Object context, Output<String[]> arguments, 
    157431        Output<Finder> matcherFound, List<String> failures) { 
    158         for (Map.Entry<Finder, T> entry : entries.entrySet()) { 
    159             Finder matcher = entry.getKey(); 
    160             synchronized (matcher) { 
    161                 if (matcher.find(source, context)) { 
    162                     if (arguments != null) { 
    163                         arguments.value = matcher.getInfo(); 
    164                     } 
    165                     if (matcherFound != null) { 
    166                         matcherFound.value = matcher; 
    167                     } 
    168                     return entry.getValue(); 
    169                 } else if (failures != null) { 
     432         
     433        T ret = entries.get(source, context, arguments, matcherFound); 
     434        if( ret != null ){ 
     435            return ret; 
     436        } 
     437         
     438        if( failures != null ) { 
     439            for (Map.Entry<Finder, T> entry : entries.entrySet()) { 
     440                Finder matcher = entry.getKey(); 
     441                synchronized (matcher) { 
    170442                    int failPoint = matcher.getFailPoint(source); 
    171443                    String show = source.substring(0, failPoint) + "☹" + source.substring(failPoint) + "\t" 
     
    175447            } 
    176448        } 
     449         
    177450        // not really necessary, but makes debugging easier. 
    178451        if (arguments != null) { 
     
    194467     * @return 
    195468     */ 
    196     public List<T> getAll(String source, Object context, List<Finder> matcherList, List<String> failures) { 
    197         List<T> matches = new ArrayList<T>(); 
    198         for (Map.Entry<Finder, T> entry : entries.entrySet()) { 
    199             Finder matcher = entry.getKey(); 
    200             if (matcher.find(source, context)) { 
    201                 if (matcherList != null) { 
    202                     matcherList.add(matcher); 
    203                 } 
    204                 matches.add(entry.getValue()); 
    205             } else if (failures != null) { 
    206                 int failPoint = matcher.getFailPoint(source); 
    207                 String show = source.substring(0, failPoint) + "☹" + source.substring(failPoint) + "\t" 
    208                     + matcher.toString(); 
    209                 failures.add(show); 
    210             } 
    211         } 
    212         return matches; 
     469    public List<T> getAll(String source, Object context, List<Finder> matcherList, List<String> failures) {     
     470        List<T> matches = entries.getAll(source, context, matcherList); 
     471        if( matches != null ){ 
     472            return matches; 
     473        } 
     474         
     475        if( failures != null ) { 
     476            for (Map.Entry<Finder, T> entry : entries.entrySet()) { 
     477                Finder matcher = entry.getKey(); 
     478                synchronized (matcher) { 
     479                    int failPoint = matcher.getFailPoint(source); 
     480                    String show = source.substring(0, failPoint) + "☹" + source.substring(failPoint) + "\t" 
     481                        + matcher.toString(); 
     482                    failures.add(show); 
     483                } 
     484            } 
     485        } 
     486        return null; 
    213487    } 
    214488 
     
    344618            throw new NullPointerException("null disallowed, unless allowNull(true) is called."); 
    345619        } 
     620         
    346621        T old = entries.get(pattern); 
    347622        if (old == null) { 
Note: See TracChangeset for help on using the changeset viewer.