Как получить картографический массив при сжатии с тягой

Question

Мне нужно знать, в какую позицию наносится каждый элемент, когда он компактен с тягой.

Например:

arr:  5 2 -1 3 -1 6 -1 7 
compacted: 5 2 3 6 7  --------------(remove all -1 element) 
map Arr: 0 1 -1 2 -1 3 -1 4 

Отображение массива, здесь я имею в виду массив, указывающий, какое положение, что каждый элемент перемещается к, извините, я не могу придумать лучшего названия, чтобы описать это, Надеюсь, я ясно прояснил ситуацию.

Компактный с тягой очень прост, но мне интересно, могу ли я получить этот массив отображения, пока упор уплотняется.

Answer 1

Следующая последовательность вызовов тяги может генерировать желаемый массив отображения.

Выход для примера:

compacted: 5 2 3 6 7 
map: 0 0 -1 0 -1 0 -1 0 
map: 0 0 -1 -1 -2 -2 -3 -3 
map: 0 1 1 2 2 3 3 4 
map: 0 1 -1 2 -1 3 -1 4 

---

#include <iostream> 
#include <string> 

#include <thrust/scan.h> 
#include <thrust/scatter.h> 
#include <thrust/remove.h> 
#include <thrust/iterator/counting_iterator.h> 
#include <thrust/iterator/constant_iterator.h> 

void print(const std::string& name, int* begin, int* end) 
{ 
    std::cout << name << ": "; 
    thrust::copy(begin, end, std::ostream_iterator<int>(std::cout, " ")); 
    std::cout <<std::endl; 
} 

struct is_marker 
{ 
    __host__ __device__ 
    bool operator()(const int x) const 
    { 
    return (x == -1); 
    } 
}; 

int main() 
{ 
    const int N = 8; 
    int arr[N] = {5,2,-1,3,-1,6,-1,7}; 

    int compacted[N] = {0}; 
    int* compacted_end = thrust::remove_copy(arr, arr+N, compacted, -1); 
    print("compacted", compacted, compacted_end); 

    int map[N] = {0}; 
    thrust::scatter_if(thrust::make_constant_iterator(-1), thrust::make_constant_iterator(-1)+N, thrust::make_counting_iterator(0), arr, map, is_marker()); 
    print("map", map, map+N); 

    thrust::inclusive_scan(map, map+N, map); 
    print("map", map, map+N); 

    thrust::transform(map, map+N, thrust::make_counting_iterator(0), map, thrust::plus<int>()); 
    print("map", map, map+N); 

    thrust::scatter_if(thrust::make_constant_iterator(-1), thrust::make_constant_iterator(-1)+N, thrust::make_counting_iterator(0), arr, map, is_marker()); 
    print("map", map, map+N); 

    return 0; 
}