# Continous Looping of a List

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
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);
}

--
cp

## Re: Continous Looping of a List

> 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);
> }

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

## Re: Continous Looping of a List

> > 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

## Re: Continous Looping of a List

Brian Helterline wrote:

>

>>
>>>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);
>>>}
>>
>>
>>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.

## Re: Continous Looping of a List

wrote:

> > 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.

> >
> > 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);
> }
>

--
cp

## Re: Continous Looping of a List

cp wrote:

> 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?

> wrote:
>
>>
>>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

## Re: Continous Looping of a List

> 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

>
> > wrote:
> >
> >>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.

--
cp

## Re: Continous Looping of a List

> wrote:
>
> > > 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.

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

> >     return (\$prev, \$next);
> > }

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

## Re: Continous Looping of a List

>> 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.

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

--
John                               MexIT: http://johnbokma.com/mexit/
personal page:       http://johnbokma.com/
Experienced programmer available:     http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

## Re: Continous Looping of a List

John Bokma wrote:

>
>
>>

>>>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.
>
>
> 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

## Re: Continous Looping of a List

> John Bokma wrote:

>> 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?

sub something {

:
:
something();
}

This is called tail recursion. A "smart" compiler can rewrite this.

http://www.program-transformation.org/Transform/TailRecursionElimination

Hence, it's not expensive.

--
John                               MexIT: http://johnbokma.com/mexit/
personal page:       http://johnbokma.com/
Experienced programmer available:     http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

## Re: Continous Looping of a List

cpryce@nospam.pryce.net:

> 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.

--
John                               MexIT: http://johnbokma.com/mexit/
personal page:       http://johnbokma.com/
Experienced programmer available:     http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

## Re: Continous Looping of a List

cp wrote:

> 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);
> }
>

Sometimes recursion is slick, but this is probably not
one of those times. :-)

Perhaps something like the below might work. The only thing
that worries me is you stated the list is 'arbitrarily long'.
What does that mean? The below assumes the whole list will
fit comfortably in memory. If not, well.....

#! /usr/bin/perl -w
use strict;

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

# testing, note the bogus number
for( qw( 3 5 9 7 1 35 ) ) {
my @rv = array_nav( \$_, @ids );
# this might work better as an if/else block
# in real life, but for now...
@rv == 2 ? print "\$rv[0]\t\$rv[1]\n"
: print "\$rv[0]\n";
}

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

# *might* want to check \$val and/or @ids before
# we start the loop, that's up to you

my \$ct = -1;
for( @ids ){
\$ct++;
\$_ == \$val or next;
\$ct == \$#ids ?  return ( \$ids[\$ct-1], \$ids[0] )
:  return ( \$ids[\$ct-1], \$ids[\$ct+1] );
}

# didn't find it, obviously...

}

And our results...
[steve@linux steve]\$ ./test_array.pl
1       5
3       7
7       1
5       9
9       3