------=_Part_40387_31392522.1192545962218
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
>>>>>> Ethan Galstad wrote:
>
> >>>>>>> For the event queue, I was thinking that a skip
> >>>>>>> list structure might be best for efficiency
> >>>>>>> (http://en.wikipedia.org/wiki/Skip_list). The
> >>>>>>> event queue is used in primarily two
> >>>>>>> situations:
> >>>>>>> 1. Popping events from the head of the list to
> >>>>>>> be executed
> >>>>>>> 2. Inserting events into the list (mid- or
> >>>>>>> endpoint).
Sorry for butting in so late in this discussion. But have you considered a
"Heap" (or a priority queue)?
(Or maybe I'm misunderstanding something here?)
http://en.wikipedia.org/wiki/Heap_%28data_structure%29
http://en.wikipedia.org/wiki/Priority_queue
This will allow you, with ease, to get the "lowest" priority. (It is the
first item on the heap).
Time complexity of retrieval is of order: O(n * log(n))
Adding an item, with assorted priority, is also of order: O(n * log(n))
Cheers,
--
EinarI
------=_Part_40387_31392522.1192545962218
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
>>>>>> Ethan Galstad wrote:>>>>>>> For the event queue, I was thinking that a skip
>>>>>>> list structure might be best for efficiency>>>>>>> (http://en.wikipedia.org/wiki/Skip_list). The>>>>>>> event queue is used in primarily two
>>>>>>> situations:>>>>>>> 1. Popping events from the head of the list to>>>>>>> be executed>>>>>>> 2. Inserting events into the list (mid- or
>>>>>>> endpoint).Sorry for butting in so late in this discussion. But have you considered a "Heap" (or a priority queue)?(Or maybe I'm misunderstanding something here?)
http://en.wikipedia.org/wiki/Heap_%28da ... rity_queue
This will allow you, with ease, to get the "lowest" priority. (It is the first item on the heap). Time complexity of retrieval is of order: O(n * log(n))Adding an item, with assorted priority, is also of order: O(n * log(n))
Cheers,--EinarI
------=_Part_40387_31392522.1192545962218--
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]