class FifoBinarySemaphore(initiallyAvailable: Boolean) extends Semaphore {
  private final class Waiter { var granted = false }
  private val queue = scala.collection.mutable.Queue[Waiter]()
  private var available = initiallyAvailable

  def down: Unit = {
    val mine: Option[Waiter] = synchronized {
      if (available) {
        assert(queue.isEmpty)
        available = false
        None
      } else {
        val w = new Waiter
        queue.enqueue(w)
        Some(w)
      }
    }
    mine.foreach { w =>
      var interrupted = false
      w.synchronized {
        while (!w.granted) {
          try { w.wait() }
          catch { case _: InterruptedException => interrupted = true }
        }
      }
      if (interrupted) Thread.currentThread().interrupt()
    }
  }

  def up: Unit = synchronized {
    if (queue.nonEmpty) {
      val w = queue.dequeue()
      // available stays false: this permit is reserved for w.
      w.synchronized {
        w.granted = true
        w.notify()
      }
    } else {
      require(!available, "unmatched binary-semaphore release")
      available = true
    }
  }
}

private val empty: Semaphore = new FifoBinarySemaphore(true)
private val full: Semaphore = new FifoBinarySemaphore(false)

class SemaphoreMemory[T] extends Memory[T] {
  private val empty: Semaphore = new CountingSemaphore(1)
  private val full: Semaphore = {
    val s = new CountingSemaphore(1)
    s.down
    s
  }
  private var slot: Option[T] = None

  def write(msg: T): Unit = {
    empty.down
    slot = Some(msg)
    full.up
  }
  def read: T = {
    full.down
    val result = slot.get
    slot = None
    empty.up
    result
  }
}

class MonitorMemory[T] extends Memory[T] {
  private var slot: Option[T] = None
  def write(msg: T): Unit = synchronized {
    while (slot.nonEmpty) wait()
    slot = Some(msg)
    notifyAll()
  }
  def read: T = synchronized {
    while (slot.isEmpty) wait()
    val result = slot.get
    slot = None
    notifyAll()
    result
  }
}

def sameFringe(node1: Array[Node], root1: NodeId,
               node2: Array[Node], root2: NodeId): Boolean = {
  val a = OneOne[NodeId]
  val b = OneOne[NodeId]
  var equal = true

  def next(p: ?[NodeId]): Option[NodeId] =
    try { Some(p ? ()) }
    catch { case _: io.threadcso.process.Stopped => None }

  val compare = proc {
    var done = false
    try {
      while (!done) {
        val x = next(a)
        val y = next(b)
        (x, y) match {
          case (None, None) => done = true
          case (Some(u), Some(v)) if u == v => ()
          case _ => equal = false; done = true
        }
      }
    } finally { a.closeIn; b.closeIn }
  }
  (dfFringe(node1, root1, a) || dfFringe(node2, root2, b) || compare)()
  equal
}

def dfFringe(node: Array[Node], root: NodeId, fringe: ![NodeId]): PROC = proc {
  def walk(v: NodeId): Unit = {
    val cs = node(v).children
    if (cs.isEmpty) fringe ! v
    else cs.foreach(walk)
  }
  try { walk(root) }
  catch { case _: io.threadcso.process.Stopped => () }
  finally { fringe.closeOut }
}

final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends Msg

def span: PROC = proc {
  val adj = neighbours.distinct
  val routed = scala.collection.mutable.Set[Int]()
  var entered = false
  var done = false

  def flood(message: Msg): Unit =
    for (w <- adj) toNode(w) ! message

  def move(target: NodeId, state: Token): Unit = {
    val s = state.serial + 1
    routed += s
    flood(Route(s, target, state.copy(serial = s)))
  }

  def step(t: Token): Unit = {
    assert(t.stack.head == me)
    if (!entered) {
      entered = true
      parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
      children = Nil
    }
    adj.find(w => !t.visited(w)) match {
      case Some(w) =>
        children = children :+ w
        move(w, Token(t.visited + w, w :: t.stack, t.serial))
      case None =>
        t.stack.tail match {
          case p :: rest => move(p, t.copy(stack = p :: rest))
          case Nil => flood(Finished); done = true
        }
    }
  }

  if (me == 0) step(Token(Set(0), List(0), 0))
  while (!done) {
    fromNode(me) ? () match {
      case r @ Route(s, target, t) =>
        if (!routed(s)) {
          routed += s
          if (target == me) step(t) else flood(r)
        }
      case Finished => flood(Finished); done = true
    }
  }
}

sealed trait Msg { def from: NodeId }
final case class Discover(from: NodeId) extends Msg
final case class Active(from: NodeId, origin: NodeId) extends Msg

val mailbox = Vector.fill(N)(N2NBuf[Msg](B, 0, 1))
val toNode: Seq[![Msg]] = mailbox
val fromNode: Seq[?[Msg]] = mailbox

def span: PROC = proc {
  val adj = neighbours.distinct
  var started = false
  val known = scala.collection.mutable.Set[NodeId]()

  def announce(origin: NodeId): Unit = {
    if (!known(origin)) {
      known += origin
      for (w <- adj) toNode(w) ! Active(me, origin)
    }
  }
  def activate(sender: NodeId): Unit = {
    started = true
    parent = if (me == 0) 0 else sender
    for (w <- adj if me == 0 || w != parent)
      toNode(w) ! Discover(me)
    announce(me)
  }

  if (me == 0) activate(0)
  while (known.size < N) {
    val message = fromNode(me) ? ()
    if (!started) activate(message.from)
    message match {
      case Discover(_) => ()
      case Active(_, origin) => announce(origin)
    }
  }
}