X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils%2Fsrc%2Forg%2Fsimantics%2Futils%2Fstrings%2FAlphanumComparator.java;h=ba18265e5e98229d92e153b8c2d6e18d2c0f5d3a;hb=8905e67e82991121305889e6474a124d6ec79bf8;hp=74a687d1ea0e91ac025ea6ee541fc6fb2dc21cf0;hpb=969bd23cab98a79ca9101af33334000879fb60c5;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.utils/src/org/simantics/utils/strings/AlphanumComparator.java b/bundles/org.simantics.utils/src/org/simantics/utils/strings/AlphanumComparator.java index 74a687d1e..ba18265e5 100644 --- a/bundles/org.simantics.utils/src/org/simantics/utils/strings/AlphanumComparator.java +++ b/bundles/org.simantics.utils/src/org/simantics/utils/strings/AlphanumComparator.java @@ -1,207 +1,207 @@ -/* - * The Alphanum Algorithm is an improved sorting algorithm for strings - * containing numbers. Instead of sorting numbers in ASCII order like - * a standard sort, this algorithm sorts numbers in numeric order. - * - * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com - * - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - * - */ -package org.simantics.utils.strings; - -import java.nio.CharBuffer; -import java.util.Comparator; - -/** - * This is an updated version with enhancements made by Daniel Migowski, Andre - * Bogus, and David Koelle - * - * To convert to use Templates (Java 1.5+): - Change "implements Comparator" to - * "implements Comparator" - Change "compare(Object o1, Object o2)" to - * "compare(String s1, String s2)" - Remove the type checking and casting in - * compare(). - * - * To use this class: Use the static "sort" method from the - * java.util.Collections class: Collections.sort(your list, new - * AlphanumComparator()); - * - * Modified by Tuukka Lehtonen to re-use two CharBuffer instances compared to - * 2*chunk-count StringBuilders per single comparison for some added efficiency. - */ -public class AlphanumComparator implements Comparator -{ - private static final CaseInsensitiveComparator CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator(); - - private static class CaseInsensitiveComparator implements Comparator, java.io.Serializable { - - private static final long serialVersionUID = 5247677019801470582L; - - @Override - public int compare(CharBuffer s1, CharBuffer s2) { - int n1 = s1.limit(), n2 = s2.limit(); - for (int i1 = 0, i2 = 0; i1 < n1 && i2 < n2; i1++, i2++) { - char c1 = s1.charAt(i1); - char c2 = s2.charAt(i2); - if (c1 != c2) { - c1 = Character.toUpperCase(c1); - c2 = Character.toUpperCase(c2); - if (c1 != c2) { - c1 = Character.toLowerCase(c1); - c2 = Character.toLowerCase(c2); - if (c1 != c2) { - return c1 - c2; - } - } - } - } - return n1 - n2; - } - } - - public static final AlphanumComparator COMPARATOR = new AlphanumComparator(null); - public static final AlphanumComparator CASE_INSENSITIVE_COMPARATOR = new AlphanumComparator(CASE_INSENSITIVE_ORDER); - - private final Comparator comparator; - - private static class Buffers { - CharBuffer b1 = CharBuffer.allocate(0); - CharBuffer b2 = b1; - } - - private static final ThreadLocal buffers = new ThreadLocal() { - protected Buffers initialValue() { - return new Buffers(); - } - }; - - private AlphanumComparator(Comparator comparator) { - this.comparator = comparator; - } - - private final boolean isDigit(char ch) - { - return ch >= 48 && ch <= 57; - } - - /** Length of string is passed in for improved efficiency (only need to calculate it once) **/ - private final CharBuffer getChunk(String s, int slength, int marker, CharBuffer chunk) - { - if (chunk == null || chunk.capacity() < slength) { - chunk = CharBuffer.allocate(slength); - } else { - chunk.rewind(); - chunk.limit(chunk.capacity()); - } - - char c = s.charAt(marker); - chunk.append(c); - marker++; - if (isDigit(c)) - { - while (marker < slength) - { - c = s.charAt(marker); - if (!isDigit(c)) - break; - chunk.append(c); - marker++; - } - } else - { - while (marker < slength) - { - c = s.charAt(marker); - if (isDigit(c)) - break; - chunk.append(c); - marker++; - } - } - chunk.limit(chunk.position()); - chunk.rewind(); - return chunk; - } - - @Override - public int compare(Object o1, Object o2) - { - if (o1 == o2) - return 0; - - String s1 = o1.toString(); - String s2 = o2.toString(); - - int thisMarker = 0; - int thatMarker = 0; - int s1Length = s1.length(); - int s2Length = s2.length(); - - Buffers bufs = buffers.get(); - CharBuffer thisChunk = bufs.b1; - CharBuffer thatChunk = bufs.b2; - - try { - while (thisMarker < s1Length && thatMarker < s2Length) - { - thisChunk = getChunk(s1, s1Length, thisMarker, thisChunk); - thisMarker += thisChunk.limit(); - - thatChunk = getChunk(s2, s2Length, thatMarker, thatChunk); - thatMarker += thatChunk.limit(); - - // If both chunks contain numeric characters, sort them numerically - int result = 0; - if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) - { - // Simple chunk comparison by length. - int thisChunkLength = thisChunk.limit(); - result = thisChunkLength - thatChunk.limit(); - // If equal, the first different number counts - if (result == 0) - { - for (int i = 0; i < thisChunkLength; i++) - { - result = thisChunk.charAt(i) - thatChunk.charAt(i); - if (result != 0) - { - return result; - } - } - } - } else - { - result = comparator != null ? comparator.compare(thisChunk, thatChunk) : thisChunk.compareTo(thatChunk); - } - - if (result != 0) - return result; - } - - return s1Length - s2Length; - } finally { - bufs.b1 = reset(thisChunk); - bufs.b2 = reset(thatChunk); - } - } - - private static CharBuffer reset(CharBuffer buffer) { - buffer.rewind(); - buffer.limit(buffer.capacity()); - return buffer; - } - -} +/* + * The Alphanum Algorithm is an improved sorting algorithm for strings + * containing numbers. Instead of sorting numbers in ASCII order like + * a standard sort, this algorithm sorts numbers in numeric order. + * + * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com + * + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + */ +package org.simantics.utils.strings; + +import java.nio.CharBuffer; +import java.util.Comparator; + +/** + * This is an updated version with enhancements made by Daniel Migowski, Andre + * Bogus, and David Koelle + * + * To convert to use Templates (Java 1.5+): - Change "implements Comparator" to + * "implements Comparator" - Change "compare(Object o1, Object o2)" to + * "compare(String s1, String s2)" - Remove the type checking and casting in + * compare(). + * + * To use this class: Use the static "sort" method from the + * java.util.Collections class: Collections.sort(your list, new + * AlphanumComparator()); + * + * Modified by Tuukka Lehtonen to re-use two CharBuffer instances compared to + * 2*chunk-count StringBuilders per single comparison for some added efficiency. + */ +public class AlphanumComparator implements Comparator +{ + private static final CaseInsensitiveComparator CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator(); + + private static class CaseInsensitiveComparator implements Comparator, java.io.Serializable { + + private static final long serialVersionUID = 5247677019801470582L; + + @Override + public int compare(CharBuffer s1, CharBuffer s2) { + int n1 = s1.limit(), n2 = s2.limit(); + for (int i1 = 0, i2 = 0; i1 < n1 && i2 < n2; i1++, i2++) { + char c1 = s1.charAt(i1); + char c2 = s2.charAt(i2); + if (c1 != c2) { + c1 = Character.toUpperCase(c1); + c2 = Character.toUpperCase(c2); + if (c1 != c2) { + c1 = Character.toLowerCase(c1); + c2 = Character.toLowerCase(c2); + if (c1 != c2) { + return c1 - c2; + } + } + } + } + return n1 - n2; + } + } + + public static final AlphanumComparator COMPARATOR = new AlphanumComparator(null); + public static final AlphanumComparator CASE_INSENSITIVE_COMPARATOR = new AlphanumComparator(CASE_INSENSITIVE_ORDER); + + private final Comparator comparator; + + private static class Buffers { + CharBuffer b1 = CharBuffer.allocate(0); + CharBuffer b2 = b1; + } + + private static final ThreadLocal buffers = new ThreadLocal() { + protected Buffers initialValue() { + return new Buffers(); + } + }; + + private AlphanumComparator(Comparator comparator) { + this.comparator = comparator; + } + + private final boolean isDigit(char ch) + { + return ch >= 48 && ch <= 57; + } + + /** Length of string is passed in for improved efficiency (only need to calculate it once) **/ + private final CharBuffer getChunk(String s, int slength, int marker, CharBuffer chunk) + { + if (chunk == null || chunk.capacity() < slength) { + chunk = CharBuffer.allocate(slength); + } else { + chunk.rewind(); + chunk.limit(chunk.capacity()); + } + + char c = s.charAt(marker); + chunk.append(c); + marker++; + if (isDigit(c)) + { + while (marker < slength) + { + c = s.charAt(marker); + if (!isDigit(c)) + break; + chunk.append(c); + marker++; + } + } else + { + while (marker < slength) + { + c = s.charAt(marker); + if (isDigit(c)) + break; + chunk.append(c); + marker++; + } + } + chunk.limit(chunk.position()); + chunk.rewind(); + return chunk; + } + + @Override + public int compare(Object o1, Object o2) + { + if (o1 == o2) + return 0; + + String s1 = o1.toString(); + String s2 = o2.toString(); + + int thisMarker = 0; + int thatMarker = 0; + int s1Length = s1.length(); + int s2Length = s2.length(); + + Buffers bufs = buffers.get(); + CharBuffer thisChunk = bufs.b1; + CharBuffer thatChunk = bufs.b2; + + try { + while (thisMarker < s1Length && thatMarker < s2Length) + { + thisChunk = getChunk(s1, s1Length, thisMarker, thisChunk); + thisMarker += thisChunk.limit(); + + thatChunk = getChunk(s2, s2Length, thatMarker, thatChunk); + thatMarker += thatChunk.limit(); + + // If both chunks contain numeric characters, sort them numerically + int result = 0; + if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) + { + // Simple chunk comparison by length. + int thisChunkLength = thisChunk.limit(); + result = thisChunkLength - thatChunk.limit(); + // If equal, the first different number counts + if (result == 0) + { + for (int i = 0; i < thisChunkLength; i++) + { + result = thisChunk.charAt(i) - thatChunk.charAt(i); + if (result != 0) + { + return result; + } + } + } + } else + { + result = comparator != null ? comparator.compare(thisChunk, thatChunk) : thisChunk.compareTo(thatChunk); + } + + if (result != 0) + return result; + } + + return s1Length - s2Length; + } finally { + bufs.b1 = reset(thisChunk); + bufs.b2 = reset(thatChunk); + } + } + + private static CharBuffer reset(CharBuffer buffer) { + buffer.rewind(); + buffer.limit(buffer.capacity()); + return buffer; + } + +}