algorithms.h

Go to the documentation of this file.

#ifndef ALGORITHMS_H
#define ALGORITHMS_H
 
#include <functional>
#include <cmath>
#include "vector.h"
#include "filter.h"
#include "iterator.h"
#include "types.h"
#include "refCntPtr.h"
 

 
namespace original
{

    class algorithms final
    {
    public:

        template<typename TYPE>
        static integer distance(const iterator<TYPE>& end, const iterator<TYPE>& begin);

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> frontOf(const iterator<TYPE>& it, integer steps);

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> backOf(const iterator<TYPE>& it, integer steps);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static bool allOf(const iterator<TYPE>& begin, const iterator<TYPE>& end, const Callback& condition);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static bool anyOf(const iterator<TYPE>& begin, const iterator<TYPE>& end, const Callback& condition);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static bool noneOf(const iterator<TYPE>& begin, const iterator<TYPE>& end, const Callback& condition);

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> find(const iterator<TYPE> &begin, const iterator<TYPE> &end, const TYPE &target);

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> find(const iterator<TYPE> &begin, u_integer n, const TYPE &target);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static strongPtr<iterator<TYPE>> find(const iterator<TYPE> &begin,
                                    const iterator<TYPE> &end, const Callback& condition);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static strongPtr<iterator<TYPE>> find(const iterator<TYPE> &begin, u_integer n, const Callback& condition);

        template<typename TYPE>
        static u_integer count(const iterator<TYPE>& begin, const iterator<TYPE>& end, const TYPE& target);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static u_integer count(const iterator<TYPE>& begin, const iterator<TYPE>& end, const Callback& condition);

        template<typename TYPE>
        static bool equal(const iterator<TYPE>& begin1, const iterator<TYPE>& end1,
                          const iterator<TYPE>& begin2, const iterator<TYPE>& end2);

        template<typename TYPE, typename Callback>
        requires Operation<Callback, TYPE>
        static void forEach(const iterator<TYPE>& begin,
                            const iterator<TYPE>& end, Callback operation);

        template<typename TYPE, typename Callback>
        requires Operation<Callback, TYPE>
        static strongPtr<iterator<TYPE>> forEach(const iterator<TYPE> &begin, u_integer n, Callback operation);

        template<typename TYPE, typename Callback_O, typename Callback_C>
        requires Operation<Callback_O, TYPE> && Condition<Callback_C, TYPE>
        static void forEach(const iterator<TYPE>& begin, const iterator<TYPE>& end, Callback_O operation, const Callback_C& condition);

        template<typename TYPE, typename Callback_O, typename Callback_C>
        requires Operation<Callback_O, TYPE> && Condition<Callback_C, TYPE>
        static strongPtr<iterator<TYPE>> forEach(const iterator<TYPE> &begin, u_integer n, Callback_O operation, const Callback_C& condition);

        template<typename TYPE>
        static void fill(const iterator<TYPE>& begin,
                         const iterator<TYPE>& end, const TYPE& value = TYPE{});

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> fill(const iterator<TYPE> &begin, u_integer n, const TYPE &value = TYPE{});

        template<typename TYPE>
        static void swap(const iterator<TYPE>& it1, const iterator<TYPE>& it2) noexcept;

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> copy(const iterator<TYPE> &begin_src, const iterator<TYPE> &end_src,
                                    const iterator<TYPE> &begin_tar);

        template<typename TYPE, typename Callback>
        requires Condition<Callback, TYPE>
        static strongPtr<iterator<TYPE>> copy(const iterator<TYPE> &begin_src, const iterator<TYPE> &end_src,
                                    const iterator<TYPE> &begin_tar, Callback condition = filter<TYPE>{});

