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 q1G2mEem001392 for ; Thu, 16 Feb 2012 03:48:15 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Al4CADhtPE+GoCGimWdsb2JhbABDgw6CA5o/kTwBAQEBAQYNCwcUJ4FyAQEEASMEETYKEQsYAgIFBBIIAwICCQMCAQIBMwEREwYCAQEOh20Jp1qRaoEviiUkAw0RAQIHCAYBAgMDAgcEBw8JAoNtByoHAgcHBgMDAgEQggeBFgSIS4xrhV2NGg X-IronPort-AV: E=Sophos;i="4.73,426,1325458800"; d="scan'208";a="144457203" Received: from postman2.riken.jp (HELO postman.riken.jp) ([134.160.33.162]) by mail1-smtp-roc.national.inria.fr with ESMTP; 16 Feb 2012 03:48:08 +0100 Received: from postman.riken.jp (postman2.riken.jp [127.0.0.1]) by postman.riken.jp (Postfix) with SMTP id 364FE12601B7 for ; Thu, 16 Feb 2012 11:48:07 +0900 (JST) Received: from [172.27.98.103] (rikad98.riken.jp [134.160.214.98]) by postman.riken.jp (Postfix) with ESMTPA id 16A821270063 for ; Thu, 16 Feb 2012 11:48:07 +0900 (JST) Message-ID: <4F3C6E67.6080109@riken.jp> Date: Thu, 16 Feb 2012 11:48:07 +0900 From: Francois Berenger User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.26) Gecko/20120131 Thunderbird/3.1.18 MIME-Version: 1.0 To: caml-list@inria.fr 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> <87mx8kruk1.fsf@frosties.localnet> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-PMX-Version: 5.6.0.2009776, Antispam-Engine: 2.7.2.376379, Antispam-Data: 2012.2.15.235415 Subject: Re: [Caml-list] Fwd: interval trees On 02/16/2012 02:22 AM, Edgar Friendly wrote: > I struggled with this too, but if you read the wikipedia page > http://en.wikipedia.org/wiki/Interval_tree, he's implemented a centered > interval tree. Yes, there's a lot of complications needed to insert and > remove, but what he's done works for static interval trees. > > His lookup function is `int -> interval list` Precisely, it is: type: interval_tree -> float -> interval list > , not `int -> bool`, so he > must keep all the intervals that overlap the center point so he can > return them. It's useful to have them sorted by left endpoint as well > as right endpoint. I might have used arrays for them instead of lists > so that binary search is doable, That would be a nice optimization for queries indeed. At the moment, I'm more concerned about the program blowing up during tree construction. Regards, F. > but if they're small, it doesn't matter > much. > > E. > > On Wed, Feb 15, 2012 at 10:21 AM, Goswin von Brederlow > > wrote: > > 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 > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > >