Page MenuHomeSoftware Heritage
Paste P416

(An Untitled Masterwork)
ActivePublic

Authored by seirl on Jun 6 2019, 12:03 PM.
import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.nio.charset.StandardCharsets.US_ASCII;
import static java.util.Arrays.copyOf;
import static java.lang.Math.max;
// https://stackoverflow.com/a/47048431
static int interpolate(String ys, String xs, String iOfTs, int id) {
int maxLen = max(max(xs.length(), ys.length()), iOfTs.length());
BigInteger x = new BigInteger(1, copyOf(xs.getBytes(US_ASCII), maxLen));
BigInteger y = new BigInteger(1, copyOf(ys.getBytes(US_ASCII), maxLen));
BigInteger iOfT = new BigInteger(1, copyOf(iOfTs.getBytes(US_ASCII), maxLen));
BigInteger d = BigInteger.valueOf(id);
BigInteger den = x.subtract(y);
return ZERO.equals(den) ? 0 : (int) d.multiply(iOfT.subtract(y)).divide(den).longValue();
}
public String stringAtLine(lineNumber) {
return swhToNodeMap.readLine(lineNumber).split(" ");
}
public long getNode(SwhId swhId) {
long start = 0;
long end = nbIds;
String target = swhId.toString();
while (start <= end) {
String[] start_string = stringAtLine(start)[0];
String[] end_string = stringAtLine(end)[0];
long lineNumber = start + interpolate(start_string, end_string, target, start - end);
String[] parts = stringAtLine(lineNumber);
String currentSwhId = parts[0];
long currentNodeId = Long.parseLong(parts[1]);
int cmp = currentSwhId.compareTo(target);
if (cmp == 0) {
return currentNodeId;
} else if (cmp < 0) {
start = lineNumber + 1;
} else {
end = lineNumber - 1;
}
}
return -1;
}