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