001package 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 */
025import java.text.Collator;
026import java.util.Comparator;
027import java.util.Locale;
028
029/**
030 * The Alphanum Algorithm is an improved sorting algorithm for strings
031 * containing numbers: Instead of sorting numbers in ASCII order like a standard
032 * sort, this algorithm sorts numbers in numeric order.
033 *
034 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
035 *
036 * This is an updated version with enhancements made by Daniel Migowski, Andre
037 * Bogus, and David Koelle and others.
038 *
039 */
040public class AlphanumComparator implements Comparator<String> {
041
042    /**
043     * Length of string is passed in for improved efficiency (only need to
044     * calculate it once) *
045     */
046    private String getChunk(String s, int slength, int marker) {
047        StringBuilder chunk = new StringBuilder();
048        char c = s.charAt(marker);
049        chunk.append(c);
050        marker++;
051        if (Character.isDigit(c)) {
052            while (marker < slength) {
053                c = s.charAt(marker);
054                if (!Character.isDigit(c)) {
055                    break;
056                }
057                chunk.append(c);
058                marker++;
059            }
060        } else {
061            while (marker < slength) {
062                c = s.charAt(marker);
063                if (Character.isDigit(c)) {
064                    break;
065                }
066                chunk.append(c);
067                marker++;
068            }
069        }
070        return chunk.toString();
071    }
072
073    @Override
074    public int compare(String s1, String s2) {
075        if (s1 == null && s2 == null) {
076            return 0;
077        } else if (s1 == null) {
078            return -1;
079        } else if (s2 == null) {
080            return 1;
081        }
082
083        int thisMarker = 0;
084        int thatMarker = 0;
085        int s1Length = s1.length();
086        int s2Length = s2.length();
087
088        while (thisMarker < s1Length && thatMarker < s2Length) {
089            String thisChunk = getChunk(s1, s1Length, thisMarker);
090            thisMarker += thisChunk.length();
091
092            String thatChunk = getChunk(s2, s2Length, thatMarker);
093            thatMarker += thatChunk.length();
094
095            // If both chunks contain numeric characters, sort them numerically
096            int result;
097            if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
098                // Simple chunk comparison by length.
099                int thisChunkLength = thisChunk.length();
100                result = thisChunkLength - thatChunk.length();
101                // If equal, the first different number counts
102                if (result == 0) {
103                    for (int i = 0; i < thisChunkLength; i++) {
104                        result = thisChunk.charAt(i) - thatChunk.charAt(i);
105                        if (result != 0) {
106                            return result;
107                        }
108                    }
109                }
110            } else {
111                // Instantiate the collator
112                Collator compareOperator = Collator.getInstance(Locale.getDefault());
113                // Compare regardless of accented letters
114                compareOperator.setStrength(Collator.SECONDARY);
115                result = compareOperator.compare(thisChunk, thatChunk);
116            }
117
118            if (result != 0) {
119                return result;
120            }
121        }
122
123        return s1Length - s2Length;
124    }
125}