Tournament computation in two dimensions

Tournament computation can also take place in two dimensions. Here, tournamentOp₂ applies a quaternary function g to a 2-dimensional variable X, and keeps doing this to the results until there is a single result.

fun tournamentOp₂.d₁.d₂.n.g X = Y @ [d <- 0]
where
  dim t <- ilog.n ;;
  var Y = fby.t X (g.(NWofQuad.d₁.d₂ Y).(NEofQuad.d₁.d₂ Y).
                     (SWofQuad.d₁.d₂ Y).(SEofQuad.d₁.d₂ Y)) ;;
end ;;

As for the single-dimensional case, it is useful to have a way of filling a two-dimensional grid with a neutral element if we do not have a grid whose extent in every dimension is the same power of 2.

fun default₂.d₁.m₁.n₁.d₂.m₂.n₂.val X = Y
where
  var Y [d₁ : m₁..n₁, d₂ : m₂..n₂] = X ;;
  var Y [d₁ : nat, d₂ : nat] = val ;;
end ;;
Advertisement