1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.util.Comparator; 13 14 import std.traits; 15 debug import hunt.logging.ConsoleLogger; 16 17 /** 18 * A comparison function, which imposes a <i>total ordering</i> on some 19 * collection of objects. Comparators can be passed to a sort method (such 20 * as {@link Collections#sort(List,Comparator) Collections.sort} or {@link 21 * Arrays#sort(Object[],Comparator) Arrays.sort}) to allow precise control 22 * over the sort order. Comparators can also be used to control the order of 23 * certain data structures (such as {@link SortedSet sorted sets} or {@link 24 * SortedMap sorted maps}), or to provide an ordering for collections of 25 * objects that don't have a {@link Comparable natural ordering}.<p> 26 * 27 * The ordering imposed by a comparator <tt>c</tt> on a set of elements 28 * <tt>S</tt> is said to be <i>consistent with equals</i> if and only if 29 * <tt>c.compare(e1, e2)==0</tt> has the same bool value as 30 * <tt>e1.equals(e2)</tt> for every <tt>e1</tt> and <tt>e2</tt> in 31 * <tt>S</tt>.<p> 32 * 33 * Caution should be exercised when using a comparator capable of imposing an 34 * ordering inconsistent with equals to order a sorted set (or sorted map). 35 * Suppose a sorted set (or sorted map) with an explicit comparator <tt>c</tt> 36 * is used with elements (or keys) drawn from a set <tt>S</tt>. If the 37 * ordering imposed by <tt>c</tt> on <tt>S</tt> is inconsistent with equals, 38 * the sorted set (or sorted map) will behave "strangely." In particular the 39 * sorted set (or sorted map) will violate the general contract for set (or 40 * map), which is defined in terms of <tt>equals</tt>.<p> 41 * 42 * For example, suppose one adds two elements {@code a} and {@code b} such that 43 * {@code (a.equals(b) && c.compare(a, b) != 0)} 44 * to an empty {@code TreeSet} with comparator {@code c}. 45 * The second {@code add} operation will return 46 * true (and the size of the tree set will increase) because {@code a} and 47 * {@code b} are not equivalent from the tree set's perspective, even though 48 * this is contrary to the specification of the 49 * {@link Set#add Set.add} method.<p> 50 * 51 * Note: It is generally a good idea for comparators to also implement 52 * <tt>java.io.Serializable</tt>, as they may be used as ordering methods in 53 * serializable data structures (like {@link TreeSet}, {@link TreeMap}). In 54 * order for the data structure to serialize successfully, the comparator (if 55 * provided) must implement <tt>Serializable</tt>.<p> 56 * 57 * For the mathematically inclined, the <i>relation</i> that defines the 58 * <i>imposed ordering</i> that a given comparator <tt>c</tt> imposes on a 59 * given set of objects <tt>S</tt> is:<pre> 60 * {(x, y) such that c.compare(x, y) <= 0}. 61 * </pre> The <i>quotient</i> for this total order is:<pre> 62 * {(x, y) such that c.compare(x, y) == 0}. 63 * </pre> 64 * 65 * It follows immediately from the contract for <tt>compare</tt> that the 66 * quotient is an <i>equivalence relation</i> on <tt>S</tt>, and that the 67 * imposed ordering is a <i>total order</i> on <tt>S</tt>. When we say that 68 * the ordering imposed by <tt>c</tt> on <tt>S</tt> is <i>consistent with 69 * equals</i>, we mean that the quotient for the ordering is the equivalence 70 * relation defined by the objects' {@link Object#equals(Object) 71 * equals(Object)} method(s):<pre> 72 * {(x, y) such that x.equals(y)}. </pre> 73 * 74 * <p>Unlike {@code Comparable}, a comparator may optionally permit 75 * comparison of null arguments, while maintaining the requirements for 76 * an equivalence relation. 77 * 78 * <p>This interface is a member of the 79 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 80 * Java Collections Framework</a>. 81 * 82 * @param (T) the type of objects that may be compared by this comparator 83 * 84 * @author Josh Bloch 85 * @author Neal Gafter 86 * @see Comparable 87 * @see java.io.Serializable 88 * @since 1.2 89 */ 90 interface Comparator(T) { 91 /** 92 * Compares its two arguments for order. Returns a negative integer, 93 * zero, or a positive integer as the first argument is less than, equal 94 * to, or greater than the second.<p> 95 * 96 * In the foregoing description, the notation 97 * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical 98 * <i>signum</i> function, which is defined to return one of <tt>-1</tt>, 99 * <tt>0</tt>, or <tt>1</tt> according to whether the value of 100 * <i>expression</i> is negative, zero or positive.<p> 101 * 102 * The implementor must ensure that <tt>sgn(compare(x, y)) == 103 * -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>. (This 104 * implies that <tt>compare(x, y)</tt> must throw an exception if and only 105 * if <tt>compare(y, x)</tt> throws an exception.)<p> 106 * 107 * The implementor must also ensure that the relation is transitive: 108 * <tt>((compare(x, y)>0) && (compare(y, z)>0))</tt> implies 109 * <tt>compare(x, z)>0</tt>.<p> 110 * 111 * Finally, the implementor must ensure that <tt>compare(x, y)==0</tt> 112 * implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all 113 * <tt>z</tt>.<p> 114 * 115 * It is generally the case, but <i>not</i> strictly required that 116 * <tt>(compare(x, y)==0) == (x.equals(y))</tt>. Generally speaking, 117 * any comparator that violates this condition should clearly indicate 118 * this fact. The recommended language is "Note: this comparator 119 * imposes orderings that are inconsistent with equals." 120 * 121 * @param o1 the first object to be compared. 122 * @param o2 the second object to be compared. 123 * @return a negative integer, zero, or a positive integer as the 124 * first argument is less than, equal to, or greater than the 125 * second. 126 * @throws NullPointerException if an argument is null and this 127 * comparator does not permit null arguments 128 * @throws ClassCastException if the arguments' types prevent them from 129 * being compared by this comparator. 130 */ 131 int compare(T o1, T o2) nothrow; 132 133 // /** 134 // * Indicates whether some other object is "equal to" this 135 // * comparator. This method must obey the general contract of 136 // * {@link Object#equals(Object)}. Additionally, this method can return 137 // * <tt>true</tt> <i>only</i> if the specified object is also a comparator 138 // * and it imposes the same ordering as this comparator. Thus, 139 // * <code>comp1.equals(comp2)</code> implies that <tt>sgn(comp1.compare(o1, 140 // * o2))==sgn(comp2.compare(o1, o2))</tt> for every object reference 141 // * <tt>o1</tt> and <tt>o2</tt>.<p> 142 // * 143 // * Note that it is <i>always</i> safe <i>not</i> to override 144 // * <tt>Object.equals(Object)</tt>. However, overriding this method may, 145 // * in some cases, improve performance by allowing programs to determine 146 // * that two distinct comparators impose the same order. 147 // * 148 // * @param obj the reference object with which to compare. 149 // * @return <code>true</code> only if the specified object is also 150 // * a comparator and it imposes the same ordering as this 151 // * comparator. 152 // * @see Object#equals(Object) 153 // * @see Object#hashCode() 154 // */ 155 // bool equals(Object obj); 156 157 // /** 158 // * Returns a comparator that imposes the reverse ordering of this 159 // * comparator. 160 // * 161 // * @return a comparator that imposes the reverse ordering of this 162 // * comparator. 163 // * @since 1.8 164 // */ 165 // Comparator!(T) reversed() { 166 // return Collections.reverseOrder(this); 167 // } 168 169 // /** 170 // * Returns a lexicographic-order comparator with another comparator. 171 // * If this {@code Comparator} considers two elements equal, i.e. 172 // * {@code compare(a, b) == 0}, {@code other} is used to determine the order. 173 // * 174 // * <p>The returned comparator is serializable if the specified comparator 175 // * is also serializable. 176 // * 177 // * @apiNote 178 // * For example, to sort a collection of {@code string} based on the length 179 // * and then case-insensitive natural ordering, the comparator can be 180 // * composed using following code, 181 // * 182 // * <pre>{@code 183 // * Comparator<string> cmp = Comparator.comparingInt(string::length) 184 // * .thenComparing(string.CASE_INSENSITIVE_ORDER); 185 // * }</pre> 186 // * 187 // * @param other the other comparator to be used when this comparator 188 // * compares two objects that are equal. 189 // * @return a lexicographic-order comparator composed of this and then the 190 // * other comparator 191 // * @throws NullPointerException if the argument is null. 192 // * @since 1.8 193 // */ 194 // Comparator!(T) thenComparing(Comparator<T> other) { 195 // Objects.requireNonNull(other); 196 // return (Comparator!(T) & Serializable) (c1, c2) -> { 197 // int res = compare(c1, c2); 198 // return (res != 0) ? res : other.compare(c1, c2); 199 // }; 200 // } 201 202 // /** 203 // * Returns a lexicographic-order comparator with a function that 204 // * extracts a key to be compared with the given {@code Comparator}. 205 // * 206 // * @implSpec This implementation behaves as if {@code 207 // * thenComparing(comparing(keyExtractor, cmp))}. 208 // * 209 // * @param !(U) the type of the sort key 210 // * @param keyExtractor the function used to extract the sort key 211 // * @param keyComparator the {@code Comparator} used to compare the sort key 212 // * @return a lexicographic-order comparator composed of this comparator 213 // * and then comparing on the key extracted by the keyExtractor function 214 // * @throws NullPointerException if either argument is null. 215 // * @see #comparing(Function, Comparator) 216 // * @see #thenComparing(Comparator) 217 // * @since 1.8 218 // */ 219 // !(U) Comparator!(T) thenComparing( 220 // Function<T, U> keyExtractor, 221 // Comparator<U> keyComparator) 222 // { 223 // return thenComparing(comparing(keyExtractor, keyComparator)); 224 // } 225 226 // /** 227 // * Returns a lexicographic-order comparator with a function that 228 // * extracts a {@code Comparable} sort key. 229 // * 230 // * @implSpec This implementation behaves as if {@code 231 // * thenComparing(comparing(keyExtractor))}. 232 // * 233 // * @param !(U) the type of the {@link Comparable} sort key 234 // * @param keyExtractor the function used to extract the {@link 235 // * Comparable} sort key 236 // * @return a lexicographic-order comparator composed of this and then the 237 // * {@link Comparable} sort key. 238 // * @throws NullPointerException if the argument is null. 239 // * @see #comparing(Function) 240 // * @see #thenComparing(Comparator) 241 // * @since 1.8 242 // */ 243 // <U extends Comparable<U>> Comparator!(T) thenComparing( 244 // Function<T, U> keyExtractor) 245 // { 246 // return thenComparing(comparing(keyExtractor)); 247 // } 248 249 // /** 250 // * Returns a lexicographic-order comparator with a function that 251 // * extracts a {@code int} sort key. 252 // * 253 // * @implSpec This implementation behaves as if {@code 254 // * thenComparing(comparingInt(keyExtractor))}. 255 // * 256 // * @param keyExtractor the function used to extract the integer sort key 257 // * @return a lexicographic-order comparator composed of this and then the 258 // * {@code int} sort key 259 // * @throws NullPointerException if the argument is null. 260 // * @see #comparingInt(ToIntFunction) 261 // * @see #thenComparing(Comparator) 262 // * @since 1.8 263 // */ 264 // Comparator!(T) thenComparingInt(ToIntFunction<T> keyExtractor) { 265 // return thenComparing(comparingInt(keyExtractor)); 266 // } 267 268 // /** 269 // * Returns a lexicographic-order comparator with a function that 270 // * extracts a {@code long} sort key. 271 // * 272 // * @implSpec This implementation behaves as if {@code 273 // * thenComparing(comparingLong(keyExtractor))}. 274 // * 275 // * @param keyExtractor the function used to extract the long sort key 276 // * @return a lexicographic-order comparator composed of this and then the 277 // * {@code long} sort key 278 // * @throws NullPointerException if the argument is null. 279 // * @see #comparingLong(ToLongFunction) 280 // * @see #thenComparing(Comparator) 281 // * @since 1.8 282 // */ 283 // Comparator!(T) thenComparingLong(ToLongFunction<T> keyExtractor) { 284 // return thenComparing(comparingLong(keyExtractor)); 285 // } 286 287 // /** 288 // * Returns a lexicographic-order comparator with a function that 289 // * extracts a {@code double} sort key. 290 // * 291 // * @implSpec This implementation behaves as if {@code 292 // * thenComparing(comparingDouble(keyExtractor))}. 293 // * 294 // * @param keyExtractor the function used to extract the double sort key 295 // * @return a lexicographic-order comparator composed of this and then the 296 // * {@code double} sort key 297 // * @throws NullPointerException if the argument is null. 298 // * @see #comparingDouble(ToDoubleFunction) 299 // * @see #thenComparing(Comparator) 300 // * @since 1.8 301 // */ 302 // Comparator!(T) thenComparingDouble(ToDoubleFunction<T> keyExtractor) { 303 // return thenComparing(comparingDouble(keyExtractor)); 304 // } 305 306 // /** 307 // * Returns a comparator that imposes the reverse of the <em>natural 308 // * ordering</em>. 309 // * 310 // * <p>The returned comparator is serializable and throws {@link 311 // * NullPointerException} when comparing {@code null}. 312 // * 313 // * @param !(T) the {@link Comparable} type of element to be compared 314 // * @return a comparator that imposes the reverse of the <i>natural 315 // * ordering</i> on {@code Comparable} objects. 316 // * @see Comparable 317 // * @since 1.8 318 // */ 319 // static <T extends Comparable<T>> Comparator!(T) reverseOrder() { 320 // return Collections.reverseOrder(); 321 // } 322 323 // /** 324 // * Returns a comparator that compares {@link Comparable} objects in natural 325 // * order. 326 // * 327 // * <p>The returned comparator is serializable and throws {@link 328 // * NullPointerException} when comparing {@code null}. 329 // * 330 // * @param !(T) the {@link Comparable} type of element to be compared 331 // * @return a comparator that imposes the <i>natural ordering</i> on {@code 332 // * Comparable} objects. 333 // * @see Comparable 334 // * @since 1.8 335 // */ 336 // @SuppressWarnings("unchecked") 337 // static <T extends Comparable<T>> Comparator!(T) naturalOrder() { 338 // return (Comparator!(T)) Comparators.NaturalOrderComparator.INSTANCE; 339 // } 340 341 // /** 342 // * Returns a null-friendly comparator that considers {@code null} to be 343 // * less than non-null. When both are {@code null}, they are considered 344 // * equal. If both are non-null, the specified {@code Comparator} is used 345 // * to determine the order. If the specified comparator is {@code null}, 346 // * then the returned comparator considers all non-null values to be equal. 347 // * 348 // * <p>The returned comparator is serializable if the specified comparator 349 // * is serializable. 350 // * 351 // * @param !(T) the type of the elements to be compared 352 // * @param comparator a {@code Comparator} for comparing non-null values 353 // * @return a comparator that considers {@code null} to be less than 354 // * non-null, and compares non-null objects with the supplied 355 // * {@code Comparator}. 356 // * @since 1.8 357 // */ 358 // static !(T) Comparator!(T) nullsFirst(Comparator<T> comparator) { 359 // return new Comparators.NullComparator<>(true, comparator); 360 // } 361 362 // /** 363 // * Returns a null-friendly comparator that considers {@code null} to be 364 // * greater than non-null. When both are {@code null}, they are considered 365 // * equal. If both are non-null, the specified {@code Comparator} is used 366 // * to determine the order. If the specified comparator is {@code null}, 367 // * then the returned comparator considers all non-null values to be equal. 368 // * 369 // * <p>The returned comparator is serializable if the specified comparator 370 // * is serializable. 371 // * 372 // * @param !(T) the type of the elements to be compared 373 // * @param comparator a {@code Comparator} for comparing non-null values 374 // * @return a comparator that considers {@code null} to be greater than 375 // * non-null, and compares non-null objects with the supplied 376 // * {@code Comparator}. 377 // * @since 1.8 378 // */ 379 // static !(T) Comparator!(T) nullsLast(Comparator<T> comparator) { 380 // return new Comparators.NullComparator<>(false, comparator); 381 // } 382 383 // /** 384 // * Accepts a function that extracts a sort key from a type {@code T}, and 385 // * returns a {@code Comparator!(T)} that compares by that sort key using 386 // * the specified {@link Comparator}. 387 // * 388 // * <p>The returned comparator is serializable if the specified function 389 // * and comparator are both serializable. 390 // * 391 // * @apiNote 392 // * For example, to obtain a {@code Comparator} that compares {@code 393 // * Person} objects by their last name ignoring case differences, 394 // * 395 // * <pre>{@code 396 // * Comparator<Person> cmp = Comparator.comparing( 397 // * Person::getLastName, 398 // * string.CASE_INSENSITIVE_ORDER); 399 // * }</pre> 400 // * 401 // * @param !(T) the type of element to be compared 402 // * @param !(U) the type of the sort key 403 // * @param keyExtractor the function used to extract the sort key 404 // * @param keyComparator the {@code Comparator} used to compare the sort key 405 // * @return a comparator that compares by an extracted key using the 406 // * specified {@code Comparator} 407 // * @throws NullPointerException if either argument is null 408 // * @since 1.8 409 // */ 410 // static <T, U> Comparator!(T) comparing( 411 // Function<T, U> keyExtractor, 412 // Comparator<U> keyComparator) 413 // { 414 // Objects.requireNonNull(keyExtractor); 415 // Objects.requireNonNull(keyComparator); 416 // return (Comparator!(T) & Serializable) 417 // (c1, c2) -> keyComparator.compare(keyExtractor.apply(c1), 418 // keyExtractor.apply(c2)); 419 // } 420 421 // /** 422 // * Accepts a function that extracts a {@link java.lang.Comparable 423 // * Comparable} sort key from a type {@code T}, and returns a {@code 424 // * Comparator!(T)} that compares by that sort key. 425 // * 426 // * <p>The returned comparator is serializable if the specified function 427 // * is also serializable. 428 // * 429 // * @apiNote 430 // * For example, to obtain a {@code Comparator} that compares {@code 431 // * Person} objects by their last name, 432 // * 433 // * <pre>{@code 434 // * Comparator<Person> byLastName = Comparator.comparing(Person::getLastName); 435 // * }</pre> 436 // * 437 // * @param !(T) the type of element to be compared 438 // * @param !(U) the type of the {@code Comparable} sort key 439 // * @param keyExtractor the function used to extract the {@link 440 // * Comparable} sort key 441 // * @return a comparator that compares by an extracted key 442 // * @throws NullPointerException if the argument is null 443 // * @since 1.8 444 // */ 445 // static <T, U extends Comparable<U>> Comparator!(T) comparing( 446 // Function<T, U> keyExtractor) 447 // { 448 // Objects.requireNonNull(keyExtractor); 449 // return (Comparator!(T) & Serializable) 450 // (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2)); 451 // } 452 453 // /** 454 // * Accepts a function that extracts an {@code int} sort key from a type 455 // * {@code T}, and returns a {@code Comparator!(T)} that compares by that 456 // * sort key. 457 // * 458 // * <p>The returned comparator is serializable if the specified function 459 // * is also serializable. 460 // * 461 // * @param !(T) the type of element to be compared 462 // * @param keyExtractor the function used to extract the integer sort key 463 // * @return a comparator that compares by an extracted key 464 // * @see #comparing(Function) 465 // * @throws NullPointerException if the argument is null 466 // * @since 1.8 467 // */ 468 // static !(T) Comparator!(T) comparingInt(ToIntFunction<T> keyExtractor) { 469 // Objects.requireNonNull(keyExtractor); 470 // return (Comparator!(T) & Serializable) 471 // (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2)); 472 // } 473 474 // /** 475 // * Accepts a function that extracts a {@code long} sort key from a type 476 // * {@code T}, and returns a {@code Comparator!(T)} that compares by that 477 // * sort key. 478 // * 479 // * <p>The returned comparator is serializable if the specified function is 480 // * also serializable. 481 // * 482 // * @param !(T) the type of element to be compared 483 // * @param keyExtractor the function used to extract the long sort key 484 // * @return a comparator that compares by an extracted key 485 // * @see #comparing(Function) 486 // * @throws NullPointerException if the argument is null 487 // * @since 1.8 488 // */ 489 // static !(T) Comparator!(T) comparingLong(ToLongFunction<T> keyExtractor) { 490 // Objects.requireNonNull(keyExtractor); 491 // return (Comparator!(T) & Serializable) 492 // (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2)); 493 // } 494 495 // /** 496 // * Accepts a function that extracts a {@code double} sort key from a type 497 // * {@code T}, and returns a {@code Comparator!(T)} that compares by that 498 // * sort key. 499 // * 500 // * <p>The returned comparator is serializable if the specified function 501 // * is also serializable. 502 // * 503 // * @param !(T) the type of element to be compared 504 // * @param keyExtractor the function used to extract the double sort key 505 // * @return a comparator that compares by an extracted key 506 // * @see #comparing(Function) 507 // * @throws NullPointerException if the argument is null 508 // * @since 1.8 509 // */ 510 // static!(T) Comparator!(T) comparingDouble(ToDoubleFunction<T> keyExtractor) { 511 // Objects.requireNonNull(keyExtractor); 512 // return (Comparator!(T) & Serializable) 513 // (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2)); 514 // } 515 } 516 517 518 int compare(T)(T x, T y) nothrow if(isOrderingComparable!(T)) { 519 try { 520 return (x < y) ? -1 : ((x == y) ? 0 : 1); 521 } catch(Exception ex) { 522 debug warning(ex.msg); 523 return false; 524 } 525 } 526 527 // FIXME: Needing refactor or cleanup -@zxp at 12/30/2018, 9:43:22 AM 528 // opCmp in a class, struct or interface should be nothrow. 529 bool lessThan(T)(T a, T b) nothrow if(isOrderingComparable!(T)) { 530 try { 531 return a < b; 532 } catch(Exception ex) { 533 debug warning(ex.msg); 534 return false; 535 } 536 } 537 538 bool greaterthan(T)(T a, T b) nothrow if(isOrderingComparable!(T)) { 539 try { 540 return a > b; 541 } catch(Exception ex) { 542 debug warning(ex.msg); 543 return false; 544 } 545 }