CavityTools
This small package contains:

cavity!
andcavity
: Functions to compute theN
allbutone operations betweenN
elements in timeO(N)
. The operation is arbitrary and needs only to be associative. This is equivalent to computing[reduce(op, (src[j] for j in eachindex(src) if i != j); init) for i in eachindex(src)]
which however would needN*(N1)
evaluations ofop
. Ifop
is commutative with exact inverseinvop
, you could obtain the same result ofcavity(src, op, init)
, also in timeO(N)
, withinvop.(reduce(op, src; init), src)
. 
Accumulator
: Ana = Accumulator(v::AbstractVector)
works as a replacement forv
with extra tracking computations. Construction of
a
requires timeO(N)
whereN == length(v)
. sum(a)
requires timeO(1)
.cumsum(a)
,cavity(a)
require timeO(1)
and return respectively aCumSum
andCavity
objects that are linked toa
.
 Construction of

c::CumSum(a::Accumulator)
: keeps a liveupdatedcumsum
ofa
. Create it with
c = cumsum(a::Accumulator)
 Retrieval
c[i]
takes timeO(log N)
. collect(c)
takes timeO(N)
searchsortedfirst(r, c)
takes timeO(log N)
 Create it with

c::Cavity(a::Accumulator)
: keeps a liveupdatedcavity
ofa
. Create it with
c = cavity(a::Accumulator)
.  Retrieval
c[i]
takes timeO(log N)
. collect(c)
takes timeO(N)
(but is slower thancavity(v::Vector)
).
 Create it with

Q::ExponentialQueueDict{K}()
:Dict
like interface to a collection of events with associated independent probability rates, intended for sampling on a Gillespielike scheme. Events are of type
K
.  Dictlike contruction
Q = ExponentialQueueDict([:a => 0.1, :b => 0.2, :c => 0.3])
is allowed  Rates can be queried by
getindex
(i.e.r = Q[k]
) and updated viasetindex!
(i.e.Q[k] = r
), both in timeO(log N)
whereN
is the number of stored events.  Next event type and time can extracted from the queue by
k,t = pop!(Q)
ork,t = peek(Q)
. Onpop!
, eventk
is then removed from the collection.pop!
andpeek
take timeO(log N)
.  If event time is unneeded, next event alone can be extracted with
k = peekevent(Q)
(taking also timeO(log N)
).
 Events are of type

Q::ExponentialQueue()
: LikeExponentialQueue{Int}
but events are stored on a vector instead of aDict
, so it may be slightly more efficient. Event indices are positive integers (note that the memory space needed scales with the maximum index, so use ExponentialQueueDIct{Int} if you need very large indices).