I need a data structure
d with somewhat conflicting requirements. What are the different tradeoffs I could pick?
The same algorithm will be repeatedly done on each time step:
pushone new element to the right (so all elements remain naturally ordered by the date they came into the data structure).
updateall elements. I mean iterate (in any order or parallel) and mutate in place.
- based on the result of the update,
drainrandom elements in order (new or old). I mean that some will have to be both returned in order to user and removed from
- user should also easily
iteratein order over remaining elements.
For instance, think of a bunch of fruit that takes a random time to ripen. One new piece of fruit is spawned each day. And each day we need to collect (ordered) ripe fruit, while keeping remaining pieces of fruit ordered by age.
Is there a dedicated data structure?
If not, is there a pattern for this case?
If not, what are the different tradeoffs I’ll have to deal with? Is there any assumption I could make on the data (like drain frequency) to help me choose?
(for instance, I suspect that many pieces of fruit will be ripe on the first or the first few update(s), and only a few will last longer)