Continous Looping of a List

C

cp

I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

The ids will not neccessarily be in sequence. The function is called
once, so the original list does not need to be preserved. The list is
arbitrarily long.

I.e., given a list: 1, 3, 5, 7, 9 and the currently selected id is
value is 5, I need 3 and 7.

I came up with the following, and I have 2 basic questions:
1) is this the best solution?
2) How would I add error checking? I need to abort if the value passed
in is not part of the list, and I only want to check that once, not on
every recursion.


use strict;
use warnings;

my @ids = qw( 1 3 5 7 9 );

# testing
for( qw(3 5 9 7 1) ) {
print join("\t", array_nav( $_, @ids )), "\n";
}

exit(0);

sub array_nav {
my ($val, @ids) = @_;

my $test = shift @ids;
return ( $ids[-1], $ids[0] ) if $test == $val;

push @ids, $test;
array_nav( $val, @ids);
}
 
P

Paul Lalli

cp said:
I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

The ids will not neccessarily be in sequence. The function is called
once, so the original list does not need to be preserved. The list is
arbitrarily long.

I.e., given a list: 1, 3, 5, 7, 9 and the currently selected id is
value is 5, I need 3 and 7.

I came up with the following, and I have 2 basic questions:
1) is this the best solution?

Probably not. Most every algorithm using recursion can better be wrtten
without recursion. This one included.
2) How would I add error checking? I need to abort if the value passed
in is not part of the list, and I only want to check that once, not on
every recursion.

I've added error checking to my solution. See below.
use strict;
use warnings;

my @ids = qw( 1 3 5 7 9 );

# testing
for( qw(3 5 9 7 1) ) {
print join("\t", array_nav( $_, @ids )), "\n";
}

exit(0);

sub array_nav {
my ($val, @ids) = @_;

my $test = shift @ids;
return ( $ids[-1], $ids[0] ) if $test == $val;

push @ids, $test;
array_nav( $val, @ids);
}

My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking
my $prev = $ids[$pos-1];
my $next = $pos == $#ids ? $ids[0] : $ids[$pos+1];
return ($prev, $next);
}

We simply traverse the list once, stopping when we find the correct
item. Then we find the previous and following values of the list.

Hope this Helps,
Paul Lalli
 
C

cp

[QUOTE="Paul Lalli said:
I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

The ids will not neccessarily be in sequence. The function is called
once, so the original list does not need to be preserved. The list is
arbitrarily long.

I.e., given a list: 1, 3, 5, 7, 9 and the currently selected id is
value is 5, I need 3 and 7.
[/QUOTE]

My very bad. In my original problem statement, I neglected to mention
that I need the loop to be continuous. So if the current selected id is
9, the functions needs to return 7 and 1. If the current selection is
1, it needs to return 9 and 3.
I came up with the following, and I have 2 basic questions:
1) is this the best solution?

Probably not. Most every algorithm using recursion can better be wrtten
without recursion. This one included.
2) How would I add error checking? I need to abort if the value passed
in is not part of the list, and I only want to check that once, not on
every recursion.

I've added error checking to my solution. See below.
use strict;
use warnings;

my @ids = qw( 1 3 5 7 9 );

# testing
for( qw(3 5 9 7 1) ) {
print join("\t", array_nav( $_, @ids )), "\n";
}

exit(0);

sub array_nav {
my ($val, @ids) = @_;

my $test = shift @ids;
return ( $ids[-1], $ids[0] ) if $test == $val;

push @ids, $test;
array_nav( $val, @ids);
}

My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking

Yes. I see what you are doing. however, I was hoping for error checking
to determine whether the selected id was part of the set Before
looping. May fault for not stating the problem more clearly.
my $prev = $ids[$pos-1];
my $next = $pos == $#ids ? $ids[0] : $ids[$pos+1];
return ($prev, $next);
}
 
B

Brian Helterline

Paul Lalli said:
cp said:
I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

The ids will not neccessarily be in sequence. The function is called
once, so the original list does not need to be preserved. The list is
arbitrarily long.

I.e., given a list: 1, 3, 5, 7, 9 and the currently selected id is
value is 5, I need 3 and 7.

I came up with the following, and I have 2 basic questions:
1) is this the best solution?

Probably not. Most every algorithm using recursion can better be wrtten
without recursion. This one included.
2) How would I add error checking? I need to abort if the value passed
in is not part of the list, and I only want to check that once, not on
every recursion.

I've added error checking to my solution. See below.
use strict;
use warnings;

my @ids = qw( 1 3 5 7 9 );

# testing
for( qw(3 5 9 7 1) ) {
print join("\t", array_nav( $_, @ids )), "\n";
}

exit(0);

sub array_nav {
my ($val, @ids) = @_;

my $test = shift @ids;
return ( $ids[-1], $ids[0] ) if $test == $val;

push @ids, $test;
array_nav( $val, @ids);
}

My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking
my $prev = $ids[$pos-1];

This can evaluate to $ids[-1] for the first element.
The OP may not want this wrap-around.
my $prev = $pos == 0 ? $ids[0] : $ids[$pos-1];

-brian
 
J

John Bokma

Paul Lalli said:
Probably not. Most every algorithm using recursion can better be wrtten
without recursion. This one included.

