November 01, 1996
URL:http://drdobbs.com/nesting-for-statements-revisited/184403251

Sometimes the best way to capture looping logic is not in the program control structures but in an object that lets you decide at run time how many loops to iterate over.

When C and C++ provide insufficient loop control using existing constructs, use a C++ class to extend the loop control's capabilities. In the July 1996 issue of CUJ ("Nested for Statements, CUJ, July 1996), James Bell presented a solution to a problem concerning nested for statements. To recap, C/C++ programs frequently use nested for statements to cycle through a range of variables. For example, three nested for loops can be used as follows:

for (int i=0; i<p; i++)
    for (int j=0; j<q; j++)
        for (int k=0; k<r; k++)
            DoSomething( i, j, k);

It is often the case that the number of cycles in each loop, controlled by the values of the p, q, and r variables above, are not known until run time. Usually, however, the number of loops themselves (three in this example) are known in advance, allowing them to be hard-coded. The problem that James addressed concerned the situation where the number of for statements cannot be predetermined, and is only known at run time. His solution was to define a function that could be called in place of the nested for loops, and which used recursion to iterate over the required number of loops.

I have recently had to implement a nested for loop with an unknown number of loops, and was interested in the algorithm used. However, the solution given seemed to me to suffer from a few limitations. First, the way that it was coded meant that a specific recursive subroutine needed to be defined for each implementation. Second, although not dogmatic about this, I am personally inclined to avoid recursion if possible; recursion can all too easily result in run-time stack overflows that are difficult to diagnose. Third, the implementation doesn't resemble a normal for-loop construct, which makes following the program logic more difficult and could affect maintenance. Finally, it was coded in C, and my personal preference is for C++.

My solution is the CMultiFor class shown in listings 1 and 2. The big advantage of this class is that it can be used in a manner resembling a standard for loop. This class lends itself to general-purpose use, and does not require a specific routine to be coded for each implementation. Using CMultiFor, you can rewrite the three-loop construct above as:

CMultiFor mfor;
mfor.Add( 0, p );
mfor.Add( 0, q );
mfor.Add( 0, r );
for ( mfor.Initialize();
      mfor.CarryOn();
      mfor.Increment() )
    DoSomething( mfor.Index(0),
                 mfor.Index(1),
                 mfor.Index(2) );

Implementation Details

CMultiFor uses the CArray template class, which is part of the Microsoft Foundation Classes -- replace this with an STL container class if you prefer. In addition, CMultiFor uses the relatively primitive Windows BOOL type to hold the result of the logical comparison; swap this for C++'s new bool if your compiler can cope.

The CMultiFor class contains various member functions:

void CMultiFor::Add( int start,
                     int end )

This adds a for loop. The for loop is equivalent to:

for (i = start; i < end; i++ )

where start and end are defined by the Add function, and i is the loop index for this for loop. The for loops are executed in the order that they are added. For example,

mfor.Add( a, b );
mfor.Add( c, d );
mfor.Add( e, f );

will be equivalent to:

for (int i=a; i<b; i++)
    for (int j=c; j<d; j++)
        for (int k=e; k<f; k++)

As defined, CMultiFor assumes that the loop indices increment at the end of each loop, and that the loop continues while the loop index is less than the end value. In addition, your code must define the values for start and end before any of the loops are executed.

void CMultiFor::Initialize();

Call this member function to initialize the loop indices.

BOOL CMultiFor::CarryOn();

This function tests whether the loop should continue, and returns FALSE when the all loops have exhausted their indices.

void CMultiFor::Increment();

This increments the loop counters.

int CMultiFor::Count()

This function returns the number of nested for loops that have been defined.

int CMultiFor::Index( int i )

The Index function returns the current value of the loop counter for loop i.

Dr. Robin J. Leatherbarrow is a lecturer in Chemistry at Imperial College, University of London, UK. He has a D.Phil. from Oxford University, and uses C++ for various data analysis applications. Robin can be reached at [email protected].

Listing 1: MultiFor.h Definition of the CMultiFor Class

class CMultiFor
{
public:
    CMultiFor() {};
    ~CMultiFor() {};

    // add a for loop
    void Add( int start, int end );

    // looping constucts
    void Initialize();
    BOOL CarryOn();
    void Increment();

    // information
    int Count() {return m_start.GetSize();};
    int Index( int i );

// data
private:
    CArray<int, int&>    m_start;
    CArray<int, int&>    m_end;
    CArray<int, int&>    m_current;
};

// End of File

Listing 2: MultiFor.cpp Multiple for loop class

#include "stdafx.h"    // uses MFC
#include "MultiFor.h"

// Add a for loop
// the loop is used as if it is implemented
// for (i=start; i<end; i++)
void CMultiFor::Add(int start, int end)
{
    // this class assumes that counters increment
    ASSERT( end >= start );
    m_start.Add( start );
    m_end.Add( end );
}

// Initialise the constructs
void CMultiFor::Initialize()
{
    m_current.SetSize( Count() );
    for (int i=0; i<Count(); i++) {
        m_current[i] = m_start[i];
        }
}

int CMultiFor::Index( int i )
{
    // check for invalid conditions
    if (i > m_current.GetUpperBound()) {
        ASSERT(FALSE);
        return -1;
        }

    // have we called Initialize?
    ASSERT( m_current.GetSize() == Count() );

    return m_current[i];
}

BOOL CMultiFor::CarryOn()
{
    // just in case we are called with no entries
    if (Count()==0)
        return FALSE;
    // have we called Initialize?
    ASSERT( m_current.GetSize() == Count() );
    return ( m_current[0] < m_end[0] );
}

void CMultiFor::Increment()
{
    // have we called Initialize?
    ASSERT( m_current.GetSize() == Count() );
    // loop over the array of loop indices
    // starting from the last one added
    int position = m_current.GetUpperBound();
    for (;;) {
        m_current[position]++;
        if (m_current[position] < m_end[position])
            break; // no need to go to the next loop index
        if (position==0)
            break; // terminating condition reached
        // reset this index, and start on the previous one
        m_current[position] = m_start[position];
        position--; 
        }
}
//End of File

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.