001 package fj.pre; 002 003 import fj.Function; 004 import fj.F; 005 import fj.F2; 006 import fj.P; 007 import fj.P1; 008 import fj.P2; 009 import fj.P3; 010 import fj.Unit; 011 import static fj.FW.$; 012 import static fj.Function.compose; 013 import static fj.Function.curry; 014 import fj.data.Array; 015 import fj.data.Either; 016 import fj.data.List; 017 import fj.data.Natural; 018 import fj.data.NonEmptyList; 019 import fj.data.Option; 020 import fj.data.Set; 021 import fj.data.Stream; 022 import fj.data.Validation; 023 import static fj.pre.Ordering.*; 024 025 import java.math.BigDecimal; 026 import java.math.BigInteger; 027 028 /** 029 * Tests for ordering between two objects. 030 * 031 * @version %build.number%<br> 032 * <ul> 033 * <li>$LastChangedRevision: 159 $</li> 034 * <li>$LastChangedDate: 2009-05-31 17:41:43 +1000 (Sun, 31 May 2009) $</li> 035 * </ul> 036 */ 037 public final class Ord<A> { 038 private final F<A, F<A, Ordering>> f; 039 040 private Ord(final F<A, F<A, Ordering>> f) { 041 this.f = f; 042 } 043 044 /** 045 * First-class ordering. 046 * 047 * @return A function that returns an ordering for its arguments. 048 */ 049 public F<A, F<A, Ordering>> compare() { 050 return f; 051 } 052 053 /** 054 * Returns an ordering for the given arguments. 055 * 056 * @param a1 An instance to compare for ordering to another. 057 * @param a2 An instance to compare for ordering to another. 058 * @return An ordering for the given arguments. 059 */ 060 public Ordering compare(final A a1, final A a2) { 061 return f.f(a1).f(a2); 062 } 063 064 /** 065 * Returns <code>true</code> if the given arguments are equal, <code>false</code> otherwise. 066 * 067 * @param a1 An instance to compare for equality to another. 068 * @param a2 An instance to compare for equality to another. 069 * @return <code>true</code> if the given arguments are equal, <code>false</code> otherwise. 070 */ 071 public boolean eq(final A a1, final A a2) { 072 return compare(a1, a2) == EQ; 073 } 074 075 /** 076 * Returns an <code>Equal</code> for this order. 077 * 078 * @return An <code>Equal</code> for this order. 079 */ 080 public Equal<A> equal() { 081 return Equal.equal(curry(new F2<A, A, Boolean>() { 082 public Boolean f(final A a1, final A a2) { 083 return eq(a1, a2); 084 } 085 })); 086 } 087 088 /** 089 * Maps the given function across this ord as a contra-variant functor. 090 * 091 * @param f The function to map. 092 * @return A new ord. 093 */ 094 public <B> Ord<B> comap(final F<B, A> f) { 095 return ord($(f).<Ordering>andThen_().o(this.f).o(f)); 096 } 097 098 /** 099 * Returns <code>true</code> if the first given argument is less than the second given argument, 100 * <code>false</code> otherwise. 101 * 102 * @param a1 An instance to compare for ordering to another. 103 * @param a2 An instance to compare for ordering to another. 104 * @return <code>true</code> if the first given argument is less than the second given argument, 105 * <code>false</code> otherwise. 106 */ 107 public boolean isLessThan(final A a1, final A a2) { 108 return compare(a1, a2) == LT; 109 } 110 111 /** 112 * Returns <code>true</code> if the first given argument is greater than the second given 113 * argument, <code>false</code> otherwise. 114 * 115 * @param a1 An instance to compare for ordering to another. 116 * @param a2 An instance to compare for ordering to another. 117 * @return <code>true</code> if the first given argument is greater than the second given 118 * argument, <code>false</code> otherwise. 119 */ 120 public boolean isGreaterThan(final A a1, final A a2) { 121 return compare(a1, a2) == GT; 122 } 123 124 /** 125 * Returns a function that returns true if its argument is less than the argument to this method. 126 * 127 * @param a A value to compare against. 128 * @return A function that returns true if its argument is less than the argument to this method. 129 */ 130 public F<A, Boolean> isLessThan(final A a) { 131 return new F<A, Boolean>() { 132 public Boolean f(final A a2) { 133 return compare(a2, a) == LT; 134 } 135 }; 136 } 137 138 /** 139 * Returns a function that returns true if its argument is greater than than the argument to this method. 140 * 141 * @param a A value to compare against. 142 * @return A function that returns true if its argument is greater than the argument to this method. 143 */ 144 public F<A, Boolean> isGreaterThan(final A a) { 145 return new F<A, Boolean>() { 146 public Boolean f(final A a2) { 147 return compare(a2, a) == GT; 148 } 149 }; 150 } 151 152 /** 153 * Returns the greater of its two arguments. 154 * 155 * @param a1 A value to compare with another. 156 * @param a2 A value to compare with another. 157 * @return The greater of the two values. 158 */ 159 public A max(final A a1, final A a2) { 160 return isGreaterThan(a1, a2) ? a1 : a2; 161 } 162 163 164 /** 165 * Returns the lesser of its two arguments. 166 * 167 * @param a1 A value to compare with another. 168 * @param a2 A value to compare with another. 169 * @return The lesser of the two values. 170 */ 171 public A min(final A a1, final A a2) { 172 return isLessThan(a1, a2) ? a1 : a2; 173 } 174 175 /** 176 * A function that returns the greater of its two arguments. 177 */ 178 public F<A, F<A, A>> max = curry(new F2<A, A, A>() { 179 public A f(final A a, final A a1) { 180 return max(a, a1); 181 } 182 }); 183 184 /** 185 * A function that returns the lesser of its two arguments. 186 */ 187 public F<A, F<A, A>> min = curry(new F2<A, A, A>() { 188 public A f(final A a, final A a1) { 189 return min(a, a1); 190 } 191 }); 192 193 /** 194 * Returns an order instance that uses the given equality test and ordering function. 195 * 196 * @param f The order function. 197 * @return An order instance. 198 */ 199 public static <A> Ord<A> ord(final F<A, F<A, Ordering>> f) { 200 return new Ord<A>(f); 201 } 202 203 /** 204 * An order instance for the <code>boolean</code> type. 205 */ 206 public static final Ord<Boolean> booleanOrd = new Ord<Boolean>( 207 new F<Boolean, F<Boolean, Ordering>>() { 208 public F<Boolean, Ordering> f(final Boolean a1) { 209 return new F<Boolean, Ordering>() { 210 public Ordering f(final Boolean a2) { 211 final int x = a1.compareTo(a2); 212 return x < 0 ? LT : x == 0 ? EQ : GT; 213 } 214 }; 215 } 216 }); 217 218 /** 219 * An order instance for the <code>byte</code> type. 220 */ 221 public static final Ord<Byte> byteOrd = new Ord<Byte>( 222 new F<Byte, F<Byte, Ordering>>() { 223 public F<Byte, Ordering> f(final Byte a1) { 224 return new F<Byte, Ordering>() { 225 public Ordering f(final Byte a2) { 226 final int x = a1.compareTo(a2); 227 return x < 0 ? LT : x == 0 ? EQ : GT; 228 } 229 }; 230 } 231 }); 232 233 /** 234 * An order instance for the <code>char</code> type. 235 */ 236 public static final Ord<Character> charOrd = new Ord<Character>( 237 new F<Character, F<Character, Ordering>>() { 238 public F<Character, Ordering> f(final Character a1) { 239 return new F<Character, Ordering>() { 240 public Ordering f(final Character a2) { 241 final int x = a1.compareTo(a2); 242 return x < 0 ? LT : x == 0 ? EQ : GT; 243 } 244 }; 245 } 246 }); 247 248 /** 249 * An order instance for the <code>double</code> type. 250 */ 251 public static final Ord<Double> doubleOrd = new Ord<Double>( 252 new F<Double, F<Double, Ordering>>() { 253 public F<Double, Ordering> f(final Double a1) { 254 return new F<Double, Ordering>() { 255 public Ordering f(final Double a2) { 256 final int x = a1.compareTo(a2); 257 return x < 0 ? LT : x == 0 ? EQ : GT; 258 } 259 }; 260 } 261 }); 262 263 /** 264 * An order instance for the <code>float</code> type. 265 */ 266 public static final Ord<Float> floatOrd = new Ord<Float>( 267 new F<Float, F<Float, Ordering>>() { 268 public F<Float, Ordering> f(final Float a1) { 269 return new F<Float, Ordering>() { 270 public Ordering f(final Float a2) { 271 final int x = a1.compareTo(a2); 272 return x < 0 ? LT : x == 0 ? EQ : GT; 273 } 274 }; 275 } 276 }); 277 278 /** 279 * An order instance for the <code>int</code> type. 280 */ 281 public static final Ord<Integer> intOrd = new Ord<Integer>( 282 new F<Integer, F<Integer, Ordering>>() { 283 public F<Integer, Ordering> f(final Integer a1) { 284 return new F<Integer, Ordering>() { 285 public Ordering f(final Integer a2) { 286 final int x = a1.compareTo(a2); 287 return x < 0 ? LT : x == 0 ? EQ : GT; 288 } 289 }; 290 } 291 }); 292 293 /** 294 * An order instance for the <code>BigInteger</code> type. 295 */ 296 public static final Ord<BigInteger> bigintOrd = new Ord<BigInteger>( 297 new F<BigInteger, F<BigInteger, Ordering>>() { 298 public F<BigInteger, Ordering> f(final BigInteger a1) { 299 return new F<BigInteger, Ordering>() { 300 public Ordering f(final BigInteger a2) { 301 final int x = a1.compareTo(a2); 302 return x < 0 ? LT : x == 0 ? EQ : GT; 303 } 304 }; 305 } 306 }); 307 308 /** 309 * An order instance for the <code>BigDecimal</code> type. 310 */ 311 public static final Ord<BigDecimal> bigdecimalOrd = new Ord<BigDecimal>( 312 new F<BigDecimal, F<BigDecimal, Ordering>>() { 313 public F<BigDecimal, Ordering> f(final BigDecimal a1) { 314 return new F<BigDecimal, Ordering>() { 315 public Ordering f(final BigDecimal a2) { 316 final int x = a1.compareTo(a2); 317 return x < 0 ? LT : x == 0 ? EQ : GT; 318 } 319 }; 320 } 321 }); 322 323 /** 324 * An order instance for the <code>long</code> type. 325 */ 326 public static final Ord<Long> longOrd = new Ord<Long>( 327 new F<Long, F<Long, Ordering>>() { 328 public F<Long, Ordering> f(final Long a1) { 329 return new F<Long, Ordering>() { 330 public Ordering f(final Long a2) { 331 final int x = a1.compareTo(a2); 332 return x < 0 ? LT : x == 0 ? EQ : GT; 333 } 334 }; 335 } 336 }); 337 338 /** 339 * An order instance for the <code>short</code> type. 340 */ 341 public static final Ord<Short> shortOrd = new Ord<Short>( 342 new F<Short, F<Short, Ordering>>() { 343 public F<Short, Ordering> f(final Short a1) { 344 return new F<Short, Ordering>() { 345 public Ordering f(final Short a2) { 346 final int x = a1.compareTo(a2); 347 return x < 0 ? LT : x == 0 ? EQ : GT; 348 } 349 }; 350 } 351 }); 352 353 /** 354 * An order instance for the {@link Ordering} type. 355 */ 356 public static final Ord<Ordering> orderingOrd = new Ord<Ordering>(curry(new F2<Ordering, Ordering, Ordering>() { 357 public Ordering f(final Ordering o1, final Ordering o2) { 358 return o1 == o2 ? 359 EQ : 360 o1 == LT ? 361 LT : 362 o2 == LT ? 363 GT : 364 o1 == EQ ? 365 LT : 366 GT; 367 } 368 })); 369 370 /** 371 * An order instance for the {@link String} type. 372 */ 373 public static final Ord<String> stringOrd = new Ord<String>( 374 new F<String, F<String, Ordering>>() { 375 public F<String, Ordering> f(final String a1) { 376 return new F<String, Ordering>() { 377 public Ordering f(final String a2) { 378 final int x = a1.compareTo(a2); 379 return x < 0 ? LT : x == 0 ? EQ : GT; 380 } 381 }; 382 } 383 }); 384 385 /** 386 * An order instance for the {@link StringBuffer} type. 387 */ 388 public static final Ord<StringBuffer> stringBufferOrd = 389 new Ord<StringBuffer>(new F<StringBuffer, F<StringBuffer, Ordering>>() { 390 public F<StringBuffer, Ordering> f(final StringBuffer a1) { 391 return new F<StringBuffer, Ordering>() { 392 public Ordering f(final StringBuffer a2) { 393 return stringOrd.compare(a1.toString(), a2.toString()); 394 } 395 }; 396 } 397 }); 398 399 /** 400 * An order instance for the {@link StringBuffer} type. 401 */ 402 public static final Ord<StringBuilder> stringBuilderOrd = 403 new Ord<StringBuilder>(new F<StringBuilder, F<StringBuilder, Ordering>>() { 404 public F<StringBuilder, Ordering> f(final StringBuilder a1) { 405 return new F<StringBuilder, Ordering>() { 406 public Ordering f(final StringBuilder a2) { 407 return stringOrd.compare(a1.toString(), a2.toString()); 408 } 409 }; 410 } 411 }); 412 413 /** 414 * An order instance for the {@link Option} type. 415 * 416 * @param oa Order across the element of the option. 417 * @return An order instance for the {@link Option} type. 418 */ 419 public static <A> Ord<Option<A>> optionOrd(final Ord<A> oa) { 420 return new Ord<Option<A>>(new F<Option<A>, F<Option<A>, Ordering>>() { 421 public F<Option<A>, Ordering> f(final Option<A> o1) { 422 return new F<Option<A>, Ordering>() { 423 public Ordering f(final Option<A> o2) { 424 return o1.isNone() ? 425 o2.isNone() ? 426 EQ : 427 LT : 428 o2.isNone() ? 429 GT : 430 oa.f.f(o1.some()).f(o2.some()); 431 } 432 }; 433 } 434 }); 435 } 436 437 /** 438 * An order instance for the {@link Either} type. 439 * 440 * @param oa Order across the left side of {@link Either}. 441 * @param ob Order across the right side of {@link Either}. 442 * @return An order instance for the {@link Either} type. 443 */ 444 public static <A, B> Ord<Either<A, B>> eitherOrd(final Ord<A> oa, final Ord<B> ob) { 445 return new Ord<Either<A, B>>(new F<Either<A, B>, F<Either<A, B>, Ordering>>() { 446 public F<Either<A, B>, Ordering> f(final Either<A, B> e1) { 447 return new F<Either<A, B>, Ordering>() { 448 public Ordering f(final Either<A, B> e2) { 449 return e1.isLeft() ? 450 e2.isLeft() ? 451 oa.f.f(e1.left().value()).f(e2.left().value()) : 452 LT : 453 e2.isLeft() ? 454 GT : 455 ob.f.f(e1.right().value()).f(e2.right().value()); 456 } 457 }; 458 } 459 }); 460 } 461 462 /** 463 * An order instance for the {@link Validation} type. 464 * 465 * @param oa Order across the failing side of {@link Validation}. 466 * @param ob Order across the succeeding side of {@link Validation}. 467 * @return An order instance for the {@link Validation} type. 468 */ 469 public static <A, B> Ord<Validation<A, B>> validationOrd(final Ord<A> oa, final Ord<B> ob) { 470 return eitherOrd(oa, ob).comap(Validation.<A, B>either()); 471 } 472 473 /** 474 * An order instance for the {@link List} type. 475 * 476 * @param oa Order across the elements of the list. 477 * @return An order instance for the {@link List} type. 478 */ 479 public static <A> Ord<List<A>> listOrd(final Ord<A> oa) { 480 return new Ord<List<A>>(new F<List<A>, F<List<A>, Ordering>>() { 481 public F<List<A>, Ordering> f(final List<A> l1) { 482 return new F<List<A>, Ordering>() { 483 public Ordering f(final List<A> l2) { 484 if (l1.isEmpty()) 485 return l2.isEmpty() ? EQ : LT; 486 else if (l2.isEmpty()) 487 return l1.isEmpty() ? EQ : GT; 488 else { 489 final Ordering c = oa.compare(l1.head(), l2.head()); 490 return c == EQ ? listOrd(oa).f.f(l1.tail()).f(l2.tail()) : c; 491 } 492 } 493 }; 494 } 495 }); 496 } 497 498 /** 499 * An order instance for the {@link NonEmptyList} type. 500 * 501 * @param oa Order across the elements of the non-empty list. 502 * @return An order instance for the {@link NonEmptyList} type. 503 */ 504 public static <A> Ord<NonEmptyList<A>> nonEmptyListOrd(final Ord<A> oa) { 505 return listOrd(oa).comap(NonEmptyList.<A>toList_()); 506 } 507 508 /** 509 * An order instance for the {@link Stream} type. 510 * 511 * @param oa Order across the elements of the stream. 512 * @return An order instance for the {@link Stream} type. 513 */ 514 public static <A> Ord<Stream<A>> streamOrd(final Ord<A> oa) { 515 return new Ord<Stream<A>>(new F<Stream<A>, F<Stream<A>, Ordering>>() { 516 public F<Stream<A>, Ordering> f(final Stream<A> s1) { 517 return new F<Stream<A>, Ordering>() { 518 public Ordering f(final Stream<A> s2) { 519 if (s1.isEmpty()) 520 return s2.isEmpty() ? EQ : LT; 521 else if (s2.isEmpty()) 522 return s1.isEmpty() ? EQ : GT; 523 else { 524 final Ordering c = oa.compare(s1.head(), s2.head()); 525 return c == EQ ? streamOrd(oa).f.f(s1.tail()._1()).f(s2.tail()._1()) : c; 526 } 527 } 528 }; 529 } 530 }); 531 } 532 533 /** 534 * An order instance for the {@link Array} type. 535 * 536 * @param oa Order across the elements of the array. 537 * @return An order instance for the {@link Array} type. 538 */ 539 public static <A> Ord<Array<A>> arrayOrd(final Ord<A> oa) { 540 return new Ord<Array<A>>(new F<Array<A>, F<Array<A>, Ordering>>() { 541 public F<Array<A>, Ordering> f(final Array<A> a1) { 542 return new F<Array<A>, Ordering>() { 543 public Ordering f(final Array<A> a2) { 544 int i = 0; 545 //noinspection ForLoopWithMissingComponent 546 for (; i < a1.length() && i < a2.length(); i++) { 547 final Ordering c = oa.compare(a1.get(i), a2.get(i)); 548 if (c == GT || c == LT) 549 return c; 550 } 551 return i == a1.length() ? 552 i == a2.length() ? 553 EQ : 554 LT : 555 i == a1.length() ? 556 EQ : 557 GT; 558 } 559 }; 560 } 561 }); 562 } 563 564 /** 565 * An order instance for the {@link Set} type. 566 * 567 * @param oa Order across the elements of the set. 568 * @return An order instance for the {@link Set} type. 569 */ 570 public static <A> Ord<Set<A>> setOrd(final Ord<A> oa) { 571 return streamOrd(oa).comap(new F<Set<A>, Stream<A>>() { 572 public Stream<A> f(final Set<A> as) { 573 return as.toStream(); 574 } 575 }); 576 } 577 578 /** 579 * An order instance for the {@link Unit} type. 580 */ 581 public static final Ord<Unit> unitOrd = ord(curry(new F2<Unit, Unit, Ordering>() { 582 public Ordering f(final Unit u1, final Unit u2) { 583 return EQ; 584 } 585 })); 586 587 /** 588 * An order instance for a product-1. 589 * 590 * @param oa Order across the produced type. 591 * @return An order instance for a product-1. 592 */ 593 public static <A> Ord<P1<A>> p1Ord(final Ord<A> oa) { 594 return oa.comap(P1.<A>__1()); 595 } 596 597 598 /** 599 * An order instance for a product-2, with the first factor considered most significant. 600 * 601 * @param oa An order instance for the first factor. 602 * @param ob An order instance for the second factor. 603 * @return An order instance for a product-2, with the first factor considered most significant. 604 */ 605 public static <A, B> Ord<P2<A, B>> p2Ord(final Ord<A> oa, final Ord<B> ob) { 606 return ord(curry(new F2<P2<A, B>, P2<A, B>, Ordering>() { 607 public Ordering f(final P2<A, B> a, final P2<A, B> b) { 608 return oa.eq(a._1(), b._1()) ? ob.compare(a._2(), b._2()) : oa.compare(a._1(), b._1()); 609 } 610 })); 611 } 612 613 /** 614 * An order instance for a product-3, with the first factor considered most significant. 615 * 616 * @param oa An order instance for the first factor. 617 * @param ob An order instance for the second factor. 618 * @param oc An order instance for the third factor. 619 * @return An order instance for a product-3, with the first factor considered most significant. 620 */ 621 public static <A, B, C> Ord<P3<A, B, C>> p3Ord(final Ord<A> oa, final Ord<B> ob, final Ord<C> oc) { 622 return ord(curry(new F2<P3<A, B, C>, P3<A, B, C>, Ordering>() { 623 public Ordering f(final P3<A, B, C> a, final P3<A, B, C> b) { 624 return oa.eq(a._1(), b._1()) ? 625 p2Ord(ob, oc).compare(P.p(a._2(), a._3()), P.p(b._2(), b._3())) 626 : oa.compare(a._1(), b._1()); 627 } 628 })); 629 } 630 631 /** 632 * An order instance for the <code>long</code> type. 633 */ 634 public static final Ord<Natural> naturalOrd = bigintOrd.comap(Natural.bigIntegerValue); 635 636 637 /** 638 * An order instance for the <code>Comparable</code> interface. 639 * 640 * @return An order instance for the <code>Comparable</code> interface. 641 */ 642 public static <A extends Comparable<A>> Ord<A> comparableOrd() { 643 return ord(new F<A, F<A, Ordering>>() { 644 public F<A, Ordering> f(final A a1) { 645 return new F<A, Ordering>() { 646 public Ordering f(final A a2) { 647 final int x = a1.compareTo(a2); 648 return x < 0 ? LT : x == 0 ? EQ : GT; 649 } 650 }; 651 } 652 }); 653 } 654 }