今まで書いてきた、Pythonのitertoolsに入ってたりそれに近かったり頻繁に使うクラスや関数をここにまとめておき、常に参照することにする。勝手に追加される。
破壊的な変更がされる場合は別にエントリーを立てる。
// // itertools.h // by M.Inamori // written 3/15/10 // reviced 3/24/10 #pragma once #include <iostream> #include <vector> #include <tuple> #include <string> namespace itertools { 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> class filter : public cGenerator<T>{ bool (* pred)(T); bool (* pred2)(T, void *); void *args; cGenerator<T> *obj; public: filter(bool (* p)(T), cGenerator<T> *o) : pred(p), pred2(nullptr), args(nullptr), obj(o) { } filter(bool (* p)(T, void *), void *a, cGenerator<T> *o) : pred(nullptr), pred2(p), args(a), obj(o) { } ~filter() { delete obj; } T next() { T v; do { v = obj->next(); } while(!is_passed(v)); return v; } filter<T> *copy() const { return new filter<T>(pred, obj); } private: bool is_passed(const T& v) const { if(pred != nullptr) return pred(v); else return pred2(v, args); } }; template<typename T> class takewhile : public cGenerator<T>{ bool (* pred)(T); bool (* pred2)(T, void *); void *args; cGenerator<T> *g; public: takewhile(bool (* p)(T), cGenerator<T> *o) : pred(p), pred2(nullptr), args(nullptr), g(o) { } takewhile(bool (* p)(T, void *), void *a, cGenerator<T> *o) : pred(nullptr), pred2(p), args(a), g(o) { } ~takewhile() { delete g; } T next() { T v = g->next(); if(!is_passed(v)) throw(1); return v; } takewhile<T> *copy() const { return new takewhile<T>(pred, g); } private: bool is_passed(const T& v) const { if(pred != nullptr) return pred(v); else return pred2(v, args); } }; template<typename T, typename U> class map : public cGenerator<T> { T (* f)(U); T (* f2)(U, void *); void *args; cGenerator<U> *g; public: map(T (*f)(U), cGenerator<U> *g) : f(f), g(g) { } map(T (*f2)(U, void *), void *a, cGenerator<U> *g) : f(nullptr), f2(f2), args(a), g(g) { } ~map() { delete g; } T next() { return f != nullptr ? f(g->next()) : f2(g->next(), args); } map<T,U> *copy() const { return new map<T,U>(f, g); } }; template<typename T, typename U> class zip : public cGenerator<std::tuple<T,U>> { cGenerator<T> *g1; cGenerator<U> *g2; public: zip(cGenerator<T> *g1, cGenerator<U> *g2) : g1(g1), g2(g2) { } ~zip() { delete g1; delete g2; } std::tuple<T,U> next() { return std::tuple<T,U>(g1->next(), g2->next()); } zip<T,U> *copy() const { return new zip<T,U>(g1, g2); } }; template<typename T> auto fst(T& v) -> decltype(get<0>(v)) { return get<0>(v); } template<typename T> auto snd(T& v) -> decltype(get<1>(v)) { return get<1>(v); } template<typename T,typename U> bool all(T& pred, cGenerator<U> *g) { try { while(true) { if(!pred(g->next())) { return false; } } } catch(int e) { return true; } } template<typename T> T head(cGenerator<T> *g) { try { T v = g->next(); delete g; return v; } catch(int e) { delete g; throw(1); } } template<typename T> auto last(T *g) -> decltype(g->next()) { auto v = g->next(); while(true) { try { v = g->next(); } catch(int e) { delete g; return v; } } } template<typename T> class take : public cGenerator<T> { int n; cGenerator<T> *g; public: take(int n, cGenerator<T> *g) : n(n), g(g) { } T next() { if(n == 0) throw(1); n--; return g->next(); } take *copy() const { return new take(n, g); } }; 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; } T next() { if(current < end) { T v = current; current += delta; return v; } else { throw(1); } } range<T> *copy() const { return new range<T>(current, end, delta); } }; template<typename T = int> class count : public cGenerator<T> { T current; T delta; public: count(T b, T d = 1) : current(b), delta(d) { } count() { current = delta = 0; } T next() { T v = current; current += delta; return v; } count<T> *copy() const { return new count<T>(current, delta); } }; template<typename T> class product : public cGenerator<std::tuple<T,T>> { cGenerator<T> *g; cGenerator<T> *g1; cGenerator<T> *g2; int v; public: product(cGenerator<T> *g) : g(g), g2(nullptr) { g1 = g->copy(); } product(cGenerator<T> *g1, cGenerator<T> *g2) : g(g2), g1(g1), g2(nullptr) { } std::tuple<T,T> next() { if(g2 == nullptr) { g2 = g->copy(); v = g1->next(); } try { return std::tuple<T,T>(v, g2->next()); } catch(int e) { g2 = nullptr; return next(); } } product<T> *copy() const { return new product<T>(g); } }; template<typename T> auto sum(T *g) -> decltype(g->next()) { decltype(g->next()) s = 0; try { while(true) { s += g->next(); } } catch(int e) { delete g; return s; } } template<typename T> auto list(T *g) -> std::vector<decltype(g->next())> { std::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> { const std::vector<T>& v; int k; public: reversed(const std::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); } }; class words : public cGenerator<std::string> { 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); } } words *copy() const { return new words(str); } }; }