Re: scheduler going backwards solution?

[Sean Murphy <murphys@teltec.dcu.ie>]

> What is "added desk calendar wrapping feature"?
> 
> Heap as well as Calendar had a problem with re-ordering of
> simultaneous events, but that has been fixed.  Keeping the order the
> same is useful for validations and lets different schedulers verify
> each other.
> 
> Calendar is still the default because no one ventured to change it to
> Heap.  There is a hope that recent fixes are enough to keep that
> 'backwards' error from reappearing.  In theory, Calendar's hold time
> (1 enqueue + 1 dequeue) is O(1), which is better than Heap's O(lg(N)).
> In practice, there may be not that much difference, though.

I never understood the differences between these different schedulers, but
I think I'm beginning to see it now. Am I right in saying that

1. The Calendar scheduler uses hashing to insert an event into the
scheduler queue, and hence it takes O(1) to insert and remove an event

2. The Heap scheduler is based on some form of binary tree and it takes
O(lg(N)) to insert and remove events into/out of the scheduler queue?

3. The List scheduler is based on a simple linked list, and it takes O(N)
to insert an event and O(1) to remove the next event - just pop it from
the top of the queue?

Rgds,
Sean.

-----
Sean Murphy,			Email: sean.murphy@teltec.dcu.ie
Teltec Ireland,			Phone: +353-1-7045080
DCU, Dublin 9,			Fax:   +353-1-7045092
Ireland.