001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.tools; 003 004/* 005 * The Alphanum Algorithm is an improved sorting algorithm for strings 006 * containing numbers. Instead of sorting numbers in ASCII order like a standard 007 * sort, this algorithm sorts numbers in numeric order. 008 * 009 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 010 * 011 * 012 * This library is free software; you can redistribute it and/or modify it under 013 * the terms of the GNU Lesser General Public License as published by the Free 014 * Software Foundation; either version 2.1 of the License, or any later version. 015 * 016 * This library is distributed in the hope that it will be useful, but WITHOUT 017 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 018 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more 019 * details. 020 * 021 * You should have received a copy of the GNU Lesser General Public License 022 * along with this library; if not, write to the Free Software Foundation, Inc., 023 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 024 * 025 */ 026import java.io.Serializable; 027import java.text.Collator; 028import java.util.Comparator; 029import java.util.Locale; 030 031/** 032 * The Alphanum Algorithm is an improved sorting algorithm for strings 033 * containing numbers: Instead of sorting numbers in ASCII order like a standard 034 * sort, this algorithm sorts numbers in numeric order. 035 * 036 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 037 * 038 * This is an updated version with enhancements made by Daniel Migowski, Andre 039 * Bogus, and David Koelle and others. 040 * 041 */ 042public final class AlphanumComparator implements Comparator<String>, Serializable { 043 044 private static final long serialVersionUID = 1L; 045 046 private static final AlphanumComparator INSTANCE = new AlphanumComparator(); 047 048 /** 049 * Replies the unique instance. 050 * @return the unique instance 051 */ 052 public static AlphanumComparator getInstance() { 053 return INSTANCE; 054 } 055 056 /** 057 * Constructs a new Alphanum Comparator. 058 */ 059 private AlphanumComparator() { 060 } 061 062 /** 063 * Returns an alphanum chunk. 064 * Length of string is passed in for improved efficiency (only need to calculate it once). 065 * @param s string 066 * @param slength string length 067 * @param marker position 068 * @return alphanum chunk found at given position 069 */ 070 private static String getChunk(String s, int slength, int marker) { 071 StringBuilder chunk = new StringBuilder(); 072 char c = s.charAt(marker); 073 chunk.append(c); 074 marker++; 075 if (Character.isDigit(c)) { 076 while (marker < slength) { 077 c = s.charAt(marker); 078 if (!Character.isDigit(c)) { 079 break; 080 } 081 chunk.append(c); 082 marker++; 083 } 084 } else { 085 while (marker < slength) { 086 c = s.charAt(marker); 087 if (Character.isDigit(c)) { 088 break; 089 } 090 chunk.append(c); 091 marker++; 092 } 093 } 094 return chunk.toString(); 095 } 096 097 @Override 098 public int compare(String s1, String s2) { 099 if (s1 == null && s2 == null) { 100 return 0; 101 } else if (s1 == null) { 102 return -1; 103 } else if (s2 == null) { 104 return 1; 105 } 106 107 int thisMarker = 0; 108 int thatMarker = 0; 109 int s1Length = s1.length(); 110 int s2Length = s2.length(); 111 112 while (thisMarker < s1Length && thatMarker < s2Length) { 113 String thisChunk = getChunk(s1, s1Length, thisMarker); 114 thisMarker += thisChunk.length(); 115 116 String thatChunk = getChunk(s2, s2Length, thatMarker); 117 thatMarker += thatChunk.length(); 118 119 // If both chunks contain numeric characters, sort them numerically 120 int result; 121 if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) { 122 // Simple chunk comparison by length. 123 int thisChunkLength = thisChunk.length(); 124 result = thisChunkLength - thatChunk.length(); 125 // If equal, the first different number counts 126 if (result == 0) { 127 for (int i = 0; i < thisChunkLength; i++) { 128 result = thisChunk.charAt(i) - thatChunk.charAt(i); 129 if (result != 0) { 130 return result; 131 } 132 } 133 } 134 } else { 135 // Instantiate the collator 136 Collator compareOperator = Collator.getInstance(Locale.getDefault()); 137 // Compare regardless of accented letters 138 compareOperator.setStrength(Collator.SECONDARY); 139 result = compareOperator.compare(thisChunk, thatChunk); 140 } 141 142 if (result != 0) { 143 return result; 144 } 145 } 146 147 return s1Length - s2Length; 148 } 149}