Optimal median function

Question

I was experimenting with some code in an attempt to answer Generic Method to find the median of 3 values and was trying to ensure that the compareTo method was called a minimum number of times and to maximise the efficiency of the code and came up with this:

// Flattens the results of a compareTo to -1, 0, 1
static int sign(int x) {
    return x < 0 ? -1 : x == 0 ? 0 : 1;
}

// Use an enum to help.
enum ABC {

    A() {

                @Override
                <T> T which(T a, T b, T c) {
                    return a;
                }

            },
    B() {

                @Override
                <T> T which(T a, T b, T c) {
                    return b;
                }

            },
    C() {

                @Override
                <T> T which(T a, T b, T c) {
                    return c;
                }

            },
    INSANE() {

                @Override
                <T> T which(T a, T b, T c) {
                    // Something like a < b and b < c but c < a
                    return null;
                }

            };

    abstract <T> T which(T a, T b, T c);
}

// Straight lookup.
private static final ABC[][][] median = {
    { // a < b
        { // b < c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b == c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b > c
            // a < c
            ABC.C,
            // a == c
            ABC.A,
            // a > c
            ABC.A
        }
    },
    { // a == b
        { // b < c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b == c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.B,
            // a > c
            ABC.INSANE
        },
        { // b > c
            // a < c
            ABC.A,
            // a == c
            ABC.B,
            // a > c
            ABC.A
        }
    },
    { // a > b
        { // b < c
            // a < c
            ABC.A,
            // a == c
            ABC.A,
            // a > c
            ABC.C
        },
        { // b == c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.B
        },
        { // b > c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.B
        }
    }
};

private static <T extends Comparable> T median(T a, T b, T c) {
    System.out.print(" ab=" + sign(a.compareTo(b)) + " bc=" + sign(b.compareTo(c)) + " ac=" + sign(a.compareTo(c)));
    // Least number of comparisons.
    return median[sign(a.compareTo(b)) + 1][sign(b.compareTo(c)) + 1][sign(a.compareTo(c)) + 1]
            .which(a, b, c);
}

// My test case.
private static <T extends Comparable> T median2(T a, T b, T c) {
    List<T> medianHelper = Arrays.asList(a, b, c);

    Collections.sort(medianHelper);

    return medianHelper.get(1);
}

public void test() {
    for (int a = -5; a <= 5; a += 5) {
        for (int b = -3; b <= 3; b += 3) {
            for (int c = -1; c <= 1; c++) {
                System.out.print("(" + a + "," + b + "," + c + ")");
                Integer m = median(a, b, c);
                Integer m2 = median2(a, b, c);
                System.out.print(" -> " + m + " & " + m2);
                if (m != m2) {
                    System.out.print(" <-- WRONG");
                }
                System.out.println();
            }

        }
    }
}

To get it working I just used the sort them and pick the middle one technique and manually tweaked my matrix until it returned the same result.

Although this seems to work it clearly does not cover all of the possibilities for when compareTo is unstable (e.g. a < b && b < c && c < a) but I don't think that is too important.

Is there some mechanism I could use to correctly generate the matrix? Ideally one that could also be used to generate the min and max matrices too.

Answer 1

If you just want to call compareTo only 3 times (I don't think you can make it work with 2 calls), why not a simple nested if/else:

public static <T extends Comparable> T median(T a, T b, T c) {
  if (a.compareTo(b) <= 0) {
    if (a.compareTo(c) <= 0) {
      return b.compareTo(c) <= 0 ? b : c; //a <= b && a <= c, return min(b, c)
    } else {
      return a;  //c < a <= b, return a
    }
  } else { // b < a
    if (a.compareTo(c) <= 0) {
      return a; // b < a <= c, return a
    } else {
      return b.compareTo(c) <= 0 ? c : b; //b < a && a > c, return max(b, c)
    }
  }
}