jfager / LexiSortable.java

Created July 26, 2010

import java.util.Arrays;
import java.util.Random;
 
public class LexiSortable {
 
    // Converting to hex is fast and easy
    private final static char[] HEX_DIGITS = {
        '0', '1', '2', '3', '4', '5', '6', '7',
        '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
    };
 
    // And chars to bytes is pretty easy, too.
    private final static byte[] BYTE_LOOKUP = new byte['F' + 1];
    static {
        for (int i = 0; i < HEX_DIGITS.length; i++) {
            BYTE_LOOKUP[HEX_DIGITS[i]] = (byte) i;
        }
    }
 
    // 16 chars to represent a long in hex, plus a type token.
    private static final int LEXI_STRING_LEN = 17;
 
    // Utility method converts a long to a hex string and prepends a type token
    private static String toHexString(char type, long i) {
        final char[] buf = new char[LEXI_STRING_LEN];
        int charPos = LEXI_STRING_LEN;
        do {
            // read bottom 4 bits to lookup hex char for current position
            buf[--charPos] = HEX_DIGITS[(int) (i & 0xf)];
            // shift so we can do it again for the next.
            i >>>= 4;
        } while (charPos > 0);
        buf[0] = type;
        return new String(buf);
    }
 
    // Utility method converts a hex string to a long.  It ignores the leading
    // type token; verification needs to be handled by the calling function.
    private static long fromHexString(final String s) {
        final byte[] bytes = s.getBytes();
        long out = 0L;
        for (int i = 1; i < LEXI_STRING_LEN; i++) {
            // first shift is wasted, but after that, move previously xor'd out
            // of the way so they don't get clobbered by subsequent chars.
            out <<= 4;
            // Note that we shifted 4 bits b/c we're using hex, but we have to
            // XOR a byte at a time.  This is fine, b/c the high bits of the
            // bytes stored in the lookup table are zeroed out.
            out ^= BYTE_LOOKUP[bytes[i]];
        }
        return out;
    }
 
    // All zeroes except the sign bit.
    private static final long SIGN_MASK = 0x8000000000000000L;
 
    /**
     * Returns a string s for long l such that for any long l' where l < l',
     * s.compareTo(toLexiSortable(l')) < 0.
     *
     * @param l The long to represent as a properly sortable String.
     * @return A properly sortable String representation of the input value.
     */
    public static String toLexiSortable(final long l) {
        // Toggle the sign bit with an XOR and dump out as a hex string.
        return toHexString('l', l ^ SIGN_MASK);
    }
 
    /**
     * Returns a long such that longFromLexiSortable(toLexiSortable(l)) == l.
     *
     * @param s The String to convert back to a source long.
     * @return The source long for the input String s.
     */
    public static long longFromLexiSortable(final String s) {
        if (!s.startsWith("l")) {
            throw new IllegalArgumentException(s + " does not represent a long");
        }
        // Get an intermediate long representation from the hex string.
        long tmp = fromHexString(s);
        // Toggle the sign bit with an XOR to get original long back.
        return tmp ^ SIGN_MASK;
    }
 
    public static String toLexiSortable(final double d) {
        long tmp = Double.doubleToRawLongBits(d);
        return toHexString('d', (tmp < 0) ? ~tmp : (tmp ^ SIGN_MASK));
    }
 
    public static double doubleFromLexiSortable(final String s) {
        if (!s.startsWith("d")) {
            throw new IllegalArgumentException(s
                    + " does not represent a double");
        }
        long tmp = fromHexString(s);
        tmp = (tmp < 0) ? (tmp ^ SIGN_MASK) : ~tmp;
        return Double.longBitsToDouble(tmp);
    }
 
    private static void cmp(long l1, long l2) {
        if (!(l1 <= l2)) {
            throw new RuntimeException("Out of order! l1: " + l1 + ", l2: "
                    + l2);
        }
        String s1 = toLexiSortable(l1);
        String s2 = toLexiSortable(l2);
        if (!(s1.compareTo(s2) <= 0)) {
            throw new RuntimeException("Conversion not in order");
        }
        long t1 = longFromLexiSortable(s1);
        long t2 = longFromLexiSortable(s2);
        if (t1 != l1 || t2 != l2) {
            throw new RuntimeException("Couldn't convert back to original");
        }
    }
 
