algorithm.hpp

Go to the documentation of this file.

#ifndef GENESIS_UTILS_CORE_ALGORITHM_H_
#define GENESIS_UTILS_CORE_ALGORITHM_H_
 
/*
    Genesis - A toolkit for working with phylogenetic data.
    Copyright (C) 2014-2024 Lucas Czech
 
    This program 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.
 
    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
 
    Contact:
    Lucas Czech <lucas.czech@h-its.org>
    Exelixis Lab, Heidelberg Institute for Theoretical Studies
    Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
*/
 
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <numeric>
#include <unordered_set>
#include <utility>
#include <vector>
 
namespace genesis {
namespace utils {
 
// =================================================================================================
//     Shortcomings of the C++ 11 STL...
// =================================================================================================
 
template<class ForwardIt, class T, class Compare=std::less<T>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
    // This is stricter than lower_bound requirement (see above)
 
    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}
 
template<class C, class T>
inline bool contains(const C& v, const T& x)
{
    return std::end(v) != std::find(std::begin(v), std::end(v), x);
}
 
template<class C>
inline bool contains_duplicates( C const& v )
{
    auto test = std::unordered_set< typename C::value_type >();
    for( auto const& e : v ) {
        if( test.count(e) > 0 ) {
            return true;
        }
        test.insert(e);
    }
    return false;
}
 
template< class Container, class UnaryPredicate >
inline void erase_if( Container &c, UnaryPredicate p )
{
    using std::begin;
    using std::end;
    using std::remove_if;
 
    auto old_end = end( c );
    auto new_end = remove_if( begin( c ), old_end, p );
 
    if ( new_end != old_end ) {
        c.erase( new_end, old_end );
    }
}
 
template<class T>
std::pair<T, T> minmax_value( T const& a, T const& b )
{
    return (a < b) ? std::pair<T, T>(a, b) : std::pair<T, T>(b, a);
}
 
template<class T, class Compare>
std::pair<T, T> minmax_value( T const& a, T const& b, Compare comp )
{
    return comp(a, b) ? std::pair<T, T>(a, b) : std::pair<T, T>(b, a);
}
 
// =================================================================================================
//     Insert Sorted
// =================================================================================================
 
template< typename T >
typename std::vector<T>::iterator
insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert(
        std::upper_bound( vec.begin(), vec.end(), item ),
        item
    );
}
 
template< typename T, typename Pred >
typename std::vector<T>::iterator
insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert(
       std::upper_bound( vec.begin(), vec.end(), item, pred ),
       item
    );
}
 
// =================================================================================================
//     Sort Indices
// =================================================================================================
 
template <typename RandomAccessIterator, typename Comparator>
inline std::vector<size_t> sort_indices(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Comparator           comparator
) {
    // Initialize original index locations with increasing numbers.
    size_t size = std::distance( first, last );
    std::vector<size_t> idx( size );
    std::iota( idx.begin(), idx.end(), static_cast<size_t>(0) );
 
    // Sort indexes based on comparing values of the iterator range.
    std::sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
        assert( first + i1 < last );
        assert( first + i2 < last );
        return comparator( *(first + i1), *(first + i2) );
    });
 
    return idx;
}
 
template <typename RandomAccessIterator>
inline std::vector<size_t> sort_indices(
    RandomAccessIterator first,
    RandomAccessIterator last
) {
    return sort_indices(
        first,
        last,
        std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
    );
}
 
template <typename RandomAccessIterator, typename Comparator>
inline std::vector<size_t> stable_sort_indices(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Comparator           comparator
) {
    // Initialize original index locations with increasing numbers.
    size_t size = std::distance( first, last );
    std::vector<size_t> idx( size );
    std::iota( idx.begin(), idx.end(), static_cast<size_t>(0) );
 
    // Sort indexes based on comparing values of the iterator range.
    std::stable_sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
        assert( first + i1 < last );
        assert( first + i2 < last );
        return comparator( *(first + i1), *(first + i2) );
    });
 
    return idx;
}
 
template <typename RandomAccessIterator>
inline std::vector<size_t> stable_sort_indices(
    RandomAccessIterator first,
    RandomAccessIterator last
) {
    return stable_sort_indices(
        first,
        last,
        std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
    );
}
 
} // namespace utils
} // namespace genesis
 
#endif // include guard