counting_sort.hpp

/*********************************************************************
 *
 * Linear Arrangement Library - A library that implements a collection
 * algorithms for linear arrangments of graphs.
 *
 * Copyright (C) 2019 - 2024
 *
 * This file is part of Linear Arrangement Library. The full code is available
 * at:
 *      https://github.com/LAL-project/linear-arrangement-library.git
 *
 * Linear Arrangement Library is free software: you can redistribute it
 * and/or modify it under the terms of the GNU Affero General Public License
 * as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Linear Arrangement Library is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Linear Arrangement Library.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Contact:
 *
 *     Lluís Alemany Puig (lluis.alemany.puig@upc.edu)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/lalemany/
 *
 *     Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Office 220, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/rferrericancho/
 *
 ********************************************************************/
 
#pragma once
 
// C++ includes
#include <functional>
#include <tuple>
 
// lal includes
#include <lal/detail/array.hpp>
#include <lal/detail/type_traits/is_pointer_iterator.hpp>
#include <lal/detail/sorting/sorting_types.hpp>
 
namespace lal {
namespace detail {
namespace sorting {
 
namespace countingsort {
 
template <typename T>
struct memory {
    array<std::size_t> count;
    array<T> output;
 
    memory() noexcept = default;
    memory(const memory&) noexcept = default;
    memory(memory&&) noexcept = default;
    memory& operator= (const memory&) noexcept = default;
    memory& operator= (memory&&) noexcept = default;
 
    memory(const std::size_t largest_key_plus_1, const std::size_t max_size_container)
    noexcept
        : count(largest_key_plus_1, 0),
          output(max_size_container)
    { }
 
    ~memory() noexcept = default;
 
    void reset_count() noexcept { count.fill(0); }
};
 
} // -- namespace countingsort
 
template <
    typename value_t,
    sort_type type,
    bool memory_has_frequencies,
    // Can be inferred \/ ...
    typename value_iterator_t,
    typename Callable,
    std::enable_if_t< is_pointer_iterator_v<value_t, value_iterator_t>, bool > = true
>
void counting_sort(
    const value_iterator_t begin, const value_iterator_t end,
    const std::size_t largest_key_plus_1,
    const Callable& key,
    countingsort::memory<value_t>& mem
)
noexcept
{
    // ensure the 'key' function is correct
    static_assert(
        std::is_constructible_v<
            std::function<std::size_t (const value_t&)>,
            Callable
        >
    );
 
    if (begin == end) { return; }
 
    if constexpr (not memory_has_frequencies) {
        // calculate frequency of each element
        for (auto it = begin; it != end; ) {
            // get the key of the element into a variable so that
            // the function is NOT called more than once per iteration
            const std::size_t elem_key = key(*(it++));
 
            ++mem.count[elem_key];
        }
    }
 
    std::size_t total = 0;
    for (std::size_t k = 0; k < largest_key_plus_1; ++k) {
        std::tie(mem.count[k], total)
            = std::make_pair(total, mem.count[k] + total);
    }
 
    std::size_t actual_container_size = 0;
    for (auto it = begin; it != end; ) {
        ++actual_container_size;
 
        // get the key of the element into a variable so that
        // the function is NOT called more than once per iteration
        const std::size_t elem_key = key(*it);
 
        mem.output[mem.count[elem_key]] = std::move(*(it++));
        ++mem.count[elem_key];
    }
 
    // calculate output
    if constexpr (type == sort_type::non_decreasing) {
        auto it = begin;
        for (std::size_t k = 0; k < actual_container_size;) {
            *(it++) = std::move(mem.output[k++]);
        }
    }
    else {
        auto it = begin;
        for (std::size_t k = actual_container_size - 1; k > 0;) {
            *(it++) = std::move(mem.output[k--]);
        }
        *it = std::move(mem.output[0]);
    }
}
 
template <
    typename value_t,
    sort_type type,
    typename value_iterator_t,
    // Can be inferred \/ ...
    typename Callable,
    std::enable_if_t< is_pointer_iterator_v<value_t, value_iterator_t>, bool > = true
>
void counting_sort(
    const value_iterator_t begin, const value_iterator_t end,
    const std::size_t largest_key,
    const std::size_t upper_bound_size,
    const Callable& key
)
noexcept
{
    // ensure the 'key' function is correct
    static_assert(
        std::is_constructible_v<
            std::function<std::size_t (const value_t&)>,
            Callable
        >
    );
 
    // nothing to do if there are no elements to sort
    if (begin == end) { return; }
 
    countingsort::memory<value_t> mem(largest_key+1, upper_bound_size);
 
    counting_sort<value_t, type, false, value_iterator_t>
        (begin, end, largest_key+1, key, mem);
}
 
} // -- namespace sorting
} // -- namespace detail
} // -- namespace lal