Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!munnari.oz.au!bunyip.cc.uq.oz.au!brolga!uqcspe!cs.uq.oz.au!grue
From: grue@cs.uq.oz.au (Frobozz)
Newsgroups: comp.lang.c
Subject: Re: How to implement these loops ...
Message-ID: <2054@uqcspe.cs.uq.oz.au>
Date: 21 Jun 91 02:49:32 GMT
References: <12844@skye.cs.ed.ac.uk> <1377@unisql.UUCP>
Sender: news@cs.uq.oz.au
Reply-To: grue@cs.uq.oz.au
Lines: 90

In <1377@unisql.UUCP> pckim@unisql.UUCP (Pyung-Chul Kim) writes:

]In article <12844@skye.cs.ed.ac.uk>, scm@cs.ed.ac.uk (Santa C Maria) writes:
]>    for ( i[0] = 0; i[0] < x[0]; ++i[0] ) {
]>       for ( i[1] = 0; i[1] < x[1]; ++i[1] ) {
]> 	 ......
]> 	    for ( i[m-1] = 0; i[m-1] < x[m-1]; ++i[m-1] ) {
]> 	       do_something_here();
]> 	    }
]> 	 ......
]>       }
]>    }
]> 
]> The problem is that m, x[0], ... x[m-1] all depend upon run-time
]> values. The question is how do I code this? 
]> 

]/* assume m and x are global variables */
]foo(j)
]int     j;
]{
]	int     i;
]	if(j == m-1) for(i = 0; i < x[j]; i++) do_something_here(i,j);
]	else for(i = 0; i < x[j]; i++) foo(j+1);
]}

I think that this can be done without a recursive function.  Something
like the following code should be able to do what is required.  I should
also mention that I haven't checked the following code for correctness,
so don't blame me when it don't work.

i[0] = 0;
for(j=0;j>=0;) {
  if(i[j] == x[j]) {	/* terminate a loop */
	j--;		/* to prev loop */
	i[j]++;		/* inc this counter */
  	continue;
  }
  if(j != m-1) {	/* not at deepest level of looping */
	j++;
	i[j] = 0;
	continue;
  }
  do_something();
  i[j]++;
}


An alternative would be to do something like:

	for(j=0,n=1;j<m;j++)	/* calc number of times through loop */
		n *= i[j];

	for(j=0;j<n;j++) {
		for(k=j,j1=m-1;j1>=0;j1--) {
			i[j1] = k % x[j1];
			k /= x[j1];
		}
		do_something();
	}

which first finds out how many times the loops will execute do_something and
then it sets up a loop that big.  At the start of every iteration, it
recalculates the loop index array i[].  This isn't a very efficient method,
but it does avoid the recursion that was present. There should be methods
to save recalculating the entire index array --- it should suffice to stop
recalculating when one of the elements doesn't change.
i.e. Change the line:
			i[j1] = k % x[j1];
to
			tmp = k % x[j1];
			if(i[j1] == tmp) break;
			i[j1] = tmp;


Again I haven't verified this code either.



        						Pauli
seeya

Paul Dale               | Internet/CSnet:            grue@cs.uq.oz.au
Dept of Computer Science| Bitnet:       grue%cs.uq.oz.au@uunet.uu.net
Uni of Qld              | JANET:           grue%cs.uq.oz.au@uk.ac.ukc
Australia, 4072         | EAN:                          grue@cs.uq.oz
                        | UUCP:           uunet!munnari!cs.uq.oz!grue
f4e6g4Qh4++             | JUNET:                     grue@cs.uq.oz.au

--