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 * Released under the MIT License - https://opensource.org/licenses/MIT 012 * 013 * Copyright 2007-2017 David Koelle 014 * 015 * Permission is hereby granted, free of charge, to any person obtaining 016 * a copy of this software and associated documentation files (the "Software"), 017 * to deal in the Software without restriction, including without limitation 018 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 019 * and/or sell copies of the Software, and to permit persons to whom the 020 * Software is furnished to do so, subject to the following conditions: 021 * 022 * The above copyright notice and this permission notice shall be included 023 * in all copies or substantial portions of the Software. 024 * 025 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 026 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 027 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 028 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 029 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 030 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 031 * USE OR OTHER DEALINGS IN THE SOFTWARE. 032 */ 033import java.io.Serializable; 034import java.text.Collator; 035import java.util.Comparator; 036 037/** 038 * The Alphanum Algorithm is an improved sorting algorithm for strings 039 * containing numbers: Instead of sorting numbers in ASCII order like a standard 040 * sort, this algorithm sorts numbers in numeric order. 041 * 042 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 043 * 044 * This is an updated version with enhancements made by Daniel Migowski, Andre 045 * Bogus, David Koelle and others. 046 * 047 */ 048public final class AlphanumComparator implements Comparator<String>, Serializable { 049 050 private static final long serialVersionUID = 1L; 051 052 private static final AlphanumComparator INSTANCE = new AlphanumComparator(); 053 054 /** 055 * Replies the unique instance. 056 * @return the unique instance 057 */ 058 public static AlphanumComparator getInstance() { 059 return INSTANCE; 060 } 061 062 /** 063 * Constructs a new Alphanum Comparator. 064 */ 065 private AlphanumComparator() { 066 } 067 068 /** 069 * Returns an alphanum chunk. 070 * Length of string is passed in for improved efficiency (only need to calculate it once). 071 * @param s string 072 * @param slength string length 073 * @param marker position 074 * @return alphanum chunk found at given position 075 */ 076 private static String getChunk(String s, int slength, int marker) { 077 StringBuilder chunk = new StringBuilder(); 078 char c = s.charAt(marker); 079 chunk.append(c); 080 marker++; 081 if (Character.isDigit(c)) { 082 while (marker < slength) { 083 c = s.charAt(marker); 084 if (!Character.isDigit(c)) { 085 break; 086 } 087 chunk.append(c); 088 marker++; 089 } 090 } else { 091 while (marker < slength) { 092 c = s.charAt(marker); 093 if (Character.isDigit(c)) { 094 break; 095 } 096 chunk.append(c); 097 marker++; 098 } 099 } 100 return chunk.toString(); 101 } 102 103 @Override 104 public int compare(String s1, String s2) { 105 if (s1 == null && s2 == null) { 106 return 0; 107 } else if (s1 == null) { 108 return -1; 109 } else if (s2 == null) { 110 return 1; 111 } 112 113 int thisMarker = 0; 114 int thatMarker = 0; 115 int s1Length = s1.length(); 116 int s2Length = s2.length(); 117 118 while (thisMarker < s1Length && thatMarker < s2Length) { 119 String thisChunk = getChunk(s1, s1Length, thisMarker); 120 thisMarker += thisChunk.length(); 121 122 String thatChunk = getChunk(s2, s2Length, thatMarker); 123 thatMarker += thatChunk.length(); 124 125 // If both chunks contain numeric characters, sort them numerically 126 int result; 127 if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) { 128 // Simple chunk comparison by length. 129 int thisChunkLength = thisChunk.length(); 130 result = thisChunkLength - thatChunk.length(); 131 // If equal, the first different number counts 132 if (result == 0) { 133 for (int i = 0; i < thisChunkLength; i++) { 134 result = thisChunk.charAt(i) - thatChunk.charAt(i); 135 if (result != 0) { 136 return result; 137 } 138 } 139 } 140 } else { 141 // Instantiate the collator 142 Collator compareOperator = Collator.getInstance(); 143 // Compare regardless of accented letters 144 compareOperator.setStrength(Collator.SECONDARY); 145 result = compareOperator.compare(thisChunk, thatChunk); 146 } 147 148 if (result != 0) { 149 return result; 150 } 151 } 152 153 return s1Length - s2Length; 154 } 155}