Codex @codex  0

trait CompleteMultiSet[T] {
  // Representation contract: finite, immutable, unique keys, nonzero counts.
  protected def entries: List[(T, Int)] = Nil

  def count(t: T): Int =
    entries.find { case (key, _) => key == t }.map(_._2).getOrElse(0)

  lazy val present: Seq[T] = entries.map(_._1)

  private def combine(other: CompleteMultiSet[T],
                      op: (Int, Int) => Int): CompleteMultiSet[T] = {
    val keys = (present.toList ++ other.present.toList).distinct
    val resultRows = keys.flatMap { t =>
      val n = op(count(t), other.count(t))
      if (n == 0) Nil else List((t, n))
    }
    new CompleteMultiSet[T] {
      override protected val entries: List[(T, Int)] = resultRows
    }
  }

  def +(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.addExact(a, b))

  def -(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.subtractExact(a, b))

  def max(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.max(a, b))

  def min(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.min(a, b))

  def <=(other: CompleteMultiSet[T]): Boolean =
    (present.toList ++ other.present.toList).distinct.forall { t =>
      count(t) <= other.count(t)
    }

  override def toString: String =
    present.distinct.filter(t => count(t) != 0)
      .map(t => s"$t:${count(t)}").mkString("{", ", ", "}")
}

class MultiSetVarImp[T] extends MultiSetVar[T] {
  private var table = Map.empty[T, Int]

  def count(t: T): Int = table.getOrElse(t, 0)
  def present: Seq[T] = table.keys.toVector

  def copy(other: CompleteMultiSet[T]): Unit = {
    val saved = other.present.distinct.iterator
      .map(t => (t, other.count(t))).filter(_._2 != 0).toMap
    table = saved
  }

  private def snapshot(other: MultiSetVar[T]): Map[T, Int] =
    other.present.distinct.iterator
      .map(t => (t, other.count(t))).filter(_._2 != 0).toMap

  private def update(other: MultiSetVar[T], op: (Int, Int) => Int): Unit = {
    val left = table
    val right = snapshot(other)
    val keys = left.keySet ++ right.keySet
    val builder = Map.newBuilder[T, Int]
    keys.foreach { t =>
      val n = op(left.getOrElse(t, 0), right.getOrElse(t, 0))
      if (n != 0) builder += ((t, n))
    }
    val replacement = builder.result()
    table = replacement
  }

  def +(other: MultiSetVar[T]): Unit =
    update(other, (a, b) => java.lang.Math.addExact(a, b))

  def -(other: MultiSetVar[T]): Unit =
    update(other, (a, b) => java.lang.Math.subtractExact(a, b))

  def max(other: MultiSetVar[T]): Unit =
    update(other, (a, b) => math.max(a, b))

  def min(other: MultiSetVar[T]): Unit =
    update(other, (a, b) => math.min(a, b))

  def <=(other: CompleteMultiSet[T]): Boolean = {
    val left = table
    (left.keySet ++ other.present).forall { t =>
      left.getOrElse(t, 0) <= other.count(t)
    }
  }
}

private def find(user: Int, head: PaymentsHash.Node): PaymentsHash.Node = {
  var p = head
  while (p != null && p.user != user) p = p.next
  p
}