[Tutor] value range checker

[Albert-Jan Roskam]

----------------------------------------
> Subject: Re: value range checker
> To: sjeik_appie at hotmail.com
> CC: tutor at python.org
> From: matt.ruffalo at gmail.com
> Date: Thu, 27 Aug 2015 12:41:45 -0400
>
> On 2015-08-26 09:19, Albert-Jan Roskam wrote:
>> For example, the category-min-max tuples
>>
>> ("cat a", 1, 1),
>>
>> ("cat a", 3, 3),
>>
>> ("cat a", 6, 10),
>>
>> correspond to a range of category A of 1-1, 3-3, 6-10, which is the same as 1, and 3, and 6, 7, 8, 9, 10.
>
> Hi-
>
> An interval tree ( https://en.wikipedia.org/wiki/Interval_tree ) is the
> typical choice of data structure for storing and searching sets of
> intervals, and the bx-python package (
> https://bitbucket.org/james_taylor/bx-python ) has a high-quality Cython
> implementation of one. I have used that interval tree implementation for
> storing intervals of genome coordinates, and it worked very well. I
> don't remember whether that implementation deals with single points very
> well (i.e. start and end are the same value) -- some interval tree
> implementations handle that well and some do not. It shouldn't be much
> of a tweak if not, though.
>
> Like almost any tree-based index structure with O(log n) performance, it
> might only be worth using this when the number of intervals grows large
> enough for a linear search to become a bottleneck.


Hi Matt -- thanks, I did not know this. Interesting. It looks a bit like overkill for what I am trying to do (performance is not a bottleneck), but I will certainly look at it in more detail!


regards,

Albert-Jan