| Subject: | Possible bug in IntervalTree |
| Date: | Thu, 23 Mar 2017 19:36:28 -0400 |
| To: | bug-IntervalTree [...] rt.cpan.org |
| From: | Jesse McGraw <jlmcgraw [...] gmail.com> |
I'm honestly not sure if this is a bug or not, mathematically speaking
use IntervalTree;
my $intersecter = IntervalTree->new();
$intersecter->insert( 0, 10, "food" );
$intersecter->insert( 3, 7, "wine" );
$intersecter->insert( 2, 12, "cheese" );
print Dumper $intersecter->find( 2, 3 );
Outputs:
/$VAR1 = [//
// 'food',//
// 'cheese'//
// ];/
print Dumper $intersecter->find( 2, 2 );
Outputs:
/$VAR1 = [//
// 'food'//
// ];/
I would expect it to match "cheese" as well
print Dumper $intersecter->find( 7, 7 )
Outputs:
/$VAR1 = [//
// 'food',//
// 'cheese'//
// ];/
I would expect it to match "wine" as well
Should an interval with 0 width (eg the 2,2 or 7,7 intervals above)
match when they fall on the beginning or end of an interval in the tree?
I encountered this lack of matching when using IntervalTree for working
with IPv4 subnets expressed as an interval
Editing IntervalTree.pm as follows worked for my purposes but I'm not
sure if it's correct generally speaking
sub _intersect {
my ( $self, $start, $end, $results ) = @_;
# Left subtree
if ( $self->{cleft} != $EmptyNode && $self->{cleft}{maxend} >
$start ) {
# JLM added the = to the > $start comparison
# if ( $self->{cleft} != $EmptyNode && $self->{cleft}{maxend} >=
$start ) {
$self->{cleft}->_intersect( $start, $end, $results );
}
# This interval
if ( ( $self->{end} > $start ) && ( $self->{start} < $end ) ) {
# JLM added the = to both of these comparisons
# if ( ( $self->{end} >= $start ) && ( $self->{start} <= $end ) ) {
push @$results, $self->{interval};
}
# Right subtree
if ( $self->{cright} != $EmptyNode && $self->{start} < $end ) {
# JLM added the = to the < $end comparison
# if ( $self->{cright} != $EmptyNode && $self->{start} <= $end ) {
$self->{cright}->_intersect( $start, $end, $results );
}
Thanks!
--Jesse