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.io.File;
  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     {
  54         StringBuilder chunk = new StringBuilder();
  55         char c = s.charAt(marker);
  56         chunk.append(c);
  57         marker++;
  58         if (isDigit(c))
  59         {
  60             while (marker < slength)
  61             {
  62                 c = s.charAt(marker);
  63                 if (!isDigit(c))
  64                     break;
  65                 chunk.append(c);
  66                 marker++;
  67             }
  68         } else
  69         {
  70             while (marker < slength)
  71             {
  72                 c = s.charAt(marker);
  73                 if (isDigit(c))
  74                     break;
  75                 chunk.append(c);
  76                 marker++;
  77             }
  78         }
  79         return chunk.toString();
  80     }
  81
  82     public int compare(OCFile o1, OCFile o2){
  83         String s1 = o1.getRemotePath().toLowerCase();
  84         String s2 = o2.getRemotePath().toLowerCase();
  85
  86         return compare(s1, s2);
  87     }
  88
  89     public int compare(File f1, File f2){
  90         String s1 = f1.getPath().toLowerCase();
  91         String s2 = f2.getPath().toLowerCase();
  92
  93         return compare(s1, s2);
  94     }
  95
  96     public int compare(String s1, String s2) {
  97         int thisMarker = 0;
  98         int thatMarker = 0;
  99         int s1Length = s1.length();
 100         int s2Length = s2.length();
 101
 102         while (thisMarker < s1Length && thatMarker < s2Length)
 103         {
 104             String thisChunk = getChunk(s1, s1Length, thisMarker);
 105             thisMarker += thisChunk.length();
 106
 107             String thatChunk = getChunk(s2, s2Length, thatMarker);
 108             thatMarker += thatChunk.length();
 109
 110             // If both chunks contain numeric characters, sort them numerically
 111             int result = 0;
 112             if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))
 113             {
 114                 // Simple chunk comparison by length.
 115                 int thisChunkLength = thisChunk.length();
 116                 result = thisChunkLength - thatChunk.length();
 117                 // If equal, the first different number counts
 118                 if (result == 0)
 119                 {
 120                     for (int i = 0; i < thisChunkLength; i++)
 121                     {
 122                         result = thisChunk.charAt(i) - thatChunk.charAt(i);
 123                         if (result != 0)
 124                         {
 125                             return result;
 126                         }
 127                     }
 128                 }
 129             } else
 130             {
 131                 result = thisChunk.compareTo(thatChunk);
 132             }
 133
 134             if (result != 0)
 135                 return result;
 136         }
 137
 138         return s1Length - s2Length;
 139     }
 140 }