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 q1AITOSE013353 for ; Fri, 10 Feb 2012 19:29:24 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ap0IAH5hNU9QRFuw/2dsb2JhbABErl1/gQeBcgEBAQQBAjc/DAQLEQMBAgEcEhQUFBMOE4d/BrkSiSaCXQIEBwIHBwsEAQkCARYQg1+DOmMEkwiCJ5Jl X-IronPort-AV: E=Sophos;i="4.73,397,1325458800"; d="scan'208";a="143768068" Received: from furbychan.cocan.org ([80.68.91.176]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/AES256-SHA; 10 Feb 2012 19:29:18 +0100 Received: from rich by furbychan.cocan.org with local (Exim 4.72) (envelope-from ) id 1RvvDe-0004xj-Sp; Fri, 10 Feb 2012 18:29:14 +0000 Date: Fri, 10 Feb 2012 18:29:14 +0000 From: "Richard W.M. Jones" To: Francois Berenger Cc: caml-list@inria.fr Message-ID: <20120210182914.GA17498@annexia.org> References: <4F346DB9.2070303@riken.jp> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4F346DB9.2070303@riken.jp> User-Agent: Mutt/1.5.20 (2009-06-14) Subject: Re: [Caml-list] Fwd: interval trees 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. -- Richard Jones Red Hat