    private static void cmp(double d1, double d2) {
        if (!(d1 <= d2)) {
            throw new RuntimeException("Out of order! d1: " + d1 + ", d2: "
                    + d2);
        }
        String s1 = toLexiSortable(d1);
        String s2 = toLexiSortable(d2);
        if (!(s1.compareTo(s2) <= 0)) {
            throw new RuntimeException("Conversion not in order");
        }
        double t1 = doubleFromLexiSortable(s1);
        double t2 = doubleFromLexiSortable(s2);
        if (t1 != d1 || t2 != d2) {
            throw new RuntimeException("Couldn't convert back to original");
        }
 
        if (Double.doubleToRawLongBits(t1) != Double.doubleToRawLongBits(d1)) {
            throw new RuntimeException("Couldn't convert back to original");
        }
 
        if (Double.doubleToRawLongBits(t2) != Double.doubleToRawLongBits(d2)) {
            throw new RuntimeException("Couldn't convert back to original");
        }
 
        if (inc(dec(d1)) != d1 || dec(inc(d1)) != d1) {
            throw new RuntimeException("Inc/Dec broken for d1: " + d1);
        }
 
        if (inc(dec(d2)) != d2 || dec(inc(d2)) != d2) {
            throw new RuntimeException("Inc/Dec broken for d2: " + d2);
        }
    }
 
    private static double inc(double d) {
        if (d == -0.0) {
            return Double.MIN_VALUE;
        }
        long tmp = Double.doubleToRawLongBits(d);
        return Double.longBitsToDouble((tmp < 0) ? tmp - 1 : tmp + 1);
    }
 
    private static double dec(double d) {
        if (d == -0.0) {
            return -Double.MIN_VALUE;
        }
        long tmp = Double.doubleToRawLongBits(d);
        return Double.longBitsToDouble((tmp < 0) ? tmp + 1 : tmp - 1);
    }
 
    public static void main(String[] args) {
        int TEST_CASES = 9999999;
        Random RANDOM = new Random();
 
        {
            long[] special_longs = { Long.MIN_VALUE, Long.MIN_VALUE + 1, -1L,
                    0L, 1L, Long.MAX_VALUE - 1, Long.MAX_VALUE };
            for (int i = 1; i < special_longs.length; i++) {
                cmp(special_longs[i - 1], special_longs[i]);
            }
            long[] longs = new long[TEST_CASES];
            System.arraycopy(special_longs, 0, longs, 0, special_longs.length);
            for (int i = special_longs.length; i < longs.length; i++) {
                longs[i] = RANDOM.nextLong();
            }
            Arrays.sort(longs);
            for (int i = 1; i < longs.length; i++) {
                cmp(longs[i - 1], longs[i]);
            }
        }
 
        {
            double[] special_doubles = { Double.NEGATIVE_INFINITY,
                    -Double.MAX_VALUE, inc(-Double.MAX_VALUE),
                    dec(-Double.MIN_NORMAL), -Double.MIN_NORMAL,
                    inc(-Double.MIN_NORMAL), dec(-Double.MIN_VALUE),
                    -Double.MIN_VALUE, inc(-Double.MIN_VALUE), -0.0, 0.0,
                    dec(Double.MIN_VALUE), Double.MIN_VALUE,
                    inc(Double.MIN_VALUE), dec(Double.MIN_NORMAL),
                    Double.MIN_NORMAL, inc(Double.MIN_NORMAL),
                    dec(Double.MAX_VALUE), Double.MAX_VALUE,
                    Double.POSITIVE_INFINITY };
            for (int i = 1; i < special_doubles.length; i++) {
                cmp(special_doubles[i - 1], special_doubles[i]);
            }
            double[] doubles = new double[TEST_CASES];
            System.arraycopy(special_doubles, 0, doubles, 0,
                    special_doubles.length);
            for (int i = special_doubles.length; i < doubles.length; i++) {
                doubles[i] = RANDOM.nextDouble()
                        * (RANDOM.nextBoolean() ? Double.MAX_VALUE
                                : -Double.MAX_VALUE);
            }
            Arrays.sort(doubles);
            for (int i = 1; i < doubles.length; i++) {
                cmp(doubles[i - 1], doubles[i]);
            }
        }
    }
}