001    package org.openstreetmap.josm.tools;
002    
003    /*
004     * The Alphanum Algorithm is an improved sorting algorithm for strings
005     * containing numbers. Instead of sorting numbers in ASCII order like a standard
006     * sort, this algorithm sorts numbers in numeric order.
007     *
008     * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
009     *
010     *
011     * This library is free software; you can redistribute it and/or modify it under
012     * the terms of the GNU Lesser General Public License as published by the Free
013     * Software Foundation; either version 2.1 of the License, or any later version.
014     *
015     * This library is distributed in the hope that it will be useful, but WITHOUT
016     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
017     * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
018     * details.
019     *
020     * You should have received a copy of the GNU Lesser General Public License
021     * along with this library; if not, write to the Free Software Foundation, Inc.,
022     * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
023     *
024     */
025    import java.util.Comparator;
026    
027    /**
028     * The Alphanum Algorithm is an improved sorting algorithm for strings
029     * containing numbers: Instead of sorting numbers in ASCII order like a standard
030     * sort, this algorithm sorts numbers in numeric order.
031     *
032     * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
033     * 
034     * This is an updated version with enhancements made by Daniel Migowski, Andre
035     * Bogus, and David Koelle.
036     *
037     */
038    public class AlphanumComparator implements Comparator<String> {
039    
040        /**
041         * Length of string is passed in for improved efficiency (only need to
042         * calculate it once) *
043         */
044        private String getChunk(String s, int slength, int marker) {
045            StringBuilder chunk = new StringBuilder();
046            char c = s.charAt(marker);
047            chunk.append(c);
048            marker++;
049            if (Character.isDigit(c)) {
050                while (marker < slength) {
051                    c = s.charAt(marker);
052                    if (!Character.isDigit(c)) {
053                        break;
054                    }
055                    chunk.append(c);
056                    marker++;
057                }
058            } else {
059                while (marker < slength) {
060                    c = s.charAt(marker);
061                    if (Character.isDigit(c)) {
062                        break;
063                    }
064                    chunk.append(c);
065                    marker++;
066                }
067            }
068            return chunk.toString();
069        }
070    
071        @Override
072        public int compare(String s1, String s2) {
073            if (s1 == null && s2 == null) {
074                return 0;
075            } else if (s1 == null) {
076                return -1;
077            } else if (s2 == null) {
078                return 1;
079            }
080    
081            int thisMarker = 0;
082            int thatMarker = 0;
083            int s1Length = s1.length();
084            int s2Length = s2.length();
085    
086            while (thisMarker < s1Length && thatMarker < s2Length) {
087                String thisChunk = getChunk(s1, s1Length, thisMarker);
088                thisMarker += thisChunk.length();
089    
090                String thatChunk = getChunk(s2, s2Length, thatMarker);
091                thatMarker += thatChunk.length();
092    
093                // If both chunks contain numeric characters, sort them numerically
094                int result;
095                if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
096                    // Simple chunk comparison by length.
097                    int thisChunkLength = thisChunk.length();
098                    result = thisChunkLength - thatChunk.length();
099                    // If equal, the first different number counts
100                    if (result == 0) {
101                        for (int i = 0; i < thisChunkLength; i++) {
102                            result = thisChunk.charAt(i) - thatChunk.charAt(i);
103                            if (result != 0) {
104                                return result;
105                            }
106                        }
107                    }
108                } else {
109                    result = thisChunk.compareTo(thatChunk);
110                }
111    
112                if (result != 0) {
113                    return result;
114                }
115            }
116    
117            return s1Length - s2Length;
118        }
119    }