# Algorithms

Many samplers depend on data structures to allow efficient querying of clocks ordered with respect to some value, usually the firing time. These types and methods implement them for CompetingClocks.

CompetingClocks.CumSumPrefixSearchType
CumSumPrefixSearch{T}()

This stores hazard rates in order to make it easier for the Direct method to sample them. This version is the dumbest possible, but it can be faster when there are few hazards enabled. It uses a simple array and, each time the Direct method samples, this evaluates the cumulative sum of the array.

CompetingClocks.BinaryTreePrefixSearchType
BinaryTreePrefixSearch{T}(N=32)

This stores hazard rates to make them faster for the Direct method to sample. This is a binary tree where the leaves are values and the nodes are sums of those values. It is meant to make it easier to find the leaf such that the sum of it and all previous leaves is greater than a given value.

CompetingClocks.KeyedKeepPrefixSearchType

This decorator turns a Prefix Search algorithm into one that works for arbitrary keys. This version only adds entries, so disabling a clock sets its hazard to zero without removing it. If a simulation re-enables the same set of clocks, this is the faster choice.

CompetingClocks.KeyedRemovalPrefixSearchType

This decorator turns a Prefix Search algorithm into one that works for arbitrary keys. This version reuses entries in the prefix search after their clocks have been disabled. If the simulation moves through a large key space, this will use less memory.

CompetingClocks.chooseFunction
choose(pst::BinaryTreePrefixSearch, value)

Find the minimum index such that the prefix is greater than the given value.

Precondition: The value must be strictly less than the total for the tree.

Base.randFunction
rand(rng, sampler::SamplerTrivial{BinaryTreePrefixSearch})

This method overload allows the machinery of Random to generate random variates from the BinaryTreePrefixSearch set of values.

rand(rng, sampler::SamplerTrivial{CumSumPrefixSearch})

This method overload allows the machinery of Random to generate random variates from the CumSumPrefixSearch set of values.

Drawing a random number from a left-truncated exponential is particularly simple.