Tournament Tree



This is necessary for implementing an online gaming system that is expecting events for completed games. If an expected 'nextGame' is played, then we automatically want to advance the tournament forward.

There's not enough description for this to be clear, so you might want to avoid reading this one.

Tournament tree

The interface


sealed trait TournamentTree[T] {

  def win(player: T): TournamentTree[T]

  def nextGames: Set[(T, T)]

  def winner: Option[T]


The specification


class TournamentTreeSpec extends FunSuite {
  val Drakas = "Drakas"
  val Lucas = "Lucas"
  val Sanzo = "Sanzo"
  private val tourney = TournamentTree(Drakas, Lucas, Sanzo)

  test("First iteration is correct") {
    tourney.nextGames should contain theSameElementsAs Set(Drakas -> Lucas)
    tourney.winner shouldBe empty
  test("Sanzo win does nothing") { shouldEqual tourney.nextGames shouldEqual tourney.winner
  test("Drakas win pushes to next stage") { should contain theSameElementsAs Set(Drakas -> Sanzo) shouldBe empty
  test("Drakas win 2x pushes to final stage") { shouldBe empty shouldBe Some(Drakas)



We want to meet the specification with minimal possible work. We shall represent the solution as a tree structure because it looks like a tree.

In this solution, a Tournament is in either an Undecided state or a Decided state. An Undecided state will contain two Tournaments, one to the left and one to the right.

Solution for generating the tree


/** Bottom up build: take every 2 consecutive items, create an UndefinedPlayer,
  * then reprocess the new list of trees until we're left with only 1.
private def buildTree[T](tournamentTree: TournamentTree[T]*): TournamentTree[T] = {
  tournamentTree.toList match {
    case tree :: Nil => tree
    case other =>
      buildTree {
        other.grouped(2).map(_.toList).map {
          case a :: b :: Nil => UndefinedPlayer(a, b)
          case a :: _ => a
          case Nil => ???
        }.toList: _*

Solution for a Decided state


case class DefinedPlayer[T](player: T) extends TournamentTree[T] {
  def win(player: T): TournamentTree[T] = this

  def nextGames: Set[(T, T)] = Set.empty

  def winner: Option[T] = Some(player)

Solution for an Undecided state


case class UndefinedPlayer[T](left: TournamentTree[T], right: TournamentTree[T]) extends TournamentTree[T] {
  def win(player: T): TournamentTree[T] = (left, right) match {
    case (DefinedPlayer(`player`), DefinedPlayer(_)) => DefinedPlayer(player)
    case (DefinedPlayer(_), DefinedPlayer(`player`)) => DefinedPlayer(player)
    case _ => UndefinedPlayer(,

  def nextGames: Set[(T, T)] = (left, right) match {
    case (DefinedPlayer(a), DefinedPlayer(b)) => Set(a -> b)
    case _ => left.nextGames ++ right.nextGames

  def winner: Option[T] = None