2 * The Alphanum Algorithm is an improved sorting algorithm for strings
\r
3 * containing numbers. Instead of sorting numbers in ASCII order like
\r
4 * a standard sort, this algorithm sorts numbers in numeric order.
\r
6 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
\r
9 * This library is free software; you can redistribute it and/or
\r
10 * modify it under the terms of the GNU Lesser General Public
\r
11 * License as published by the Free Software Foundation; either
\r
12 * version 2.1 of the License, or any later version.
\r
14 * This library is distributed in the hope that it will be useful,
\r
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
\r
17 * Lesser General Public License for more details.
\r
19 * You should have received a copy of the GNU Lesser General Public
\r
20 * License along with this library; if not, write to the Free Software
\r
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
\r
24 package org.simantics.utils.strings;
\r
26 import java.nio.CharBuffer;
\r
27 import java.util.Comparator;
\r
30 * This is an updated version with enhancements made by Daniel Migowski, Andre
\r
31 * Bogus, and David Koelle
\r
33 * To convert to use Templates (Java 1.5+): - Change "implements Comparator" to
\r
34 * "implements Comparator<String>" - Change "compare(Object o1, Object o2)" to
\r
35 * "compare(String s1, String s2)" - Remove the type checking and casting in
\r
38 * To use this class: Use the static "sort" method from the
\r
39 * java.util.Collections class: Collections.sort(your list, new
\r
40 * AlphanumComparator());
\r
42 * Modified by Tuukka Lehtonen to re-use two CharBuffer instances compared to
\r
43 * 2*chunk-count StringBuilders per single comparison for some added efficiency.
\r
45 public class AlphanumComparator implements Comparator<Object>
\r
47 private static final CaseInsensitiveComparator CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator();
\r
49 private static class CaseInsensitiveComparator implements Comparator<CharBuffer>, java.io.Serializable {
\r
51 private static final long serialVersionUID = 5247677019801470582L;
\r
54 public int compare(CharBuffer s1, CharBuffer s2) {
\r
55 int n1 = s1.limit(), n2 = s2.limit();
\r
56 for (int i1 = 0, i2 = 0; i1 < n1 && i2 < n2; i1++, i2++) {
\r
57 char c1 = s1.charAt(i1);
\r
58 char c2 = s2.charAt(i2);
\r
60 c1 = Character.toUpperCase(c1);
\r
61 c2 = Character.toUpperCase(c2);
\r
63 c1 = Character.toLowerCase(c1);
\r
64 c2 = Character.toLowerCase(c2);
\r
75 public static final AlphanumComparator COMPARATOR = new AlphanumComparator(null);
\r
76 public static final AlphanumComparator CASE_INSENSITIVE_COMPARATOR = new AlphanumComparator(CASE_INSENSITIVE_ORDER);
\r
78 private final Comparator<CharBuffer> comparator;
\r
80 private static class Buffers {
\r
81 CharBuffer b1 = CharBuffer.allocate(0);
\r
85 private static final ThreadLocal<Buffers> buffers = new ThreadLocal<Buffers>() {
\r
86 protected Buffers initialValue() {
\r
87 return new Buffers();
\r
91 private AlphanumComparator(Comparator<CharBuffer> comparator) {
\r
92 this.comparator = comparator;
\r
95 private final boolean isDigit(char ch)
\r
97 return ch >= 48 && ch <= 57;
\r
100 /** Length of string is passed in for improved efficiency (only need to calculate it once) **/
\r
101 private final CharBuffer getChunk(String s, int slength, int marker, CharBuffer chunk)
\r
103 if (chunk == null || chunk.capacity() < slength) {
\r
104 chunk = CharBuffer.allocate(slength);
\r
107 chunk.limit(chunk.capacity());
\r
110 char c = s.charAt(marker);
\r
115 while (marker < slength)
\r
117 c = s.charAt(marker);
\r
125 while (marker < slength)
\r
127 c = s.charAt(marker);
\r
134 chunk.limit(chunk.position());
\r
140 public int compare(Object o1, Object o2)
\r
145 String s1 = o1.toString();
\r
146 String s2 = o2.toString();
\r
148 int thisMarker = 0;
\r
149 int thatMarker = 0;
\r
150 int s1Length = s1.length();
\r
151 int s2Length = s2.length();
\r
153 Buffers bufs = buffers.get();
\r
154 CharBuffer thisChunk = bufs.b1;
\r
155 CharBuffer thatChunk = bufs.b2;
\r
158 while (thisMarker < s1Length && thatMarker < s2Length)
\r
160 thisChunk = getChunk(s1, s1Length, thisMarker, thisChunk);
\r
161 thisMarker += thisChunk.limit();
\r
163 thatChunk = getChunk(s2, s2Length, thatMarker, thatChunk);
\r
164 thatMarker += thatChunk.limit();
\r
166 // If both chunks contain numeric characters, sort them numerically
\r
168 if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))
\r
170 // Simple chunk comparison by length.
\r
171 int thisChunkLength = thisChunk.limit();
\r
172 result = thisChunkLength - thatChunk.limit();
\r
173 // If equal, the first different number counts
\r
176 for (int i = 0; i < thisChunkLength; i++)
\r
178 result = thisChunk.charAt(i) - thatChunk.charAt(i);
\r
187 result = comparator != null ? comparator.compare(thisChunk, thatChunk) : thisChunk.compareTo(thatChunk);
\r
194 return s1Length - s2Length;
\r
196 bufs.b1 = reset(thisChunk);
\r
197 bufs.b2 = reset(thatChunk);
\r
201 private static CharBuffer reset(CharBuffer buffer) {
\r
203 buffer.limit(buffer.capacity());
\r