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