[Home] [Groups] - Message: [Prev in Group] [Next in Group]

nu.kanga.list.mud-dev

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