Skip to content

Instantly share code, notes, and snippets.

@jaymoid

jaymoid/ComparatorLawEnforcer.java

Created June 14, 2017 19:45
Show Gist options
  • Save jaymoid/c84afe1e03e797ec0f1bb634dfadb62e to your computer and use it in GitHub Desktop.
Save jaymoid/c84afe1e03e797ec0f1bb634dfadb62e to your computer and use it in GitHub Desktop.
Download ZIP
JavaComparatorLawEnforcer
Raw
ComparatorLawEnforcer.java
import java.util.Comparator;
import static junit.framework.Assert.assertEquals;
import static junit.framework.Assert.assertTrue;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.greaterThan;
import static org.hamcrest.Matchers.lessThan;
/**
* As per the contract for Comparator Interface, the implementor must ensure:
*
* sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
* ^ This is known as AntiCommutativity
*
* (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)
* ^ This is known as Exception Symmetry
*
* The implementor must also ensure that the relation is transitive:
* (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0
*
* Finally, the implementor must ensure that x.compareTo(y) == 0 implies that
* sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z
* ^ I don't know the mathematical term for this, so I'm calling it signumSymmetry
*
* For more info, please see:
* Effective Java - item 12
* The Comparator API Spec: http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html
* "Implementing compareTo": http://www.javapractices.com/topic/TopicAction.do?Id=10
*
* @param <T> The comparable type
*/
public class ComparatorLawEnforcer<T> {
private Comparator<T> comparator;
private T a;
private T b;
private T c;
private T equalToA;
/**
* Constructs a Comparator law enforcer, and runs some post initialisation checks to make sure your items are all good
*
* @param comparator the comparator you would like to test
* @param first the comparable object that you would expect to appear FIRST when ordered with the supplied comparator
* @param second the comparable object that you would expect to appear SECOND when ordered with the supplied comparator
* @param third the comparable object that you would expect to appear THIRD when ordered with the supplied comparator
* @param equalToFirst the comparable object that you would expect return EQUAL (0) when compared to the first object with the supplied comparator
*/
public ComparatorLawEnforcer(Comparator<T> comparator, T first, T second, T third, T equalToFirst) {
this.comparator = comparator;
this.a = first;
this.b = second;
this.c = third;
this.equalToA = equalToFirst;
basicPostInitChecks();
comparatorIsAnticommutative();
comparatorHasExceptionSymmetry();
comparatorIsTransitive();
comparatorIsReflexive();
comparatorHasSignumSymmetry();
}
private void basicPostInitChecks() {
String failMsg = "Please make sure that the four parameters you pass satisfy: (first < second < third) && (equalToFirst == first)";
assertThat(failMsg, comparator.compare(a, b), is(lessThan(0)));
assertThat(failMsg, comparator.compare(b, c), is(lessThan(0)));
assertThat(failMsg, comparator.compare(a, equalToA), is(equalTo(0)));
}
private void comparatorIsAnticommutative() {
assertAnticommutativity(a, b);
assertAnticommutativity(b, c);
}
void assertAnticommutativity(T lhs, T rhs) {
String failMsg = "You comparator does not satisfy: sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y";
assertTrue(failMsg,
Math.signum(comparator.compare(lhs, rhs)) == -Math.signum(comparator.compare(rhs, lhs))
);
}
private void comparatorHasExceptionSymmetry() {
assertExceptionSymmetry(a, b);
assertExceptionSymmetry(b, c);
}
void assertExceptionSymmetry(T lhs, T rhs) {
String failMsg = "You comparator does not satisfy: compare(x, y) must throw an exception if and only if compare(y, x) throws an exception";
Throwable t1 = null;
Throwable t2 = null;
try {
comparator.compare(lhs, rhs);
} catch (Throwable t) {
t1 = t;
}
try {
comparator.compare(rhs, lhs);
} catch (Throwable t) {
t2 = t;
}
assertEquals(failMsg, t1, t2);
}
void comparatorIsTransitive() {
// assertTransitive needs (biggestThing, middleThing, smallestThing)
assertTransitive(c, b, a);
}
void assertTransitive(T x, T y, T z) {
String failMsg = "You comparator does not satisfy: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0";
assertThat(comparator.compare(x, y), is(greaterThan(0)));
assertThat(comparator.compare(y, z), is(greaterThan(0)));
assertThat(comparator.compare(x, z), is(greaterThan(0)));
}
void comparatorIsReflexive() {
assertReflexive(a, b, c, equalToA);
}
void assertReflexive(T... comparableThings) {
String failMsg = "You comparator does not satisfy: compare(x, x) == 0";
for (T comparableThing : comparableThings) {
assertThat(failMsg, comparator.compare(comparableThing, comparableThing), is(equalTo(0)));
}
}
void comparatorHasSignumSymmetry() {
assertSignumSymmetry(a, equalToA, b, c);
}
void assertSignumSymmetry(T x, T y, T... allZ) {
String failMsg = "You comparator does not satisfy: sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z";
assertThat(failMsg, comparator.compare(x, y), is(equalTo(0)));
for (T z : allZ) {
assertEquals(failMsg, Math.signum(comparator.compare(x, z)), Math.signum(comparator.compare(y, z)));
}
}
}
@jaymoid
Copy link
Author

jaymoid commented Jun 14, 2017 •
edited
Loading

Sample usage:

    Comparator<Comparable> naturalComparator = (o1, o2) -> o1.compareTo(o2);

    new ComparatorLawEnforcer(naturalComparator,1,2,3,1);
    new ComparatorLawEnforcer(naturalComparator,"A", "B", "C", "A");

    new ComparatorLawEnforcer(naturalComparator.reversed(),3,2,1,3);
    new ComparatorLawEnforcer(naturalComparator.reversed(),"C", "B", "A", "C");

Obviously your comparator may be a bit more complex :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment