itertools.h

今まで作ったcIterable関係をここにまとめておきます。予告なく修正されることがあります。

#include <iostream>
#include <vector>
#include <tuple>

namespace itertools {
    template<typename T>
    class cIterable {
    public:
        virtual ~cIterable() { }
        virtual bool exists_next() = 0;
        virtual T value() const = 0;
    };
    
    template<typename T>
    std::ostream& operator <<(std::ostream& os,
                    const std::shared_ptr<cIterable<T>>& g) {
        if(g->exists_next()) {
            os << g->value();
            while(g->exists_next())
                os << " " << g->value();
        }
        return os;
    }
    
    template<typename T, typename U>
    std::ostream& operator <<(std::ostream& os, std::tuple<T,U>& x) {
        os << '(' << get<0>(x) << ", " << get<1>(x) << ')';
        return os;
    }
    
    template<typename T, typename U, typename V>
    T reduce(U f, std::shared_ptr<cIterable<V>> g, T init) {
        while(g->exists_next()) {
            init = f(init, g->value());
        }
        return init;
    }
    
    template<typename T, typename U>
    T fst(std::tuple<T,U> x) { return std::get<0>(x); }
    
    template<typename T, typename U>
    U snd(std::tuple<T,U> x) { return std::get<1>(x); }
    
    template<typename T, typename U, typename V, typename W>
    class cUnfold : public cIterable<T> {
        T   val;
        U   stat;
        V   func;
        W   pred;
        
    public:
        cUnfold(V f, U s, W p) : stat(s), func(f), pred(p) { }
        
        bool exists_next() {
            bool    b = !pred(stat);
            if(b) {
                std::tuple<T,U> p = func(stat);
                val = fst(p);
                stat = snd(p);
            }
            return b;
        }
        T value() const { return val; }
    };
    
    template<typename U, typename V, typename W>
    auto unfold(V f, U s, W p) ->
                    std::shared_ptr<cIterable<decltype(fst(f(s)))>> {
        typedef decltype(fst(f(s))) T;
        return std::shared_ptr<cIterable<T>>(new cUnfold<T,U,V,W>(f, s, p));
    }
    
    template<typename U, typename V>
    auto unfold(V f, U s) -> std::shared_ptr<cIterable<decltype(fst(f(s)))>> {
        typedef decltype(fst(f(s))) T;
        auto    pred = [] (U s) { return false; };
        typedef decltype(pred)  W;
        return std::shared_ptr<cIterable<T>>(new cUnfold<T,U,V,W>(f, s, pred));
    }
    
    template<typename T, typename U, typename V>
    class cMap : public cIterable<T> {
        U       func;
        std::shared_ptr<cIterable<V>>   gen;
        
    public:
        cMap(U f, std::shared_ptr<cIterable<V>> g) : func(f), gen(g) { }
        
        bool exists_next() {
            return gen->exists_next();
        }
        T value() const { return func(gen->value()); }
    };
    
    template<typename U, typename V>
    auto map(U func, std::shared_ptr<cIterable<V>> gen) ->
                    std::shared_ptr<cIterable<decltype(func(gen->value()))>> {
        typedef decltype(func(gen->value()))    T;
        return std::shared_ptr<cIterable<T>>(new cMap<T,U,V>(func, gen));
    }
    
    template<typename T, typename U>
    class cFilter : public cIterable<T> {
        U       pred;
        std::shared_ptr<cIterable<T>>   gen;
        
    public:
        cFilter(U p, std::shared_ptr<cIterable<T>> g) : pred(p), gen(g) { }
        
        bool exists_next() {
            while(gen->exists_next()) {
                if(pred(gen->value()))
                    return true;
            }
            return false;
        }
        T value() const {
            return gen->value();
        }
    };
    
    template<typename T, typename U>
    std::shared_ptr<cIterable<T>> filter(
                    U pred, std::shared_ptr<cIterable<T>> gen) {
        return std::shared_ptr<cIterable<T>>(new cFilter<T,U>(pred, gen));
    }
    
    // takewhile
    template<typename T, typename U>
    class cTakeWhile : public cIterable<T> {
        U       pred;
        std::shared_ptr<cIterable<T>>   gen;
        
