stlab.adobe.com Adobe Systems Incorporated
reduce.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 /*************************************************************************************************/
7 
8 #ifndef ADOBE_ALGORITHM_REDUCE_HPP
9 #define ADOBE_ALGORITHM_REDUCE_HPP
10 
11 #include <adobe/config.hpp>
12 
15 #include <adobe/functional.hpp>
17 
18 #include <algorithm>
19 #include <functional>
20 #include <vector>
21 
22 /*************************************************************************************************/
23 
24 namespace adobe {
25 
26 /*************************************************************************************************/
31 /*************************************************************************************************/
37 template <typename I, // I models InputIterator
38  typename Op> // Op model BinaryOperation
39 typename std::iterator_traits<I>::value_type reduce_nonzeros(I f,
40  I l,
41  Op op,
42  ADOBE_VALUE_TYPE(I) z =
44 {
45  // skip zeros
46  f = adobe::find_not(f, l, z);
47 
48  if (f == l)
49  return z;
50 
51  ADOBE_VALUE_TYPE(I) result(*f);
52 
53  ++f;
54 
55  while (f != l)
56  {
57  if (*f != z)
58  result = op(result, *f);
59 
60  ++f;
61  }
62 
63  return result;
64 }
65 
66 /*************************************************************************************************/
72 template <typename I, // I models Forward Iterator
73  typename Op> // Op models Binary Operation
74 typename std::iterator_traits<I>::value_type add_to_counter(I f,
75  I l,
76  Op op,
77  ADOBE_VALUE_TYPE(I) x,
78  ADOBE_VALUE_TYPE(I) z =
80 {
81  if (x == z)
82  return z;
83 
84  while (f != l)
85  {
86  if (*f != z)
87  {
88  // NOTE (stepanov) : op(*f, x) and not op(x, *f) because the partial
89  // result pointed to by f is the result of adding elements
90  // earlier in the sequence.
91  x = op(*f, x);
92 
93  *f = z;
94  }
95  else
96  {
97  *f = x;
98 
99  return z;
100  }
101 
102  ++f;
103  }
104 
105  return x;
106 }
107 
108 /*************************************************************************************************/
114 template <typename I, // I models InputIterator
115  typename Op> // Op models BinaryOperation
116 typename std::iterator_traits<I>::value_type reduce_balanced(I f,
117  I l,
118  Op op,
119  ADOBE_VALUE_TYPE(I) z =
121 {
122  std::vector<ADOBE_VALUE_TYPE(I)> v;
123 
124  while (f != l)
125  {
126  ADOBE_VALUE_TYPE(I) tmp = add_to_counter(v.begin(), v.end(), op, *f, z);
127 
128  if (tmp != z)
129  v.push_back(tmp);
130 
131  ++f;
132  }
133 
134  return reduce_nonzeros(v.begin(), v.end(), f_transpose(op), z);
135 }
136 
137 /*************************************************************************************************/
138 
139 } // namespace adobe
140 
141 /*************************************************************************************************/
142 
143 #endif
144 
145 /*************************************************************************************************/

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google