Simple Programming Challenge: Arbitrary Iteration

Introduction

Have you ever written code which was focused on stepping through an array of however many dimensions the provider of the array had to use? If you have, then you're familiar with how annoying it can be to rewrite the same method more than once only to provide the same calculations, differing by the number of loops used to step through them. It's also possible to create a recursive method which has the same functionality; however, the user of such a system has less control over when you can break out of the loop.

Background

If you're familiar with C# 2.0 and above, you've probably used iterators to some degree. If not, head over to MSDN read up on them, they're increasingly useful in today's environment.

Traditionally

Let's assume the array you're working with is from another source, and they were such nice chaps that they created it like so:

int[, , , , , ,] values = (int[, , , , , ,])Array.CreateInstance
(typeof(int), new int[] { 4, 4, 4, 4, 4, 4, 4 }, new int[] 
{ -3, 15, 1024, 58, -90, 3, -1 });

If you're familiar with such array creation, you know that there are seven dimensions and four items in each dimension, for a total of 4⁷ (16,384) elements, with start indices of: -3, 15, 1024, 58, -90, 3, -1.

Now, normally to iterate through a seven-dimensional array, you'd need to set up seven different loops nested within one another:

for (int i1 = values.GetLowerBound(0), i1M = values.GetUpperBound(0),
    i2L = values.GetLowerBound(1), i2M = values.GetUpperBound(1),
    i3L = values.GetLowerBound(2), i3M = values.GetUpperBound(2),
    i4L = values.GetLowerBound(3), i4M = values.GetUpperBound(3),
    i5L = values.GetLowerBound(4), i5M = values.GetUpperBound(4),
    i6L = values.GetLowerBound(5), i6M = values.GetUpperBound(5),
    i7L = values.GetLowerBound(6), i7M = values.GetUpperBound(6); i1 <= i1M; i1++)
    for (int i2 = i2L; i2 <= i2M; i2++)
        for (int i3 = i3L; i3 <= i3M; i3++)
            for (int i4 = i4L; i4 <= i4M; i4++)
                for (int i5 = i5L; i5 <= i5M; i5++)
                    for (int i6 = i6L; i6 <= i6M; i6++)
                        for (int i7 = i7L; i7 <= i7M; i7++)
                            values[i1, i2, i3, i4, i5, i6, i7] *= 
				values[i1, i2, i3, i4, i5, i6, i7];

As I'm sure you know, such code is irksome to write. It can also become difficult to maintain if you cover a large series of different dimensions of arrays.

A Simpler Solution

Granted, iterating through an array in most cases is easily achieved by a foreach over the array. The issue with this is that you're unable to alter the array, and you're also unaware of exactly where within the array you are at any given moment. Sure you could track it using an index, but that single index wouldn't be representative of all the dimensions within that array.

This is where an iterator comes in:

/// <summary>
/// Obtains an enumerable object which can iterate through all of
/// the indices of an <see cref="Array"/> regardless of its 
/// dimensional complexity.
/// </summary>
/// <param name="array">The <see cref="Array"/> to perform
/// iteration on.</param>
/// <returns>A <see cref="IEnumerable{T}"/> object that
/// yields a single-dimensional array per iteration relative
/// to the <paramref name="array"/> provided.</returns>
/// <remarks><para>The number of values in the resultant array,
/// per iteration, is equivalent to the
/// <see cref="Array.ArrayRank"/> of the 
/// <paramref name="array"/> provided.</para>
/// <para>Due to the nature this method was intended to be used,
/// the array retrieved per iteration is the same so it is not
/// guaranteed to be the same on a much later access
/// should its reference be stored, and the iteration
/// continued.</para></remarks>
public static IEnumerable<int[]> Iterate(this Array array)
{
    int[] indices;
    int rank = array.Rank;
    if (rank == 1)
    {
        /* *
         * Simple answer for one dimension
         * */
        indices = new int[] { array.GetLowerBound(0) };
        for (; indices[0] <= array.GetUpperBound(0); indices[0]++)
            yield return indices;
    }
    else
    {
        /* *
         * Multi-dimensional, or non-vector, arrays are a bit different.
         * */
        indices = new int[array.Rank];
        /* *
            * Obtain the upper/lower bounds..
            * */
        int[] upperBounds = new int[array.Rank];
                
        for (int i = 0; i < rank; i++)
        {
            indices[i] = array.GetLowerBound(i);
            upperBounds[i] = array.GetUpperBound(i);
        }
 
        int[] lowerBounds = (int[])indices.Clone();
 
    Repeater:
        {
            /* *
             * Nifty thing is... it's always the same array,
             * which means there's no performance hit for
             * creating and returning new arrays, because we don't.
             * */
            yield return indices;
            /* *
                * Move through the dimensions, starting 
                * with the highest-order.
                * */
            for (int i = rank - 1; i >= 0; i--)
            {
                /* *
                 * Index the current dimension...
                 * */
                indices[i]++;
                /* *
                 * If the current dimension is in range
                 * we're done.
                 * */
                if (indices[i] <= upperBounds[i])
                    break;
                /* *
                 * Reset the current index, the loop
                 * will continue until all 'overflows' 
                 * on the array are hit and reset 
                 * accordingly.
                 * */
                indices[i] = lowerBounds[i];
                /* *
                 * If the first dimension has been incremented
                 * and exceeded the high point of the dimension,
                 * then exit stage left.
                 * */
                if (i == 0)
                    yield break;
            }
            goto Repeater;
        }
    }
    yield break;
}

Each point within the array is yielded as a set of indices within that array. Further, there's only one array instance ever returned, reducing memory footprint of such a method.

Since it's an iterator, instead of a recursive solution, breaking from the array is as simple as breaking any one of the loops, perhaps easier.

Here's an example use of the iterator:

foreach (var indices in values.Iterate())
{
    int current = (int)values.GetValue(indices);
    values.SetValue(current * current, indices);
}

Points of Interest

There is an overhead incurred by using this, versus a dimension-specific set of alternatives; however, the simplicity it gives you mitigates it, in my mind. The level of overhead is negligible, as an example, iterating through the array demonstrated above takes 0.0002451 seconds traditionally (with seven nested loops), and 0.0009789 with the iterator. Odds are the action you'll be executing within that loop will take far longer than the overhead incurred by the iterator.

One thing I can see this being useful for is printing an array. Versus creating a set of loops to print the elements within an n-dimensional array, you can just use the iterator, emit the indices each step, and emit the actual value associated to that set of indices.

History

• October 12, 2010 - Version 1.0