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