[MUD-Dev] TECH DGN: Re: a few mud server design questions (long)

[Adam Martin]

----- Original Message -----
From: "Sean Kelly" <sean at ffwd.cx>
> From: "Robert Zubek" <rob at cs.northwestern.edu>

>> as i read this, it occured to me that one could also implement
>> this as an unbounded queue of scheduled events, sorted by
>> time. thus, the next scheduled event would always be at the front
>> of the queue, and addition of a new scheduled event would be an
>> insertion into the sorted queue.

>> then, at every tick the global clock pops all events from the
>> front of the queue that have the right timestamp (in tick
>> numbers, not RL time), and sends them off to the appropriate
>> targets.

> Yup.  Another entirely workable solution.  In this case, though,
> scheduling an event would likely be an O(n) operation, as it would
> have to be inserted into the sorted list (by scanning for the
> insertion point from the front).  But processing of events would
> be efficient.

Store the queue as an indexed list (or some other random-insertion
point sorted data structure) and then jump in halfway and do >, <
comparisons to jump to the right place. Insertion becomes O( log(n)
). Otherwise you aren't taking advantage of the fact that its
sorted.

Perhaps use a red-black tree, with a pointer to the item which is
head of the queue.

Adam M
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev