use binarySearch.frink

/** This class generates random elements from a discrete set with a
    known distribution, for example, the frequency of letters in the English
    language.

    HOWEVER, when generating random items, it is O(log n) with a
    worst case of O(n) (where n is the number of items to be chosen from).
    For a better constant-time algorithm, see DiscreteDistribution.frink .
    However, an O(1) efficient algorithm can be found in the
    DiscreteDistribution.frink sample program.
*/
class randomDistribution
{
   // An array of elements
   var elements

   // The sum of probabilities
   var sum
   
   new[] :=
   {
      elements = new array
      sum = 0
   }

   // Adds an item with the specified probability.
   add[item, prob] :=
   {
      sum = sum + prob
      elements.push[ [item, prob, sum] ]
   }

   // Selects a random item based on the specified probabilities.
   random[] :=
   {
      z = randomFloat[0, sum]
      index = binarySearch[elements, z, {|a,b| a <=> b@2}]
      return elements@index@0
   }
}