fbpx

C++: Generator

Bjarne-stroustrup
 

A generator is an executable entity (like a function or procedure) that contains code that yields a sequence of values, one at a time, so that each time you call the generator, the next value in the sequence is provided. Generators are often built on top of coroutines or objects so that the internal state of the object is handled “naturally”. Generators are often used in situations where a sequence is potentially infinite, and where it is possible to construct the next value of the sequence with only minimal state.

Task description

  1. Create a function that returns a generation of the m’th powers of the positive integers starting from zero, in order, and without obvious or simple upper limit. (Any upper limit to the generator should not be stated in the source but should be down to factors such as the languages natural integer size limit or computational time/size).
  2. Use it to create a generator of:
  1. Squares.
  2. Cubes.
  1. Create a new generator that filters all cubes from the generator of squares.
  2. Drop the first 20 values from this last generator of filtered results then show the next 10 values

Note that this task requires the use of generators in the calculation of the result.

A templated solution:

#include <iostream>
using namespace std;

template<class T>
class Generator
{
public:
	virtual T operator()() = 0;
};

// Does nothing unspecialized
template<class T, T P>
class PowersGenerator: Generator<T> {};

// Specialize with other types, or provide a generic version of pow
template<int P>
class PowersGenerator<int, P>: Generator<int>
{
public:
	int i;
	PowersGenerator() { i = 1; }
	virtual int operator()() 
	{ 
		int o = 1; 
		for(int j = 0; j < P; ++j) o *= i; 
		++i;
		return o; 
	}
};

// Only works with non-decreasing generators
template<class T, class G, class F>
class Filter: Generator<T>
{
public:
	G gen;
	F filter;
	T lastG, lastF;

	Filter() { lastG = gen(); lastF = filter(); }

	virtual T operator()() 
	{
		while(lastG >= lastF)
		{
			if(lastG == lastF)
			lastG = gen();
			lastF = filter();
		}

		T out = lastG;
		lastG = gen();
		return out;
	}
};

int main()
{
	Filter<int, PowersGenerator<int, 2>, PowersGenerator<int, 3>> gen;

	for(int i = 0; i < 20; ++i)
	gen();

	for(int i = 20; i < 30; ++i)
	cout << i << ": " << gen() << endl;
}
Output:
20: 529
21: 576
22: 625
23: 676
24: 784
25: 841
26: 900
27: 961
28: 1024
29: 1089

SOURCE

Content is available under GNU Free Documentation License 1.2.