Getting around nested conditionals

[hgolden]

Hey

I tried to Super Search this, and I posted it in the Chatterbox, but I got directed here. This is really about finding the most elegant solution to a problem that suggests several ugly answers to me.

I have an N X M matrix that gives an output value for a pair of input values, say $x and $y. Each row of the matrix represents a range of values (disjoint from the others) that $x might fall into. Similarly for columns and $y. Thus, each matrix entry corresponds to the pair of intervals that contain $x and $y.

The most obvious way to deal with this is to create nested conditionals or a bunch of && conditionals that account for $x and $y, but that's unspeakably ugly and takes N*M conditional statements.

Less ugly is making a multi-dimensional hash, keyed by interval ID (e.g. Interval 1, Interval 2...), and then just setting up conditionals to return the right pair of IDs for $x and $y. That reduces the problem to N+M conditionals, but that's still a lot.

I thought about trying to find a way to transform $x and $y into their interval IDs, but the interval boundaries are floats and the first and last intervals are <some_value and >some_other_value, which makes that transformation harder.

I was taught to avoid a long sequence of conditionals, so I have to wonder: Is there a more elegant solution to this? Perhaps a module? Or should I just banish N+M conditionals to a subroutine at the bottom?

Thanks in advance,

Hays

Update:I like jdporter's solution for making the conditionals prettier, but it still involves a bunch of conditionals (unless I misunderstand). I don't have current code, since I'm looking for the best approach, but as per Grandfather's request, here's what code might look like that corresponds to the two approaches I've described:

Here's the solution most obvious to me (and least elegant):

if ($x<1) {
    if ($y<2.5) {
        $z=4;
    } elsif ($y>=2.5 && $y<3.5) {
        $z=6;
    } elsif.....
} elsif ($x>=1 && $x<3.3) {
    if ($y<2.5) {
        $z=3
    }......

And here's the solution that reduces it to N+M conditionals:

if ($x<1) {
    $xkey=1;
} elsif ($x>=1 && $x<3.3) {
    $xkey=2;
}...

if ($y<2.5) {
    $ykey=1;
} elsif ($y>=2.5 && $y<3.5) {
    $ykey=2;
}...

$z=$hash{$xkey}{$ykey};

What else would help?

Update 2: Thanks, nevyn!

[jdporter]

You could use Number::Interval to represent each interval on each axis; then testing a coordinate against an interval is if ( $int->contains( $x ) )

To improve performance, you'd want to do a binary search on each array of intervals, rather than a linear search.

Update: Number::Interval won't work well for binary searches, since it only tells you whether the value is inside the interval or not — not whether (in the latter case) it is above or below the interval.

And since your intervals are contiguous, you're better off simply binary-searching the intervals.

Here's a solution using Search::Binary:

use Search::Binary;
use strict;
use warnings;

#
# Define the intervals in terms of the "critical points" between them:
#
my @x_int = ( 1.0, 3.3 );
my @y_int = ( 2.5, 3.5 );

#
# Define the function on each interval:
# (that is, what should be the "output" value for each interval)
#
my %f;
$f{0,0} = 4;
$f{1,0} = 6;
# . . .
$f{0,1} = 3;
# . . .
$f{2,2} = 5;

#
# Construct the mapping function for each dimension:
#
sub intervalF
{
    my $points_ar = shift;
    my $prev;
    my $read = sub
    { # ugliness necessitated by Search::Binary :-(
        my( $cpar, $v, $p ) = @_;
        if ( defined $p )
        {
            $prev = $p;
        }
        else
        {
            $p = ++$prev;
        }
        ( defined $cpar->[$p] ? ( $v <=> $cpar->[$p] ) : 1, $p )
    };
    sub
    {
        my $val = shift;
        (scalar binary_search( 0, $#{$points_ar},
            $val, $read, $points_ar ))
    }
}

my $xF = intervalF( \@x_int );
my $yF = intervalF( \@y_int );

#
# test:
#
for (
    # x, y
    [ 0, 0 ],
    [ 2, 0 ],
    [ 0, 3 ],
    [ 4, 4 ],
)
{
    my( $x, $y ) = @$_;
    # voila!
    my $z = $f{$xF->($x),$yF->($y)};
    print "( $x $y ) -> $z\n";
}

[BrowserUk]

#! perl -slw
use strict;
use List::Util qw[ first ];
use constant {
    XLIMITS => [ -1e308, 1.0, 2.5, 3.6, 4.8, 5.0, 6.123456789, 1e308 ]
+,
    YLIMITS => [ -1e308, 1.0, 3.3, 4.6, 5.7, 6.8, 7.912345678, 1e308 ]
+,
    XYMAP   => [
        [ 1, 2, 3, 4, 5, 6, 7 ],
        [ 2, 3, 4, 5, 6, 7, 8 ],
        [ 3, 4, 5, 6, 7, 8, 9 ],
        [ 4, 5, 6, 7, 8, 9, 0 ],
        [ 5, 6, 7, 8, 9, 0, 1 ],
        [ 6, 7, 8, 9, 0, 1, 2 ],
        [ 7, 8, 9, 0, 1, 2, 3 ],
    ],
};

sub lookup{
    my( $xVal, $yVal ) = @_;
    my $xIndex = -1 + first{ XLIMITS->[ $_ ] > $xVal } 0 .. $#{ XLIMIT
+S() };
    my $yIndex = -1 + first{ YLIMITS->[ $_ ] > $yVal } 0 .. $#{ YLIMIT
+S() };
    return XYMAP->[ $yIndex ][ $xIndex ];
}


