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

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