001package jmri.util;
002
003/*
004 * The Alphanum Algorithm is an improved sorting algorithm for strings
005 * containing numbers.  Instead of sorting numbers in ASCII order like
006 * a standard sort, this algorithm sorts numbers in numeric order.
007 *
008 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
009 *
010 * This library is free software; you can redistribute it and/or
011 * modify it under the terms of the GNU Lesser General Public
012 * License as published by the Free Software Foundation; either
013 * version 2.1 of the License, or any later version.
014 *
015 * This library is distributed in the hope that it will be useful,
016 * but WITHOUT ANY WARRANTY; without even the implied warranty of
017 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
018 * Lesser General Public License for more details.
019 *
020 * You should have received a copy of the GNU Lesser General Public
021 * License along with this library; if not, write to the Free Software
022 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
023 *
024 */
025import java.util.Comparator;
026
027/**
028 * This is an updated version with enhancements made by Daniel Migowski, Andre
029 * Bogus, and David Koelle
030 * <p>
031 * To use this class: Use the static "sort" method from the
032 * java.util.Collections class: Collections.sort(your list, new
033 * AlphanumComparator());
034 * <p>
035 * Note: this code compares numbers one at a time if those numbers are in chunks
036 * of the same size. For example, when comparing abc123 to abc184, 123 and 184
037 * are the same size, so their values are compared digit-by- digit: 1 equals 1,
038 * 2 is less than 8, etc. This was done to solve the problem of numeric chunks
039 * that are too large to fit in range of values allowed by the programming
040 * language for a particular datatype: in Java, an int is limited to 2147483647.
041 * The problem with this approach is doesn't properly handle numbers that have
042 * leading zeros. For example, 0001 is seem as larger than 1 because it's the
043 * longer number. A version that does not compare leading zeros is forthcoming.
044 */
045public class AlphanumComparator implements Comparator<String> {
046
047    private final boolean isDigit(char ch) {
048        return (('0' <= ch) && (ch <= '9'));
049    }
050
051    // Length of string is passed in for improved efficiency (only need to calculate it once)
052    private final String getChunk(String s, int slength, int marker) {
053        StringBuilder chunk = new StringBuilder();
054        int markstart = marker;
055        char c = s.charAt(marker);
056        boolean startIsDigit = isDigit(c);
057        if (c == '0') {
058            // strip leading zeros - cases:
059            //    This is or isn't the only leading zero
060            //    There are or aren't more digits after the run of zeros
061            while (marker+1 < slength && s.charAt(marker+1) == '0') {
062                marker++; // skip that zero
063            }
064            // now what's the next character?
065            if (marker+1 >= slength) {
066                // nothing more, continue with that single zero
067            } else if (isDigit(s.charAt(marker+1))) {
068                // number, drop the leading zero
069                marker++;
070                c = s.charAt(marker);
071            } else {
072                // is letter, let the zero go
073            }
074        }
075        chunk.append(c);
076        while (++marker < slength) {
077            c = s.charAt(marker);
078            if (isDigit(c) != startIsDigit) {
079                break;
080            }
081            chunk.append(c);
082        }
083
084        skip = marker - markstart;
085        return chunk.toString();
086    }
087
088    // internal temporary used to efficiently return how many characters were skipped
089    int skip;
090
091    @Override
092    public int compare(String s1, String s2) {
093        int length1 = s1.length();
094        int length2 = s2.length();
095        int result = length1 - length2;
096
097        int marker1 = 0, marker2 = 0;
098        while (marker1 < length1 && marker2 < length2) {
099            String chunk1 = getChunk(s1, length1, marker1);
100            marker1 += skip;
101
102            String chunk2 = getChunk(s2, length2, marker2);
103            marker2 += skip;
104
105            // If both chunks contain numeric characters, sort them numerically
106            if (isDigit(chunk1.charAt(0)) && isDigit(chunk2.charAt(0))) {
107                // Simple chunk comparison by length.
108                int chunkLength1 = chunk1.length();
109                result = chunkLength1 - chunk2.length();
110                // If lengths equal, the first different number counts
111                if (result == 0) {
112                    for (int i = 0; i < chunkLength1; i++) {
113                        result = chunk1.charAt(i) - chunk2.charAt(i);
114                        if (result != 0) {
115                            break;
116                        }
117                    }
118                }
119            } else {
120                result = chunk1.compareTo(chunk2);
121            }
122
123            if (result != 0) {
124                break;
125            }
126        }
127        if (result == 0 && marker1 == length1 && marker2 < length2) return -1;
128        if (result == 0 && marker1 < length1 && marker2 == length2) return +1;
129
130        return Integer.signum(result);  // limit to -1, 0, 1
131    }
132}