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]); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment