Are semitokens in a SortedSet persistent?


#1

I am trying to write a code for a scheduler of moves for Monte-Carlo simulation. Basically, I need a container where I could insert an event scheduled to happen at a given time, and keep the set of times sorted. Once in a while, the first element of the set is popped; the corresponding event can invalidate some already programmed events and also can make possible some other ones. Thus, one has to access the sorted set of times by some sort of a unique identifier, and the best thing I can think of is SortedSet.SemiToken. This is why I use a Dictionary mapping an external id::Int64 to the internal type SemiToken. Here’s how the type is defined:

mutable struct Scheduler
    times::SortedSet{Float64}
    moves::Dict{Int64,IntSemiToken}
    wc::Float64
end

The question is: can one rely on that the semi-token of an element in a SortedSet will remain valid as long as the element itself is not removed from the collection, irrespective of what happens with other elements?

Thanks.

Update: it seems that semitokens are de facto not invalidated (in the implementation of BalancedTree23, the elements of the array data are not moved). However, the question remains, since this seems to be an undocumented feature.


#2

@Stephen_Vavasis would be the best person to answer here, since he wrote the original code. Your update describing the de facto behavior does seem to be correct, however.

Cheers,
Kevin


#3

Deleting a k=>v pair from a SortedDict or SortedMultiDict or an entry from a SortedSet should not invalidate tokens or semitokens that refer to other items. This was an intentional design decision. You are correct that the documentation does not state this fact. Instead, the documentation indicates which operations do invalidate tokens and semitokens. I agree that it would be better for the documentation to state for every kind of mutating operation whether it does or does not invalidate tokens, so perhaps you can open an issue in DataStructures.jl requesting this documentation improvement.