Adobe Source Libraries 1.49.0
A collection of C++ libraries.
Loading...
Searching...
No Matches
reduce.hpp
Go to the documentation of this file.
1/*
2 Copyright 2013 Adobe
3 Distributed under the Boost Software License, Version 1.0.
4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5*/
6/**************************************************************************************************/
7
8#ifndef ADOBE_ALGORITHM_REDUCE_HPP
9#define ADOBE_ALGORITHM_REDUCE_HPP
10
11#include <adobe/config.hpp>
12
13#include <adobe/algorithm/identity_element.hpp>
14#include <adobe/algorithm/other_of.hpp>
15#include <adobe/functional.hpp>
16#include <adobe/iterator/type_functions.hpp>
17
18#include <algorithm>
19#include <functional>
20#include <vector>
21
22/**************************************************************************************************/
23
24namespace adobe {
25
26/**************************************************************************************************/
31/**************************************************************************************************/
37template <typename I, // I models InputIterator
38 typename Op> // Op model BinaryOperation
39typename std::iterator_traits<I>::value_type
40reduce_nonzeros(I f, I l, Op op, ADOBE_VALUE_TYPE(I) z = adobe::identity_element<Op>()()) {
41 // skip zeros
42 f = adobe::find_not(f, l, z);
43
44 if (f == l)
45 return z;
46
47 ADOBE_VALUE_TYPE(I) result(*f);
48
49 ++f;
50
51 while (f != l) {
52 if (*f != z)
53 result = op(result, *f);
54
55 ++f;
56 }
57
58 return result;
59}
60
61/**************************************************************************************************/
67template <typename I, // I models Forward Iterator
68 typename Op> // Op models Binary Operation
69typename std::iterator_traits<I>::value_type
70add_to_counter(I f, I l, Op op, ADOBE_VALUE_TYPE(I) x,
71 ADOBE_VALUE_TYPE(I) z = adobe::identity_element<Op>()()) {
72 if (x == z)
73 return z;
74
75 while (f != l) {
76 if (*f != z) {
77 // NOTE (stepanov) : op(*f, x) and not op(x, *f) because the partial
78 // result pointed to by f is the result of adding elements
79 // earlier in the sequence.
80 x = op(*f, x);
81
82 *f = z;
83 } else {
84 *f = x;
85
86 return z;
87 }
88
89 ++f;
90 }
91
92 return x;
93}
94
95/**************************************************************************************************/
101template <typename I, // I models InputIterator
102 typename Op> // Op models BinaryOperation
103typename std::iterator_traits<I>::value_type
104reduce_balanced(I f, I l, Op op, ADOBE_VALUE_TYPE(I) z = adobe::identity_element<Op>()()) {
105 std::vector<ADOBE_VALUE_TYPE(I)> v;
106
107 while (f != l) {
108 ADOBE_VALUE_TYPE(I) tmp = add_to_counter(v.begin(), v.end(), op, *f, z);
109
110 if (tmp != z)
111 v.push_back(tmp);
112
113 ++f;
114 }
115
116 return reduce_nonzeros(v.begin(), v.end(), transpose(op), z);
117}
118
119/**************************************************************************************************/
120
121} // namespace adobe
122
123/**************************************************************************************************/
124
125#endif
126
127/**************************************************************************************************/
ADOBE_VALUE_TYPE
#define ADOBE_VALUE_TYPE(I)
Definition type_functions.hpp:35
adobe::find_not
InputIterator find_not(InputIterator first, InputIterator last, const T &value)
Definition find.hpp:111
adobe::reduce_balanced
std::iterator_traits< I >::value_type reduce_balanced(I f, I l, Op op, ADOBE_VALUE_TYPE(I) z=adobe::identity_element< Op >()())
reduce implementation
Definition reduce.hpp:104
adobe::add_to_counter
std::iterator_traits< I >::value_type add_to_counter(I f, I l, Op op, ADOBE_VALUE_TYPE(I) x, ADOBE_VALUE_TYPE(I) z=adobe::identity_element< Op >()())
reduce implementation
Definition reduce.hpp:70
adobe::reduce_nonzeros
std::iterator_traits< I >::value_type reduce_nonzeros(I f, I l, Op op, ADOBE_VALUE_TYPE(I) z=adobe::identity_element< Op >()())
reduce implementation
Definition reduce.hpp:40
identity_element.hpp
other_of.hpp
adobe::identity_element
Definition identity_element.hpp:28
type_functions.hpp