OddEvenMerge.scala

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