how to iterate subranges in a "cyclic array"?

Question

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

Answer 1

You can just get a list of indicies 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 modding 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 back a valid index. 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.