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    // The number of characters consumed is returned in skip[0]
053    private final String getChunk(String s, int slength, int marker, int[] skip) {
054        StringBuilder chunk = new StringBuilder();
055        int markstart = marker;
056        char c = s.charAt(marker);
057        boolean startIsDigit = isDigit(c);
058        if (c == '0') {
059            // strip leading zeros - cases:
060            //    This is or isn't the only leading zero
061            //    There are or aren't more digits after the run of zeros
062            while (marker+1 < slength && s.charAt(marker+1) == '0') {
063                marker++; // skip that zero
064            }
065            // now what's the next character?
066            if (marker+1 >= slength) {
067                // nothing more, continue with that single zero
068            } else if (isDigit(s.charAt(marker+1))) {
069                // number, drop the leading zero
070                marker++;
071                c = s.charAt(marker);
072            } else {
073                // is letter, let the zero go
074            }
075        }
076        chunk.append(c);
077        while (++marker < slength) {
078            c = s.charAt(marker);
079            if (isDigit(c) != startIsDigit) {
080                break;
081            }
082            chunk.append(c);
083        }
084
085        skip[0] = marker - markstart;
086        return chunk.toString();
087    }
088
089    @Override
090    public int compare(String s1, String s2) {
091        int length1 = s1.length();
092        int length2 = s2.length();
093        int result = length1 - length2;
094
095        int marker1 = 0, marker2 = 0;
096        // local, so that one instance can be shared between threads
097        int[] skip = new int[1];
098        while (marker1 < length1 && marker2 < length2) {
099            String chunk1 = getChunk(s1, length1, marker1, skip);
100            marker1 += skip[0];
101
102            String chunk2 = getChunk(s2, length2, marker2, skip);
103            marker2 += skip[0];
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}