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}