Olaf Titz wrote: >>I wonder if it would be worth rewriting cSchedule to store events in a >>binary tree based on time. A double-linked list could be included in the >>nodes pointing to allow for scanning through the schedule in the >>conventional way (for(cEvent *p = events.First()...) > > > The right data structure for this (or rather, the canonical data > structure for any sort of timer queue) is a binary heap. Guaranteed > O(log n) time for insert and delete(first) operation and O(1) for > lookup(first), zero memory overhead and much easier to implement than > all other sorts of balanced tree. > > >>What do people think, would it be worth me writing a patch? > > > Definitely. Come one, guys, you must be kidding! For a few dozen timers even the simplest data structure has to perform extremely well, unless there is a bug. So I suggest keeping the data structure and fixing the bug (which is propably exactly what Darren's patch does). Carsten.
