The FactorialState Struct

The most important thing in designing an iterator is to start with a structure that contains the iterator's "state": all of the data needed when one iteration completes to compute the next one. Iterators never use static or global storage.

Here's the header file factorial.h, which implements the iterator state as a C struct:

struct FactorialState {
// contains all state of the Factorial iterator.
    unsigned int n;     // previous value of n
    unsigned int nFact; // current value of n!
};

extern void factorial_init(struct FactorialState *factorialState);
extern int factorial_next(struct FactorialState *factorialState,
                          unsigned int *nFact);

This header also includes extern declarations for two functions. (You can think of them as "methods" in an object-oriented sense.) In keeping with object-oriented conventions, they always take a (pointer to the) state struct as a first argument.

The first function, fibonacci_init(), is passed a FibonacciState struct (pointer) to initialize. It may also take any parameters needed to initialize that struct, but in this case there are none.

Once the struct is initialized, you pass it to the second ("next") function fibonacci_next() to get every successive member of the sequence. When the sequence is not complete, the "next" function returns 1. When the sequence completes (if it completes), it returns 0. (See the test program below for how this works.)

The Factorial Implementation

The implementations of these functions are in factorial.c:

#include <limits.h>
#include <stdio.h>

#include "factorial.h"


void factorial_init(struct FactorialState *factorialState)
// initialize factorial state
{
    factorialState->n = 1;

    // this will be the first value returned by the iterator
    factorialState->nFact = 1;
}


int factorial_next(struct FactorialState *factorialState, unsigned int *result)
// the "next" method for factorial iterator
{
    if (factorialState->nFact == 0) // can't compute the next result
        return 0;
    (*result) = factorialState->nFact;

    // compute the next step (or prepare to terminate)
    factorialState->n++;

    //
    // In principle, (n+1)! = n! * (n+1), but for this to work with
    // finite precision (32- or 64-bit) ints, we must have
    // 
    //     (n+1)! = n! * (n+1) <= UINT_MAX
    //
    // which implies
    //
    //     n! <= UINT_MAX / (n+1)
    //
    // This predicts, but avoids, overflow. If n! can't be
    // represented, the iterator exits.
    //
    if (factorialState->nFact > UINT_MAX / factorialState->n)
        factorialState->nFact = 0; // iterator will stop on the next call
    else
        factorialState->nFact *= factorialState->n;

    return 1;
}

factorial_init() is easy enough. There's a bit of a complication in factorial_next(): Even though the factorial sequence is infinite, the fact that the results have to be represented in 32-bit unsigned integers limits the sequence. (See the comments for details.)

Test Program

Here is a test program factorial_t.c for the factorial iterator:

#include <stdio.h>

#include "factorial.h"


int main(int argc, char *argv[])
{
    struct FactorialState factorialState;
    unsigned int nFact;

    factorial_init(&factorialState);
    while (factorial_next(&factorialState, &nFact)) {
        printf("%u\n", nFact);
    }
}

Notice how simple this makes using the iterator: Call the "init" function once and the iterator (the "next" function) as many times as needed. If the iterator returns zero, there are no more elements in the sequence. It's even possible to create iterators for infinite sequences that never return 0, such as one for n-sided die rolls where n would be an argument to the "init" function.

Download a copy of the test program from the lab link on the course web page. You will not need to modify this file.

Assignment

1. Download and modify factorial.c and factorial.h to work with (64-bit) unsigned long s. This will allow it to generate more values. (This should not take long. The idea is to get you used to the idea of working with iterators.)
2. Create a makefile that compiles factorial.c into factorial.o and then links factorial.o and factorial_t.o into factorial.

Assignment

1. Download the above string_range.h.
2. In the header file, design and code the StringRangeState struct.
3. Implement the StringRange iterator in a file named string_range.c. You may want to use factorial.c as a template.
4. Write your own test program (in a separate file) to test the iterator.