object ProbabilisticChoice extends App {
  import scala.collection.mutable.LinkedHashMap

  def weightedProb[A](prob: LinkedHashMap[A,Double]): A = {
    require(prob.forall{case (_, p) => p > 0 && p < 1})
    assume(prob.values.sum == 1)
    def weighted(todo: Iterator[(A,Double)], rand: Double, accum: Double = 0): A = todo.next match {
      case (s, i) if rand < (accum + i) => s
      case (_, i) => weighted(todo, rand, accum + i)
    }
    weighted(prob.toIterator, scala.util.Random.nextDouble)
  }

  def weightedFreq[A](freq: LinkedHashMap[A,Int]): A = {
    require(freq.forall{case (_, f) => f >= 0})
    require(freq.values.sum > 0)
    def weighted(todo: Iterator[(A,Int)], rand: Int, accum: Int = 0): A = todo.next match {
      case (s, i) if rand < (accum + i) => s
      case (_, i) => weighted(todo, rand, accum + i)
    }
    weighted(freq.toIterator, scala.util.Random.nextInt(freq.values.sum))
  }