tlx
exclusive_scan.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/algorithm/exclusive_scan.hpp
3  *
4  * Part of tlx - http://panthema.net/tlx
5  *
6  * Copyright (C) 2018 Michael Axtmann <michael.axtmann@kit.edu>
7  *
8  * All rights reserved. Published under the Boost Software License, Version 1.0
9  ******************************************************************************/
10 
11 #ifndef TLX_ALGORITHM_EXCLUSIVE_SCAN_HEADER
12 #define TLX_ALGORITHM_EXCLUSIVE_SCAN_HEADER
13 
14 #include <functional>
15 #include <iterator>
16 
17 namespace tlx {
18 
19 //! \addtogroup tlx_algorithm
20 //! \{
21 
22 /*!
23  * Computes an exclusive prefix sum operation using binary_op the range [first,
24  * last), using init as the initial value, and writes the results to the range
25  * beginning at result. The term "exclusive" means that the i-th input element
26  * is not included in the i-th sum.
27  */
28 template <typename InputIterator, typename OutputIterator,
29  typename T, typename BinaryOperation = std::plus<T> >
30 OutputIterator exclusive_scan(InputIterator first, InputIterator last,
31  OutputIterator result, T init,
32  BinaryOperation binary_op = BinaryOperation()) {
33  *result++ = init;
34  if (first != last) {
35  typename std::iterator_traits<InputIterator>::value_type value =
36  binary_op(init, *first);
37  *result = value;
38  while (++first != last) {
39  value = binary_op(value, *first);
40  *++result = value;
41  }
42  ++result;
43  }
44  return result;
45 }
46 
47 //! \}
48 
49 } // namespace tlx
50 
51 #endif // !TLX_ALGORITHM_EXCLUSIVE_SCAN_HEADER
52 
53 /******************************************************************************/
OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op=BinaryOperation())
Computes an exclusive prefix sum operation using binary_op the range [first, last), using init as the initial value, and writes the results to the range beginning at result.