Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Something went wrong with that request. Please try again.