1 /*
   2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  *   - Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  *
  11  *   - Redistributions in binary form must reproduce the above copyright
  12  *     notice, this list of conditions and the following disclaimer in the
  13  *     documentation and/or other materials provided with the distribution.
  14  *
  15  *   - Neither the name of Oracle nor the names of its
  16  *     contributors may be used to endorse or promote products derived
  17  *     from this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  20  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31 
  32 /*
  33  * This source code is provided to illustrate the usage of a given feature
  34  * or technique and has been deliberately simplified. Additional steps
  35  * required for a production-quality application, such as security checks,
  36  * input validation and proper error handling, might not be present in
  37  * this sample code.
  38  */
  39 
  40 package comparator;
  41 
  42 import java.util.Comparator;
  43 
  44 class AlphaNumericStringComparator implements Comparator<String>
  45 {
  46     final Comparator<Character> charComparator;
  47 
  48     public AlphaNumericStringComparator() {
  49         this(Character::compare);
  50     }
  51 
  52     public AlphaNumericStringComparator(Comparator<Character> charComparator) {
  53         this.charComparator = charComparator;
  54     }
  55 
  56     /**
  57      * Counts how many consequtive characters in the string {@code o}
  58      * are digits, starting from the position {@code from}.
  59      */
  60     private int countDigits(String o, int from) {
  61         final int oLength = o.length();
  62         for (int i = from; ; ++i) {
  63             if (i == oLength || !Character.isDigit(o.charAt(i))) {
  64                 return (i - from);
  65             }
  66         }
  67     }
  68 
  69     @Override
  70     public int compare(String o1, String o2) {
  71         final int minLength = Integer.min(o1.length(), o2.length());
  72         int numStart1 = 0;
  73         int index = 0;
  74 
  75         // skip common prefix of the arguments
  76         while (index < minLength &&
  77                 charComparator.compare(o1.charAt(index),
  78                         o2.charAt(index)) == 0)
  79         {
  80             if (!Character.isDigit(o1.charAt(index++))) {
  81                 numStart1 = index;
  82             }
  83         }
  84 
  85         int numCount1 = index - numStart1;
  86         if (numCount1 > 0 ||
  87                 (index < minLength &&
  88                         Character.isDigit(o1.charAt(index)) &&
  89                         Character.isDigit(o2.charAt(index))))
  90         {
  91             // first different character is a digit
  92             int numCount2 = numCount1;
  93             int numStart2 = numStart1;
  94 
  95             numCount1 += countDigits(o1, index);
  96             numCount2 += countDigits(o2, index);
  97 
  98             int numCountWithZeros1 = numCount1;
  99             int numCountWithZeros2 = numCount2;
 100 
 101             while (numCount1 < numCount2) {
 102                 if (charComparator.compare(o2.charAt(numStart2), '0') != 0) {
 103                     return -1;
 104                 }
 105                 numStart2++;
 106                 numCount2--;
 107             }
 108 
 109             while (numCount2 < numCount1) {
 110                 if (charComparator.compare(o1.charAt(numStart1), '0') != 0) {
 111                     return 1;
 112                 }
 113                 numStart1++;
 114                 numCount1--;
 115             }
 116 
 117             // here numCount1 == numCount2;
 118             while (numCount1-- > 0) {
 119                 int res = charComparator.compare(o1.charAt(numStart1++),
 120                         o2.charAt(numStart2++));
 121                 if (res != 0) {
 122                     return res;
 123                 }
 124             }
 125 
 126             if (numCountWithZeros1 != numCountWithZeros2) {
 127                 return (numCountWithZeros1 < numCountWithZeros2) ? -1 : 1;
 128             }
 129 
 130         }
 131 
 132         // otherwise, compare literally
 133         for (;; ++index) {
 134             if (index < o1.length()) {
 135                 if (index < o2.length()) {
 136                     int res = charComparator.compare(o1.charAt(index),
 137                             o2.charAt(index));
 138                     if (res != 0) {
 139                         return res;
 140                     }
 141                 } else {
 142                     return 1;
 143                 }
 144             } else {
 145                 if (index < o2.length()) {
 146                     return -1;
 147                 }
 148                 return 0;
 149             }
 150         }
 151     }
 152 }