Project Euler 4（2）

productを書きたかったが、なかなか大変だった。タプルで返したかったが、うまくいかない。しかたなくvectorで返すことにした。
productの絡みで、cGeneratorを継承したらcopyメソッドが必要ということにした。今さらだが、mapも作った。
動かしてみたら、Pythonより遅かった。やはりvectorのせい？

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class cGenerator {
public:
    virtual ~cGenerator() { }
    virtual T next() = 0;
    virtual cGenerator *copy() const = 0;
};

template<typename T, typename U>
auto reduce(T f, U *g) -> decltype(f(g->next(), g->next())) {
    decltype(f(g->next(), g->next()))   x = g->next();
    try {
        while(true)
            x = f(x, g->next());
    }
    catch(int e) {
        delete  g;
        return x;
    }
}

template<typename T = int>
class range : public cGenerator<T> {
    T   current;
    T   end;
    T   delta;
    
public:
    range(T b, T e, T d = 1) : current(b), end(e), delta(d) { }
    range(T e) : end(e) {
        current = 0;
        delta = 1;
    }
    range() {
        current = end = delta = 0;
    }
    ~range() { }
    
    T next() {
        if(current < end) {
            T   v = current;
            current += 1;
            return v;
        }
        else {
            throw(1);
        }
    }
    
    range<T> *copy() const {
        return new range<T>(current, end, delta);
    }
};

template<typename T>
class product : public cGenerator<vector<T>> {
    cGenerator<T>   *g;
    cGenerator<T>   *g1;
    cGenerator<vector<T>>   *g2;
    int     repeat;
    bool    first;
    T       v;
    
public:
    product(cGenerator<T> *g, int rep) : g(g), repeat(rep) {
        g1 = g->copy();
        if(repeat >= 2)
            g2 = new product<T>(g->copy(), repeat - 1);
        
        first = true;
    }
    
    vector<T> next() {
        if(repeat == 0) {
            if(first) {
                first = false;
                return vector<T>();
            }
            else {
                throw(1);
            }
        }
        else if(repeat == 1) {
            return vector<T>(1, g1->next());
        }
        else {
            try {
                if(first) {
                    v = g1->next();
                    first = false;
                }
                
                vector<T>   w = g2->next();
                w.insert(w.begin(), v);
                return w;
            }
            catch(int e) {
                delete g2;
                g2 = new product<T>(g->copy(), repeat - 1);
                vector<T>   w = g2->next();
                try {
                    v = g1->next();
                    w.insert(w.begin(), v);
                    return w;
                }
                catch(int e) {
                    delete g;
                    delete g1;
                    delete g2;
                    throw(1);
                }
            }
        }
    }
    
    product<T> *copy() const {
        return new product<T>(g, repeat);
    }
};

template<typename T>
class filter : public cGenerator<T>{
    bool (* pred)(T);
    cGenerator<T>   *obj;
    
public:
    filter(bool (* p)(T), cGenerator<T> *o) : pred(p), obj(o) { }
    ~filter() {
        delete obj;
    }
    T next() {
        T   v;
        do {
            v = obj->next();
        } while(!pred(v));
        return v;
    }
    filter<T> *copy() const { return new filter<T>(pred, obj); }
};

template<typename T, typename U>
class map : public cGenerator<T> {
    T (* f)(U);
    cGenerator<U>   *g;
    
public:
    map(T (*f)(U), cGenerator<U> *g) : f(f), g(g) { }
    ~map() { delete g; }
    T next() { return f(g->next()); }
    map<T,U> *copy() const { return new map<T,U>(f, g); }
};

template<typename T>
auto list(T *g) -> vector<decltype(g->next())> {
    vector<decltype(g->next())> v;
    try {
        while(true)
            v.push_back(g->next());
    }
    catch(int e) {
        return v;
    }
}

template<typename T>
class reversed : public cGenerator<T> {
    vector<T>&  v;
    int k;
    
public:
    reversed(vector<T>& v) : v(v) { k = (int)v.size() - 1; }
    T next() {
        if(k == -1)
            throw(1);
        return v[k--];
    }
    
    reversed<T> *copy() const {
        return new reversed<T>(v);
    }
};

template<typename T>
class digits : cGenerator<T> {
    int     d;
    digits<T>   *g;
    
public:
    digits(int n) {
        g = NULL;
        if(n > 0)
            g = new digits(n / 10);
        d = n % 10;
    }
    digits(digits<T> *g, int d) : g(g), d(d) { }
    
    int next() {
        if(g != NULL) {
            try {
                return g->next();
            }
            catch(int e) {
                g = NULL;
                return d;
            }
        }
        throw(1);
    }
    
    digits<T> *copy() const {
        return new digits<T>(g->copy(), d);
    }
};

template<typename T>
T to_numerize(cGenerator<T> *g) {
    return reduce([](int x, int y) { return x * 10 + y; }, g);
}

template<typename T>
bool is_palindromic(T n) {
    return n == to_numerize(new reversed<int>(list(new digits<T>(n))));
}

template<typename T>
T mul(vector<T> v) {
    return v[0] * v[1];
}

int main() {
    cout << reduce([](int x, int y) { return x >= y ? x : y; },
                new filter<int>(is_palindromic,
                new map<int,vector<int>>(mul<int>,
                new product<int>(new range<>(100, 1000), 2)))) << endl;
}