A toolkit for working with phylogenetic data.
v0.20.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 // Insert Sorted
86 // =================================================================================================
87 
92 template< typename T >
93 typename std::vector<T>::iterator
94 insert_sorted( std::vector<T> & vec, T const& item )
95 {
96  return vec.insert(
97  std::upper_bound( vec.begin(), vec.end(), item ),
98  item
99  );
100 }
101 
106 template< typename T, typename Pred >
107 typename std::vector<T>::iterator
108 insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
109 {
110  return vec.insert(
111  std::upper_bound( vec.begin(), vec.end(), item, pred ),
112  item
113  );
114 }
115 
116 // =================================================================================================
117 // Sort Indices
118 // =================================================================================================
119 
123 template <typename RandomAccessIterator, typename Comparator>
124 inline std::vector<size_t> sort_indices(
125  RandomAccessIterator first,
126  RandomAccessIterator last,
127  Comparator comparator
128 ) {
129  // Initialize original index locations with increasing numbers.
130  size_t size = std::distance( first, last );
131  std::vector<size_t> idx( size );
132  std::iota( idx.begin(), idx.end(), 0 );
133 
134  // Sort indexes based on comparing values of the iterator range.
135  std::sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
136  assert( first + i1 < last );
137  assert( first + i2 < last );
138  return comparator( *(first + i1), *(first + i2) );
139  });
140 
141  return idx;
142 }
143 
165 template <typename RandomAccessIterator>
166 inline std::vector<size_t> sort_indices(
167  RandomAccessIterator first,
168  RandomAccessIterator last
169 ) {
170  return sort_indices(
171  first,
172  last,
173  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
174  );
175 }
176 
180 template <typename RandomAccessIterator, typename Comparator>
181 inline std::vector<size_t> stable_sort_indices(
182  RandomAccessIterator first,
183  RandomAccessIterator last,
184  Comparator comparator
185 ) {
186  // Initialize original index locations with increasing numbers.
187  size_t size = std::distance( first, last );
188  std::vector<size_t> idx( size );
189  std::iota( idx.begin(), idx.end(), 0 );
190 
191  // Sort indexes based on comparing values of the iterator range.
192  std::stable_sort( idx.begin(), idx.end(), [&] ( size_t i1, size_t i2 ) {
193  assert( first + i1 < last );
194  assert( first + i2 < last );
195  return comparator( *(first + i1), *(first + i2) );
196  });
197 
198  return idx;
199 }
200 
222 template <typename RandomAccessIterator>
223 inline std::vector<size_t> stable_sort_indices(
224  RandomAccessIterator first,
225  RandomAccessIterator last
226 ) {
227  return stable_sort_indices(
228  first,
229  last,
230  std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >()
231  );
232 }
233 
234 } // namespace utils
235 } // namespace genesis
236 
237 #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:124
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:181
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:94