//Rewrite from https://github.com/k06a/boolinq
//Test successfully on VS2009 16.11.2

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <type_traits>
#include <unordered_set>
#include <vector>

namespace boolinq
{
  struct LinqEndException {};

  template<typename S, typename T>
  class Linq
  {
    std::function<T(S&)> nextFunc; //操作子
    S storage; //实际存储

  public:
    typedef T value_type;

    Linq() : nextFunc(), storage() {}
    Linq(S storage, std::function<T(S&)> nextFunc) : nextFunc(nextFunc), storage(storage) {}
    T next() { return nextFunc(storage); } //调用操作子，取下一个有效值

    void for_each_i(std::function<void(T, int)> apply) const //遍历不能改变本身
    {
      Linq<S, T> linq = *this; //所以必须要拷贝一份
      try {
        for (int i = 0; ; i++)
          apply(linq.next(), i);
      } catch (LinqEndException&) {} //捕获：from, orderBy, distinct
    }

    void for_each(std::function<void(T)> apply) const
    {
      return for_each_i([apply](T value, int) { return apply(value); });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> where_i(std::function<bool(T, int)> filter) const
    {
      return Linq<std::tuple<Linq<S, T>, int>, T>(std::make_tuple(*this, 0),
        [filter](std::tuple<Linq<S, T>, int>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          int& index = std::get<1>(tuple);
          while (true) {
            T ret = linq.next(); //可能会抛异常。但上有源头，下有终结，因此这里不用捕获
            if (filter(ret, index++))
              return ret;
          }
        });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> where(std::function<bool(T)> filter) const
    {
      return where_i([filter](T value, int) { return filter(value); });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> take(int count) const
    {
      return where_i([count](T /*value*/, int i) {
        if (i == count)
          throw LinqEndException{};
        return true;
        });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> takeWhile_i(std::function<bool(T, int)> predicate) const
    {
      return where_i([predicate](T value, int i) {
        if (!predicate(value, i))
          throw LinqEndException{};
        return true;
        });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> takeWhile(std::function<bool(T)> predicate) const
    {
      return takeWhile_i([predicate](T value, int /*i*/) { return predicate(value); });
    }

    Linq<std::tuple<Linq<S, T>, int>, T> skip(int count) const
    {
      return where_i([count](T /*value*/, int i) { return i >= count; });
    }

    Linq<std::tuple<Linq<S, T>, int, bool>, T> skipWhile_i(std::function<bool(T, int)> predicate) const
    {
      return Linq<std::tuple<Linq<S, T>, int, bool>, T>(std::make_tuple(*this, 0, false),
        [predicate](std::tuple<Linq<S, T>, int, bool>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          int& index = std::get<1>(tuple);
          bool& flag = std::get<2>(tuple); //跳过结束标记
          if (flag)
            return linq.next();
          while (true) {
            T ret = linq.next();
            if (!predicate(ret, index++)) {
              flag = true;
              return ret;
            }
          }
        });
    }

    Linq<std::tuple<Linq<S, T>, int, bool>, T> skipWhile(std::function<bool(T)> predicate) const
    {
      return skipWhile_i([predicate](T value, int /*i*/) { return predicate(value); });
    }

    template<typename ... Types>
    Linq<std::tuple<Linq<S, T>, std::vector<T>, int>, T> append(Types ... newValues) const
    {
      return Linq<std::tuple<Linq<S, T>, std::vector<T>, int>, T>(
        std::make_tuple(*this, std::vector<T>{ newValues... }, -1), //第三个参数为新加值索引，-1未开始
        [](std::tuple<Linq<S, T>, std::vector<T>, int>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          std::vector<T>& values = std::get<1>(tuple);
          int& index = std::get<2>(tuple);
          if (index == -1) { //-1先遍历已有
            try {
              return linq.next();
            } catch (LinqEndException&) {
              index = 0; //已有的遍历完了，开始添加新值
            }
          }
          if (index < static_cast<int>(values.size())) //遍历新值
            return values[index++];
          throw LinqEndException{}; //全部加完，抛异常以结束（使用端捕获）
        }
      );
    }

    template<typename ... Types>
    Linq<std::tuple<Linq<S, T>, std::vector<T>, int>, T> prepend(Types ... newValues) const
    {
      return Linq<std::tuple<Linq<S, T>, std::vector<T>, int>, T>(
        std::make_tuple(*this, std::vector<T>{ newValues... }, 0), //第三个参数为新加值索引，从零开始
        [](std::tuple<Linq<S, T>, std::vector<T>, int>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          std::vector<T>& values = std::get<1>(tuple);
          int& index = std::get<2>(tuple);
          if (index < static_cast<int>(values.size())) //先遍历新加值
            return values[index++];
          return linq.next(); //再遍历已有，内部结束已含抛异常
        });
    }

    template<typename F, typename RT = std::invoke_result<F, T>::type>
    Linq<Linq<S, T>, RT> select(F apply) const
    {
      return Linq<Linq<S, T>, RT>(*this, [apply](Linq<S, T>& linq) { return apply(linq.next()); });
    }

    template<typename TRet>
    Linq<std::tuple<Linq<S, T>, int>, TRet> cast() const
    {
      return select_i([](T value, int) { return TRet(value); });
    }

    template<typename S2, typename T2>
    Linq<std::tuple<Linq<S, T>, Linq<S2, T2>, bool>, T> concat(const Linq<S2, T2>& rhs) const
    {
      return Linq<std::tuple<Linq<S, T>, Linq<S2, T2>, bool>, T>(std::make_tuple(*this, rhs, false),
        [](std::tuple<Linq<S, T>, Linq<S2, T2>, bool>& tuple) {
          Linq<S, T>& first = std::get<0>(tuple);
          Linq<S2, T2>& second = std::get<1>(tuple);
          bool& flag = std::get<2>(tuple); //标记是否已进入后段
          if (!flag) {
            try {
              return first.next();
            } catch (LinqEndException&) {}
          }
          return second.next();
        }
      );
    }

    template<typename F, typename TR = std::invoke_result<F, T, int>::type, typename TRV = TR::value_type>
    Linq<std::tuple<Linq<S, T>, TR, int, bool>, TRV> selectMany_i(F apply) const
    {
      return Linq<std::tuple<Linq<S, T>, TR, int, bool>, TRV>(std::make_tuple(*this, TR{}, 0, true),
        [apply](std::tuple<Linq<S, T>, TR, int, bool>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          TR& current = std::get<1>(tuple);
          int& index = std::get<2>(tuple);
          bool& finished = std::get<3>(tuple); //上一次 selectMany 已结束，或最开始
          while (true) {
            if (finished) {
              current = apply(linq.next(), index++); //返回的也是一个 Linq
              finished = false;
            }
            try {
              return current.next(); //在上面返回的 Linq 中遍历结果并返回
            } catch (LinqEndException&) {
              finished = true;
            }
          }
        });
    }

    template<typename F, typename TR = std::invoke_result<F, T>::type, typename TRV = TR::value_type>
    Linq<std::tuple<Linq<S, T>, TR, int, bool>, TRV> selectMany(F apply) const
    {
      return selectMany_i([apply](T value, int) { return apply(value); });
    }

    template<typename F, typename TK = std::invoke_result<F, T>::type, typename TV = Linq<std::tuple<Linq<S, T>, int>, T>>
    Linq<std::tuple<Linq<S, T>, Linq<S, T>, std::unordered_set<TK> >, std::pair<TK, TV> > groupBy(F apply) const
    {
      return Linq<std::tuple<Linq<S, T>, Linq<S, T>, std::unordered_set<TK> >, std::pair<TK, TV> >(
        std::make_tuple(*this, *this, std::unordered_set<TK>{}),
        [apply](std::tuple<Linq<S, T>, Linq<S, T>, std::unordered_set<TK> >& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple); //第一个副本，用来遍历并 apply
          Linq<S, T>& linqCopy = std::get<1>(tuple); //第二个副本，基于 apply 结果进行分类，且不影响遍历过程
          std::unordered_set<TK>& set = std::get<2>(tuple); //分类结果的集合
          while (true) {
            TK key = apply(linq.next()); //分类结果通过 elementAt 来访问，使用时要确保索引不越界，否则需处理 LinqException
            if (set.insert(key).second)
              return std::make_pair(key, linqCopy.where([apply, key](T v) { return apply(v) == key; }));
          }
        });
    }

    template<typename F, typename RT = std::invoke_result<F, T>::type>
    Linq<std::tuple<Linq<S, T>, std::unordered_set<RT>>, T> distinct(F transform) const
    {
      return Linq<std::tuple<Linq<S, T>, std::unordered_set<RT> >, T>(
        std::make_tuple(*this, std::unordered_set<RT>{}),
        [transform](std::tuple<Linq<S, T>, std::unordered_set<RT>>& tuple) {
          Linq<S, T>& linq = std::get<0>(tuple);
          std::unordered_set<RT>& set = std::get<1>(tuple);
          while (true) {
            T value = linq.next(); //异常会被上层遍历过程捕获
            if (set.insert(transform(value)).second)
              return value;
          }
        });
    }

    Linq<std::tuple<Linq<S, T>, std::unordered_set<T>>, T> distinct() const
    {
      return distinct([](T value) { return value; });
    }

    template<typename F, typename Iter = std::vector<T>::const_iterator>
    Linq<std::tuple<std::vector<T>, Iter, bool>, T> orderBy(F transform) const
    {
      std::vector<T> items = toStdVector(); //先转换成向量，便于排序
      std::sort(items.begin(), items.end(), [transform](const T& a, const T& b) { return transform(a) < transform(b); });
      return Linq<std::tuple<std::vector<T>, Iter, bool>, T>(std::make_tuple(items, Iter{}, true),
        //make_tuple 返回值在 lambda 整个生存期有效，所以可在函数体内更改，以持续向后传递
        [](std::tuple<std::vector<T>, Iter, bool>& tuple) {
          std::vector<T>& vec = std::get<0>(tuple); //排序后的向量
          Iter& it = std::get<1>(tuple); //当前迭代子
          bool& first = std::get<2>(tuple); //标记，是否首次。引用使得更改有效
          if (first) {
            first = false;
            it = vec.cbegin();
          }
          if (it == vec.cend())
            throw LinqEndException{}; //遍历结束抛异常。捕获在 for_each
          return *(it++);
        }
      );
    }

    Linq<std::tuple<std::vector<T>, typename std::vector<T>::const_iterator, bool>, T> orderBy() const
    {
      return orderBy([](T value) { return value; });
    }

    template<typename Iter = std::list<T>::const_reverse_iterator>
    Linq<std::tuple<std::list<T>, Iter, bool>, T> reverse() const
    {
      return Linq<std::tuple<std::list<T>, Iter, bool>, T>(std::make_tuple(toStdList(), Iter{}, true),
        [](std::tuple<std::list<T>, Iter, bool>& tuple) {
          std::list<T>& list = std::get<0>(tuple); //列表引用。不涉及排序操作，用列表就够了
          Iter& it = std::get<1>(tuple);
          bool& first = std::get<2>(tuple); //起始标志
          if (first) {
            first = false;
            it = list.crbegin();
          }
          if (it == list.crend())
            throw LinqEndException{};
          return *(it++);
        }
      );
    }

    // Aggregators

    template<typename RT>
    RT aggregate(RT start, std::function<RT(RT, T)> accumulate) const
    {
      Linq<S, T> linq = *this;
      try {
        while (true)
          start = accumulate(start, linq.next());
      } catch (LinqEndException&) {}
      return start;
    }

    template<typename F, typename RT = std::invoke_result<F, T>::type>
    RT sum(F transform) const
    {
      return aggregate<RT>(RT{}, [transform](RT accumulator, T value) { return accumulator + transform(value); });
    }

    template<typename RT = T>
    RT sum() const
    {
      return sum([](T value) { return RT(value); });
    }

    template<typename F, typename RT = std::invoke_result<F, T>::type>
    RT avg(F transform) const
    {
      int count = 0;
      RT res = sum([transform, &count](T value) { count++; return transform(value); });
      return res / count;
    }

    template<typename RT = T>
    RT avg() const
    {
      return avg([](T value) { return RT(value); });
    }

    int count() const
    {
      int index = 0;
      for_each([&index](T) { index++; });
      return index;
    }

    int count(std::function<bool(T)> predicate) const
    {
      return where(predicate).count();
    }

    int count(const T& item) const
    {
      return count([item](T value) { return item == value; });
    }

    // Bool aggregators

    bool any(std::function<bool(T)> predicate) const
    {
      Linq<S, T> linq = *this;
      try {
        while (true)
          if (predicate(linq.next()))
            return true;
      } catch (LinqEndException&) {} //遍历操作，可终止，应捕获异常
      return false;
    }

    bool any() const
    {
      return any([](T value) { return static_cast<bool>(value); });
    }

    bool all(std::function<bool(T)> predicate) const
    {
      return !any([predicate](T value) { return !predicate(value); });
    }

    bool all() const
    {
      return all([](T value) { return static_cast<bool>(value); });
    }

    bool contains(const T& item) const
    {
      return any([&item](T value) { return value == item; });
    }

    // Election aggregators

    T elect(std::function<T(T, T)> accumulate) const
    {
      T result;
      for_each_i([accumulate, &result](T value, int i) { result = i == 0 ? value : accumulate(result, value); });
      return result;
    }

    template<typename F>
    T max(F transform) const
    {
      return elect([transform](const T& a, const T& b) { return (transform(a) < transform(b)) ? b : a; });
    }

    T max() const
    {
      return max([](T value) { return value; });
    }

    template<typename F>
    T min(F transform) const
    {
      return elect([transform](const T& a, const T& b) { return (transform(a) < transform(b)) ? a : b; });
    }

    T min() const
    {
      return min([](T value) { return value; });
    }

    // Single object returners

    T elementAt(int index) const
    {
      return skip(index).next();
    }

    T first(std::function<bool(T)> predicate) const
    {
      return where(predicate).next();
    }

    T first() const
    {
      return Linq<S, T>(*this).next();
    }

    T firstOrDefault(std::function<bool(T)> predicate, T const& defaultValue = T{}) const
    {
      try {
        return where(predicate).next();
      } catch (LinqEndException&) {}
      return defaultValue;
    }

    T firstOrDefault(T const& defaultValue = T{}) const
    {
      try {
        return Linq<S, T>(*this).next();
      } catch (LinqEndException&) {}
      return defaultValue;
    }

    T last(std::function<bool(T)> predicate) const
    {
      T res;
      int index = -1;
      where(predicate).for_each_i([&res, &index](T value, int i) { res = value; index = i; });
      if (index == -1)
        throw LinqEndException{};
      return res;
    }

    T last() const
    {
      return last([](T) { return true; });
    }

    T lastOrDefault(std::function<bool(T)> predicate, T const& defaultValue = T{}) const
    {
      T res = defaultValue;
      where(predicate).for_each([&res](T value) { res = value; });
      return res;
    }

    T lastOrDefault(T const& defaultValue = T{}) const
    {
      return lastOrDefault([](T) { return true; }, defaultValue);
    }

    // Export to containers

    std::vector<T> toStdVector() const
    {
      std::vector<T> items;
      for_each([&items](T value) { items.push_back(value); }); //异常已处理，无需再捕获
      return items;
    }

    std::list<T> toStdList() const
    {
      std::list<T> items;
      for_each([&items](T value) { items.push_back(value); });
      return items;
    }
  }; //class Linq

  template<typename T>
  Linq<std::pair<T, T>, typename std::iterator_traits<T>::value_type> from(const T& begin, const T& end)
  {
    return Linq<std::pair<T, T>, typename std::iterator_traits<T>::value_type>(std::make_pair(begin, end),
      [](std::pair<T, T>& pair) {
        if (pair.first == pair.second)
          throw LinqEndException{}; //遍历结束抛此异常，捕获在 for_each
        return *(pair.first++);
      });
  }

  template<typename T, int N>
  Linq<std::pair<const T*, const T*>, T> from(T(&array)[N])
  {
    return from((const T*)(&array), (const T*)(&array) + N);
  }

  template<template<class, class> class TV, typename TT, typename TU>
  auto from(const TV<TT, TU>& container) //std::list, std::vector, std::dequeue
  {
    return from(container.cbegin(), container.cend());
  }

  template<typename T>
  Linq<std::pair<T, int>, T> repeat(const T& value, int count)
  {
    return Linq<std::pair<T, int>, T>(std::make_pair(value, count),
      [](std::pair<T, int>& pair) {
        if (pair.second > 0) {
          pair.second--;
          return pair.first;
        }
        throw LinqEndException();
      }
    );
  }

  template<typename T>
  Linq<std::tuple<T, T, T>, T> range(const T& start, const T& end, const T& step)
  {
    return Linq<std::tuple<T, T, T>, T>(std::make_tuple(start, end, step),
      [](std::tuple<T, T, T>& tuple) {
        T& start = std::get<0>(tuple);
        T& end = std::get<1>(tuple);
        T& step = std::get<2>(tuple);
        T value = start;
        if (value < end) {
          start += step;
          return value;
        }
        throw LinqEndException{};
      });
  }
}

int main()
{
  {
    struct Man { std::string name; int age; };
    Man mans[] = { {"Kevin",12}, {"Anton",18}, {"Agata",15}, {"Terra",20}, {"Layer",13}, };
    auto childs = boolinq::from(mans).where([](const Man& man) { return man.age < 18; })
      .orderBy([](const Man& man) { return man.age; })
      .select([](const Man& man) { return man.name; })
      .toStdVector();
    for (auto& s : childs)
      std::cout << s << " ";
    std::cout << std::endl; //Kevin Layer Agata

    auto littles = boolinq::from(mans).groupBy([](const Man& man) { return man.age < 14; });
    if (littles.elementAt(0).first && littles.elementAt(1).second.first().name == "Anton")
      std::cout << "groupBy ok" << std::endl;

    struct Message { std::string PhoneA; std::string PhoneB; std::string Text; };
    Message messages[] = {
      {"Anton","Troll","Hello, friend!"},
      {"Denis","Wride","OLOLO"},
      {"Anton","Papay","WTF?"},
      {"Denis","Maloy","How r u?"},
      {"Denis","Wride","Param-pareram!"},
    };
    int DenisUniqueContactCount = boolinq::from(messages)
      .where([](const Message& msg) { return msg.PhoneA == "Denis"; })
      .distinct([](const Message& msg) { return msg.PhoneB; }).count();
    if (DenisUniqueContactCount == 2)
      std::cout << "distinct ok" << std::endl;

    std::vector<int> src{ 1,2,3 };
    auto rng = boolinq::from(src);
    auto rngMany = rng.selectMany([](int a) { return boolinq::repeat(a, a); }) //1,2,2,3,3,3
      .skip(3).takeWhile([](int a) { return a < 5; });
    if (rngMany.all([](int a) { return a == 3; }) && rng.skipWhile([](int a) { return a < 3; }).count() == 1)
      std::cout << "selectMany & skip & take ok" << std::endl;
    if (rng.prepend(0).all([](int a) { return a >= 0 && a < 4; }) && rng.append(4).any([](int a) { return a > 3; }))
      std::cout << "all & any & append & prepend ok" << std::endl;

    int cat[] = { 4,5,6 };
    auto rng2 = boolinq::from(cat);
    auto dst = rng.concat(rng2);
    if (dst.count() == 6 && dst.count([](int a) { return a % 2 == 0; }) == 3)
      std::cout << "concat & count ok" << std::endl;
    if (dst.contains(6) && dst.elementAt(2) == 3)
      std::cout << "contains & elementAt ok" << std::endl;
    if (dst.first() == 1 && dst.firstOrDefault([](int a) { return a % 7 == 0; }) == 0)
      std::cout << "first & firstOrDefault ok" << std::endl;
    if (dst.last([](int a) { return a % 2 == 0; }) == 6 && dst.reverse().lastOrDefault() == 1)
      std::cout << "last & lastOrDefault & reverse ok" << std::endl;

    auto range = boolinq::range(1, 5, 1); //1,2,3,4
    if (range.avg<double>() == 2.5 && range.max() == 4 && range.min([](int a) { return -a; }) == 4)
      std::cout << "range & avg & max & min ok" << std::endl; //注意 max、min 返回的都是元素原始值
    if (range.sum() == 10 && range.sum([](int a) { return a % 2; }) == 2)
      std::cout << "sum ok" << std::endl; //sum 也可以实现字符串连接
  }
}