[Home] [Groups] - Message: [Prev in Group] [Next in Group]
20297: Re: [MUD-Dev] TECH DGN: Re: a few mud server design questions (long)
[Full Header] [Plain Text]
From: "Adam Martin" <ya_hoo_com@yahoo.com>
Newsgroups: nu.kanga.list.mud-dev
Date: Mon, 30 Jul 2001 13:03:08 +0100
References: [1] [2] [3] <-newest
Organization: Kanga.Nu
----- Original Message -----
From: "Sean Kelly" <sean@ffwd.cx>
> From: "Robert Zubek" <rob@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@kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev