permutation.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_PERMUTATION_HPP__
#define NEFORCE_CORE_ALGORITHM_PERMUTATION_HPP__

 
#include "NeForce/core/algorithm/shift.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator1, typename Iterator2, typename BinaryPred>
constexpr bool is_permutation(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, BinaryPred pred) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterator must be forward_iterator");
 
    for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
        if (!pred(*first1, *first2)) {
            break;
        }
    }
 
    if (first1 == last1 && first2 == last2) {
        return true;
    }
    if (first1 == last1 || first2 == last2) {
        return false;
    }
 
    for (Iterator1 i = first1; i != last1; ++i) {
        bool already_counted = false;
        for (Iterator1 j = first1; j != i; ++j) {
            if (pred(*j, *i)) {
                already_counted = true;
                break;
            }
        }
        if (!already_counted) {
            size_t cnt2 = 0;
            for (Iterator2 j = first2; j != last2; ++j) {
                if (pred(*i, *j)) {
                    ++cnt2;
                }
            }
            if (cnt2 == 0) {
                return false;
            }
 
            size_t cnt1 = 1;
            Iterator1 j = i;
            for (++j; j != last1; ++j) {
                if (pred(*i, *j)) {
                    ++cnt1;
                }
            }
            if (cnt1 != cnt2) {
                return false;
            }
        }
    }
    return true;
}

template <typename Iterator1, typename Iterator2>
constexpr bool is_permutation(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    return _NEFORCE is_permutation(first1, last1, first2, last2, _NEFORCE equal_to<>());
}

template <typename Iterator, typename Compare>
constexpr bool next_permutation(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterator must be bidirectional_iterator");
 
    if (first == last) {
        return false;
    }
    Iterator i = first;
    ++i;
    if (i == last) {
        return false;
    }
    i = last;
    --i;
    for (;;) {
        Iterator ii = i;
        --i;
        if (comp(*i, *ii)) {
            Iterator j = last;
            while (!comp(*i, *--j)) {
            }
            _NEFORCE iter_swap(i, j);
            _NEFORCE reverse(ii, last);
            return true;
        }
        if (i == first) {
            _NEFORCE reverse(first, last);
            return false;
        }
    }
}

template <typename Iterator>
constexpr bool next_permutation(Iterator first, Iterator last) {
    return _NEFORCE next_permutation(first, last, _NEFORCE less<>());
}

template <typename Iterator, typename Compare>
constexpr bool prev_permutation(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterator must be bidirectional_iterator");
 
    if (first == last) {
        return false;
    }
    Iterator i = first;
    ++i;
    if (i == last) {
        return false;
    }
    i = last;
    --i;
    for (;;) {
        Iterator ii = i;
        --i;
        if (comp(*ii, *i)) {
            Iterator j = last;
            while (!comp(*--j, *i)) {
            }
            _NEFORCE iter_swap(i, j);
            _NEFORCE reverse(ii, last);
            return true;
        }
        if (i == first) {
            _NEFORCE reverse(first, last);
            return false;
        }
    }
}

template <typename Iterator>
constexpr bool prev_permutation(Iterator first, Iterator last) {
    return _NEFORCE prev_permutation(first, last, _NEFORCE less<>());
}
 // PermutationAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_PERMUTATION_HPP__