// Copyright (c) 2020 by cpp 实战笔记
//
// g++ algo.cpp -std=c++11 -o a.out;./a.out
// g++ algo.cpp -std=c++14 -o a.out;./a.out
// g++ algo.cpp -std=c++14 -I../common -o a.out;./a.out

#include <cassert>

#include <iostream>

#include <array>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// C++ 里的算法，指的是工作在容器上的一些泛型函数
void case1()
{
    // vector 容器 定义及初始化
    vector<int> v = {1,3,1,7,5}; 

    // count 计算容器中元素的数量，begin() 和end() 指定容器范围 ，每个元素计数1 
    auto n1 = std::count(
        begin(v), end(v), 1
    );

    // 等价于手写循环实现统计。
    int n2 = 0;
    for(auto x : v) {
        if (x == 1) {
            n2++;
        }
    }

    assert(n1 == n2);

    // count_if 计算满足一定条件的元素的数量，
    // begin(), end() 指定 容器范围，第三个参数可以传递lambda 函数 定义 条件函数
    auto n = std::count_if(
        begin(v), end(v),
        [](auto x) {
            return x > 2;
        }
    );

    assert(n == 3);
}


// 算法操作容器，但实际上它看到的并不是容器，而是指向起始位置和结束位置的迭代器，
// 算法只能通过迭代器去“间接”访问容器以及元素，算法的能力是由迭代器决定的。
// 这是泛型编程的理念，与面向对象正好相反，分离了数据和操作。算法可以不关心容器的内部结构，
// 以一致的方式去操作元素，适用范围更广，用起来也更灵活。
void case2()
{
    vector<int> v = {1,2,3,4,5};

    auto iter1 = v.begin();  // 成员函数的迭代器 开头
    auto iter2 = v.end();    // 成员函数的迭代器 结尾

    auto iter3 = std::begin(v);  // 全局函数获取迭代器 获取开头，自动类型推导
    auto iter4 = std::end(v);   // // 全局函数获取迭代器 获取结尾，自动类型推导

    // 建议使用更加通用的全局函数 begin()、end()，虽然效果是一样的，但写起来比较方便，看起来也更清楚
    //（另外还有 cbegin()、cend() 函数，返回的是常量迭代器）
    assert(iter1 == iter3);
    assert(iter2 == iter4);
}

// 迭代器计算相关的函数
void case3()
{
    array<int, 5> arr = {0,1,2,3,4};  // array静态数组容器

    auto b = begin(arr); // 全局函数获取迭代器，首端
    auto e = end(arr); // 全局函数获取迭代器，末端

    assert(distance(b, e) == 5);  // distance 计算迭代器的距离

    auto p = next(b);  // next 获取迭代器"下一个" 位置
    assert(distance(b, p) == 1);  // 迭代器距离
    assert(distance(p, b) == -1);  // distance 可以反向计算迭代器距离。

    advance(p, 2);  // advance 使迭代器前进 2 个位置。
    assert(*p == 3);
    assert(p == prev(e, 2));  // prev 计算迭代器 的前 2 个位置。

}


// 常用 的函数式 编程相关的函数
void case4()
{
#if 1
    vector<int> v = {3,5,1,7,10};

    // range for 循环方式
    for(const auto& x : v) {
        cout << x << ",";
    }
#endif
    cout << endl;

#if 1
    // 定义一个打印功能的lambda 函数
    auto print = [](const auto& x)
    {
        cout << x << ",";
    };

// for_each 算法的价值就体现在，把要做的事情分成了两部分，也就是两个函数：一
// 个遍历容器元素，另一个操纵容器元素，而且名字的含义更明确，代码也有更好的封装。
// 建议你尽量多用 for_each 来替代 for，因为它能 够促使我们更多地以“函数式编程”来思考，
// 使用 lambda 来封装逻辑，得到更干净、更安全的代码。
    // for_each 算法 对容器内的每个函数执行同样的操作
    for_each(cbegin(v), cend(v), print);
#endif
    cout << endl;

#if 1
    // for_each 可以直接传递 lambda 函数的方式
    for_each(
        cbegin(v), cend(v),
        [](const auto& x)
        {
            cout << x << ",";
        }
    );
#endif
    cout << endl;
}

