git.gag.com Git - debian/openrocket/blob - core/src/net/sf/openrocket/util/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 \r
  25 /*\r
  26  * Subsequently this code had been hacked up to make it genericized and support\r
  27  * folding upper/lower case.\r
  28  */\r
  29 package net.sf.openrocket.util;\r
  30 \r
  31 import java.text.Collator;\r
  32 import java.util.Comparator;\r
  33 \r
  34 /**\r
  35  * This is an updated version with enhancements made by Daniel Migowski,\r
  36  * Andre Bogus, and David Koelle\r
  37  *\r
  38  * To convert to use Templates (Java 1.5+):\r
  39  *   - Change "implements Comparator" to "implements Comparator<String>"\r
  40  *   - Change "compare(Object o1, Object o2)" to "compare(String s1, String s2)"\r
  41  *   - Remove the type checking and casting in compare().\r
  42  *\r
  43  * To use this class:\r
  44  *   Use the static "sort" method from the java.util.Collections class:\r
  45  *   Collections.sort(your list, new AlphanumComparator());\r
  46  */\r
  47 public class AlphanumComparator implements Comparator<String>\r
  48 {\r
  49 \r
  50         private static final Collator sorter = Collator.getInstance();\r
  51         static {\r
  52                 sorter.setStrength(Collator.TERTIARY);\r
  53                 sorter.setDecomposition(Collator.CANONICAL_DECOMPOSITION);\r
  54         }\r
  55 \r
  56         private final boolean isDigit(char ch)\r
  57         {\r
  58                 return ch >= 48 && ch <= 57;\r
  59         }\r
  60 \r
  61         /** Length of string is passed in for improved efficiency (only need to calculate it once) **/\r
  62         private final String getChunk(String s, int slength, int marker)\r
  63         {\r
  64                 StringBuilder chunk = new StringBuilder();\r
  65                 char c = s.charAt(marker);\r
  66                 chunk.append(c);\r
  67                 marker++;\r
  68                 if (isDigit(c))\r
  69                 {\r
  70                         while (marker < slength)\r
  71                         {\r
  72                                 c = s.charAt(marker);\r
  73                                 if (!isDigit(c))\r
  74                                         break;\r
  75                                 chunk.append(c);\r
  76                                 marker++;\r
  77                         }\r
  78                 } else\r
  79                 {\r
  80                         while (marker < slength)\r
  81                         {\r
  82                                 c = s.charAt(marker);\r
  83                                 if (isDigit(c))\r
  84                                         break;\r
  85                                 chunk.append(c);\r
  86                                 marker++;\r
  87                         }\r
  88                 }\r
  89                 return chunk.toString();\r
  90         }\r
  91 \r
  92         @Override\r
  93         public int compare(String s1, String s2)\r
  94         {\r
  95 \r
  96                 int thisMarker = 0;\r
  97                 int thatMarker = 0;\r
  98                 int s1Length = s1.length();\r
  99                 int s2Length = s2.length();\r
 100 \r
 101                 while (thisMarker < s1Length && thatMarker < s2Length)\r
 102                 {\r
 103                         String thisChunk = getChunk(s1, s1Length, thisMarker);\r
 104                         thisMarker += thisChunk.length();\r
 105 \r
 106                         String thatChunk = getChunk(s2, s2Length, thatMarker);\r
 107                         thatMarker += thatChunk.length();\r
 108 \r
 109                         // If both chunks contain numeric characters, sort them numerically\r
 110                         int result = 0;\r
 111                         if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))\r
 112                         {\r
 113                                 // Simple chunk comparison by length.\r
 114                                 int thisChunkLength = thisChunk.length();\r
 115                                 result = thisChunkLength - thatChunk.length();\r
 116                                 // If equal, the first different number counts\r
 117                                 if (result == 0)\r
 118                                 {\r
 119                                         for (int i = 0; i < thisChunkLength; i++)\r
 120                                         {\r
 121                                                 result = thisChunk.charAt(i) - thatChunk.charAt(i);\r
 122                                                 if (result != 0)\r
 123                                                 {\r
 124                                                         return result;\r
 125                                                 }\r
 126                                         }\r
 127                                 }\r
 128                         } else\r
 129                         {\r
 130                                 result = sorter.compare(thisChunk, thatChunk);\r
 131                         }\r
 132 \r
 133                         if (result != 0)\r
 134                                 return result;\r
 135                 }\r
 136 \r
 137                 return s1Length - s2Length;\r
 138         }\r
 139 }\r