backup note for contributing is_heap and is_heap_until to HPX.

note.txt

Check Box
---------------
 - [x] implementation of is_heap.
 - [x] unit tests for is_heap.
 - [x] implementation of is_heap_until.
 - [x] unit tests for is_heap_until.
 - [ ] benchmark codes for is_heap.
 - [ ] benchmark codes for is_heap_until.
 - [ ] benchmark for is_heap_until.

I writed benchmark codes. And then I found that my implementation's performance is better than std::* and has scalability as the number of cores increase.

Benchmark for is_heap_until (Fix the number of cores and adjust N)
--------------------------------------
 - The range [0, N) is heap.
 - Environment : Rostam. ( 8 physical cores / 16 logical cores )
 - The number of cores used = 16.
 - time unit : seconds

|   kind\N     | 100,000      | 1,000,000 | 10,000,000 | 100,000,000 |1,000,000,000 |
| ------------- |:-------------:| -----:|-----:|-----:|-----:|
| std      | 0.00019 | 0.00149 | 0.01172 | 0.11785 | 1.02402 |
| seq      | 0.00018 | 0.00140 | 0.01171 | 0.11217 | 1.01263 |
| par | 0.00053     | 0.00033 | 0.00125 | 0.01657 | 0.16828 |
| par_unseq | 0.00014     |  0.00018 | 0.00118 | 0.01629 | 0.16750 |

Benchmark for is_heap_until (Fix N and adjust M(the number of cores used))
--------------------------------------
 - The range [0, N) is heap.
 - N = 100,000,000
 - Environment : Rostam. ( 8 physical cores / 16 logical cores )
 - std::* version : 0.10221
 - time unit : seconds

|   kind\M     | 1      | 2 | 4 | 8 | 12 | 16 | 32 |
| ------------- |:-------------:| -----:|-----:|-----:|-----:|-----:|-----:|
| par | 0.10097     | 0.05089 | 0.02685 | 0.01554 | 0.01595 | 0.01636 | 0.04736 |

/*
        /// \cond NOINTERNAL
        struct is_heap_until_helper
        {
            template <typename ExPolicy, typename RandIter, typename Comp>
            hpx::future<std::size_t>
            operator()(ExPolicy && policy, RandIter first, std::size_t node,
                std::size_t size, Comp comp)
            {
                hpx::future<std::size_t> left, right;
                std::size_t left_child = node * 2 + 1;
                std::size_t right_child = node * 2 + 2;

                
                if (left_child >= size) // Leaf Node 
                {
                    return make_ready_future<std::size_t>(std::size_t(size));
                }
                else if (right_child >= size) // Only has a left child 
                {
                    auto node_iter = std::next(first, node);
                    auto left_child_iter = std::next(first, left_child);
                    if (comp(*node_iter, *left_child_iter))
                    {
                        return make_ready_future<std::size_t>(node + 1);
                    }
                    else
                    {
                        left = execution::async_execute(
                            policy.executor(), *this, policy, first, left_child,
                            size, comp);
                        right = make_ready_future<std::size_t>(std::size_t(size));
                    }
                }
                else // Has left child and right child, both. 
                {
                    auto node_iter = std::next(first, node);
                    auto left_child_iter = std::next(first, left_child);
                    auto right_child_iter = std::next(first, right_child);

                    if (comp(*node_iter, *left_child_iter))
                    {
                        return make_ready_future<std::size_t>(node + 1);
                    }
                    else if (comp(*node_iter, *right_child_iter))
                    {
                        return make_ready_future<std::size_t>(left_child + 1);
                    }
                    else
                    {
                        left = execution::async_execute(
                            policy.executor(), *this, policy, first, left_child,
                            size, comp);
                        right = execution::async_execute(
                            policy.executor(), *this, policy, first, right_child,
                            size, comp);
                    }
                }

                return
                    dataflow(
                        policy.executor(),
                        [](
                            hpx::future<std::size_t> && left,
                            hpx::future<std::size_t> && right
                        ) -> std::size_t
                        {
                            if (left.has_exception() || right.has_exception())
                            {
                                std::list<boost::exception_ptr> errors;
                                if(left.has_exception())
                                    hpx::parallel::util::detail::
                                    handle_local_exceptions<ExPolicy>::call(
                                        left.get_exception_ptr(), errors);
                                if(right.has_exception())
                                    hpx::parallel::util::detail::
                                    handle_local_exceptions<ExPolicy>::call(
                                        right.get_exception_ptr(), errors);

                                if (!errors.empty())
                                {
                                    boost::throw_exception(
                                        exception_list(std::move(errors)));
                                }
                            }
                            auto left_val = left.get();
                            auto right_val = right.get();

                            std::size_t left_val_level;
                            std::size_t right_val_level;
                            

                            
                        },
                        std::move(left), std::move(right));
            }
        };
        */


struct user_defined_type
{
    bool operator<(user_defined_type const& t) const
    {
        if (this->name < t.name)
            return true;
        else if (this->name < t.name)
            return false;
        else
            return this->val < t.val;
    }

    const user_defined_type& operator++()
    {
        static const std::vector<std::string> name_list = {
            "ABB", "ABC", "ACB", "BCA", "CAA", "CAAA", "CAAB"
        };
        name = name_list[std::rand() % name_list.size()];
        ++val;
        return *this;
    }

    std::string name;
    int val;
};