Continous Looping of a List

Discussion in 'Perl Misc' started by cp, Sep 24, 2004.

  1. cp

    cp Guest

    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
    cp, Sep 24, 2004
    #1
    1. Advertising

  2. cp

    Paul Lalli Guest

    "cp" <> wrote in message
    news:240920041408114571%...
    > 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
    Paul Lalli, Sep 24, 2004
    #2
    1. Advertising

  3. cp

    cp Guest

    In article <KW_4d.173$va.125@trndny03>, Paul Lalli <>
    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
    cp, Sep 24, 2004
    #3
  4. "Paul Lalli" <> wrote in message
    news:KW_4d.173$va.125@trndny03...
    > "cp" <> wrote in message
    > news:240920041408114571%...
    > > 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
    Brian Helterline, Sep 24, 2004
    #4
  5. cp

    John Bokma Guest

    "Paul Lalli" <> wrote in news:KW_4d.173$va.125@trndny03:

    > "cp" <> wrote in message
    > news:240920041408114571%...
    >> 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
    John Bokma, Sep 24, 2004
    #5
  6. cp

    John Bokma Guest

    cp <> wrote in news:240920041408114571%
    :

    > 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
    John Bokma, Sep 24, 2004
    #6
  7. cp

    Paul Lalli Guest

    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?

    > In article <KW_4d.173$va.125@trndny03>, Paul Lalli <>
    > 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

    >
    >> my $prev = $ids[$pos-1];
    >> my $next = $pos == $#ids ? $ids[0] : $ids[$pos+1];
    >> return ($prev, $next);
    >>}


    Paul Lalli
    Paul Lalli, Sep 25, 2004
    #7
  8. cp

    Paul Lalli Guest

    Brian Helterline wrote:

    > "Paul Lalli" <> wrote in message
    > news:KW_4d.173$va.125@trndny03...
    >
    >>"cp" <> wrote in message
    >>news:240920041408114571%...


    >>
    >>>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.
    Paul Lalli, Sep 25, 2004
    #8
  9. cp

    Paul Lalli Guest

    John Bokma wrote:

    > "Paul Lalli" <> wrote in news:KW_4d.173$va.125@trndny03:
    >
    >
    >>"cp" <> wrote in message
    >>news:240920041408114571%...
    >>


    >>>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
    Paul Lalli, Sep 25, 2004
    #9
  10. cp

    Anno Siegel Guest

    cp <> wrote in comp.lang.perl.misc:
    > In article <KW_4d.173$va.125@trndny03>, Paul Lalli <>
    > 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
    Anno Siegel, Sep 25, 2004
    #10
  11. cp

    John Bokma Guest

    Paul Lalli <> wrote in
    news:cj2bgs$sk$:

    > 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
    <http://www.google.com/search?q=tail+recursion+elimination>

    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
    John Bokma, Sep 27, 2004
    #11
  12. cp

    cp Guest

    In article <cj2bca$sk$>, Paul Lalli
    <> wrote:

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

    >
    > > In article <KW_4d.173$va.125@trndny03>, Paul Lalli <>
    > > 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
    cp, Sep 27, 2004
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    19
    Views:
    10,254
    Neredbojias
    Jun 29, 2005
  2. mobil
    Replies:
    3
    Views:
    235
    Basilisk96
    May 1, 2007
  3. nirvana
    Replies:
    4
    Views:
    304
  4. piyu
    Replies:
    1
    Views:
    303
    John B. Matthews
    Dec 12, 2008
  5. Replies:
    5
    Views:
    261
Loading...

Share This Page