    public:
        cTakeWhile(U p, std::shared_ptr<cIterable<T>> g) : pred(p), gen(g) { }
        
        bool exists_next() {
            return gen->exists_next() && pred(gen->value());
        }
        T value() const { return gen->value(); }
    };
    
    template<typename T, typename U>
    std::shared_ptr<cIterable<T>> takewhile(
                    U pred, std::shared_ptr<cIterable<T>> gen) {
        return std::shared_ptr<cIterable<T>>(new cTakeWhile<T,U>(pred, gen));
    }
    
    // dropwhile
    template<typename T, typename U>
    class cDropWhile : public cIterable<T> {
        U       pred;
        std::shared_ptr<cIterable<T>>   gen;
        bool    first;
        
    public:
        cDropWhile(U p, std::shared_ptr<cIterable<T>> g) :
                                    pred(p), gen(g), first(true) { }
        
        bool exists_next() {
            if(first) {
                first = false;
                while(gen->exists_next()) {
                    if(!pred(gen->value()))
                        return true;
                }
                return false;
            }
            else {
                return gen->exists_next();
            }
        }
        T value() const { return gen->value(); }
    };
    
    template<typename T, typename U>
    std::shared_ptr<cIterable<T>> dropwhile(
                    U pred, std::shared_ptr<cIterable<T>> gen) {
        return std::shared_ptr<cIterable<T>>(new cDropWhile<T,U>(pred, gen));
    }
    
    // list
    template<typename T>
    std::vector<T> list(std::shared_ptr<cIterable<T>> g) {
        std::vector<T>  v;
        while(g->exists_next())
            v.push_back(g->value());
        return v;
    }
    
    // iter
    template<typename T>
    class cIter : public cIterable<T> {
        const std::vector<T>    v;
        typename std::vector<T>::const_iterator current;
        bool    first;
        
    public:
        cIter(const std::vector<T>& w) : v(w), first(true) { }
        
        bool exists_next() {
            if(first) {
                current = v.begin();
                first = false;
            }
            else
                ++current;
            return current != v.end();
        }
        T value() const { return *current; }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> iter(const std::vector<T>& v) {
        return std::shared_ptr<cIterable<T>>(new cIter<T>(v));
    }
    
    template<typename T>
    class cReversed : public cIterable<T> {
        const std::vector<T>    v;
        typename std::vector<T>::const_reverse_iterator p;
        bool    first;
        
    public:
        cReversed(const std::vector<T>& w) : v(w), first(true) { }
        
        bool exists_next() {
            if(first) {
                first = false;
                p = v.rbegin();
            }
            else {
                ++p;
            }
            return p != v.rend();
        }
        T value() const { return *p; }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> reversed(const std::vector<T>& v) {
        return std::shared_ptr<cIterable<T>>(new cReversed<T>(v));
    }
    
    // zip
    template<typename T, typename U>
    class cZip : public cIterable<std::tuple<T,U>> {
        std::shared_ptr<cIterable<T>>   gen1;
        std::shared_ptr<cIterable<U>>   gen2;
    
    public:
        cZip(std::shared_ptr<cIterable<T>> g1,
                    std::shared_ptr<cIterable<U>> g2) : gen1(g1), gen2(g2) { }
        
        bool exists_next() {
            return gen1->exists_next() && gen2->exists_next();
        }
        std::tuple<T,U> value() const {
            return std::tuple<T,U>(gen1->value(), gen2->value());
        }
    };
    
    template<typename T, typename U>
    std::shared_ptr<cIterable<std::tuple<T,U>>>
    zip(std::shared_ptr<cIterable<T>> g1, std::shared_ptr<cIterable<U>> g2) {
        return std::shared_ptr<cIterable<std::tuple<T,U>>>(new cZip<T,U>(g1, g2));
    }
    
    template<typename T>
    class cSlice : public cIterable<T> {
        std::shared_ptr<cIterable<std::tuple<int,T>>>   gen;
        int     current;
        int     end;
        int     delta;
        bool    last;
        std::shared_ptr<cIterable<int>> counter;
        
