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 }