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