implemented software timer using binary heap priority queue. works well as long as no "cancel timer" operation is needed.
what is a good data structure for a timer where cancellation is common? (e.g. mostly handling timeouts)
Conversation
Replying to
Option A: Use your binary heap normally, but introduce an intermediate cancellation object wrapping the callback. I.e. use mutation.
Option B: Use a finger-tree. In the monoidal summary for each subtree, track priority and the range of cancellation IDs (& optionally tree size).
1
1
Replying to
Thanks for the suggestion. I'm not familiar with B, will look into it.
Option A doesn't work for me: worst case I would have about 40 cancelled events in the queue and 4 active ones.