/*
 * Lazy generation of Pythagorean Triples
 * Inspired by http://b...content-available-to-author-only...i.com/2014/04/21/getting-lazy-with-c/
 * John Zwinck, 2014-04-22
 * 
 * This demonstrates a different, perhaps more C++ish solution to lazily
 * generate a sequence.  This approach does no dynamic memory allocation.
 * The main idea is to implement a custom forward iterator (STL compatible).
 *
 * Separation of concerns are handled thusly:
 * 1. Generating Pythagorean Triples is done by our triple_iterator.
 * 2. Printing is handled by std::ostream_iterator<>.
 * 3. Limiting the number of triples generated is via std::copy_n().
 *
 * As in the original version, the algorithm is naive.
 */
 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cassert>
#include <climits>
 
using namespace std;
 
struct triple
{
    int x = 0;
    int y = 0;
    int z = 0;
};
 
ostream& operator<<(ostream& out, const triple& value)
{
	//another sanity check
	assert((value.x * value.x) + (value.y * value.y) == (value.z * value.z));
    return out << value.x << ", " << value.y << ", " << value.z;
}
 
// unbounded forward iterator producing Pythagorean Triples on demand
class triple_iterator : public iterator<forward_iterator_tag, triple>, triple
{
public:
    triple_iterator() { ++*this; } // initialize to the first valid triple
    const triple& operator*() { return *this; }
 
    // set ourselves to the next Pythagorean Triple
    triple_iterator& operator++()
    {
    	//checking sanity since x,y,and z are public members of this iterator
    	assert(z < INT_MAX);
    	assert(y <= z);
    	assert(x <= z);
 
    	++y;
 
        for (;z < INT_MAX; ++z) {
            for (; x < z; ++x) {
                for (; y < z; ++y) {
                    if (x*x + y*y == z*z) {
                        return *this;
                    }
                }
                y = x + 1;
            }
            x = 1;
        }
 
        cerr << "Could not calculate the next Pythagorean triple..." << endl;
        exit(EXIT_FAILURE);
    }
};
 
int main()
{
    // write the first few Pythagorean Triples to stdout
    copy_n(triple_iterator(), 100, ostream_iterator<triple>(cout, "\n"));
}
 

