git.gag.com Git - debian/openrocket/blob - android/src/net/sf/openrocket/android/filebrowser/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.android.filebrowser;\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     public int compare(String s1, String s2)\r
  93     {\r
  94 \r
  95         int thisMarker = 0;\r
  96         int thatMarker = 0;\r
  97         int s1Length = s1.length();\r
  98         int s2Length = s2.length();\r
  99 \r
 100         while (thisMarker < s1Length && thatMarker < s2Length)\r
 101         {\r
 102             String thisChunk = getChunk(s1, s1Length, thisMarker);\r
 103             thisMarker += thisChunk.length();\r
 104 \r
 105             String thatChunk = getChunk(s2, s2Length, thatMarker);\r
 106             thatMarker += thatChunk.length();\r
 107 \r
 108             // If both chunks contain numeric characters, sort them numerically\r
 109             int result = 0;\r
 110             if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))\r
 111             {\r
 112                 // Simple chunk comparison by length.\r
 113                 int thisChunkLength = thisChunk.length();\r
 114                 result = thisChunkLength - thatChunk.length();\r
 115                 // If equal, the first different number counts\r
 116                 if (result == 0)\r
 117                 {\r
 118                     for (int i = 0; i < thisChunkLength; i++)\r
 119                     {\r
 120                         result = thisChunk.charAt(i) - thatChunk.charAt(i);\r
 121                         if (result != 0)\r
 122                         {\r
 123                             return result;\r
 124                         }\r
 125                     }\r
 126                 }\r
 127             } else\r
 128             {\r
 129                 result = sorter.compare(thisChunk, thatChunk);\r
 130             }\r
 131 \r
 132             if (result != 0)\r
 133                 return result;\r
 134         }\r
 135 \r
 136         return s1Length - s2Length;\r
 137     }\r
 138 }\r