itertools.h（3）

VC10β2で先取りしたC++0xの機能を用いてHaskell風に書けるようにするためのライブラリ。一部は趣味でPython風の名前になっていたりする。ここを常に参照することにする。勝手に追加される。
破壊的な変更がされる場合は別にエントリーを立てる。

//
// itertools.h
// by M.Inamori
// written 3/15/10
// reviced 4/30/10

#pragma once
#include <vector>
#include <tuple>
#include <string>
#include <set>
#include <type_traits>
#include <algorithm>

namespace itertools {
    // reduce
    template<typename T, typename U, typename V>
    V reduce(T f, U& g, V x) {
        while(true) {
            if(g.exists_next())
                x = f(x, g.next());
            else
                return x;
        }
    }
    
    template<typename T, typename U>
    auto reduce1(T f, U& g) -> decltype(g.next()) {
        if(!g.exists_next())
            throw("error : 2nd argument of reduce1 is empty.");
        
        auto    x = g.next();
        while(true) {
            if(g.exists_next())
                x = f(x, g.next());
            else
                return x;
        }
    }
    
    // iterate
    template<typename T, typename U>
    class cIterate {
        T&  func_obj;
        U   v;
        
    public:
        cIterate(T& fo, U v) : func_obj(fo), v(v) { }
        U next() {
            U   tmp = v;
            v = func_obj(v);
            return tmp;
        }
        bool exists_next() { return true; }
    };
    
    template<typename T, typename U>
    cIterate<T,U> iterate(T& fo, U v) {
        return cIterate<T,U>(fo, v);
    }
    
    // iter
    template<typename T, typename U>
    void iter(T& f, U& g) {
        while(g.exists_next())
            f(g.next());
    }
    
    // map
    template<typename T, typename U, typename V>
    class cMap {
        T&  func;
        U&  gen;
        
    public:
        cMap(T& f, U& g) : func(f), gen(g) { }
        V next() {
            return func(gen.next());
        }
        bool exists_next() {
            return gen.exists_next();
        }
    };
    
    template<typename T, typename U>
    auto map(T& func, U& gen) -> cMap<T,U,decltype(func(gen.next()))>{
        return cMap<T,U,decltype(func(gen.next()))>(func, gen);
    }
    
    // filter
    template<typename T, typename U, typename V>
    class cFilter {
        T&  pred;
        U&  gen;
        V   v;
        bool    bexists;
        bool    searched;
        
    public:
        cFilter(T& p, U& g) : pred(p), gen(g), searched(false) { }
        V next() {
            if(!searched) {
                if(!exists_next())
                    throw("error : 2nd argument of filter is empty.");
            }
            searched = false;
            return v;
        }
        bool exists_next() {
            if(searched) {
                return bexists;
            }
            else {
                while(gen.exists_next()) {
                    v = gen.next();
                    if(pred(v)) {
                        bexists = true;
                        searched = true;
                        return true;
                    }
                }
                bexists = false;
                searched = true;
                return false;
            }
        }
    };
    
    template<typename T, typename U>
    auto filter(T& pred, U& gen) -> cFilter<T,U,decltype(gen.next())> {
        return cFilter<T,U,decltype(gen.next())>(pred, gen);
    }
    
    // takewhile
    template<typename T, typename U, typename V>
    class cTakeWhile {
        T&  pred;
        U&  gen;
        V   v;
        bool    bexists;
        bool    searched;
        
    public:
        cTakeWhile(T& p, U& g) : pred(p), gen(g), searched(false) { }
        V next() {
            if(!searched) {
                if(!exists_next())
                    throw("error : 2nd argument of filter is empty.");
            }
            searched = false;
            return v;
        }
        bool exists_next() {
            if(searched) {
                return bexists;
            }
            else {
                if(gen.exists_next()) {
                    v = gen.next();
                    if(pred(v)) {
                        bexists = true;
                        searched = true;
                        return true;
                    }
                }
                bexists = false;
                searched = true;
                return false;
            }
        }
    };
    
    template<typename T, typename U>
    auto takewhile(T& pred, U& gen) -> cTakeWhile<T,U,decltype(gen.next())> {
        return cTakeWhile<T,U,decltype(gen.next())>(pred, gen);
    }
    
