Heap sorter with d-ary heaps

dary_heap_operations.h

// // boost heap: d-ary heap as containter adaptor
//
// Copyright (C) 2010 Tim Blechmann
//  Modified in 2016 by Morwenn for inclusion into cpp-sort
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef CPPSORT_DETAIL_DARY_HEAP_OPERATIONS_H_
#define CPPSORT_DETAIL_DARY_HEAP_OPERATIONS_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <utility>

namespace cppsort
{
namespace detail
{
    template<std::size_t D, typename RandomAccessIterator>
    auto parent_it(RandomAccessIterator first, RandomAccessIterator it)
        -> RandomAccessIterator
    {
        auto index = std::distance(first, it);
        return first + (index - 1) / D;
    }

    template<std::size_t D, typename RandomAccessIterator>
    auto first_child_it(RandomAccessIterator first, RandomAccessIterator it)
        -> RandomAccessIterator
    {
        auto index = std::distance(first, it);
        return first + index * D + 1;
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    auto top_child_it(RandomAccessIterator first, RandomAccessIterator last,
                      RandomAccessIterator it, Compare compare)
        -> RandomAccessIterator
    {
        // invariant: it is not a leaf, so the iterator range is not empty

        RandomAccessIterator first_child = first_child_it<D>(first, it);
        auto max_elements = std::distance(first_child, last);
        RandomAccessIterator last_child = (max_elements > D) ? first_child + D : last;

        return std::max_element(first_child, last_child, compare);
    }

    template<std::size_t D, typename RandomAccessIterator>
    auto not_leaf(RandomAccessIterator first, RandomAccessIterator last,
                  RandomAccessIterator it)
        -> bool
    {
        RandomAccessIterator first_child = first_child_it<D>(first, it);
        return first_child < last;
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    void siftdown(RandomAccessIterator first, RandomAccessIterator last,
                  RandomAccessIterator it, Compare compare)
    {
        using std::swap;

        while (not_leaf<D>(first, last, it)) {
            RandomAccessIterator max_child = top_child_it<D>(first, last, it, compare);
            if (not compare(*max_child, *it)) {
                swap(*max_child, *it);
                it = max_child;
            } else {
                return;
            }
        }
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    void siftup(RandomAccessIterator first, RandomAccessIterator last,
                RandomAccessIterator it, Compare compare)
    {
        using std::swap;

        while (it != first) {
            RandomAccessIterator parent = parent_it<D>(first, it);

            if (compare(*parent, *it)) {
                swap(*parent, *it);
                it = parent;
            } else {
                return;
            }
        }
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    auto push_d_ary_heap(RandomAccessIterator first, RandomAccessIterator last,
                   Compare compare)
        -> void
    {
        siftup<D>(first, last, std::prev(last), compare);
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    auto pop_d_ary_heap(RandomAccessIterator first, RandomAccessIterator last,
                  Compare compare)
        -> void
    {
        using std::swap;
        swap(*first, *--last);
        if (first == last) return;

        siftdown<D>(first, last, first, compare);
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    auto make_d_ary_heap(RandomAccessIterator first, RandomAccessIterator last,
                   Compare compare)
        -> void
    {
        if (first == last) return;

        for (auto it = std::next(first) ; it != last ; ++it) {
            push_d_ary_heap<D>(first, it, compare);
        }
        // Take the last element into consideration
        push_d_ary_heap<D>(first, last, compare);
    }

    template<std::size_t D, typename RandomAccessIterator, typename Compare>
    auto sort_d_ary_heap(RandomAccessIterator first, RandomAccessIterator last,
                   Compare compare)
        -> void
    {
        for (auto it = last ; it != first ; --it) {
            pop_d_ary_heap<D>(first, it, compare);
        }
    }
}}

#endif // CPPSORT_DETAIL_DARY_HEAP_OPERATIONS_H_

dary_heap_sorter.h

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2016 Morwenn
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#ifndef CPPSORT_SORTERS_D_ARY_HEAP_SORTER_H_
#define CPPSORT_SORTERS_D_ARY_HEAP_SORTER_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <cstddef>
#include <functional>
#include <iterator>
#include <type_traits>
#include <utility>
#include <cpp-sort/sorter_facade.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/utility/functional.h>
#include <cpp-sort/utility/static_const.h>
#include "../detail/dary_heap_operations.h"
#include "../detail/iterator_traits.h"

namespace cppsort
{
    ////////////////////////////////////////////////////////////
    // Sorter

    namespace detail
    {
        template<std::size_t D>
        struct d_ary_heap_sorter_impl
        {
            template<
                typename RandomAccessIterator,
                typename Compare = std::less<>,
                typename Projection = utility::identity,
                typename = std::enable_if_t<
                    is_projection_iterator_v<Projection, RandomAccessIterator, Compare>
                >
            >
            auto operator()(RandomAccessIterator first, RandomAccessIterator last,
                            Compare compare={}, Projection={}) const
                -> void
            {
                static_assert(
                    std::is_base_of<
                        std::random_access_iterator_tag,
                        iterator_category_t<RandomAccessIterator>
                    >::value,
                    "d_ary_heap_sorter requires at least random-access iterators"
                );

                make_d_ary_heap<D>(first, last, compare);
                sort_d_ary_heap<D>(first, last, compare);
            }

            ////////////////////////////////////////////////////////////
            // Sorter traits

            using iterator_category = std::random_access_iterator_tag;
            using is_always_stable = std::false_type;
        };
    }

    template<std::size_t D>
    struct d_ary_heap_sorter:
        sorter_facade<detail::d_ary_heap_sorter_impl<D>>
    {};

    ////////////////////////////////////////////////////////////
    // Sort function

    namespace
    {
        constexpr auto&& d_ary_heap_sort
            = utility::static_const<d_ary_heap_sorter<2>>::value;
    }
}

#endif // CPPSORT_SORTERS_D_ARY_HEAP_SORTER_H_