void case5()
{
    vector<int> v = {3,5,1,7,10,99,42};

    auto print = [](const auto& x)
    {
        cout << x << ",";
    };

    // total sort 排序算法，全排序
    std::sort(begin(v), end(v));  // 默认快拍
    for_each(cbegin(v), cend(v), print);
    cout << endl;

    // top3 排序， partial_sort 可以完成top n 排序
    std::partial_sort(
        begin(v), next(begin(v), 3), end(v));
    for_each(cbegin(v), cend(v), print);
    cout << endl;

    // best3 nth_element 选出 最好的 n 个元素，但不排序
    std::nth_element(
        begin(v), next(begin(v), 3), end(v));
    for_each(cbegin(v), cend(v), print);
    cout << endl;

    // Median nth_element 可以求中位数
    auto mid_iter =
        next(begin(v), v.size()/2);
    std::nth_element( begin(v), mid_iter, end(v));
    for_each(cbegin(v), cend(v), print);
    cout << "median is " << *mid_iter << endl;

    // partition  找出所有大于9 的元素
    auto pos = std::partition(
        begin(v), end(v),
        [](const auto& x)
        {
            return x > 9;
        }
    );
    for_each(begin(v), pos, print);
    cout << endl;
    for_each(cbegin(v), cend(v), print);
    cout << endl;

    // min/max  minmax_element 求出最大最小元素
    auto value = std::minmax_element(
        cbegin(v), cend(v)
    );
    cout << *value.first << ","
         << *value.second << endl;

// 以上排序算法最好在顺序容器 array/vector 上调用
}

void case6()
{
    vector<int> v = {3,5,1,7,10,99,42};

    auto print = [](const auto& x)
    {
        cout << x << ",";
    };

    // total sort 先排序
    std::sort(begin(v), end(v));
    for_each(cbegin(v), cend(v), print);
    cout << endl;

    // 执行二分查找，确定元素是否存在
    auto found = binary_search(
        cbegin(v), cend(v), 7
    );
    cout << "found: " << found << endl;

    decltype(cend(v)) pos;  // 使用decltype,声明一个迭代器，

    pos = std::lower_bound(
        cbegin(v), cend(v), 7   // lower_bound, 找到第一个大于等于7 的元素的位置。
    );
    //assert(pos != cend(v));
    //assert(*pos == 7);
    found = (pos != cend(v)) && (*pos == 7);   // 可能找不到需要做判断
    assert(found);   // 7 在容器里

    pos = std::lower_bound(
        cbegin(v), cend(v), 9  // lower_bound 找到第一个大于等于 9 的元素的位置。
    );
    //assert(pos != cend(v));
    //cout << *pos << endl;
    found = (pos != cend(v)) && (*pos == 9);
    assert(!found);

    // lower_bound 的返回值是一个迭代器，所以就要做一点判断工作，才能知道是否真的找到了。
    // 判断的条件有两个，一个是迭代器是否有效，另一个是迭代器的值是不是要找的值。


    //  lower_bound 的查找条件是“大于等于”，而不是“等于”，所以它的真正含义是“大于等于值的第一个位置”。
    // 相应的也就有“大于等于值的最后一个位置”，算法叫upper_bound，返回的是第一个“大于”值的元素
    pos = std::upper_bound(
        cbegin(v), cend(v), 9  // 找到第一个大于9 的位置。
    );
    //  返回的形式 begin < x <= lower_bound < upper_bound < end
    //cout << *pos << endl;
    
    // equal_range() 可以找出有序序列中所有和给定元素相等的元素。它的前两个参数是指定序列的两个正向迭代器，第三个参数是要查找的元素
    // 算法会返回一个 pair 对象，first 指向的是不小于第三个参数的一个元素，second 指向大于第三个参数的一个元素
    auto range = std::equal_range(
        cbegin(v), cend(v), 9
    );
    //cout << *range.first << endl;
    //cout << *range.second << endl;
    for_each(
        range.first, std::next(range.second), print
    );
    cout << endl;
}

void case7()
{
    // 有序容器set、map 有等价的成员函数find/lower_bound/upper_bound，效果是一样的
    multiset<int> s = {3,5,1,7,7,7,10,99,42};  // multiset 允许重复

    auto print = [](const auto& x)
    {
        cout << x << ",";
    };

    auto pos = s.find(7);
    assert(pos != s.end());   // 二分查找返回迭代器，需要和end 比较才能确定是否找到。

    auto lower_pos = s.lower_bound(7); // 获取区间的左端点
    auto upper_pos = s.upper_bound(7);  // 获取区间的右端点。

    for_each(
        lower_pos, upper_pos, print
    );
    cout << endl;
}

void case8()
{
    vector<int> v = {1,9,11,3,5,7};

    decltype(v.end()) pos;  //  声明一个迭代器，使用decltype

    pos = std::find(
        begin(v), end(v), 3   // find 查找算法，找到第一个出现的位置
    );
    assert(pos != end(v));   // 与end()比较才能知道是否找到

    // find_if 查找算法，用lambda判断条件
    pos = std::find_if(   
        begin(v), end(v),
        [](auto x) {
            return x % 2 == 0;
        }
    );
    assert(pos == end(v));

    array<int, 2> arr = {3,5};
    // find_first_of 查找一个子区间
    pos = std::find_first_of(
        begin(v), end(v),
        begin(arr), end(arr)
    );
    assert(pos != end(v));
}

int main()
{
    case1();
    case2();
    case3();
    case4();
    case5();
    case6();
    case7();
    case8();

    using namespace std;

    cout << "algorithm demo" << endl;
}