stlab.adobe.com Adobe Systems Incorporated

reduce.hpp

Go to the documentation of this file.
00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003     Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
00004     or a copy at http://stlab.adobe.com/licenses.html)
00005 */
00006 /*************************************************************************************************/
00007 
00008 #ifndef ADOBE_ALGORITHM_REDUCE_HPP
00009 #define ADOBE_ALGORITHM_REDUCE_HPP
00010 
00011 #include <adobe/config.hpp>
00012 
00013 #include <adobe/algorithm/identity_element.hpp>
00014 #include <adobe/algorithm/other_of.hpp>
00015 #include <adobe/functional.hpp>
00016 #include <adobe/iterator/type_functions.hpp>
00017 
00018 #include <algorithm>
00019 #include <functional>
00020 #include <vector>
00021 
00022 /*************************************************************************************************/
00023 
00024 namespace adobe {
00025 
00026 /*************************************************************************************************/
00031 /*************************************************************************************************/
00037 template <typename I,  // I models InputIterator 
00038           typename Op> // Op model BinaryOperation 
00039 typename std::iterator_traits<I>::value_type reduce_nonzeros(I f,
00040                                                              I l,
00041                                                              Op op,
00042                                                              ADOBE_VALUE_TYPE(I) z =
00043                                                                  adobe::identity_element<Op>()())
00044 {
00045     // skip zeros
00046     f = adobe::find_not(f, l, z);
00047 
00048     if (f == l)
00049         return z;
00050 
00051     ADOBE_VALUE_TYPE(I) result(*f);
00052 
00053     ++f;
00054 
00055     while (f != l)
00056     {
00057         if (*f != z)
00058             result = op(result, *f);
00059 
00060         ++f;
00061     }
00062 
00063     return result;
00064 }
00065 
00066 /*************************************************************************************************/
00072 template <typename I,  // I models Forward Iterator
00073           typename Op> // Op models Binary Operation
00074 typename std::iterator_traits<I>::value_type add_to_counter(I                   f,
00075                                                             I                   l,
00076                                                             Op                  op,
00077                                                             ADOBE_VALUE_TYPE(I) x,
00078                                                             ADOBE_VALUE_TYPE(I) z =
00079                                                                 adobe::identity_element<Op>()())
00080 {
00081     if (x == z)
00082         return z;
00083 
00084     while (f != l)
00085     {
00086         if (*f != z)
00087         {
00088             // NOTE (stepanov) : op(*f, x) and not op(x, *f) because the partial
00089             //                   result pointed to by f is the result of adding elements
00090             //                   earlier in the sequence.
00091             x = op(*f, x);
00092 
00093             *f = z;
00094         }
00095         else
00096         {
00097             *f = x;
00098 
00099             return z;
00100         }
00101 
00102         ++f;
00103     }
00104 
00105     return x;
00106 }
00107 
00108 /*************************************************************************************************/
00114 template <typename I,  // I models InputIterator
00115           typename Op> // Op models BinaryOperation
00116 typename std::iterator_traits<I>::value_type reduce_balanced(I                   f,
00117                                                              I                   l,
00118                                                              Op                  op,
00119                                                              ADOBE_VALUE_TYPE(I) z =
00120                                                                  adobe::identity_element<Op>()())
00121 {
00122     std::vector<ADOBE_VALUE_TYPE(I)> v;
00123 
00124     while (f != l)
00125     {
00126         ADOBE_VALUE_TYPE(I) tmp = add_to_counter(v.begin(), v.end(), op, *f, z);
00127 
00128         if (tmp != z)
00129             v.push_back(tmp);
00130 
00131         ++f;
00132     }
00133 
00134     return reduce_nonzeros(v.begin(), v.end(), f_transpose(op), z);
00135 }
00136 
00137 /*************************************************************************************************/
00138 
00139 } // namespace adobe
00140 
00141 /*************************************************************************************************/
00142 
00143 #endif
00144 
00145 /*************************************************************************************************/

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