    // all
    template<typename T, typename U>
    bool all(T& f, U& g) {
        while(g.exists_next()) {
            if(!f(g.next()))
                return false;
        }
        return true;
    }
    
    // any
    template<typename T, typename U>
    bool any(T& f, U& g) {
        while(g.exists_next()) {
            if(f(g.next()))
                return true;
        }
        return false;
    }
    
    // head
    template<typename T>
    auto head(T& g) -> decltype(g.next()) {
        if(!g.exists_next())
            throw("error : the argument of head is empty.");
        return g.next();
    }
    
    // last
    template<typename T>
    auto last(T& g) ->decltype(g.next()) {
        if(!g.exists_next())
            throw("error : the argument of last is empty.");
        auto    v = g.next();
        while(g.exists_next())
            v = g.next();
        return v;
    }
    
    // take
    template<typename T, typename U>
    class cTake {
        T&  gen;
        int counter;
        
    public:
        cTake(int n, T& g) : counter(n), gen(g) { }
        U next() {
            counter--;
            return gen.next();
        }
        bool exists_next() {
            return counter > 0 && gen.exists_next();
        }
    };
    
    template<typename T>
    auto take(int n, T& g) -> cTake<T,decltype(g.next())> {
        return cTake<T,decltype(g.next())>(n, g);
    }
    
    // length
    template<typename T>
    int length(T& g) {
        return g.exists_next() ? fst(last(zip(count<>(1), g))) : 0;
    }
    
    // zip
    template<typename T, typename U, typename V, typename W>
    class cZip {
        T&  gen1;
        U&  gen2;
        std::tuple<V,W> v;
        
    public:
        cZip(T& g1, U& g2) : gen1(g1), gen2(g2) { }
        std::tuple<V,W> next() {
            return std::make_tuple(gen1.next(), gen2.next());
        }
        bool exists_next() {
            return gen1.exists_next() && gen2.exists_next();
        }
    };
    
    template<typename T, typename U>
    auto zip(T& g1, U& g2) ->
                cZip<T,U,decltype(g1.next()),decltype(g2.next())> {
        return cZip<T,U,decltype(g1.next()),decltype(g2.next())>(g1, g2);
    }
    
    // cat
    template<typename T, typename U, typename V>
    class cConcatenate {
        U&      gen1;
        V&      gen2;
        bool    first;
        
    public:
        cConcatenate(U& g1, V& g2) : gen1(g1), gen2(g2), first(true) { }
        T next() {
            return first ? gen1.next() : gen2.next();
        }
        bool exists_next() {
            if(first) {
                if(gen1.exists_next()) {
                    return true;
                }
                else {
                    first = false;
                    return gen2.exists_next();
                }
            }
            else {
                return gen2.exists_next();
            }
        }
    };
    
    template<typename U, typename V>
    auto cat(U& g1, V& g2) -> cConcatenate<decltype(g1.next()), U, V> {
        return cConcatenate<decltype(g1.next()), U, V>(g1, g2);
    }
    
    // product
    template<typename T, typename U, typename V, typename W>
    class cProduct {
        U&  gen;
        T   gen1;
        U   gen2;
        V   v;
        
    public:
        cProduct(T& g1, U& g2) : gen(g2), gen1(g1), gen2(g2) {
            v = gen1.next();
        }
        std::tuple<V,W> next() {
            if(gen2.exists_next()) {
                return make_tuple(v, gen2.next());
            }
            else {
                v = gen1.next();
                gen2 = gen;
                return next();
            }
        }
        bool exists_next() {
            return gen2.exists_next() || gen1.exists_next();
        }
    };
    
    template<typename T, typename U, typename V, typename W, typename X>
    class cDependentlyProduct {
        T&  gen1;
        X&  fo;
        U   gen2;
        V   v;
        
    public:
        cDependentlyProduct(T& g1, X& g) : gen1(g1), fo(g) {
            v = gen1.next();
            gen2 = fo(v);
        }
        std::tuple<V,W> next() {
            if(gen2.exists_next()) {
                return std::make_tuple(v, gen2.next());
            }
            else {
                v = gen1.next();
                gen2 = fo(v);
                return next();
            }
        }
        bool exists_next() {
            return gen2.exists_next() || gen1.exists_next();
        }
    };
    
