 Syntactic Confectionery Delight PerlMonks

### Find range in array with indices

by IB2017 (Pilgrim)
 on Sep 30, 2019 at 17:48 UTC Need Help??

IB2017 has asked for the wisdom of the Perl Monks concerning the following question:

Dear monks,

Updated

My array contains a set of coordinates indices in the form of "x.x" (coming from a Tk Text widget), being the first value the row and the second the character position. Any two elements of the array represents a couple, i.e. start and end points in a text (element 0 and 1, element 2 and 3, and so forth). An example is:

```my @array = (1.1,1.4,5.33,6.1,7.23,7.133,10,11);

Given a coordinate index, I need to find the range (start end point) in which the coordinate index falls. So, for example, given 1.3, I need to find the range 1.1-1.4, i.e. element 0 and element 1 of my array. I have a small (and verbose) script that can find a range if the array is of natural numbers, but it fails with coordinates indices like mine since, in my example, 7.23 is considered bigger than 7.133 (however, in terms of indices the opposite is the truth). Is there a straightforward way to do comparisons of my indices?

```use strict;
use warnings;

my @array = (1.1,1.4,5.33,6.1,7.23,7.133,10,11);

print "\nenter number\n";
chomp (my \$cursorPosition = <STDIN>);

my \$itr=0;
foreach my \$tagBegin (@array){
if (0 == \$itr % 2) {
}
else{
last if \$cursorPosition <= \$tagBegin;
}
\$itr++;
}
print "Range is \$array[\$itr-1] - \$array[\$itr]";

With the above script, given coordinate 7.25 it finds the wrong range.

Replies are listed 'Best First'.
Re: Find range in coordinates array
by choroba (Cardinal) on Sep 30, 2019 at 18:58 UTC
Tk::Text returns indices, not coordinates. The number before the dot is the line, the number after the dot is the character. In this respect, the indices are similar to v-strings (v7.23 lt v7.133).

You need to do the comparison yourself:

```#!/usr/bin/perl
use warnings;
use strict;

my @indices = qw( 1.1 1.4 5.33 6.1 7.23 7.133 10 11 );

sub i_le {
my (\$x, \$y) = @_;
my (\$x_line, \$x_char) = split /\./, \$x;
my (\$y_line, \$y_char) = split /\./, \$y;
\$_ //= 0 for \$x_char, \$y_char;
return \$x_line < \$y_line
|| \$x_line == \$y_line && \$x_char <= \$y_char
}

sub range {
my (\$in) = @_;
for my \$i (0 .. \$#indices / 2) {
return @indices[\$i * 2, \$i * 2 + 1]
if i_le(\$indices[ \$i * 2 ], \$in)
&& i_le(\$in, \$indices[ \$i * 2 + 1 ]);
}
}

use Test::More tests => 5;
is_deeply [range('1.1')], [qw[ 1.1 1.4 ]];
is_deeply [range('1.2')], [qw[ 1.1 1.4 ]];
is_deeply [range('1.4')], [qw[ 1.1 1.4 ]];
is_deeply [range('7.50')], [qw[ 7.23 7.133 ]];
is_deeply [range('10.5')], [qw[ 10 11 ]];

This is suboptimal as the input is split again for each comparison. It might be better to store tuples instead of strings, i.e. convert on input to tuples and convert back to indices on output.

Note that I used strings to store the indices to avoid imprecise floating point arithmetic.

map{substr\$_->,\$_->||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Thank you choroba. Your solution seems to work just fine with my real data.

Re: Find range in coordinates array (updated)
by haukex (Archbishop) on Sep 30, 2019 at 19:04 UTC

If I understand your format correctly, that's a dangerous way to store these coordinates, as floating-point inaccuracies might possibly mess them up. Is there any way for you to change their format to at least be strings? And what is the maximum number of digits after the decimal point that you can expect?

One possible solution is normalizing the values into integers, then you can use a module such as Set::IntSpan. The following method is fairly expensive in setup, but in exchange lookups should be fairly fast.

<update> Here's a somewhat less complicated version that does pretty much the same. It doesn't overwrite the input array with the "normalized" values and convert them back after, it just keeps the original array.

```use warnings;
use strict;
use List::Util qw/max pairmap/;
use Set::IntSpan;

