Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View LexiSortable.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
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.