今まで作った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); } }