A library for working with phylogenetic and population genetic data.
v0.27.0
algorithm.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_CORE_ALGORITHM_H_
2 #define GENESIS_UTILS_CORE_ALGORITHM_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2020 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
34 #include <algorithm>
35 #include <cassert>
36 #include <cmath>
37 #include <functional>
38 #include <numeric>
39 #include <unordered_set>
40 #include <utility>
41 #include <vector>
42 
43 namespace genesis {
44 namespace utils {
45 
46 // =================================================================================================
47 // Shortcomings of the C++ 11 STL...
48 // =================================================================================================
49 
55 template<class ForwardIt, class T, class Compare=std::less<T>>
56 ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
57 {
58  // Note: BOTH type T and the type after ForwardIt is dereferenced
59  // must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
60  // This is stricter than lower_bound requirement (see above)
61 
62  first = std::lower_bound(first, last, value, comp);
63  return first != last && !comp(value, *first) ? first : last;
64 }
65 
73 template<class C, class T>
74 inline bool contains(const C& v, const T& x)
75 {
76  return std::end(v) != std::find(std::begin(v), std::end(v), x);
77 }
78 
85 template<class C>
86 inline bool contains_duplicates( C const& v )
87 {
88  auto test = std::unordered_set< typename C::value_type >();
89  for( auto const& e : v ) {
90  if( test.count(e) > 0 ) {
91  return true;
92  }
93  test.insert(e);
94  }
95  return false;
96 }
97 
106 template< class Container, class UnaryPredicate >
107 inline void erase_if( Container &c, UnaryPredicate p )
108 {
109  using std::begin;
110  using std::end;
111  using std::remove_if;
112 
113  auto old_end = end( c );
114  auto new_end = remove_if( begin( c ), old_end, p );
115 
116  if ( new_end != old_end ) {
117  c.erase( new_end, old_end );
118  }
119 }
120 
127 template<class T>
128 std::pair<T, T> minmax_value( T const& a, T const& b )
129 {
130  return (a < b) ? std::pair<T, T>(a, b) : std::pair<T, T>(b, a);
131 }
132 
136 template<class T, class Compare>
137 std::pair<T, T> minmax_value( T const& a, T const& b, Compare comp )
138 {
139  return comp(a, b) ? std::pair<T, T>(a, b) : std::pair<T, T>(b, a);
140 }
141 
142 // =================================================================================================
143 // Insert Sorted
144 // =================================================================================================
145 
150 template< typename T >
151 typename std::vector<T>::iterator
152 insert_sorted( std::vector<T> & vec, T const& item )
153 {
154  return vec.insert(
155  std::upper_bound( vec.begin(), vec.end(), item ),
156  item
157  );
158 }
159 
164 template< typename T, typename Pred >
165 typename std::vector<T>::iterator
166 insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
167 {
168  return vec.insert(
169  std::upper_bound( vec.begin(), vec.end(), item, pred ),
170  item
171  );
172 }
173 
174 // =================================================================================================
175 // Sort Indices
176 // =================================================================================================
177 
181 template <typename RandomAccessIterator, typename Comparator>
182 inline std::vector<size_t> sort_indices(
183  RandomAccessIterator first,
184  RandomAccessIterator last,
185  Comparator comparator
186 ) {
187  // Initialize original index locations with increasing numbers.
188  size_t size = std::distance( first, last );
189  std::vector<size_t> idx( size );
190  std::iota( idx.begin(), idx.end(), 0 );
191 
192  // Sort indexes based on comparing values of the iterator range.
193  std::sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
194  assert( first + i1 < last );
195  assert( first + i2 < last );
196  return comparator( *(first + i1), *(first + i2) );
197  });
198 
199  return idx;
200 }
201 
223 template <typename RandomAccessIterator>
224 inline std::vector<size_t> sort_indices(
225  RandomAccessIterator first,
226  RandomAccessIterator last
227 ) {
228  return sort_indices(
229  first,
230  last,
231  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
232  );
233 }
234 
238 template <typename RandomAccessIterator, typename Comparator>
239 inline std::vector<size_t> stable_sort_indices(
240  RandomAccessIterator first,
241  RandomAccessIterator last,
242  Comparator comparator
243 ) {
244  // Initialize original index locations with increasing numbers.
245  size_t size = std::distance( first, last );
246  std::vector<size_t> idx( size );
247  std::iota( idx.begin(), idx.end(), 0 );
248 
249  // Sort indexes based on comparing values of the iterator range.
250  std::stable_sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
251  assert( first + i1 < last );
252  assert( first + i2 < last );
253  return comparator( *(first + i1), *(first + i2) );
254  });
255 
256  return idx;
257 }
258 
280 template <typename RandomAccessIterator>
281 inline std::vector<size_t> stable_sort_indices(
282  RandomAccessIterator first,
283  RandomAccessIterator last
284 ) {
285  return stable_sort_indices(
286  first,
287  last,
288  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
289  );
290 }
291 
292 } // namespace utils
293 } // namespace genesis
294 
295 #endif // include guard
genesis::utils::binary_find
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T &value, Compare comp={})
Binary search on a sorted/partitioned range, returns an iterator to the element if found.
Definition: algorithm.hpp:56
genesis::utils::sort_indices
std::vector< size_t > sort_indices(RandomAccessIterator first, RandomAccessIterator last, Comparator comparator)
Get the indices to the sorted order of the given range.
Definition: algorithm.hpp:182
genesis::utils::contains_duplicates
bool contains_duplicates(C const &v)
Return whether a container contains duplicates.
Definition: algorithm.hpp:86
genesis::utils::erase_if
void erase_if(Container &c, UnaryPredicate p)
Erases all elements from the container that satisfy a given predicate. An element is erased,...
Definition: algorithm.hpp:107
genesis::utils::minmax_value
std::pair< T, T > minmax_value(T const &a, T const &b)
Returns the lowest and the greatest of the given values, by value.
Definition: algorithm.hpp:128
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::utils::contains
bool contains(const C &v, const T &x)
Returns whether a container object has a certain element.
Definition: algorithm.hpp:74
genesis::utils::stable_sort_indices
std::vector< size_t > stable_sort_indices(RandomAccessIterator first, RandomAccessIterator last, Comparator comparator)
Get the indices to the stable sorted order of the given range.
Definition: algorithm.hpp:239
genesis::utils::insert_sorted
std::vector< T >::iterator insert_sorted(std::vector< T > &vec, T const &item)
Insert into a vector vec, sorted by the value of the item. The vector must already be sorted.
Definition: algorithm.hpp:152