    public:
        cSlice(std::shared_ptr<cIterable<T>> g, int n) :
                        current(0), end(n), delta(1), last(false) {
            gen = zip(count(), g);
            counter = range(n);
        }
        cSlice(std::shared_ptr<cIterable<T>> g, int b, int e, int d) :
                            current(b), end(e), delta(d), last(false) {
            gen = zip(count(), g);
            if(e == -1)
                counter = count(b, d);
            else
                counter = range(b, e, d);
        }
        
        bool exists_next() {
            if(!counter->exists_next())
                return false;
            int k = counter->value();
            while(gen->exists_next()) {
                if(fst(gen->value()) == k)
                    return true;
            }
            return false;
        }
        T value() const {
            return snd(gen->value());
        }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> slice(
                    std::shared_ptr<cIterable<T>> g, int n) {
        return std::shared_ptr<cIterable<T>>(new cSlice<T>(g, n));
    }
    
    template<typename T>
    std::shared_ptr<cIterable<T>> slice(
            std::shared_ptr<cIterable<T>> g, int b, int e, int d = 1) {
        return std::shared_ptr<cIterable<T>>(new cSlice<T>(g, b, e, d));
    }
    
    template<typename T>
    class cCycle : public cIterable<T> {
        std::shared_ptr<cIterable<T>>   gen;
        std::vector<T>  v;
        typename std::vector<T>::const_iterator p;
        bool        first;
        
    public:
        cCycle(std::shared_ptr<cIterable<T>> g) : gen(g), first(true) { }
        
        bool exists_next() {
            if(first) {
                if(gen->exists_next()) {
                    v.push_back(gen->value());
                }
                else {
                    first = false;
                    if(v.empty())
                        return false;
                    p = v.begin();
                }
            }
            else {
                if(++p == v.end())
                    p = v.begin();
            }
            return true;
        }
        T value() const {
            return first ? gen->value() : *p;
        }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> cycle(std::shared_ptr<cIterable<T>> g) {
        return std::shared_ptr<cIterable<T>>(new cCycle<T>(g));
    }
    
    template<typename T>
    class cChain : public cIterable<T> {
        std::shared_ptr<cIterable<T>>   gen1;
        std::shared_ptr<cIterable<T>>   gen2;
        bool        first;
        
    public:
        cChain(std::shared_ptr<cIterable<T>> g1,
                            std::shared_ptr<cIterable<T>> g2) :
                            gen1(g1), gen2(g2), first(true) { }
        
        bool exists_next() {
            if(first) {
                if(!gen1->exists_next()) {
                    first = false;
                    return gen2->exists_next();
                }
                else {
                    return true;
                }
            }
            else {
                return gen2->exists_next();
            }
        }
        T value() const {
            return first ? gen1->value() : gen2->value();
        }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> chain(std::shared_ptr<cIterable<T>> g1,
                                        std::shared_ptr<cIterable<T>> g2) {
        return std::shared_ptr<cIterable<T>>(new cChain<T>(g1, g2));
    }
    
    template<typename T>
    std::shared_ptr<cIterable<T>> chain(std::shared_ptr<cIterable<T>> g1,
            std::shared_ptr<cIterable<T>> g2, std::shared_ptr<cIterable<T>> g3) {
        return std::shared_ptr<cIterable<T>>(new cChain<T>(g1, chain(g2, g3)));
    }
    
    template<typename T>
    std::shared_ptr<cIterable<T>> chain(
            std::shared_ptr<cIterable<T>> g1, std::shared_ptr<cIterable<T>> g2,
            std::shared_ptr<cIterable<T>> g3, std::shared_ptr<cIterable<T>> g4) {
        return std::shared_ptr<cIterable<T>>(
                    new cChain<T>(g1, chain(g2, chain(g3, g4))));
    }
    
    // product
    template<typename T, typename U>
    class cProduct : public cIterable<std::tuple<T,U>> {
        std::shared_ptr<cIterable<T>>   gen1;
        std::shared_ptr<cIterable<U>>   gen2;
        std::vector<U>  v;
        typename std::vector<U>::const_iterator p;
        int     mode;
        
    public:
        cProduct(std::shared_ptr<cIterable<T>> g1,
                    std::shared_ptr<cIterable<U>> g2) :
                                    gen1(g1), gen2(g2), mode(0) { }
        
