(An Untitled Masterwork)
ActivePublic
Actions

Authored by seirl on Jun 6 2019, 12:03 PM.

Tags

None

Subscribers

None

	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;
	}

(An Untitled Masterwork)ActivePublicActions