// compile with -std=c++1y

#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

namespace LoDash {

using std::begin;
using std::end;
using std::vector;
using std::function;

template<typename UNUSED>
struct LoDash {
  template<typename T>
  static auto _pure_typeof(T x) -> typename std::remove_const<typename std::remove_reference<decltype(x)>::type>::type { return decltype(_pure_typeof(x))(); };
  
  template<typename L>
  static void each(const L& list, function<void(decltype(*begin(list))&)> func) {
    for (auto& i: list) func(i);
  }

  template<typename L>
  static size_t count(const L& list) {
    return (size_t) std::distance(begin(list), end(list));
  }

  template<typename L>
  static size_t count(const L& list, function<bool(decltype(*begin(list)))> func) {
    return (size_t) std::count_if(begin(list), end(list), func);
  }

  template<typename L, typename F>
  static auto map(const L& list, F func) -> vector<decltype(func(*begin(list)))>  {
    typedef decltype(func(*begin(list))) FR;
    vector<FR> result;
    result.resize(count(list));
    std::transform(begin(list), end(list), result.begin(), func);
    return result;
  }

  template<typename L>
  static auto select(const L& list, function<bool(decltype(*begin(list)))> func) -> vector<decltype(_pure_typeof(*begin(list)))> {
    vector<decltype(_pure_typeof(*begin(list)))> result;
    std::copy_if(begin(list), end(list), std::back_inserter(result), func);
    return result;
  }

  template<typename L>
  static auto filter(const L& list, function<bool(decltype(*begin(list)))> func) -> vector<decltype(_pure_typeof(*begin(list)))> {
    return select(list, func);
  }

  template<typename L>
  static auto reject(const L& list, function<bool(decltype(*begin(list)))> func) -> vector<decltype(_pure_typeof(*begin(list)))> {
    return select(list, [&] (decltype(*begin(list)) i) { return !func(i); });
  }

  template<typename L>
  static auto sample(const L& list, size_t n) -> vector<decltype(_pure_typeof(*begin(list)))> {
    size_t avail = count(list);
    n = std::min(n, avail);

    vector<decltype(_pure_typeof(*begin(list)))> result;
    result.reserve(n);

    for (auto& i : list) {
      if (n == 0) break;
      if ((std::rand() % avail) < n) {
        result.push_back(i);
        --n;
      }
      --avail;
    }
    return result;
  }

  template<typename L>
  static auto sample(const L& list) -> decltype(_pure_typeof(*begin(list))) {
    size_t avail = count(list);
    for (auto& i : list) {
      if (std::rand() % avail == 0) return i;
    }
    return _pure_typeof(*begin(list));
  }

  template<typename L>
  static auto sort(const L& list) -> vector<decltype(_pure_typeof(*begin(list)))> {
    vector<decltype(_pure_typeof(*begin(list)))> result;
    result.reserve(count(list));
    std::copy(begin(list), end(list), std::back_inserter(result));
    std::stable_sort(result.begin(), result.end());
    return result;
  }

  template<typename L>
  static auto shuffle(const L& list) -> vector<decltype(_pure_typeof(*begin(list)))> {
    vector<decltype(_pure_typeof(*begin(list)))> result;
    result.reserve(count(list));
    std::copy(begin(list), end(list), std::back_inserter(result));
    std::random_shuffle(result.begin(), result.end());
    return result;
  }

  template<typename L>
  static auto min(const L& list) -> decltype(_pure_typeof(*begin(list))) {
    decltype(_pure_typeof(*begin(list))) result = *begin(list);
    each(list, [&] (auto x) { if (x < result) result = x;});
    return result;
  }

  template<typename L>
  static auto max(const L& list) -> decltype(_pure_typeof(*begin(list))) {
    decltype(_pure_typeof(*begin(list))) result = *begin(list);
    each(list, [&] (auto x) { if (x > result) result = x;});
    return result;
  }

