// https://stackoverflow.com/a/47048431
static long interpolate(String ys, String xs, String iOfTs, long 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 : d.multiply(iOfT.subtract(y)).divide(den).longValue();
}
public String[] stringAtLine(long lineNumber) {
return swhToNodeMap.readLine(lineNumber).split(" ");
}
public long getNode(SwhId swhId) {
long start = 0;
long end = nbIds - 1;
String target = swhId.toString();
while (target.compareTo(stringAtLine(start)[0]) >= 0 && target.compareTo(stringAtLine(end)[0]) <= 0) {
String start_string = stringAtLine(start)[0];
String end_string = stringAtLine(end)[0];
long lineNumber = start + interpolate(start_string, end_string, target, end - start);
System.out.println(lineNumber);
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;
}