is_permutation.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: BSL-1.0
// SPDX-FileCopyrightText: Copyright (C) 2019 Tobias Hienzsch
 
#ifndef TETL_ALGORITHM_IS_PERMUTATION_HPP
#define TETL_ALGORITHM_IS_PERMUTATION_HPP
 
#include <etl/_algorithm/count.hpp>
#include <etl/_algorithm/find.hpp>
#include <etl/_algorithm/mismatch.hpp>
#include <etl/_iterator/distance.hpp>
#include <etl/_iterator/iterator_traits.hpp>
#include <etl/_iterator/next.hpp>
#include <etl/_iterator/tags.hpp>
#include <etl/_type_traits/is_base_of.hpp>
 
namespace etl {
 
/// \brief Returns true if there exists a permutation of the elements in the
/// range `[first1, last1)` that makes that range equal to the range `[first2,
/// last2)`, where `last2` denotes `first2 + (last1 - first1)` if it was not
/// given.
/// \ingroup algorithm
template <typename ForwardIt1, typename ForwardIt2>
[[nodiscard]] constexpr auto is_permutation(ForwardIt1 first, ForwardIt1 last, ForwardIt2 first2) -> bool
{
    // skip common prefix
    auto const [fDiff1, fDiff2] = etl::mismatch(first, last, first2);
 
    // iterate over the rest, counting how many times each element
    // from `[first, last)` appears in [first2, last2)
    if (fDiff1 != last) {
        auto last2 = etl::next(fDiff2, etl::distance(fDiff1, last));
        for (auto i = fDiff1; i != last; ++i) {
            // this *i has been checked
            if (i != etl::find(fDiff1, i, *i)) {
                continue;
            }
 
            auto m = etl::count(fDiff2, last2, *i);
            if (m == 0 or etl::count(i, last, *i) != m) {
                return false;
            }
        }
    }
 
    return true;
}
 
/// \ingroup algorithm
template <typename ForwardIt1, typename ForwardIt2>
[[nodiscard]] constexpr auto is_permutation(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2)
    -> bool
{
    using tag = random_access_iterator_tag;
 
    constexpr auto lhsIsRandomIt = is_base_of_v<tag, typename iterator_traits<ForwardIt1>::iterator_category>;
    constexpr auto rhsIsRandomIt = is_base_of_v<tag, typename iterator_traits<ForwardIt2>::iterator_category>;
 
    if constexpr (lhsIsRandomIt and rhsIsRandomIt) {
        if (etl::distance(first1, last1) != etl::distance(first2, last2)) {
            return false;
        }
    }
    return etl::is_permutation(first1, last1, first2);
}
 
} // namespace etl
 
#endif // TETL_ALGORITHM_IS_PERMUTATION_HPP