    template<typename T>
    class has_paren {
        typedef char    yes;
        typedef struct { char a[2]; } no;
        template<typename U>
        static yes test(U *g, decltype(g->operator()));
        template<typename U>
        static no test(...);
    public:
        static const bool value = sizeof(test<T>(0, 0)) == sizeof(yes);
    };
    
    template<typename T, typename X>
    auto product(T& g, X& fo,
            typename std::enable_if<has_paren<X>::value,X>::type* = 0) ->
        cDependentlyProduct<T,decltype(fo(g.next())),decltype(g.next()),
                                    decltype(fo(g.next()).next()),X> {
        return cDependentlyProduct<T,decltype(fo(g.next())),
            decltype(g.next()), decltype(fo(g.next()).next()),X>(g,fo);
    }
    
    template<typename T, typename U>
    auto product(T& g, U& g2, ...) ->
                cProduct<T,U,decltype(g.next()),decltype(g2.next())> {
        return cProduct<T,U,decltype(g.next()),decltype(g2.next())>(g,g2);
    }
    
    template<typename T>
    auto product(T& g, ...) ->
                cProduct<T,T,decltype(g.next()),decltype(g.next())> {
        return cProduct<T,T,decltype(g.next()),decltype(g.next())>(g,g);
    }
    
    // fst
    template<typename T, typename U>
    T fst(std::tuple<T,U> t) {
        return std::get<0>(t);
    }
    
    // snd
    template<typename T, typename U>
    U snd(std::tuple<T,U> t) {
        return std::get<1>(t);
    }
    
    // range
    template<typename T = int>
    class range {
        T   current;
        T   end;
        T   delta;
        
    public:
        range(T b, T e, T d = 1) : current(b), end(e), delta(d) { }
        range(T e) : current(0), end(e), delta(1) { }
        range() : current(0), end(0), delta(0) { }
        
        T next() {
            if(current < end) {
                T   v = current;
                current += delta;
                return v;
            }
            else {
                throw("error : no more elements in range.");
            }
        }
        bool exists_next() {
            return current < end;
        }
    };
    
    // count
    template<typename T = int>
    class count {
        T   current;
        T   delta;
        
    public:
        count(T b, T d = 1) : current(b), delta(d) { }
        count() : current(0), delta(1) { }
        
        T next() {
            T   v = current;
            current += delta;
            return v;
        }
        bool exists_next() { return true; }
    };
    
    // sum
    template<typename T>
    auto sum(T& gen) -> decltype(gen.next()) {
        decltype(gen.next())    s = 0;
        while(gen.exists_next())
            s += gen.next();
        return s;
    }
    
    // list
    template<typename T>
    auto list(T g) -> std::vector<decltype(g.next())> {
        std::vector<decltype(g.next())> v;
        while(g.exists_next())
            v.push_back(g.next());
        return v;
    }
    
    // iterable
    template<typename T, typename U>
    class cIterable {
        U   current;
        U   end;
        
    public:
        cIterable(U b, U e) : current(b), end(e) { }
        T next() {
            return *(current++);
        }
        bool exists_next() { return current != end; }
    };
    
    template<typename T>
    auto iterable(const std::vector<T>& v)
                        -> cIterable<T,decltype(v.begin())> {
        return cIterable<T,decltype(v.begin())>(v.begin(), v.end());
    }
    
    template<typename T>
    auto iterable(const std::set<T>& s)
                        -> cIterable<T,decltype(s.begin())> {
        return cIterable<T,decltype(s.begin())>(s.begin(), s.end());
    }
    
    template<typename T>
    auto iterable(T begin, T end) -> cIterable<decltype(*begin), T> {
        return cIterable<decltype(*begin), T>(begin, end);
    }
    
    // reversed
    template<typename T>
    class cReversed {
        const std::vector<T>&   v;
        int k;
        
    public:
        cReversed(const std::vector<T>& v) : v(v), k((int)v.size() - 1) { }
        T next() {
            if(k == -1)
                throw("error : no more elements in reversed.");
            return v[k--];
        }
        bool exists_next() {
            return k >= 0;
        }
    };
    