        template<typename TYPE>
        static strongPtr<iterator<TYPE>> reverse(const iterator<TYPE> &begin, const iterator<TYPE> &end);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static bool compare(const iterator<TYPE>& it1, const iterator<TYPE>& it2, const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void heapAdjustDown(const iterator<TYPE>& begin, const iterator<TYPE>& range,
                                   const iterator<TYPE>& current, const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void heapAdjustUp(const iterator<TYPE>& begin, const iterator<TYPE>& current,
                                 const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void heapInit(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                             const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void sort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                              const Callback& compares, bool isStable = false);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void introSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                               const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void stableSort(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void heapSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                         const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void insertionSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                  const Callback& compares);
    protected:
        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static strongPtr<iterator<TYPE>> _heapGetPrior(const iterator<TYPE>& begin, const iterator<TYPE>& range,
                                             const iterator<TYPE>& parent, const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static strongPtr<iterator<TYPE>> _introSortGetPivot(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                                  const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static strongPtr<iterator<TYPE>> _introSortPartition(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                                   const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void _introSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                               const Callback& compares, u_integer depth_limit);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void _stableSortMerge(const iterator<TYPE>& begin, const iterator<TYPE>& mid,
                                     const iterator<TYPE>& end, const Callback& compares);

        template<typename TYPE, typename Callback>
        requires Compare<Callback, TYPE>
        static void _stableSort(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                const Callback& compares);
 
    // ---- Implementation of pointer overload version ----
 
    public:
        template <typename TYPE>
        static auto distance(const strongPtr<iterator<TYPE>> end, const strongPtr<iterator<TYPE>> begin) -> integer
        {
            return distance(*end, *begin);
        }

        template<typename TYPE>
        static auto frontOf(const strongPtr<iterator<TYPE>> it, integer steps) -> strongPtr<iterator<TYPE>> {
            return frontOf(*it, steps);
        }

        template<typename TYPE>
        static auto backOf(const strongPtr<iterator<TYPE>> it, integer steps) -> strongPtr<iterator<TYPE>> {
            return backOf(*it, steps);
        }

        template<typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto allOf(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                          const Callback &condition) -> bool {
            return allOf(*begin, *end, condition);
        }

        template<typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto anyOf(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                          const Callback &condition) -> bool {
            return anyOf(*begin, *end, condition);
        }

        template<typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto noneOf(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                           const Callback &condition) -> bool {
            return noneOf(*begin, *end, condition);
        }

        template <typename TYPE>
        static auto find(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                         const TYPE& target) -> strongPtr<iterator<TYPE>> {
            return find(*begin, *end, target);
        }

        template <typename TYPE>
        static auto find(const strongPtr<iterator<TYPE>> begin, u_integer n,
                         const TYPE& target) -> strongPtr<iterator<TYPE>> {
            return find(*begin, n, target);
        }

        template<typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto find(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                         const Callback& condition) -> strongPtr<iterator<TYPE>> {
            return find(*begin, *end, condition);
        }

        template <typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto find(const strongPtr<iterator<TYPE>> begin, u_integer n, const Callback& condition) -> strongPtr<iterator<TYPE>> {
            return find(*begin, n, condition);
        }

        template <typename TYPE>
        static auto count(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                                         const TYPE& target) -> u_integer {
            return count(*begin, *end, target);
        }

        template <typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto count(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                                         const Callback& condition) -> u_integer {
            return count(*begin, *end, condition);
        }

        template <typename TYPE>
        static auto equal(const strongPtr<iterator<TYPE>> begin1, const strongPtr<iterator<TYPE>> end1,
                                         const strongPtr<iterator<TYPE>> begin2, const strongPtr<iterator<TYPE>> end2) -> bool {
            return equal(*begin1, *end1, *begin2, *end2);
        }

        template <typename TYPE, typename Callback>
        requires original::Operation<Callback, TYPE>
        static auto forEach(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                                           Callback operation) -> void {
            forEach(*begin, *end, operation);
        }

        template <typename TYPE, typename Callback>
        requires original::Operation<Callback, TYPE>
        static auto forEach(const strongPtr<iterator<TYPE>> begin, u_integer n, Callback operation) -> strongPtr<iterator<TYPE>> {
            return forEach(*begin, n, operation);
        }

        template<typename TYPE>
        static auto fill(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                                        const TYPE& value) -> void {
            fill(*begin, *end, value);
        }

        template<typename TYPE>
        static auto fill(const strongPtr<iterator<TYPE>> begin, u_integer n, const TYPE& value) -> strongPtr<iterator<TYPE>> {
            return fill(*begin, n, value);
        }

        template <typename TYPE>
        static auto swap(const strongPtr<iterator<TYPE>> it1, const strongPtr<iterator<TYPE>> it2) noexcept -> void {
            swap(*it1, *it2);
        }

        template <typename TYPE>
        static auto copy(const strongPtr<iterator<TYPE>> begin_src, const strongPtr<iterator<TYPE>> end_src,
                                        const strongPtr<iterator<TYPE>> begin_tar) -> strongPtr<iterator<TYPE>> {
            return copy(*begin_src, *end_src, *begin_tar);
        }

        template<typename TYPE, typename Callback>
        requires original::Condition<Callback, TYPE>
        static auto copy(const strongPtr<iterator<TYPE>> begin_src, const strongPtr<iterator<TYPE>> end_src,
                                        const strongPtr<iterator<TYPE>> begin_tar, Callback condition) -> strongPtr<iterator<TYPE>> {
            return copy(*begin_src, *end_src, *begin_tar, condition);
        }

        template<typename TYPE>
        static auto reverse(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end) -> strongPtr<iterator<TYPE>> {
            return reverse(*begin, *end);
        }

        template <typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto compare(const strongPtr<iterator<TYPE>> it1, const strongPtr<iterator<TYPE>> it2,
                                           const Callback& compares) -> bool {
            return compare(*it1, *it2, compares);
        }

        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto heapAdjustDown(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> range,
                                                  const strongPtr<iterator<TYPE>> current, const Callback& compares) -> void {
            heapAdjustDown(*begin, *range, *current, compares);
        }

        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto heapAdjustUp(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> current,
                                                const Callback& compares) -> void {
            heapAdjustUp(*begin, *current, compares);
        }

        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto heapInit(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                                            const Callback& compares) -> void {
            heapInit(*begin, *end, compares);
        }

        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto heapSort(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                             const Callback& compares) -> void{
            heapSort(*begin, *end, compares);
        }

        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto insertionSort(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> end,
                             const Callback& compares) -> void{
            insertionSort(*begin, *end, compares);
        }
 
    protected:
        template<typename TYPE, typename Callback>
        requires original::Compare<Callback, TYPE>
        static auto _heapGetPrior(const strongPtr<iterator<TYPE>> begin, const strongPtr<iterator<TYPE>> range,
                                  const strongPtr<iterator<TYPE>> parent, const Callback& compares) -> strongPtr<iterator<TYPE>> {
            return _heapGetPrior(*begin, *range, *parent, compares);
        }
    };
}
 
    template <typename TYPE>
    auto original::algorithms::distance(const iterator<TYPE>& end, const iterator<TYPE>& begin) -> integer
    {
        auto it1 = strongPtr(end.clone());
        auto it2 = strongPtr(begin.clone());
        return *it1 - *it2;
    }
 
    template<typename TYPE>
    original::strongPtr<original::iterator<TYPE>> original::algorithms::frontOf(const iterator<TYPE> &it, integer steps) {
        return strongPtr(it + steps);
    }
 
    template<typename TYPE>
    original::strongPtr<original::iterator<TYPE>> original::algorithms::backOf(const iterator<TYPE> &it, integer steps) {
        return strongPtr(it - steps);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    bool original::algorithms::allOf(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                     const Callback& condition) {
        auto it = strongPtr(begin.clone());
        for (; distance(*it, end) <= 0; it->next()){
            if (!condition(it->get())){
                return false;
            }
        }
        return true;
    }
 
    template<typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    bool original::algorithms::anyOf(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                     const Callback& condition) {
        auto it = strongPtr(begin.clone());
        for (; distance(*it, end) <= 0; it->next()){
            if (condition(it->get())){
                return true;
            }
        }
        return false;
    }
 
    template<typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    bool original::algorithms::noneOf(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                      const Callback& condition) {
        auto it = strongPtr(begin.clone());
        for (; distance(*it, end) <= 0; it->next()){
            if (condition(it->get())){
                return false;
            }
        }
        return true;
    }
 
    template <typename TYPE>
    auto original::algorithms::find(const iterator<TYPE>& begin, const iterator<TYPE>& end,
        const TYPE& target) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        while (it->isValid() && !it->equal(end)) {
            if (it->get() == target) {
                return it;
            }
            it->next();
        }
        return strongPtr(end.clone());
    }
 
    template <typename TYPE>
    auto original::algorithms::find(const iterator<TYPE>& begin, const u_integer n, const TYPE& target) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        for (u_integer i = 0; i < n; i += 1, it->next())
        {
            if (it->get() == target) return it;
        }
        return it;
    }
 
    template<typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    auto original::algorithms::find(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                    const Callback& condition) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        while (it->isValid() && !it->equal(end)) {
            if (condition(it->get())) {
                return it;
            }
            it->next();
        }
        return strongPtr(end.clone());
    }
 
    template <typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    auto original::algorithms::find(const iterator<TYPE>& begin, const u_integer n, const Callback& condition) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        for (u_integer i = 0; i < n; i += 1, it->next())
        {
            if (condition(it->get())) return it;
        }
        return it;
    }
 
