From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1FFLvL1016172 for ; Wed, 15 Feb 2012 16:21:57 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkMDAFHMO0/ZSMDyjmdsb2JhbABDsFAiAQEBAQkLEhIFJIFyAQEEATo/BQsLISUPAQQoIROHfwMGtV8Ei3IVBRkFCQkMAgoCBwsMA4NFAwY0BwQFA4MuBJsAjR8 X-IronPort-AV: E=Sophos;i="4.73,424,1325458800"; d="scan'208";a="144385094" Received: from fmmailgate04.web.de ([217.72.192.242]) by mail1-smtp-roc.national.inria.fr with ESMTP; 15 Feb 2012 16:21:53 +0100 Received: from moweb002.kundenserver.de (moweb002.kundenserver.de [172.19.20.108]) by fmmailgate04.web.de (Postfix) with ESMTP id 2246271BB693 for ; Wed, 15 Feb 2012 16:21:53 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb001) with ESMTPA (Nemesis) id 0MRD4x-1S4W3c0pNH-00Ully; Wed, 15 Feb 2012 16:21:51 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1Rxgg2-0005NO-3B; Wed, 15 Feb 2012 16:21:50 +0100 From: Goswin von Brederlow To: Francois Berenger Cc: caml-list@inria.fr, biocaml@googlegroups.com References: <4F346DB9.2070303@riken.jp> <20120210182914.GA17498@annexia.org> <87wr7tb77z.fsf@frosties.localnet> <4F36AA45.1070502@colba.net> <4F38D455.1040204@irisa.fr> <4F3B0A46.3070105@riken.jp> Date: Wed, 15 Feb 2012 16:21:50 +0100 In-Reply-To: <4F3B0A46.3070105@riken.jp> (Francois Berenger's message of "Wed, 15 Feb 2012 10:28:38 +0900") Message-ID: <87mx8kruk1.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Provags-ID: V02:K0:YQOzxU1MBqTQrF+mj19fQvkSTsTfRRcQ0wMykvEwmZO DFH7VCd6DkbARs6uZC3vs7zQr21GUA1O3Q7uvAqY98hNTVnXUK FDFQJU3IKEJjG6LbhB2beHV9C8wAQhqU4CfA7PKiqZwubFcAOp k7N6PIPTQDzTc2Xeig3epw7bcfsNzcXhREz86Za01Zgr1SkX8o qluQfBbp3PPK0QZsUu4RA== Subject: Re: [Caml-list] Fwd: interval trees Francois Berenger writes: > Hello, > > I did a naive implementation of interval trees for float intervals. > > It is available here: > https://github.com/HappyCrow/interval-tree > > I wonder if it is possible to construct the trees in a tail recursive > fashion. Maybe I knew how to do this when I was still at university. > > Regards, > Francois. | Node of (* x_mid left_list right_list left_tree right_tree *) float * interval list * interval list * interval_tree * interval_tree Why interval list? You only need a single interval in leafes and none in other nodes (although it can help to store min and max in each node). You are also missing insert and remove operations, which is the actually hard part in this. Inserting an interval might require merging the rightmost interval left of the root and the leftmost interval right of the root. So you would have 2 removals and one insertion of a combined interval, which complicates balancing the whole thing efficiently. That is the part I'm struggling with. MfG Goswin