A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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-2017 Lucas Czech
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 <vector>
40 
41 namespace genesis {
42 namespace utils {
43 
44 // =================================================================================================
45 // Shortcomings of the C++ 11 STL...
46 // =================================================================================================
47 
55 template<class C, class T>
56 inline bool contains(const C& v, const T& x)
57 {
58  return std::end(v) != std::find(std::begin(v), std::end(v), x);
59 }
60 
69 template< class Container, class UnaryPredicate >
70 inline void erase_if( Container &c, UnaryPredicate p )
71 {
72  using std::begin;
73  using std::end;
74  using std::remove_if;
75 
76  auto old_end = end( c );
77  auto new_end = remove_if( begin( c ), old_end, p );
78 
79  if ( new_end != old_end ) {
80  c.erase( new_end, old_end );
81  }
82 }
83 
84 // =================================================================================================
85 // Sorting
86 // =================================================================================================
87 
91 template <typename RandomAccessIterator, typename Comparator>
92 inline std::vector<size_t> sort_indices(
93  RandomAccessIterator first,
94  RandomAccessIterator last,
95  Comparator comparator
96 ) {
97  // Initialize original index locations with increasing numbers.
98  size_t size = std::distance( first, last );
99  std::vector<size_t> idx( size );
100  std::iota( idx.begin(), idx.end(), 0 );
101 
102  // Sort indexes based on comparing values of the iterator range.
103  std::sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
104  assert( first + i1 < last );
105  assert( first + i2 < last );
106  return comparator( *(first + i1), *(first + i2) );
107  });
108 
109  return idx;
110 }
111 
133 template <typename RandomAccessIterator>
134 inline std::vector<size_t> sort_indices(
135  RandomAccessIterator first,
136  RandomAccessIterator last
137 ) {
138  return sort_indices(
139  first,
140  last,
141  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
142  );
143 }
144 
148 template <typename RandomAccessIterator, typename Comparator>
149 inline std::vector<size_t> stable_sort_indices(
150  RandomAccessIterator first,
151  RandomAccessIterator last,
152  Comparator comparator
153 ) {
154  // Initialize original index locations with increasing numbers.
155  size_t size = std::distance( first, last );
156  std::vector<size_t> idx( size );
157  std::iota( idx.begin(), idx.end(), 0 );
158 
159  // Sort indexes based on comparing values of the iterator range.
160  std::stable_sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
161  assert( first + i1 < last );
162  assert( first + i2 < last );
163  return comparator( *(first + i1), *(first + i2) );
164  });
165 
166  return idx;
167 }
168 
190 template <typename RandomAccessIterator>
191 inline std::vector<size_t> stable_sort_indices(
192  RandomAccessIterator first,
193  RandomAccessIterator last
194 ) {
195  return stable_sort_indices(
196  first,
197  last,
198  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
199  );
200 }
201 
202 } // namespace utils
203 } // namespace genesis
204 
205 #endif // include guard
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:70
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:92
bool contains(const C &v, const T &x)
Returns whether a container object has a certain element.
Definition: algorithm.hpp:56
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:149