How can I iterate subranges in a "cyclic array"?

Issue

I’m trying to write the following Perl subroutine. Given are an array a of length n, an index i in the array (0<=i<n an upstream window length u and a downstream window length d.

I want to iterate over the values in the upstream window and the downstream window to i. In the simplest case, this will iterating over the values in a[i-u..i-1] (upstream window) and a[i+1..i+d] (downstream window).

For example: if my array is 1 2 3 4 5 6 7 8 9 10, i=5 and both window sizes are 2, the upstream values are simply 6 7 and the downstream values are 9 10.

However, there are two complications:

  1. I would like to consider my array is cyclic. If i is relatively small (close to
    0) or large (close to n), then one
    of the windows may not fit in the
    array. In that case, I want to look
    at the array as a cyclic one. for
    example, if my array is 1 2 3 4 5 6 7 8 9 10, i=8 and both window sizes
    are 4, the upstream values are
    simply 4 5 6 7, but the downstream
    values are 9 10 1 2.

  2. I would prefer some way to iterate
    over these values without explicitly
    copying them into a new array, since
    they might be very long.

Solution

You can just get a list of indices using the range operator (..) by subtracting the upstream window from $i and adding the downstream window to $i. You will need to remember to skip the iterator when the iterator is equal to $i if you don’t want that $ith value.

You will need to use the modulo operator (%) to keep the index within the bounds of the array. Given an array of size 11, we can see that by modifying the index with 11 it will always point to the right place in the array:

#!/usr/bin/perl

use strict;
use warnings;

for my $i (-22 .. 22) {
    print "$i => ", $i % 11, "\n";
}

You may run into problems with huge numbers (i.e., numbers larger than what your platform holds in an unsigned integer), because Perl 5 changes the algorithm the modulus uses around there. It becomes more like C’s fmod (but there are some differences).

You may also want to not use the integer pragma. It makes % faster, but you get the behavior of the C modulo operator. Neither ANSI nor ISO define what C should do with negative numbers, so you may or may not get a valid index back. Of course, so long as the version of C spits back either

X   -5 -4 -3 -2 -1 0 1
X%5  0 -4 -3 -2 -1 0 1

or

X   -5 -4 -3 -2 -1 0 1
X%5  0  1  2  3  4 0 1

it should be fine (if not very portable).

It looks like C99 defines the modulo operator to return the second case, so long as perl gets compiled with a C99 compiler (with the C99 flag on) it should be safe to use the integer pragma.

Answered By – Chas. Owens

Answer Checked By – Mary Flores (AngularFixing Volunteer)

Leave a Reply

Your email address will not be published.