LyoKICogTGF6eSBnZW5lcmF0aW9uIG9mIFB5dGhhZ29yZWFuIFRyaXBsZXMKICogSW5zcGlyZWQgYnkgaHR0cDovL2IuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmkuY29tLzIwMTQvMDQvMjEvZ2V0dGluZy1sYXp5LXdpdGgtYy8KICogSm9obiBad2luY2ssIDIwMTQtMDQtMjIKICogCiAqIFRoaXMgZGVtb25zdHJhdGVzIGEgZGlmZmVyZW50LCBwZXJoYXBzIG1vcmUgQysraXNoIHNvbHV0aW9uIHRvIGxhemlseQogKiBnZW5lcmF0ZSBhIHNlcXVlbmNlLiAgVGhpcyBhcHByb2FjaCBkb2VzIG5vIGR5bmFtaWMgbWVtb3J5IGFsbG9jYXRpb24uCiAqIFRoZSBtYWluIGlkZWEgaXMgdG8gaW1wbGVtZW50IGEgY3VzdG9tIGZvcndhcmQgaXRlcmF0b3IgKFNUTCBjb21wYXRpYmxlKS4KICoKICogU2VwYXJhdGlvbiBvZiBjb25jZXJucyBhcmUgaGFuZGxlZCB0aHVzbHk6CiAqIDEuIEdlbmVyYXRpbmcgUHl0aGFnb3JlYW4gVHJpcGxlcyBpcyBkb25lIGJ5IG91ciB0cmlwbGVfaXRlcmF0b3IuCiAqIDIuIFByaW50aW5nIGlzIGhhbmRsZWQgYnkgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPD4uCiAqIDMuIExpbWl0aW5nIHRoZSBudW1iZXIgb2YgdHJpcGxlcyBnZW5lcmF0ZWQgaXMgdmlhIHN0ZDo6Y29weV9uKCkuCiAqCiAqIEFzIGluIHRoZSBvcmlnaW5hbCB2ZXJzaW9uLCB0aGUgYWxnb3JpdGhtIGlzIG5haXZlLgogKi8KCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNsaW1pdHM+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IHRyaXBsZQp7CiAgICBpbnQgeCA9IDA7CiAgICBpbnQgeSA9IDA7CiAgICBpbnQgeiA9IDA7Cn07Cgpvc3RyZWFtJiBvcGVyYXRvcjw8KG9zdHJlYW0mIG91dCwgY29uc3QgdHJpcGxlJiB2YWx1ZSkKewoJLy9hbm90aGVyIHNhbml0eSBjaGVjawoJYXNzZXJ0KCh2YWx1ZS54ICogdmFsdWUueCkgKyAodmFsdWUueSAqIHZhbHVlLnkpID09ICh2YWx1ZS56ICogdmFsdWUueikpOwogICAgcmV0dXJuIG91dCA8PCB2YWx1ZS54IDw8ICIsICIgPDwgdmFsdWUueSA8PCAiLCAiIDw8IHZhbHVlLno7Cn0KCi8vIHVuYm91bmRlZCBmb3J3YXJkIGl0ZXJhdG9yIHByb2R1Y2luZyBQeXRoYWdvcmVhbiBUcmlwbGVzIG9uIGRlbWFuZApjbGFzcyB0cmlwbGVfaXRlcmF0b3IgOiBwdWJsaWMgaXRlcmF0b3I8Zm9yd2FyZF9pdGVyYXRvcl90YWcsIHRyaXBsZT4sIHRyaXBsZQp7CnB1YmxpYzoKICAgIHRyaXBsZV9pdGVyYXRvcigpIHsgKysqdGhpczsgfSAvLyBpbml0aWFsaXplIHRvIHRoZSBmaXJzdCB2YWxpZCB0cmlwbGUKICAgIGNvbnN0IHRyaXBsZSYgb3BlcmF0b3IqKCkgeyByZXR1cm4gKnRoaXM7IH0KCiAgICAvLyBzZXQgb3Vyc2VsdmVzIHRvIHRoZSBuZXh0IFB5dGhhZ29yZWFuIFRyaXBsZQogICAgdHJpcGxlX2l0ZXJhdG9yJiBvcGVyYXRvcisrKCkKICAgIHsKICAgIAkvL2NoZWNraW5nIHNhbml0eSBzaW5jZSB4LHksYW5kIHogYXJlIHB1YmxpYyBtZW1iZXJzIG9mIHRoaXMgaXRlcmF0b3IKICAgIAlhc3NlcnQoeiA8IElOVF9NQVgpOwogICAgCWFzc2VydCh5IDw9IHopOwogICAgCWFzc2VydCh4IDw9IHopOwoKICAgIAkrK3k7CiAgICAJCiAgICAgICAgZm9yICg7eiA8IElOVF9NQVg7ICsreikgewogICAgICAgICAgICBmb3IgKDsgeCA8IHo7ICsreCkgewogICAgICAgICAgICAgICAgZm9yICg7IHkgPCB6OyArK3kpIHsKICAgICAgICAgICAgICAgICAgICBpZiAoeCp4ICsgeSp5ID09IHoqeikgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gKnRoaXM7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgeSA9IHggKyAxOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHggPSAxOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBjZXJyIDw8ICJDb3VsZCBub3QgY2FsY3VsYXRlIHRoZSBuZXh0IFB5dGhhZ29yZWFuIHRyaXBsZS4uLiIgPDwgZW5kbDsKICAgICAgICBleGl0KEVYSVRfRkFJTFVSRSk7CiAgICB9Cn07CgppbnQgbWFpbigpCnsKICAgIC8vIHdyaXRlIHRoZSBmaXJzdCBmZXcgUHl0aGFnb3JlYW4gVHJpcGxlcyB0byBzdGRvdXQKICAgIGNvcHlfbih0cmlwbGVfaXRlcmF0b3IoKSwgMTAwLCBvc3RyZWFtX2l0ZXJhdG9yPHRyaXBsZT4oY291dCwgIlxuIikpOwp9Cg==