    template <typename TYPE>
    auto original::algorithms::count(const iterator<TYPE>& begin, const iterator<TYPE>& end,
        const TYPE& target) -> u_integer
    {
        u_integer cnt = 0;
        auto it = strongPtr(begin.clone());
        while (it->isValid() && distance(end, *it) != -1) {
            if (it->get() == target) {
                cnt += 1;
            }
            it->next();
        }
        return cnt;
    }
 
    template <typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    auto original::algorithms::count(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                     const Callback& condition) -> u_integer
    {
        u_integer cnt = 0;
        auto it = strongPtr(begin.clone());
        while (it->isValid() && distance(end, *it) != -1) {
            if (condition(it->get())) {
                cnt += 1;
            }
            it->next();
        }
        return cnt;
    }
 
    template <typename TYPE>
    auto original::algorithms::equal(const iterator<TYPE>& begin1, const iterator<TYPE>& end1,
                                     const iterator<TYPE>& begin2, const iterator<TYPE>& end2) -> bool
    {
        auto it1 = strongPtr(begin1.clone());
        auto it2 = strongPtr(begin2.clone());
 
        while (it1->isValid() && it2->isValid() && !it1->equal(end1) && !it2->equal(end2)) {
            it1->next();
            it2->next();
        }
        const bool res = it1->equal(end1) && it2->equal(end2) && it1->get() == it2->get();
        return res;
    }
 
