Re: [Caml-list] Sorted list

["Daniel Bünzli" <daniel.buenzli@epfl.ch>]

Le 4 août 07 à 11:35, tmp123@menta.net a écrit :

> Please, has someone any sugestion?

I once did that by using a leftist heap. Your abstract timerid can  
have a mutable field that indicates if it was cancelled. When you  
peek/pop for the minimal one do it until you get on a timer that was  
not cancellled.

Daniel

P.S. You can use the following code for the heap. Public domain no  
license, no copyright.

(* A leftist heap data structure. *)
module Heap = struct
   type priority = float
   type 'a t =
     | Empty
     | Node of 'a t * int * priority * 'a * 'a t

   let rank = function
     | Empty -> 0
     | Node (_, r, _, _, _) -> r

   let make_node p v h h' =
     let r = rank h in
     let r' = rank h' in
     if r >= r' then Node(h, r' + 1, p, v, h')
     else Node(h', r + 1, p, v, h)

   let rec merge h h' = match h, h' with
   | h, Empty -> h
   | Empty, h -> h'
   | Node(a, _, p, v, b), Node (a', _, p', v', b') ->
       if p <= p' then make_node p v a (merge b h')
       else make_node p' v' a' (merge b' h)

   let empty = Empty

   let is_empty = function
     | Empty -> true
     | _ -> false

   let add h p v = merge (Node(Empty, 1, p, v, Empty)) h

   let min = function
     | Empty -> raise Not_found
     | Node(_, _, p, v, _) -> p, v

   let remove_min = function
     | Empty -> raise Not_found
     | Node(a, _, _, _, b) -> merge a b
end