Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
object PartnerOddEven {
/**
*
* Calculates partner in Batcher Odd-Even network.
*
* @param n node index: 0, 1, 2, 3, ... 2^d^-1
* @param l merge stage: 1, 2, 3, ... d
* @param p stage step: 1, 2, 3, ... l
* @return Returns partner node, or self (n) if no partner for this step
*/
def partner(n: Int, l: Int, p: Int): Int = {
assert(p <= l, "p should be at most l")
assert(p > 0, "p should be at least 1")
assert(l > 0, "l should be at least 1")
if (p == 1)
n ^ (1 << (l - 1))
else {
val (scale, box) = (1 << (l - p), 1 << p)
val sn = n / scale - (n / scale / box) * box
if (sn == 0 || sn == box - 1) n
else if (sn % 2 == 0) n - scale else n + scale
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.