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; 036import java.util.Locale; 037 038/** 039 * The Alphanum Algorithm is an improved sorting algorithm for strings 040 * containing numbers: Instead of sorting numbers in ASCII order like a standard 041 * sort, this algorithm sorts numbers in numeric order. 042 * 043 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 044 * 045 * This is an updated version with enhancements made by Daniel Migowski, Andre 046 * Bogus, David Koelle and others. 047 * 048 */ 049public final class AlphanumComparator implements Comparator<String>, Serializable { 050 051 private static final long serialVersionUID = 1L; 052 053 private static final AlphanumComparator INSTANCE = new AlphanumComparator(); 054 055 /** 056 * Replies the unique instance. 057 * @return the unique instance 058 */ 059 public static AlphanumComparator getInstance() { 060 return INSTANCE; 061 } 062 063 /** 064 * Constructs a new Alphanum Comparator. 065 */ 066 private AlphanumComparator() { 067 } 068 069 /** 070 * Returns an alphanum chunk. 071 * Length of string is passed in for improved efficiency (only need to calculate it once). 072 * @param s string 073 * @param slength string length 074 * @param marker position 075 * @return alphanum chunk found at given position 076 */ 077 private static String getChunk(String s, int slength, int marker) { 078 StringBuilder chunk = new StringBuilder(); 079 char c = s.charAt(marker); 080 chunk.append(c); 081 marker++; 082 if (Character.isDigit(c)) { 083 while (marker < slength) { 084 c = s.charAt(marker); 085 if (!Character.isDigit(c)) { 086 break; 087 } 088 chunk.append(c); 089 marker++; 090 } 091 } else { 092 while (marker < slength) { 093 c = s.charAt(marker); 094 if (Character.isDigit(c)) { 095 break; 096 } 097 chunk.append(c); 098 marker++; 099 } 100 } 101 return chunk.toString(); 102 } 103 104 @Override 105 public int compare(String s1, String s2) { 106 if (s1 == null && s2 == null) { 107 return 0; 108 } else if (s1 == null) { 109 return -1; 110 } else if (s2 == null) { 111 return 1; 112 } 113 114 int thisMarker = 0; 115 int thatMarker = 0; 116 int s1Length = s1.length(); 117 int s2Length = s2.length(); 118 119 while (thisMarker < s1Length && thatMarker < s2Length) { 120 String thisChunk = getChunk(s1, s1Length, thisMarker); 121 thisMarker += thisChunk.length(); 122 123 String thatChunk = getChunk(s2, s2Length, thatMarker); 124 thatMarker += thatChunk.length(); 125 126 // If both chunks contain numeric characters, sort them numerically 127 int result; 128 if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) { 129 // Simple chunk comparison by length. 130 int thisChunkLength = thisChunk.length(); 131 result = thisChunkLength - thatChunk.length(); 132 // If equal, the first different number counts 133 if (result == 0) { 134 for (int i = 0; i < thisChunkLength; i++) { 135 result = thisChunk.charAt(i) - thatChunk.charAt(i); 136 if (result != 0) { 137 return result; 138 } 139 } 140 } 141 } else { 142 // Instantiate the collator 143 Collator compareOperator = Collator.getInstance(Locale.getDefault()); 144 // Compare regardless of accented letters 145 compareOperator.setStrength(Collator.SECONDARY); 146 result = compareOperator.compare(thisChunk, thatChunk); 147 } 148 149 if (result != 0) { 150 return result; 151 } 152 } 153 154 return s1Length - s2Length; 155 } 156}