my @array = (1.1,1.4,5.33,6.1,7.23,7.133,10,11);
my \$input = 7.25;

# check the maxmum number of digits after the decimal point
my \$maxlen = max map { length( (split /\./,\$_,2)//'' ) } @array;

# build the set
my \$set = Set::IntSpan->new( [ pairmap { [\$a,\$b] }
map { my @x = split /\./, \$_, 2;
sprintf "%d%0*d", \$x, \$maxlen, \$x//0 } @array ] );

# normalize the input
die "Input too wide" unless \$input=~/\A\d+(\.\d{1,\$maxlen})?\z/;
my \$innorm = do { my @x = split /\./, \$input, 2;
sprintf "%d%0*d", \$x, \$maxlen, \$x//0 };

# lookup
if ( defined( my \$ord = \$set->span_ord( \$innorm ) ) ) {
my (\$x,\$y) = @array[ \$ord*2, \$ord*2+1 ];
print "found \$input in span \$x-\$y\n";
}
else { warn "did not find \$input in any of the spans\n" }

</update>

Thank you so much. This is such a beautiful implementation!

It works very well if my search value has only 2 digits after the ".". I cannot match anything if I search for the following value with 3 digits after the "." (sorry I haven't specified the forms it can take). Is it possible to make your solution more flexible in terms of number of digits?

```my \$input = 7.255;
I cannot match anything if I search for the following value with 3 digits after the "."

With the code I showed, it works for me for values such as my \$input = 7.111; (that are actually in the range 7.023-7.133). So if that's not working for you, perhaps you could show an SSCCE?

If you're getting the "Input too wide" error, then probably your @array only contains values with two digits after the decimal point or less and the code is adapting \$maxlen (the maximum number of digits after the decimal) to that automatically. You could also do something like "\$maxlen should always be at least three digits, or one digit longer than the values in @array, whichever is bigger" by saying my \$maxlen = 1 + max 2, map ..., or you could just use a fixed \$maxlen.

Re: Find range in coordinates array
by jdporter (Chancellor) on Sep 30, 2019 at 18:26 UTC
7.23 is considered bigger than 7.133 (however, in terms of coordinates the opposite is the truth)

Can you explain this? How is 7.23 not bigger than 7.133?

And what should happen when the given number isn't in any of the ranges?

I'm not sure I'm reading the OP right but I think that their list of numbers is really [start,end] pairs encoded as decimals. "7.23" means the range from character 7 to character 23, which is contained in the range [7,133]. Probably needs to split the string representation into pairs (maybe in an array ref) and then use an in_range( \$range, \$start, \$end ) sub to check.

Or something . . . </handwave>

The cake is a lie.
The cake is a lie.
The cake is a lie.

Re: Find range in coordinates array
by VinsWorldcom (Prior) on Sep 30, 2019 at 18:38 UTC

Agree with jdporter above, not aware of any coordinate system where 7.133 > 7.23.

I think maybe the varying degrees of accuracy are causing confusion? 7.133 is accurate to the thousandths place, where 7.23 is only accurate to the hundredths place. Does this make it easier to understand:

7.23 = 7.230

7.230 > 7.133

UPDATE:A-ha, so this isn't coordinate space, rather Tk indices, see Re: Find range in coordinates array below.

what if it were 7-23 and 7-133 where each size of the - was its own integer co-ord, and 7.23 was actualy 7.0023 and 7.133 was 7.0133

Quick untested idea for fix

```sub fixit {
my \$pt=shift;
my (\$x1,\$x2)=split(/\./,\$pt);
return sprintf ('%08i.%08i',\$x1,\$x2);
}
....
last if (fixit(\$cursorPosition) <= fixit(\$tagBegin));
Much optimzation could be done to that, but it gives you the idea

Thank you. I played a bit with your idea (your assumption was right) and I managed to get a working solution. However, I finally used the solution proposed by Haukex because it seems... simply perfect.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://11106882]
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (1)
As of 2023-01-27 18:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?