MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
algo.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#ifndef MATH_ALGO_HEADER
11#define MATH_ALGO_HEADER
12
13#include <cmath>
14#include <vector>
15#include <iterator>
16#include <stdexcept>
17
18#include "math/defines.h"
19
22
23/* ---------------------------- Algorithms ------------------------ */
24
29template <typename FwdIter>
30std::size_t
31min_element_id (FwdIter first, FwdIter last)
32{
33 if (first == last)
34 throw std::invalid_argument("Invalid range");
35
36 FwdIter lowest = first;
37 std::size_t lowest_id = 0;
38
39 for (std::size_t cnt = 1; ++first != last; ++cnt)
40 {
41 if (*first < *lowest)
42 {
43 lowest_id = cnt;
44 lowest = first;
45 }
46 }
47
48 return lowest_id;
49}
50
55template <typename FwdIter>
56std::size_t
57max_element_id (FwdIter first, FwdIter last)
58{
59 if (first == last)
60 throw std::invalid_argument("Invalid range");
61
62 FwdIter largest = first;
63 std::size_t largest_id = 0;
64
65 for (std::size_t cnt = 1; ++first != last; ++cnt)
66 {
67 if (*largest < *first)
68 {
69 largest_id = cnt;
70 largest = first;
71 }
72 }
73
74 return largest_id;
75}
76
81template <typename Key, typename Value>
82Value const*
83binary_search (std::vector<std::pair<Key, Value> > const& vec, Key const& key)
84{
85 std::size_t range1 = 0;
86 std::size_t range2 = vec.size();
87 while (range1 != range2)
88 {
89 std::size_t pos = (range1 + range2) / 2;
90 if (key < vec[pos].first)
91 range2 = pos;
92 else if (vec[pos].first < key)
93 range1 = pos + 1;
94 else
95 return &vec[pos].second;
96 }
97
98 return nullptr;
99}
100
101/* ---------------------- Generator functors ---------------------- */
102
103template <typename T>
105{
107
108 IncrementGenerator (T const& init = T(0)) : state(init)
109 {}
110
111 T operator() (void)
112 { return this->state++; }
113};
114
115/* ------------------- Misc: predicates, iterators, ... ----------- */
116
118template <typename T>
119inline T
120accum_squared_sum (T const& init, T const& next)
121{
122 return init + next * next;
123}
124
126template <typename T>
127inline T
128accum_absolute_sum (T const& init, T const& next)
129{
130 return init + std::abs(next);
131}
132
134template <typename T>
136{
138 predicate_epsilon_equal (T const& eps) : eps(eps) {}
139 bool operator() (T const& v1, T const& v2)
140 { return (v1 - eps <= v2 && v2 <= v1 + eps); }
141};
142
144template <typename T, int S>
145struct InterleavedIter : public std::iterator<std::input_iterator_tag, T>
146{
147 T const* pos;
148 InterleavedIter (T const* pos) : pos(pos) {}
149 InterleavedIter& operator++ (void) { pos += S; return *this; }
150 T const& operator* (void) const { return *pos; }
151 bool operator== (InterleavedIter<T,S> const& other) const
152 { return pos == other.pos; }
153 bool operator!= (InterleavedIter<T,S> const& other) const
154 { return pos != other.pos; }
155};
156
157/* --------------------------- Vector tools ----------------------- */
158
164template <typename T>
165void
166vector_clean (std::vector<bool> const& delete_list, std::vector<T>* vector)
167{
168 typename std::vector<T>::iterator vr = vector->begin();
169 typename std::vector<T>::iterator vw = vector->begin();
170 typename std::vector<bool>::const_iterator dr = delete_list.begin();
171
172 while (vr != vector->end() && dr != delete_list.end())
173 {
174 if (*dr++)
175 {
176 vr++;
177 continue;
178 }
179 if (vw != vr)
180 *vw = *vr;
181 vw++;
182 vr++;
183 }
184 vector->erase(vw, vector->end());
185}
186
187/* ------------------------------ Misc ---------------------------- */
188
195template <typename T>
196inline void
197kernel_region (T const& cx, T const& cy, T const& ks,
198 T const& width, T const& height, T* x1, T* x2, T* y1, T* y2)
199{
200 *x1 = (cx > ks ? cx - ks : T(0));
201 *x2 = (cx + ks > width - T(1) ? width - T(1) : cx + ks);
202 *y1 = (cy > ks ? cy - ks : T(0));
203 *y2 = (cy + ks > height - T(1) ? height - T(1) : cy + ks);
204}
205
206template <typename T>
207inline void
208sort_values (T* a, T* b, T* c)
209{
210 if (*b < *a)
211 std::swap(*a, *b);
212 if (*c < *b)
213 std::swap(*b, *c);
214 if (*b < *a)
215 std::swap(*b, *a);
216}
217
218/* ------------------------ for-each functors --------------------- */
219
221template <typename T>
223{
225 foreach_multiply_with_const (T const& value) : value(value) {}
226 void operator() (T& val) { val *= value; }
227};
228
230template <typename T>
232{
234 foreach_divide_by_const (T const& div) : div(div) {}
235 void operator() (T& val) { val /= div; }
236};
237
239template <typename T>
241{
243 foreach_addition_with_const (T const& value) : value(value) {}
244 void operator() (T& val) { val += value; }
245};
246
248template <typename T>
250{
252 foreach_substraction_with_const (T const& value) : value(value) {}
253 void operator() (T& val) { val -= value; }
254};
255
257template <typename T>
259{
261 foreach_constant_power (T const& value) : value(value) {}
262 void operator() (T& val) { val = std::pow(val, value); }
263};
264
266template <typename M, typename V>
268{
270 foreach_matrix_mult (M const& matrix) : mat(matrix) {}
271 void operator() (V& vec) { vec = mat * vec; }
272};
273
275template <typename T>
276inline void
278{
279 val = std::abs(val);
280}
281
283template <typename T>
284inline void
286{
287 val = -val;
288}
289
291template <typename T>
292inline void
294{
295 val = T(1) / val;
296}
297
299template <typename T>
300inline void
302{
303 val = std::floor(val);
304}
305
307template <typename T>
308inline void
310{
311 val = std::ceil(val);
312}
313
315template <typename T>
316inline void
318{
319 val = round(val);
320}
321
324
325#endif /* MATH_ALGO_HEADER */
Key
Definition key_symbols.h:18
#define MATH_NAMESPACE_BEGIN
Definition defines.h:15
#define MATH_NAMESPACE_END
Definition defines.h:16
#define MATH_ALGO_NAMESPACE_BEGIN
Definition defines.h:18
#define MATH_ALGO_NAMESPACE_END
Definition defines.h:19
std::size_t first
Definition mesh_info.cc:46
void foreach_ceil(T &val)
for-each functor: applies ceil operation to the operand.
Definition algo.h:309
void foreach_floor(T &val)
for-each functor: applies floor operation to the operand.
Definition algo.h:301
std::size_t max_element_id(FwdIter first, FwdIter last)
Algorithm that returns the ID (starting from zero at element 'first') of the largest element in range...
Definition algo.h:57
T accum_squared_sum(T const &init, T const &next)
Squared sum accumulator.
Definition algo.h:120
void vector_clean(std::vector< bool > const &delete_list, std::vector< T > *vector)
Erases all elements from 'vector' that are marked with 'true' in 'delete_list'.
Definition algo.h:166
void foreach_negate_value(T &val)
for-each functor: negates the operand.
Definition algo.h:285
void foreach_round(T &val)
for-each functor: applies rounding to the operand.
Definition algo.h:317
Value const * binary_search(std::vector< std::pair< Key, Value > > const &vec, Key const &key)
Algorithm that finds the value corresponding to a key in sorted vector of key-value pairs.
Definition algo.h:83
std::size_t min_element_id(FwdIter first, FwdIter last)
Algorithm that returns the ID (starting from zero at element 'first') of the smallest element in rang...
Definition algo.h:31
void sort_values(T *a, T *b, T *c)
Definition algo.h:208
void foreach_absolute_value(T &val)
for-each functor: applies absolute value to operand.
Definition algo.h:277
T accum_absolute_sum(T const &init, T const &next)
Absolute sum accumulator.
Definition algo.h:128
void foreach_invert_value(T &val)
for-each functor: inverts floating point values with 1/value.
Definition algo.h:293
void kernel_region(T const &cx, T const &cy, T const &ks, T const &width, T const &height, T *x1, T *x2, T *y1, T *y2)
Returns the kernel region (x1,y1) to (x2,y2) for a kernel of size ks for image of size (width,...
Definition algo.h:197
T round(T const &x)
Removes the fractional part of the value to the closest integer.
Definition functions.h:70
void swap(mve::Image< T > &a, mve::Image< T > &b)
Specialization of std::swap for efficient image swapping.
Definition image.h:478
IncrementGenerator(T const &init=T(0))
Definition algo.h:108
Iterator that advances 'S' elements of type T.
Definition algo.h:146
InterleavedIter(T const *pos)
Definition algo.h:148
for-each functor: adds a constant value to operand.
Definition algo.h:241
foreach_addition_with_const(T const &value)
Definition algo.h:243
for-each functor: raises each operand to the power of constant value.
Definition algo.h:259
foreach_constant_power(T const &value)
Definition algo.h:261
for-each functor: divides operand by constant divisor.
Definition algo.h:232
foreach_divide_by_const(T const &div)
Definition algo.h:234
for-each functor: matrix-vector multiplication.
Definition algo.h:268
foreach_matrix_mult(M const &matrix)
Definition algo.h:270
for-each functor: multiplies operand with constant factor.
Definition algo.h:223
foreach_multiply_with_const(T const &value)
Definition algo.h:225
for-each functor: substracts a constant value to operand.
Definition algo.h:250
foreach_substraction_with_const(T const &value)
Definition algo.h:252
Epsilon comparator predicate.
Definition algo.h:136
predicate_epsilon_equal(T const &eps)
Definition algo.h:138