A smart compiler removes tail recursion, so in many cases your "probably
not" is wrong. (This is a case of tail recursion, btw).
 
J

John Bokma

I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

Why don't you keep this relation *in* the database? Then you can get it in
O(1) time.
 
P

Paul Lalli

cp said:
My very bad. In my original problem statement, I neglected to mention
that I need the loop to be continuous. So if the current selected id is
9, the functions needs to return 7 and 1. If the current selection is
1, it needs to return 9 and 3.

The output of my function is identical to the output of your funciton,
including returning the 2nd and last element when given the first. Can
you explain to me what your function does that mine does not?

Did you try to run my function, or are you just making an assumption it
doesn't do what you want?
Paul Lalli <[email protected]> said:
My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking


Yes. I see what you are doing. however, I was hoping for error checking
to determine whether the selected id was part of the set Before
looping. May fault for not stating the problem more clearly.

The question here is "why?" Assuming you do have some sort of valid
reason for this, checkout the Perl FAQ:
perldoc -q contained
my $prev = $ids[$pos-1];
my $next = $pos == $#ids ? $ids[0] : $ids[$pos+1];
return ($prev, $next);
}

Paul Lalli
 
P

Paul Lalli

Brian said:
use strict;
use warnings;

my @ids = qw( 1 3 5 7 9 );

# testing
for( qw(3 5 9 7 1) ) {
print join("\t", array_nav( $_, @ids )), "\n";
}

exit(0);

sub array_nav {
my ($val, @ids) = @_;

my $test = shift @ids;
return ( $ids[-1], $ids[0] ) if $test == $val;

push @ids, $test;
array_nav( $val, @ids);
}

My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking
my $prev = $ids[$pos-1];


This can evaluate to $ids[-1] for the first element.
The OP may not want this wrap-around.
my $prev = $pos == 0 ? $ids[0] : $ids[$pos-1];

Did you try running the OP's code? This is exactly what the OP does
want. I *believe* this is what hte OP meant by "continuous".

Paul Lalli.
 
P

Paul Lalli

John said:
A smart compiler removes tail recursion, so in many cases your "probably
not" is wrong. (This is a case of tail recursion, btw).

I don't understand what you mean by this. Can you please explain?

Thank you,
Paul Lalli
 
A

Anno Siegel

cp said:
[QUOTE="Paul Lalli said:
I have a list of ids from a database, and a value for the currently
selected value. I need the previous value (or the index of the previous
value) and the next value in the list.

The ids will not neccessarily be in sequence. The function is called
once, so the original list does not need to be preserved. The list is
arbitrarily long.

I.e., given a list: 1, 3, 5, 7, 9 and the currently selected id is
value is 5, I need 3 and 7.

My very bad. In my original problem statement, I neglected to mention
that I need the loop to be continuous. So if the current selected id is
9, the functions needs to return 7 and 1. If the current selection is
1, it needs to return 9 and 3.[/QUOTE]

Ah, so you want cyclic behavior of the array. The keyword "cyclic"
should always trigger the notion of "modulo" (just like "unique"
triggers "hash").

[Paul Lalli speaking]
My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking

Yes. I see what you are doing. however, I was hoping for error checking
to determine whether the selected id was part of the set Before
looping. May fault for not stating the problem more clearly.

How would you do that? To determine that an element is not in an array
you will have to inspect all array elements. There's got to be some
loop.
my $prev = $ids[$pos-1];
my $next = $pos == $#ids ? $ids[0] : $ids[$pos+1];

The modulo function makes this simpler:

my $prev = $ids[ ($pos - 1) % @ids]; # for symmetry
my $next = $ids[ ($pos + 1) % @ids]; # simplification

You can, however hide the loop. In my solution it is hidden in a hash
slice assignment.

sub array_nav {
my ( $val, @ids) = @_;
my %inv;
@inv{ @ids} = 0 .. $#ids; # here is the invisible loop
defined( my $i = $inv{ $val}) or return;
@ids[ ($i - 1) % @ids, ($i + 1) % @ids];
}

The hash approach has the advantage that it can easily be modified
to check if the values in @ids are unique.

Anno
 
C

cp

Paul Lalli said:
The output of my function is identical to the output of your funciton,
including returning the 2nd and last element when given the first. Can
you explain to me what your function does that mine does not?

Did you try to run my function, or are you just making an assumption it
doesn't do what you want?

No. I responded with the clarrification based on another post. Sorry
about that. Your solution works as expected.
Paul Lalli <[email protected]> said:
My version of your function:

sub array_nav {
my ($val, @ids) = @_;
my $pos;
for ($pos=0; $pos<=$#ids; $pos++){
last if $val == $ids[$pos];
}
return undef unless $pos < @ids; #error checking


Yes. I see what you are doing. however, I was hoping for error checking
to determine whether the selected id was part of the set Before
looping. May fault for not stating the problem more clearly.

The question here is "why?" Assuming you do have some sort of valid
reason for this, checkout the Perl FAQ:
perldoc -q contained

Correct. I was thinking of my recursive function ( the OP ). Having
started down the recursive path, I was thinking that I would need to
check that $val as part of @ids first, or I would have inifinite
recursion. Redoing the funciton without recursion, error checking as
you wrote it is certainly correct.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top