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