    template <typename TYPE, typename Callback>
    requires original::Operation<Callback, TYPE>
    auto original::algorithms::forEach(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                       Callback operation) -> void
    {
        auto it = strongPtr(begin.clone());
        for (; !it->equal(end); it->next()) {
            operation(it->get());
        }
        operation(it->get());
    }
 
    template <typename TYPE, typename Callback>
    requires original::Operation<Callback, TYPE>
    auto original::algorithms::forEach(const iterator<TYPE>& begin, const u_integer n,
                                       Callback operation) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        for (u_integer i = 0; i < n; i += 1, it->next())
        {
            operation(it->get());
        }
        return it;
    }
 
    template<typename TYPE, typename Callback_O, typename Callback_C>
    requires original::Operation<Callback_O, TYPE> && original::Condition<Callback_C, TYPE>
    auto original::algorithms::forEach(const iterator<TYPE> &begin, const iterator<TYPE> &end, Callback_O operation,
                                       const Callback_C &condition) -> void {
        auto it = strongPtr(begin.clone());
        for (; !it->equal(end); it->next()) {
            if (condition(it->get()))
                operation(it->get());
        }
 
        if (condition(it->get()))
            operation(it->get());
    }
 
    template<typename TYPE, typename Callback_O, typename Callback_C>
    requires original::Operation<Callback_O, TYPE> && original::Condition<Callback_C, TYPE>
    auto original::algorithms::forEach(const iterator<TYPE> &begin, const u_integer n, Callback_O operation,
                                       const Callback_C &condition) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        for (u_integer i = 0; i < n; i += 1, it->next())
        {
            if (condition(it->get()))
                operation(it->get());
        }
        return it;
    }
 
    template<typename TYPE>
    auto original::algorithms::fill(const iterator<TYPE>& begin,
                                    const iterator<TYPE>& end, const TYPE& value) -> void
    {
        auto it = strongPtr(begin.clone());
        while (!it->equal(end)){
            it->set(value);
            it->next();
        }
        it->set(value);
    }
 
    template<typename TYPE>
    auto original::algorithms::fill(const iterator<TYPE>& begin,
                                    const u_integer n, const TYPE& value) -> strongPtr<iterator<TYPE>> {
        auto it = strongPtr(begin.clone());
        for (u_integer i = 0; i < n; ++i) {
            it->set(value);
            it->next();
        }
        return it;
    }
 
    template <typename TYPE>
    auto original::algorithms::swap(const iterator<TYPE>& it1, const iterator<TYPE>& it2) noexcept -> void
    {
        auto it_1 = strongPtr(it1.clone());
        auto it_2 = strongPtr(it2.clone());
        TYPE tmp = it_2->get();
        it_2->set(it_1->get());
        it_1->set(tmp);
    }
 
    template <typename TYPE>
    auto original::algorithms::copy(const iterator<TYPE>& begin_src, const iterator<TYPE>& end_src,
                        const iterator<TYPE>& begin_tar) -> strongPtr<iterator<TYPE>> {
        auto it_src = strongPtr(begin_src.clone());
        auto it_tar = strongPtr(begin_tar.clone());
        while (!it_src->equal(end_src)){
            it_tar->set(it_src->get());
            it_src->next();
            it_tar->next();
        }
        it_tar->set(it_src->get());
        it_tar->next();
        return it_tar;
    }
 
    template<typename TYPE, typename Callback>
    requires original::Condition<Callback, TYPE>
    auto original::algorithms::copy(const iterator<TYPE>& begin_src, const iterator<TYPE>& end_src,
                               const iterator<TYPE>& begin_tar, Callback condition) -> strongPtr<iterator<TYPE>> {
        auto it_src = strongPtr(begin_src.clone());
        auto it_tar = strongPtr(begin_tar.clone());
        while (!it_src->equal(end_src)){
            if (condition(it_src->get())){
                it_tar->set(it_src->get());
            }
            it_src->next();
            it_tar->next();
        }
        if (condition(it_src->get())){
            it_tar->set(it_src->get());
        }
        it_tar->next();
        return it_tar;
    }
 
    template<typename TYPE>
    auto original::algorithms::reverse(const iterator<TYPE>& begin,
                                       const iterator<TYPE>& end) -> strongPtr<iterator<TYPE>> {
        auto left = strongPtr(begin.clone());
        auto right = strongPtr(end.clone());
        while (distance(right, left) > 0){
            swap(left, right);
            left->next();
            right->prev();
        }
        return left;
    }
 
    template <typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    auto original::algorithms::compare(const iterator<TYPE>& it1, const iterator<TYPE>& it2,
                                       const Callback& compares) -> bool
    {
        return compares(it1.get(), it2.get());
    }
 
    template <typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    auto original::algorithms::heapAdjustDown(const iterator<TYPE>& begin, const iterator<TYPE>& range,
                                              const iterator<TYPE>& current, const Callback& compares) -> void
    {
        if (distance(current, begin) < 0)
            return;
 
        auto it = strongPtr(current.clone());
        while ((distance(*it, begin) + 1) * 2 - 1 <= distance(range, begin))
        {
            auto child = _heapGetPrior(begin, range, *it, compares);
            if (compare(it, child, compares))
            {
                break;
            }
            swap(it, child);
            it = strongPtr(child->clone());
        }
    }
 
    template <typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    auto original::algorithms::heapAdjustUp(const iterator<TYPE>& begin, const iterator<TYPE>& current,
                                            const Callback& compares) -> void
    {
        auto it = strongPtr(current.clone());
        while (distance(*it, begin) > 0)
        {
            auto parent = frontOf(begin, (distance(*it, begin) + 1) / 2 - 1);
            if (compare(it, parent, compares))
            {
                swap(it, parent);
                it = strongPtr(parent->clone());
            }else
            {
                break;
            }
        }
    }
 
    template <typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    auto original::algorithms::heapInit(const iterator<TYPE>& begin, const iterator<TYPE>& end,
                                        const Callback& compares) -> void
    {
        auto it = frontOf(begin, (distance(end, begin) + 1) / 2 - 1);
        for (; distance(*it, begin) >= 0; it->prev())
        {
            heapAdjustDown(begin, end, *it, compares);
        }
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::sort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                    const Callback &compares, const bool isStable) {
        isStable ? stableSort(begin, end, compares) : introSort(begin, end, compares);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::introSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                         const Callback &compares) {
        if (const integer dis = distance(end, begin); dis <= 0)
            return;
 
        u_integer depth_limit = 2 * std::log2(distance(end, begin));
        _introSort(begin, end, compares, depth_limit);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::stableSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                          const Callback &compares) {
        _stableSort(begin, end, compares);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::heapSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                        const Callback& compares) {
        if (distance(end, begin) <= 0)
            return;
 
        heapInit(begin, end, std::not_fn(compares));
        auto right = strongPtr(end.clone());
        while (distance(*right, begin) > 0){
            swap(begin, *right);
            right->prev();
            heapAdjustDown(begin, *right, begin, std::not_fn(compares));
        }
    }
 
    template <typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    auto original::algorithms::_heapGetPrior(const iterator<TYPE>& begin, const iterator<TYPE>& range,
                                             const iterator<TYPE>& parent, const Callback& compares) -> strongPtr<iterator<TYPE>>
    {
        if ((distance(parent, begin) + 1) * 2 <= distance(range, begin))
        {
            auto left = frontOf(begin, (distance(parent, begin) + 1) * 2 - 1);
            auto right = frontOf(begin, (distance(parent, begin) + 1) * 2);
            if (compare(left, right, compares))
            {
                return left;
            }
            return right;
        }
        return frontOf(begin, (distance(parent, begin) + 1) * 2 - 1);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    original::strongPtr<original::iterator<TYPE>>
    original::algorithms::_introSortGetPivot(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                             const Callback &compares) {
        auto mid = frontOf(begin, distance(end, begin) / 2);
        if ((!compare(begin, *mid, compares) && !compare(end, begin, compares))
         || (!compare(*mid, begin, compares) && !compare(begin, end, compares))){
            return strongPtr(begin.clone());
        }
        if ((!compare(*mid, begin, compares) && !compare(end, *mid, compares))
            || (!compare(begin, *mid, compares) && !compare(*mid, end, compares))){
            return mid;
        }
        return strongPtr(end.clone());
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    original::strongPtr<original::iterator<TYPE>>
    original::algorithms::_introSortPartition(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                              const Callback &compares) {
        auto left = strongPtr(begin.clone());
        auto right = strongPtr(end.clone());
        auto pivot = _introSortGetPivot(begin, end, compares);
        TYPE tmp = left->getElem();
        left->set(pivot->getElem());
        bool move_right = true;
        while (distance(right, left) > 0) {
            if (move_right){
                if (compare(right, left, std::not_fn(compares))){
                    right->prev();
                } else{
                    swap(left, right);
                    move_right = false;
                }
            } else{
                if (compare(right, left, std::not_fn(compares))){
                    left->next();
                } else{
                    swap(left, right);
                    move_right = true;
                }
            }
        }
        left->set(tmp);
        return left;
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void
    original::algorithms::_introSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                     const Callback &compares, u_integer depth_limit) {
        if (distance(end, begin) <= 16) {
            insertionSort(begin, end, compares);
            return;
        }
 
        if (depth_limit == 0) {
            heapSort(begin, end, compares);
            return;
        }
 
        auto pivot = _introSortPartition(begin, end, compares);
        _introSort(begin, *pivot, compares, depth_limit - 1);
        _introSort(*pivot, end, compares, depth_limit - 1);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::insertionSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                             const Callback &compares) {
        if (distance(end, begin) <= 0)
            return;
 
        auto left = frontOf(begin, 1);
        while (distance(end, *left) >= 0) {
            auto current = strongPtr(left->clone());
            auto prev = backOf(current, 1);
            while (distance(*current, begin) > 0 && compare(current, prev, compares)){
                swap(current, prev);
                current->prev();
                prev->prev();
            }
            left->next();
        }
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::_stableSortMerge(const iterator<TYPE> &begin, const iterator<TYPE> &mid,
                                                const iterator<TYPE> &end, const Callback &compares) {
        vector<TYPE> tmp;
        auto left = strongPtr(begin.clone());
        auto right = strongPtr(mid.clone());
 
        while (distance(mid, *left) > 0 && distance(end, *right) > 0){
            if (compare(left, right, compares)){
                tmp.pushEnd(left->get());
                left->next();
            } else{
                tmp.pushEnd(right->get());
                right->next();
            }
        }
 
        while (distance(mid, *left) > 0){
            tmp.pushEnd(left->get());
            left->next();
        }
 
        while (distance(end, *right) > 0){
            tmp.pushEnd(right->get());
            right->next();
        }
 
        copy(tmp.first(), tmp.last(), begin);
    }
 
    template<typename TYPE, typename Callback>
    requires original::Compare<Callback, TYPE>
    void original::algorithms::_stableSort(const iterator<TYPE> &begin, const iterator<TYPE> &end,
                                           const Callback &compares) {
        const integer dis = distance(end, begin);
 
        if (dis <= 1)
            return;
 
        if (dis <= 16){
            insertionSort(begin, end, compares);
            return;
        }
 
        auto mid = frontOf(begin, dis / 2);
        _stableSort(begin, *mid, compares);
        _stableSort(*mid, end, compares);
        _stableSortMerge(begin, *mid, end, compares);
    }
 
#endif // ALGORITHMS_H