bundles/org.simantics.utils/src/org/simantics/utils/strings/AlphanumComparator.java

   1 /*
   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.
   5  *
   6  * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
   7  *
   8  *
   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.
  13  *
  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.
  18  *
  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
  22  *
  23  */
  24 package org.simantics.utils.strings;
  25
  26 import java.nio.CharBuffer;
  27 import java.util.Comparator;
  28
  29 /**
  30  * This is an updated version with enhancements made by Daniel Migowski, Andre
  31  * Bogus, and David Koelle
  32  *
  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
  36  * compare().
  37  *
  38  * To use this class: Use the static "sort" method from the
  39  * java.util.Collections class: Collections.sort(your list, new
  40  * AlphanumComparator());
  41  *
  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.
  44  */
  45 public class AlphanumComparator implements Comparator<Object>
  46 {
  47     private static final CaseInsensitiveComparator CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator();
  48
  49     private static class CaseInsensitiveComparator implements Comparator<CharBuffer>, java.io.Serializable {
  50
  51         private static final long serialVersionUID = 5247677019801470582L;
  52
  53         @Override
  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);
  59                 if (c1 != c2) {
  60                     c1 = Character.toUpperCase(c1);
  61                     c2 = Character.toUpperCase(c2);
  62                     if (c1 != c2) {
  63                         c1 = Character.toLowerCase(c1);
  64                         c2 = Character.toLowerCase(c2);
  65                         if (c1 != c2) {
  66                             return c1 - c2;
  67                         }
  68                     }
  69                 }
  70             }
  71             return n1 - n2;
  72         }
  73     }
  74
  75     public static final AlphanumComparator COMPARATOR  = new AlphanumComparator(null);
  76     public static final AlphanumComparator CASE_INSENSITIVE_COMPARATOR = new AlphanumComparator(CASE_INSENSITIVE_ORDER);
  77
  78     private final Comparator<CharBuffer> comparator;
  79
  80     private static class Buffers {
  81         CharBuffer b1 = CharBuffer.allocate(0);
  82         CharBuffer b2 = b1;
  83     }
  84
  85     private static final ThreadLocal<Buffers> buffers = new ThreadLocal<Buffers>() {
  86         protected Buffers initialValue() {
  87             return new Buffers();
  88         }
  89     };
  90
  91     private AlphanumComparator(Comparator<CharBuffer> comparator) {
  92         this.comparator = comparator;
  93     }
  94
  95     private final boolean isDigit(char ch)
  96     {
  97         return ch >= 48 && ch <= 57;
  98     }
  99
 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)
 102     {
 103         if (chunk == null || chunk.capacity() < slength) {
 104             chunk = CharBuffer.allocate(slength);
 105         } else {
 106             chunk.rewind();
 107             chunk.limit(chunk.capacity());
 108         }
 109
 110         char c = s.charAt(marker);
 111         chunk.append(c);
 112         marker++;
 113         if (isDigit(c))
 114         {
 115             while (marker < slength)
 116             {
 117                 c = s.charAt(marker);
 118                 if (!isDigit(c))
 119                     break;
 120                 chunk.append(c);
 121                 marker++;
 122             }
 123         } else
 124         {
 125             while (marker < slength)
 126             {
 127                 c = s.charAt(marker);
 128                 if (isDigit(c))
 129                     break;
 130                 chunk.append(c);
 131                 marker++;
 132             }
 133         }
 134         chunk.limit(chunk.position());
 135         chunk.rewind();
 136         return chunk;
 137     }
 138
 139     @Override
 140     public int compare(Object o1, Object o2)
 141     {
 142         if (o1 == o2)
 143             return 0;
 144
 145         String s1 = o1.toString();
 146         String s2 = o2.toString();
 147
 148         int thisMarker = 0;
 149         int thatMarker = 0;
 150         int s1Length = s1.length();
 151         int s2Length = s2.length();
 152
 153         Buffers bufs = buffers.get();
 154         CharBuffer thisChunk = bufs.b1;
 155         CharBuffer thatChunk = bufs.b2;
 156
 157         try {
 158             while (thisMarker < s1Length && thatMarker < s2Length)
 159             {
 160                 thisChunk = getChunk(s1, s1Length, thisMarker, thisChunk);
 161                 thisMarker += thisChunk.limit();
 162
 163                 thatChunk = getChunk(s2, s2Length, thatMarker, thatChunk);
 164                 thatMarker += thatChunk.limit();
 165
 166                 // If both chunks contain numeric characters, sort them numerically
 167                 int result = 0;
 168                 if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))
 169                 {
 170                     // Simple chunk comparison by length.
 171                     int thisChunkLength = thisChunk.limit();
 172                     result = thisChunkLength - thatChunk.limit();
 173                     // If equal, the first different number counts
 174                     if (result == 0)
 175                     {
 176                         for (int i = 0; i < thisChunkLength; i++)
 177                         {
 178                             result = thisChunk.charAt(i) - thatChunk.charAt(i);
 179                             if (result != 0)
 180                             {
 181                                 return result;
 182                             }
 183                         }
 184                     }
 185                 } else
 186                 {
 187                     result = comparator != null ? comparator.compare(thisChunk, thatChunk) : thisChunk.compareTo(thatChunk);
 188                 }
 189
 190                 if (result != 0)
 191                     return result;
 192             }
 193
 194             return s1Length - s2Length;
 195         } finally {
 196             bufs.b1 = reset(thisChunk);
 197             bufs.b2 = reset(thatChunk);
 198         }
 199     }
 200
 201     private static CharBuffer reset(CharBuffer buffer) {
 202         buffer.rewind();
 203         buffer.limit(buffer.capacity());
 204         return buffer;
 205     }
 206
 207 }