Segmented inclusive_scan and exclusive_scan implementation - #2287

We had a long discussion about this today and my concern is that the first scan phase is done by each partition, but then the whold scan result is returned to the root partition where the merge/updte steps are performed and the final result vector is held on the root partition.

The reason for this was to do with iterators.

It seem that if the algorithm is called with a partitioned_vector as input, and a partitioned_vector as output (or in place), then those iterators are already present on the relevant partitions and the solution presented here is only useful if the output/dest iterator is actually a normal vector - and not a partitioned one.

@hkaiser - can you add a few lines to explain how to ensure that the merge/update phases will happen on the locality/partition that owns it, rather than back on the root.

can you add a few lines to explain how to ensure that the merge/update phases will happen on the locality/partition that owns it, rather than back on the root.

There is an example demonstrating how to work with the local parts of a partitioned vector only: https://github.com/STEllAR-GROUP/hpx/blob/master/examples/quickstart/partitioned_vector_spmd_foreach.cpp

• Added optimization to use locality of data if available
• In-place usage of the scan possible
• Changed tests so that changes are tested
• Also optimized tests so that less time is wasted doing setup and verification

• Refactoring of code in preparation for exclusive scan
• Code can be reviewed

• Added some comments in code
• Added exclusive scan with tests to PR

• Fixed comparison of msb to locality id
• Invocation of std::distance only if ids are the same
• Passed down init by const&
• Capturing of op done by value

• Pass localities via parameter in the tests