Re: [Caml-list] Sorted list

[skaller <skaller@users.sourceforge.net>]

On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
> tmp123@menta.net wrote:

> > Of the standard modules, the most similar seems "set", because allows 
> > insertion and has the funcion "min_elt". However, the problem is, if 
> > two timers have the same time, addition of the second one removes the 
> > first.
> >
> > Please, has someone any sugestion?
> >
> > Thanks a lot.
> Hello,
> 
> Let's remind that Set.Make is a functor that takes a module with
> sig
>   type t
>   val compare : t -> t -> int
> end
> 
> If you simply give him a compare function that never returns 0, then you 
> can add multiple elements that are the same.

You cannot do that! compare function must be a total order.

You must keep a list of functions to fire off at a given time,
so the map will be

	time -> timerid list

and you'll also need timerid -> time * (unit->unit) to fetch the
function from the id.

If you want "high performance" interrupt handling then you
should also:

(A) put close timers into the same list

(B) before returning from the interrupt,check to see
if there is another function to execute at a time less
than NOW + some constant.

Given those requirements a good data structure is not
so easy to find. A list is probably the best, assuming
interrupt performance is more important than inserting
and deleting timers.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net