1 /* 2 * Copyright (c) 2012, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.util; 26 27 import java.io.Serializable; 28 import java.util.function.BinaryOperator; 29 import java.util.function.Function; 30 import java.util.function.ToDoubleFunction; 31 import java.util.function.ToIntFunction; 32 import java.util.function.ToLongFunction; 33 34 /** 35 * Package private supporting class for {@link Comparator}. 36 */ 37 class Comparators { 38 private Comparators() { 39 throw new AssertionError("no instances"); 40 } 41 42 /** 43 * Compares {@link Comparable} objects in natural order. 44 * 45 * @see Comparable 46 */ 47 enum NaturalOrderComparator implements Comparator<Comparable<Object>> { 48 INSTANCE; 49 50 @Override 51 public int compare(Comparable<Object> c1, Comparable<Object> c2) { 52 return c1.compareTo(c2); 53 } 54 55 @Override 56 public Comparator<Comparable<Object>> reversed() { 57 return Comparator.reverseOrder(); 58 } 59 } 60 61 /** 62 * Null-friendly comparators 63 */ 64 static final class NullComparator<T> implements Comparator<T>, Serializable { 65 private static final long serialVersionUID = -7569533591570686392L; 66 private final boolean nullFirst; 67 // if null, non-null Ts are considered equal 68 private final Comparator<T> real; 69 70 @SuppressWarnings("unchecked") 71 NullComparator(boolean nullFirst, Comparator<? super T> real) { 72 this.nullFirst = nullFirst; 73 this.real = (Comparator<T>) real; 74 } 75 76 @Override 77 public int compare(T a, T b) { 78 if (a == null) { 79 return (b == null) ? 0 : (nullFirst ? -1 : 1); 80 } else if (b == null) { 81 return nullFirst ? 1: -1; 82 } else { 83 return (real == null) ? 0 : real.compare(a, b); 84 } 85 } 86 87 @Override 88 public Comparator<T> thenComparing(Comparator<? super T> other) { 89 Objects.requireNonNull(other); 90 return new NullComparator<>(nullFirst, real == null ? other : real.thenComparing(other)); 91 } 92 93 @Override 94 public Comparator<T> reversed() { 95 return new NullComparator<>(!nullFirst, real == null ? null : real.reversed()); 96 } 97 } 98 99 /** 100 * Compares char sequences, taking into account their numeric part if one exists. 101 * 102 * @see Comparator.comparingNumerically() 103 * @see Comparator.comparingNumericallyLeadingZerosFirst() 104 */ 105 static class NumericComparator<T extends CharSequence> implements Comparator<T>, Serializable { 106 107 private static final long serialVersionUID = 0x77164074580FAC97L; 108 109 static final Comparator<?> INSTANCE_LEADING_ZEROS_FIRST_NATURAL = 110 new NumericComparator<CharSequence>(true) 111 { 112 @Override 113 @SuppressWarnings("unchecked") 114 public Comparator<CharSequence> reversed() { 115 return (Comparator<CharSequence>)INSTANCE_LEADING_ZEROS_FIRST_REVERSED; 116 } 117 }; 118 119 static final Comparator<?> INSTANCE_LEADING_ZEROS_FIRST_REVERSED = 120 new NumericComparator<CharSequence>(true) 121 { 122 @Override 123 public int compare(CharSequence o1, CharSequence o2) { 124 return super.compare(o2, o1); 125 } 126 127 @Override 128 @SuppressWarnings("unchecked") 129 public Comparator<CharSequence> reversed() { 130 return (Comparator<CharSequence>)INSTANCE_LEADING_ZEROS_FIRST_NATURAL; 131 } 132 }; 133 134 static final Comparator<?> INSTANCE_LEADING_ZEROS_LAST_NATURAL = 135 new NumericComparator<CharSequence>(false) 136 { 137 @Override 138 @SuppressWarnings("unchecked") 139 public Comparator<CharSequence> reversed() { 140 return (Comparator<CharSequence>)INSTANCE_LEADING_ZEROS_LAST_REVERSED; 141 } 142 }; 143 144 static final Comparator<?> INSTANCE_LEADING_ZEROS_LAST_REVERSED = 145 new NumericComparator<CharSequence>(false) 146 { 147 @Override 148 public int compare(CharSequence o1, CharSequence o2) { 149 return super.compare(o2, o1); 150 } 151 152 @Override 153 @SuppressWarnings("unchecked") 154 public Comparator<CharSequence> reversed() { 155 return (Comparator<CharSequence>)INSTANCE_LEADING_ZEROS_LAST_NATURAL; 156 } 157 }; 158 159 /** 160 * If true, the string representation of a number with 161 * more leading zeros will be treated as smaller. 162 * E.g.: "0001" < "001" < "1". 163 */ 164 private final boolean leadingZerosFirst; 165 166 /** 167 * Constructs a new comparator with possibility to specify 168 * how it should deal with leading zeros in numbers. 169 * 170 * @param leadingZerosFirst if {@code true}, numbers with 171 * more leading zeros are treated as smaller. 172 */ 173 private NumericComparator(boolean leadingZerosFirst) { 174 this.leadingZerosFirst = leadingZerosFirst; 175 } 176 177 /** 178 * Counts how many consequtive characters in the string {@code o} 179 * are digits, starting from the position {@code from}. 180 */ 181 private int countDigits(CharSequence o, int from) { 182 for (int i = from, len = o.length(); ; ++i) { 183 if (i == len || !Character.isDigit(o.charAt(i))) { 184 return i - from; 185 } 186 } 187 } 188 189 /** 190 * Checks if all {@code cnt} chars of the sequence {@code o}, 191 * starting with {@code pos} are zeros. 192 * 193 * @param pos position of the first digit of numeric part. 194 * @param cnt number of digits to check; must be > 0. 195 * 196 * @return {@code true} if the numeric part of the string {@code o} 197 * can be reduced in length by {@code cnt} without changing its 198 * numerical value. 199 */ 200 private boolean skipLeadingZeros(CharSequence o, int pos, int cnt) { 201 do { 202 if (Character.digit(o.charAt(pos++), 10) != 0) { 203 // Leading digit of numeric part of o isn't zero 204 return false; 205 } 206 } while (--cnt > 0); 207 return true; 208 } 209 210 @Override 211 public int compare(T o1, T o2) { 212 int minLen = Math.min(o1.length(), o2.length()); 213 int numStart1 = 0; 214 int index = 0; 215 int res0 = 0; 216 217 // Skip common prefix of the arguments 218 char ch; 219 while (index < minLen && 220 (res0 = Character.compare(ch = o1.charAt(index), 221 o2.charAt(index))) == 0) { 222 ++index; 223 if (!Character.isDigit(ch)) { 224 numStart1 = index; 225 } 226 } 227 228 int numLen1 = index - numStart1; 229 if (numLen1 > 0 || 230 (index < minLen && 231 Character.isDigit(o1.charAt(index)) && 232 Character.isDigit(o2.charAt(index)))) 233 { 234 // The difference is inside or at the boundary of 235 // numerical part 236 int numLen2 = numLen1; 237 int numStart2 = numStart1; 238 239 numLen1 += countDigits(o1, index); 240 numLen2 += countDigits(o2, index); 241 242 int diffNumLen = numLen2 - numLen1; 243 244 if (diffNumLen > 0) { 245 if (!skipLeadingZeros(o2, numStart2, diffNumLen)) { 246 // Length of numeric part of o2 is greater 247 return -1; 248 } 249 numStart2 += diffNumLen; 250 numLen2 = numLen1; 251 } else if (diffNumLen < 0) { 252 if (!skipLeadingZeros(o1, numStart1, -diffNumLen)) { 253 // Length of numeric part of o1 is greater 254 return 1; 255 } 256 numStart1 -= diffNumLen; 257 numLen1 = numLen2; 258 } 259 260 // Numeric parts are of the same length, so they can 261 // be compared literally 262 while (numLen1-- > 0) { 263 int res1 = Character.compare(o1.charAt(numStart1++), 264 o2.charAt(numStart2++)); 265 if (res1 != 0) { 266 return res1; 267 } 268 } 269 270 // Numeric parts are numerically equal 271 if (diffNumLen != 0) { 272 // If leadingZerosFirst == true, treat the number 273 // with more leading zeros as smaller 274 return (leadingZerosFirst ^ (diffNumLen > 0)) ? -1 : 1; 275 } 276 } 277 278 // Otherwise, compare literally 279 return (index < o1.length()) 280 ? ((index < o2.length()) ? res0 : 1) 281 : ((index < o2.length()) ? -1 : 0); 282 } 283 } 284 }