    template<typename T>
    cReversed<T> reversed(const std::vector<T>& v) {
        return cReversed<T>(v);
    }
    
    template<typename T, typename U>
    class cSorted {
        std::vector<T>  sorted_vector;
        typename std::vector<T>::const_iterator current;
        
    public:
        cSorted(const std::vector<T>& v) {
            sorted_vector = v;
            std::sort(sorted_vector.begin(), sorted_vector.end());
            current = sorted_vector.begin();
        }
        cSorted(const std::vector<T>& v, U& cmp) {
            sorted_vector = v;
            std::sort(sorted_vector.begin(), sorted_vector.end(), cmp);
            current = sorted_vector.begin();
        }
        T next() {
            return *(current++);
        }
        bool exists_next() {
            return current != sorted_vector.end();
        }
    };
    
    template<typename T>
    cSorted<T,int> sorted(const std::vector<T>& v) {
        return cSorted<T,int>(v);
    }
    
    template<typename T, typename U>
    cSorted<T,U> sorted(const std::vector<T>& v, U cmp) {
        return cSorted<T,U>(v, cmp);
    }
    
    // 関数を関数オブジェクトに変換
    template<typename T, typename U>
    class cFuncObj {
        U (*func)(T);
        
    public:
        cFuncObj(U (*f)(T)) : func(f) { }
        U operator()(T x) { return func(x); }
    };
    
    template<typename T, typename U>
    cFuncObj<T,U> func_obj(U (*f)(T)) {
        return cFuncObj<T,U>(f);
    }
    
    // 10進関係
    template<typename T, int B = 10>
    class cDigits {
        T   n;
    
    public:
        cDigits(T n = 0) : n(n) { }
        int next() {
            if(n == 0)
                throw("error : no more elements in digits.");
            
            int r = n % B;
            n /= B;
            return r;
        }
        bool exists_next() {
            return n != 0;
        }
    };
    
    template<typename T, int B>
    cDigits<T,B> digits(T n) {
        return cDigits<T,B>(n);
    }
    
    template<typename T>
    cDigits<T> digits(T n) {
        return cDigits<T>(n);
    }
    
    // 数字の並びを変えない
    template<typename T, int B = 10>
    class cDigits2 {
        std::vector<T>  v;
        typename std::vector<T>::reverse_iterator   p;
    
    public:
        cDigits2(T n) {
            v = list(digits(n));
            p = v.rbegin();
        }
        int next() {
            return *(p++);
        }
        bool exists_next() {
            return p != v.rend();
        }
    };
    
    template<typename T, int B>
    cDigits2<T,B> digits2(T n) {
        return cDigits2<T,B>(n);
    }
    
    template<typename T>
    cDigits2<T> digits2(T n) {
        return cDigits2<T>(n);
    }
    
    template<typename T, typename U, int B>
    T to_number(U& g) {
        return reduce([] (T x, int y) { return (T)(x * B + y); }, g, (T)0);
    }
    
    template<typename T>
    auto to_number(T& g) -> decltype(g.next()) {
        typedef decltype(g.next())  U;
        return reduce([] (U x, U y) { return x * 10 + y; }, g, (U)0);
    }
    
#if 0
    template<typename T>
    T to_number(const std::vector<T>& v) {
        return to_number(iterable(v));
    }
#endif
    
    // words
    class words {
        const char  *str;
        
    public:
        words(const char *s) : str(s) { }
        std::string next() {
            const char  *p = str;
            int mode = 0;
            for( ; *p != '\0'; ++p) {
                char    c = *p;
                if(mode == 0) {
                    if(c != ' ') {
                        str = p;
                        mode = 1;
                    }
                }
                else {
                    if(c == ' ') {
                        char    *str2 = new char[p-str+1];
                        strncpy(str2, str, p - str);
                        *(str2 + (p - str)) = '\0';
                        str = p + 1;
                        std::string s = str2;
                        delete str2;
                        return s;
                    }
                }
            }
            
            if(mode == 1) {
                char    *str2 = new char[p-str+1];
                strncpy(str2, str, p - str + 1);
                str = p;
                std::string s = str2;
                delete str2;
                return s;
            }
            else {
                throw(1);
            }
        }
        bool exists_next() {
            return *str != '\0';
        }
    };
}