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