printf '         ' . '%-7.5g   ' x @{ YLIMITS() } . "\n", @{ XLIMITS()
+ };
printf "%7.5g\n\t" . '        %2d' x $#{ XLIMITS() } . "\n",
    YLIMITS->[ $_ ], @{ XYMAP->[ $_ ] }
    for 0 .. $#{ YLIMITS() } - 1;
printf "%7.5g\n", YLIMITS->[ -1 ];
printf "\nEnter X:Y : ";

while( <STDIN> ) {
    chomp;
    if( my( $x, $y ) = m[([\d.]+):([\d.]+)] ) {
        printf "[$x:$y] => %d\n", lookup( $x, $y );
    }
    else {
       warn 'Bad input. Try again';
    }
    printf "\nEnter X:Y : ";
}

__END__
C:\test>575245
         -1e+308   1         2.5       3.6       4.8       5         6
+.1235    1e+308
-1e+308
                 1         2         3         4         5         6  
+       7
      1
                 2         3         4         5         6         7  
+       8
    3.3
                 3         4         5         6         7         8  
+       9
    4.6
                 4         5         6         7         8         9  
+       0
    5.7
                 5         6         7         8         9         0  
+       1
    6.8
                 6         7         8         9         0         1  
+       2
 7.9123
                 7         8         9         0         1         2  
+       3
 1e+308

Enter X:Y : 0:0
[0:0] => 1

Enter X:Y : 999:999
[999:999] => 3

Enter X:Y : 2:2
[2:2] => 3

[sgifford]

The data structure you're looking for is called an Interval Tree.

[nevyn]

As I understand it you have:

      | 1-2   4-8
----------------
1-2   |  a     b
4-8   |  c     d
16-32 |  e     f

...the way to do this is to have a row/col -> values mapping, sort that and loop. Ie.

my $row_map = [{min =>  1, max =>  2},
               {min =>  4, max =>  8},
               {min => 16, max => 32}];
my $row = undef;
for (0..2)
{
  if (($row_map->[$_]->{min} <= $y) &&
      ($row_map->[$_]->{max} >= $y))
  { $row = $_; last }
}

[davidrw]

You can solve this with SQL (use DBD::CSV or DBD::AnyData maybe if you don't want to depend on an external db; though depending on your db you can index this).

One scheme is to make tables like this:

x_mapping
xkey min_x  max_x
1 -9999 1
2 1 3.3

y_mapping
ykey min_y  max_y
1 -9999 2.5  1
2 2.5 3.5

And then:

  my $xkey = $dbh->selectrow_array("SELECT xkey FROM x_mapping WHERE m
+in_x <= ? AND ? < max_x", {}, $x, $x );
  my $ykey = $dbh->selectrow_array("SELECT ykey FROM y_mapping WHERE m
+in_y <= ? AND ? < max_y", {}, $y, $y );


Another scheme:

x_mapping
xkey max_x
1 1.0
2 3.3

y_mapping
ykey max_y
1 2.5
2 3.5

  my $xkey = $dbh->selectrow_array("SELECT xkey FROM x_mapping WHERE ?
+ < max_x ORDER BY max_x ASC LIMIT 1", {}, $x );
  my $ykey = $dbh->selectrow_array("SELECT ykey FROM y_mapping WHERE ?
+ < max_y ORDER BY max_y ASC LIMIT 1", {}, $y );

[GrandFather]

How about a short sample? For almost absolutly sure there is a better way to do it, but in this case a whole lot of prose is not as clear as a few lines of code. Remember that you are describing this to people who do not know your problem domain and don't know what your current code looks like.

Update: a sample matrix would help:)

[fmerges]

Hi,

Don't know your problem domain, but there is also PDL

Regards,