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