Partitioner

partition.scala

  def findPartition(
      base: Set[M],            // current final fringe
      childrenF: M => List[M], // children function
      senderF: M => S,         // sender function
      highestF: List[M] => M,  // find highest message across (those seeing all others)
      jssF: M => Set[M],       // justifications
      isSupermajority: Set[S] => Boolean
  ): Option[Set[S]] = {

    // Compute the next level
    def nextLvl(curLvl: Set[M]): Set[M] = {
      val children        = curLvl.map(childrenF) // load children
      val curLvlPartition = curLvl.map(senderF)
      // find senders of the partition - those having a child for each item in curLvl
      val lvlPartition = children.map(_.map(senderF)).foldLeft(curLvlPartition) {
        case (acc, chSenders) => acc intersect chSenders.toSet
      }
      // highest fringe containing senders of partition across is the next lvl
      children.map(_.filter(lvlPartition.contains)).map(highestF)
    }

    // Check whether we have 2 levels that meet the partition criteria
    def settled(lvl1: Set[M], lvl2: Set[M]): Boolean = {
      val sameSenders = lvl1.map(senderF) == lvl2.map(senderF)
      val partSenders = lvl1.map(senderF)
      lazy val safeOutstanding = //check senders out of partition
        (lvl1.flatMap(jssF).filterNot(j => partSenders.contains(senderF(j))) ++
          lvl2.flatMap(jssF).filterNot(j => partSenders.contains(senderF(j))))
          .groupBy(senderF)
          // either the same message or different having the same justifications
          .forall { case (_, x) => x.size == 1 || x.map(jssF).size == 1 }
      sameSenders && safeOutstanding
    }

    @tailrec
    def step(lvl1: Set[M]): Option[Set[S]] = {
      val lvl2 = nextLvl(lvl1)     // jump the next level
      val p    = lvl2.map(senderF) // potential partition
      if (!isSupermajority(p)) none[Set[S]] // if its not SM - no partition of SM will be found
      else if (settled(lvl1, lvl2)) p.some  // if settled - partition is found
      else step(lvl2)                       // still chance to find partition
    }

    // start jumping from current fringe
    step(base)
  }