From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p69JMtmF025097
	for <caml-list@sympa-roc.inria.fr>; Sat, 9 Jul 2011 21:22:55 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AvABAICpGE6BryEpkWdsb2JhbABTp1IUAQEBAQkLCwcUBCGIfMJyhjoEl1KLSw
X-IronPort-AV: E=Sophos;i="4.65,505,1304287200"; 
   d="scan'208";a="86886824"
Received: from smtp1.u-psud.fr ([129.175.33.41])
  by mail3-smtp-sop.national.inria.fr with ESMTP; 09 Jul 2011 21:22:50 +0200
Received: from smtp1.u-psud.fr (localhost [127.0.0.1])
	by localhost (MTA) with SMTP id B27D72508B7;
	Sat,  9 Jul 2011 21:22:49 +0200 (CEST)
Received: from ext.lri.fr (ext.lri.fr [129.175.15.4])
	by smtp1.u-psud.fr (MTA) with ESMTP id 69342250866;
	Sat,  9 Jul 2011 21:22:49 +0200 (CEST)
Received: from localhost (localhost [127.0.0.1])
	by ext.lri.fr (Postfix) with ESMTP id 49833401F7;
	Sat,  9 Jul 2011 21:22:49 +0200 (CEST)
X-Virus-Scanned: Debian amavisd-new at lri.fr
Received: from ext.lri.fr ([127.0.0.1])
	by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id CEfvoKAHa-tW; Sat,  9 Jul 2011 21:22:49 +0200 (CEST)
Received: from [192.168.0.10] (mry91-1-82-229-156-20.fbx.proxad.net [82.229.156.20])
	(using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
	(No client certificate requested)
	by ext.lri.fr (Postfix) with ESMTPSA id E94EA3FEA4;
	Sat,  9 Jul 2011 21:22:48 +0200 (CEST)
Message-ID: <4E18AA85.7090707@lri.fr>
Date: Sat, 09 Jul 2011 21:22:45 +0200
From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?=
 <Jean-Christophe.Filliatre@lri.fr>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Thunderbird/3.1.10
MIME-Version: 1.0
To: Jon Harrop <jon@ffconsultancy.com>
CC: Caml List <caml-list@inria.fr>
References: <4E0CAEC3.7010804@gmail.com> <BANLkTinAfZGdJ19mRjpoqVTvN9dpCNymFw@mail.gmail.com> <4E0CC220.8010706@lri.fr> <028b01cc3e16$ee050210$ca0f0630$@ffconsultancy.com>
In-Reply-To: <028b01cc3e16$ee050210$ca0f0630$@ffconsultancy.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Priority queues, reloaded

Le 09/07/2011 11:02, Jon Harrop a écrit :
> Jean-Christophe Filliâtre wrote:
>> Wow, that's impressive! But I guess you didn't need to implement the
> remove
>> operation on red-black trees :-) That's a real pain.
>
> Is Kahrs' so bad:

Hum... You forgot the 13 lines for function app :-)
You must admit that all together it's quite a lot of code (37 lines).

The code for removal in AVLs is shorter (19 lines) and follows a simpler 
logic (based on min_elt and remove_min_elt).

-- 
Jean-Christophe