        bool exists_next() {
            if(mode == 0) {
                if(!gen1->exists_next())
                    return false;
                else if(!gen2->exists_next())
                    return false;
                
                mode = 1;
                v.push_back(gen2->value());
                return true;
            }
            else if(mode == 1) {
                if(gen2->exists_next()) {
                    v.push_back(gen2->value());
                    return true;
                }
                else if(gen1->exists_next()) {
                    p = v.begin();
                    mode = 2;
                    return true;
                }
                else {
                    return false;
                }
            }
            else {
                ++p;
                if(p != v.end()) {
                    return true;
                }
                else if(gen1->exists_next()) {
                    p = v.begin();
                    return true;
                }
                else {
                    return false;
                }
            }
        }
        std::tuple<T,U> value() const {
            U   y = mode == 1 ? gen2->value() : *p;
            return std::tuple<T,U>(gen1->value(), y);
        }
    };
    
    template<typename T, typename U>
    std::shared_ptr<cIterable<std::tuple<T,U>>> product(
                                std::shared_ptr<cIterable<T>> g1,
                                std::shared_ptr<cIterable<U>> g2) {
        auto    p = new cProduct<T,U>(g1, g2);
        return std::shared_ptr<cIterable<std::tuple<T,U>>>(p);
    }
    
    template<typename T, typename U, typename V>
    class cDependentlyProduct : public cIterable<std::tuple<T,U>> {
        std::shared_ptr<cIterable<T>>   gen1;
        std::shared_ptr<cIterable<U>>   gen2;
        V       func;
        bool    first;
        
    public:
        cDependentlyProduct(std::shared_ptr<cIterable<T>> g, V f) :
                                        gen1(g), func(f), first(true) { }
        
        bool exists_next() {
            if(first) {
                first = false;
                return next1();
            }
            else if(!gen2->exists_next())
                return next1();
            else
                return true;
        }
        std::tuple<T,U> value() const {
            return std::tuple<T,U>(gen1->value(), gen2->value());
        }
        
    private:
        bool next1() {
            if(!gen1->exists_next())
                return false;
            gen2 = func(gen1->value());
            return gen2->exists_next();
        }
    };
    
    template<typename T, typename V>
    auto product(std::shared_ptr<cIterable<T>> g, V f)
                        -> std::shared_ptr<cIterable<std::tuple<T,
                        decltype(f(g->value())->value())>>> {
        typedef decltype(f(g->value())->value())    U;
        auto    p = new cDependentlyProduct<T,U,V>(g, f);
        return std::shared_ptr<cIterable<std::tuple<T,U>>>(p);
    }
    
    // range
    template<typename T>
    class cRange : public cIterable<T> {
        T       current;
        T       end;
        T       delta;
        
    public:
        cRange(T e) : current(-1), end(e), delta(1) { }
        cRange(T b, T e, T d) : current(b - d), end(e), delta(d) { }
        
        bool exists_next() {
            current += delta;
            return delta > 0 ? current < end : current > end;
        }
        T value() const {
            return current;
        }
    };
    
    template<typename T>
    std::shared_ptr<cIterable<T>> range(T e) {
        return std::shared_ptr<cIterable<T>>(new cRange<T>(e));
    }
    
    template<typename T>
    std::shared_ptr<cIterable<T>> range(T b, T e, T d = 1) {
        return std::shared_ptr<cIterable<T>>(new cRange<T>(b, e, d));
    }
    
    class cCount : public cIterable<int> {
        int     current;
        int     delta;
        
    public:
        cCount(int s, int d) : current(s - d), delta(d) { }
        
        bool exists_next() {
            current += delta;
            return true;
        }
        int value() const {
            return current;
        }
    };
    
    std::shared_ptr<cIterable<int>> count(int s = 0, int d = 1) {
        return std::shared_ptr<cIterable<int>>(new cCount(s, d));
    }
    
    template<typename T>
    T sum(std::shared_ptr<cIterable<T>> g) {
        return reduce([] (T x, T y) { return x + y; }, g, T());
    }
    
    std::shared_ptr<cIterable<int>> digits(int n) {
        auto    f = [] (int n) { return std::tuple<int,int>(n % 10, n / 10); };
        auto    pred = [] (int s) { return s == 0; };
        return unfold(f, n, pred);
    }
}