This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Sorted list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-08-04 (12:15) From: Daniel_Bünzli Subject: Re: [Caml-list] Sorted list
```
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

(* 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

```