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