From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1BHd85D005056 for ; Sat, 11 Feb 2012 18:39:08 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjoDAOWmNk/ZSMDjfWdsb2JhbABEr3AiAQELCwkbBSSBcgEBAQMBAQI3PwUHBAsRAwECAQklDwEEFBQTDhOHfAMGuCCLeQoLAgQHAgcHCwQBCQIBFAYECINfhB0EkwqHb40e X-IronPort-AV: E=Sophos;i="4.73,403,1325458800"; d="scan'208";a="130987690" Received: from fmmailgate02.web.de ([217.72.192.227]) by mail4-smtp-sop.national.inria.fr with ESMTP; 11 Feb 2012 18:39:03 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate02.web.de (Postfix) with ESMTP id DF3381C1069B9 for ; Sat, 11 Feb 2012 18:39:02 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb002) with ESMTPA (Nemesis) id 0MSs2H-1S4H8S1u6P-00S9z9; Sat, 11 Feb 2012 18:39:01 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1RwGuW-0000X5-K7; Sat, 11 Feb 2012 18:38:56 +0100 From: Goswin von Brederlow To: "Richard W.M. Jones" Cc: Francois Berenger , caml-list@inria.fr References: <4F346DB9.2070303@riken.jp> <20120210182914.GA17498@annexia.org> Date: Sat, 11 Feb 2012 18:38:56 +0100 In-Reply-To: <20120210182914.GA17498@annexia.org> (Richard W. M. Jones's message of "Fri, 10 Feb 2012 18:29:14 +0000") Message-ID: <87wr7tb77z.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:9n/hA8T2d9MC7adwLuG90UXu588n28be3CZiAwiIKi7 cqdq9bKCW0DJyruqbvxwUN6kXa0i7gJFlugzr2By12bXLUB2oJ lMltjkqFL7CiwMSwXXY6jDZKX2EhTMTpw5dgVIIaqxivn5+qIA ES3p50lLkJD4Swd8EBUIlX45VIfOmIcEE6VU4d+6X0qg+k9QR0 Y5Ri4OXRpt5LXTFH4kO7A== Subject: Re: [Caml-list] Fwd: interval trees "Richard W.M. Jones" writes: > On Fri, Feb 10, 2012 at 10:07:05AM +0900, Francois Berenger wrote: >> -------- Original Message -------- >> Subject: interval trees >> Date: Thu, 09 Feb 2012 17:30:21 +0900 >> From: Francois Berenger >> To: batteries-discuss@lists.forge.ocamlcore.org >> CC: biocaml@googlegroups.com >> >> Hello, >> >> I need to use an interval tree. >> >> Biocaml has one, batteries have imap/iset, nice! >> >> However, I have intervals of reals, not integers. :( >> >> I want to build the tree (once), then query it with a real number >> (many times) like in: which intervals contain the query real number? >> >> Should I convert my floats to ints (by sorting them then ranking) before >> inserting them into some existing interval tree for integers? >> I am not so concerned about the pre-processing time. >> >> Should I write from scratch? > > I wrote a segment tree (integers, not floats), which is similar. It > wasn't very hard. The code is here if it helps: > > http://git.annexia.org/?p=virt-mem.git;a=blob;f=lib/virt_mem_mmap.ml;hb=HEAD > > Rich. Anyone have something like this but for non-overlapping intervals and allowing interval insertion and removal with merging and spliting of the internaly used intervals? MfG Goswin