# 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.CumSumPrefixSearch`

— Type`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.BinaryTreePrefixSearch`

— Type`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.KeyedKeepPrefixSearch`

— TypeThis 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.KeyedRemovalPrefixSearch`

— TypeThis 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.choose`

— Function`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.setindex!`

— Function`setindex!(A, X, inds...)`

`Base.rand`

— Function`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.

`CompetingClocks.set_multiple!`

— FunctionIf there are multiple values to enter, then present them at once as pairs of tuples, (index, value).