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 q1FHMQEo019278 for ; Wed, 15 Feb 2012 18:22:26 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoYBAKLoO0/RVde2kGdsb2JhbABDhRGaOIhGAYhKCCIBAQEBBwsNBxQEI4FyAQEBAwESAg8EGQEbEgsBAwELBgMCBAcaHQICIgERAQUBChIGEwgKEIddCZxgCosmS4JxhQU/iHMCBQuLTQIYCQEKAQIDCAgJAwIwCQGDKQoDGjUFAgkHAQMFA4IYgRYEgl2FcIxpjik9hCA X-IronPort-AV: E=Sophos;i="4.73,424,1325458800"; d="scan'208";a="144405671" Received: from mail-ey0-f182.google.com ([209.85.215.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 15 Feb 2012 18:22:20 +0100 Received: by eaan10 with SMTP id n10so519744eaa.27 for ; Wed, 15 Feb 2012 09:22:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Fcix+7ljJAf3+ru5GQN7evAnH9jHsLvArDD9EaOMZSs=; b=PzyjSKrvnLl3aPh35GZPbRZwJ7CjmWOI4RDxaQnyCqx/U9KuS2V1q70Hi+i0NlJwz4 SE24kUx5ep749kkfDw48+3iOjRohhU4JGMh9YJULQ5f8j+qe5+DibFVrdJk/oP1cdXz5 484qH28BECh7uKYGiWSaR75b0qocmf1poTaFY= MIME-Version: 1.0 Received: by 10.213.4.9 with SMTP id 9mr1408707ebp.86.1329326540177; Wed, 15 Feb 2012 09:22:20 -0800 (PST) Received: by 10.213.4.5 with HTTP; Wed, 15 Feb 2012 09:22:19 -0800 (PST) In-Reply-To: <87mx8kruk1.fsf@frosties.localnet> 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> Date: Wed, 15 Feb 2012 12:22:19 -0500 Message-ID: From: Edgar Friendly To: Goswin von Brederlow Cc: Francois Berenger , caml-list@inria.fr, biocaml@googlegroups.com Content-Type: multipart/alternative; boundary=000e0cd3401237c33a04b903f478 Subject: Re: [Caml-list] Fwd: interval trees --000e0cd3401237c33a04b903f478 Content-Type: text/plain; charset=UTF-8 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`, 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, 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 > > --000e0cd3401237c33a04b903f478 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable I struggled with this too, but if you read the wikipedia page http://en.wikipedia.org/wiki/Inte= rval_tree, he's implemented a centered interval tree.=C2=A0 Yes, th= ere's a lot of complications needed to insert and remove, but what he&#= 39;s done works for static interval trees.

His lookup function is `int -> interval list`, not `int -> bool`,= so he must keep all the intervals that overlap the center point so he can = return them.=C2=A0 It's useful to have them sorted by left endpoint as = well as right endpoint.=C2=A0 I might have used arrays for them instead of = lists so that binary search is doable, but if they're small, it doesn&#= 39;t matter much.

E.

On Wed, Feb 15, 2012 at 10:21 AM, = Goswin von Brederlow <goswin-v-b@web.de> wrote:
Francois Berenger <berenger@riken.jp> 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<= br> > fashion. Maybe I knew how to do this when I was still at university. >
> Regards,
> Francois.

| Node of
=C2=A0 (* x_mid left_list right_list left_tree right_tree *)
=C2=A0 =C2=A0 =C2=A0float * 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
=C2=A0 =C2=A0 =C2=A0 =C2=A0= Goswin

--
Caml-list mailing list. =C2=A0Subscription 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


--000e0cd3401237c33a04b903f478--