  template<typename L, typename F>
  static auto min_by(const L& list, F func) -> decltype(_pure_typeof(*begin(list))) {
    typedef decltype(func(*begin(list))) FR;
    if (count(list) == 0) return FR();
    decltype(_pure_typeof(*begin(list))) result = *begin(list);
    FR val = func(*begin(list));
    each(list, [&] (auto x) { if (x != result) { FR tmp = func(x); if (func(x) < val) {result = x; val = tmp; }}});
    return result;
  }

  template<typename L, typename F>
  static auto max_by(const L& list, F func) -> decltype(_pure_typeof(*begin(list))) {
    typedef decltype(func(*begin(list))) FR;
    if (count(list) == 0) return FR();
    decltype(_pure_typeof(*begin(list))) result = *begin(list);
    FR val = func(*begin(list));
    each(list, [&] (auto x) { if (x != result) { FR tmp = func(x); if (func(x) > val) {result = x; val = tmp; }}});
    return result;
  }

  template<typename L, typename F>
  static auto inject(const L& list, F func) -> decltype(func(*begin(list), *begin(list))) {
    decltype(func(*begin(list), *begin(list))) result;
    int i = 0;
    for (auto& x : list) {
      if (!i) {
        result = x;
        ++i;
      } else {
        result = func(result, x);
      }
    }
    return result;
  }

  template<typename L, typename R, typename F>
  static auto inject(const L& list, R init, F func) -> decltype(func(init, *begin(list))) {
    R result = init;
    for (auto& x : list) result = func(result, x);
    return result;
  }

  template<typename L, typename F>
  static auto reduce(const L& list, F func) -> decltype(func(*begin(list), *begin(list))) {
    return inject(list, func);
  }

  template<typename L, typename R, typename F>
  static auto reduce(const L& list, R init, F func) -> decltype(func(init, *begin(list))) {
    return inject(list, init, func);
  }

};

}

#ifndef LODASH_NO_EXPORT
# ifndef _LODASH_EXPORTED
#  define _LODASH_EXPORTED
auto _ = LoDash::LoDash<void>();
# endif
#endif

/*

#include "lodash.hpp"
#include <vector>
#include <set>
#include <iostream>
#include <string>

#define lambda [&]
#define P(r) { std::cout << "[ "; _.each((r), lambda (auto x) { std::cout << x << " ";}); std::cout << "]\n"; }

int main(int argc, char const *argv[]) {
  int a[] = {1, 2, 3, 4};
  std::set<int> s = {8, 7, 6, 5};
  std::vector<int> v = {9, 10, 11, 12};

  P(a); // 1 2 3 4
  P(s); // 5 6 7 8
  P(v); // 9 10 11 12

  P(_.map(s, lambda (auto x) { return -x; })); // -5 -6 -7 -8
  P(_.map(v, lambda (auto x) { return (char)('a' + x); })); // j k l m
  P(_.select(v, lambda (auto x) { return (x & 1); })); // 9 11
  P(_.filter(a, lambda (auto x) { return (x & 1); })); // 1 3
  P(_.reject(s, lambda (auto x) { return (x & 1); })); // 6 8
  P(_.sort(a)); // 1 2 3 4
  P(_.shuffle(s));
  P(_.sample(s, 2));

  std::cout << _.sample(a) << "\n"; // 1 or 2 or 3 or 4
  std::cout << _.count(a, lambda (auto x) { return x > 1; }) << "\n"; // 3
  std::cout << _.min(a) << "\n"; // 1
  std::cout << _.min_by(a, lambda (int x) {return -x;}) << "\n"; // 4
  std::cout << _.inject(s, lambda (auto x, auto y) { return x + y; }) << "\n"; // 26
  std::cout << _.reduce(a, std::string(), lambda (auto x, auto y) { char s[] = "a"; s[0] += y; return x + s; }) << "\n"; // bcde
}

 */