algorithm.hpp

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit 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 General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <algorithm>
#include <functional>
 
namespace ext {
 
template<class InputIt1, class InputIt2, class Compare>
bool excludes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp) {
    while (first2 != last2 && first1 != last1) {
        if (comp(*first2, *first1)) {
            ++first2;
        } else if (comp(*first1, *first2)) {
            ++first1;
        } else {
            return false;
        }
    }
    return true;
}
 
template<class InputIt1, class InputIt2>
bool excludes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) {
    return excludes(first1, last1, first2, last2, std::less<decltype(*first1)>());
}
 
template < class InputIterator1, class InputIterator2, class OutputIterator1, class OutputIterator2, class Compare >
void set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator1 result1, OutputIterator2 result2, Compare comp ) {
    while ( first1 != last1 && first2 != last2 ) {
        if ( comp ( * first1, * first2 ) ) {
            * result1 = * first1;
            ++ result1;
            ++ first1;
        } else if ( comp ( * first2, * first1 ) ) {
            * result2 = * first2;
            ++ result2;
            ++ first2;
        } else {
            ++first1;
            ++first2;
        }
    }
 
    if ( first1 == last1 ) {
        std::copy ( first2, last2, result2 );
    }
    if ( first2 == last2 ) {
        std::copy ( first1, last1, result1 );
    }
}
 
template < class InputIterator1, class InputIterator2, class OutputIterator1, class OutputIterator2 >
void set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator1 result1, OutputIterator2 result2 ) {
    set_symmetric_difference ( first1, last1, first2, last2, result1, result2, std::less < decltype ( * first1 ) > ( ) );
}
 
template < class ResType, class InType, typename ... Ts, template < typename ... > class ContainerType, class Callback >
ContainerType < ResType > transform(const ContainerType < InType, Ts ... > & in, Callback transform ) {
    ContainerType<ResType> res;
    std::transform ( in.begin ( ), in.end ( ), std::inserter ( res, res.begin ( ) ), transform );
    return res;
}
 
template<class InputIt, class Element>
bool contains(InputIt first, InputIt last, const Element& elem) {
    return find(first, last, elem) != last;
}
 
template<class InputIt, class Element>
bool binary_contains(InputIt first, InputIt last, const Element& elem) {
    return binary_search(first, last, elem) != last;
}
 
template < class Iterator, class Value >
std::pair < Iterator, Iterator > find_range_internal ( Iterator begin, Iterator end, const Value & open, const Value & close ) {
    for ( ; begin != end && * begin != open && * begin != close ; ++ begin );
 
    if ( begin == end || * begin == close )
        return std::make_pair ( begin, begin );
 
    Iterator openPos = begin;
 
    for ( ; ; ) {
        std::pair < Iterator, Iterator > subRange = find_range_internal ( begin + 1, end, open, close );
        if ( subRange.first == subRange.second )
            break;
        begin = subRange.second;
    }
 
    if ( begin == end )
        return std::make_pair ( begin, begin );
 
    ++ begin;
 
    for ( ; begin != end && * begin != close ; ++ begin );
 
    if ( begin == end )
        return std::make_pair ( begin, begin );
 
    Iterator closePos = begin;
 
    return std::make_pair ( openPos, closePos );
}
 
template < class Iterator, class Value >
std::pair < Iterator, Iterator > find_range ( Iterator begin, Iterator end, const Value & open, const Value & close ) {
    std::pair < Iterator, Iterator > res = find_range_internal ( begin, end, open, close );
 
    if ( res.first == res.second )
        return res;
 
    ++ res.second;
 
    return res;
}
 
template < typename T >
constexpr const T & max ( const T & a ) {
    return a;
}
 
template < typename T, typename ... Args >
constexpr const T & max ( const T & a, const T & b, const Args & ... args ) {
    return max ( b < a ? a : b, args ... );
}
 
template < typename T >
constexpr const T & min ( const T & a) {
    return a;
}
 
template < typename T, typename ... Args >
constexpr const T & min ( const T & a, const T & b, const Args & ... args) {
    return min ( b > a ? a : b, args ... );
}
 
template < typename ForwardIterator, typename BinaryPredicate >
ForwardIterator adjacent_find_internal ( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred ) {
    if ( first == last )
        return last;
    ForwardIterator next = first;
    while ( ++ next != last ) {
        if ( binary_pred ( * first, * next ) )
            return first;
        first = next;
    }
    return last;
}
 
template < typename ForwardIterator, typename BinaryPredicate >
ForwardIterator unique_internal ( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred ) {
    // Skip the beginning, if already unique.
    first = ext::adjacent_find_internal ( first, last, binary_pred );
    if ( first == last )
        return last;
 
    // Do the real copy work.
    ForwardIterator dest = first;
    ++ first;
    while ( ++ first != last )
        if ( ! binary_pred ( * dest, * first ) )
            std::swap ( * ++ dest, * first );
    return ++ dest;
}
 
template < typename ForwardIterator >
inline ForwardIterator unique ( ForwardIterator first, ForwardIterator last ) {
    return ext::unique_internal(first, last, [] ( const auto & a, const auto & b ) { return a == b; } );
}
 
template < typename ForwardIterator, typename BinaryPredicate >
inline ForwardIterator unique ( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred ) {
    return ext::unique_internal(first, last, binary_pred );
}
 
template < class ForwardIteratorBegin, class ForwardIteratorEnd, class ForwardCandidateIterator >
inline bool range_contains_iterator ( ForwardIteratorBegin from, const ForwardIteratorEnd & end, const ForwardCandidateIterator & candidate ) {
    for ( ; from != end; ++ from )
        if ( static_cast < const void * > ( std::addressof ( * from ) ) == static_cast < const void * > ( std::addressof ( * candidate ) ) )
            return true;
    return false;
}
 
} /* namespace ext */