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    }