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 }