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    private static final AlphanumComparator INSTANCE = new AlphanumComparator();
043
044    /**
045     * Replies the unique instance.
046     * @return the unique instance
047     */
048    public static AlphanumComparator getInstance() {
049        return INSTANCE;
050    }
051
052    /**
053     * Constructs a new Alphanum Comparator.
054     */
055    private AlphanumComparator() {
056    }
057
058    /**
059     * Length of string is passed in for improved efficiency (only need to
060     * calculate it once) *
061     */
062    private String getChunk(String s, int slength, int marker) {
063        StringBuilder chunk = new StringBuilder();
064        char c = s.charAt(marker);
065        chunk.append(c);
066        marker++;
067        if (Character.isDigit(c)) {
068            while (marker < slength) {
069                c = s.charAt(marker);
070                if (!Character.isDigit(c)) {
071                    break;
072                }
073                chunk.append(c);
074                marker++;
075            }
076        } else {
077            while (marker < slength) {
078                c = s.charAt(marker);
079                if (Character.isDigit(c)) {
080                    break;
081                }
082                chunk.append(c);
083                marker++;
084            }
085        }
086        return chunk.toString();
087    }
088
089    @Override
090    public int compare(String s1, String s2) {
091        if (s1 == null && s2 == null) {
092            return 0;
093        } else if (s1 == null) {
094            return -1;
095        } else if (s2 == null) {
096            return 1;
097        }
098
099        int thisMarker = 0;
100        int thatMarker = 0;
101        int s1Length = s1.length();
102        int s2Length = s2.length();
103
104        while (thisMarker < s1Length && thatMarker < s2Length) {
105            String thisChunk = getChunk(s1, s1Length, thisMarker);
106            thisMarker += thisChunk.length();
107
108            String thatChunk = getChunk(s2, s2Length, thatMarker);
109            thatMarker += thatChunk.length();
110
111            // If both chunks contain numeric characters, sort them numerically
112            int result;
113            if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
114                // Simple chunk comparison by length.
115                int thisChunkLength = thisChunk.length();
116                result = thisChunkLength - thatChunk.length();
117                // If equal, the first different number counts
118                if (result == 0) {
119                    for (int i = 0; i < thisChunkLength; i++) {
120                        result = thisChunk.charAt(i) - thatChunk.charAt(i);
121                        if (result != 0) {
122                            return result;
123                        }
124                    }
125                }
126            } else {
127                // Instantiate the collator
128                Collator compareOperator = Collator.getInstance(Locale.getDefault());
129                // Compare regardless of accented letters
130                compareOperator.setStrength(Collator.SECONDARY);
131                result = compareOperator.compare(thisChunk, thatChunk);
132            }
133
134            if (result != 0) {
135                return result;
136            }
137        }
138
139        return s1Length - s2Length;
140    }
141}