 #include <thrust/host_vector.h>
+#include <thrust/device_vector.h>
 #include <thrust/generate.h>
 #include <thrust/sequence.h>
 #include <thrust/sort.h>


    // Note: keys have not been modified
    // Note: permutation now maps unsorted keys to sorted order
    
    std::cout << "Sorted Keys" << std::endl;
    for(size_t i = 0; i < N; i++)
    {
        // p is the index in the *unsorted* arrays of the i-th sorted element
        int p = permutation[i];
        std::cout << "(" << upper[p] << "," << middle[p] << "," << lower[p] << ")" << std::endl;
    }

    return 0;
}

}


template <typename KeyVector, typename PermutationVector>
void apply_permutation(KeyVector& keys, PermutationVector& permutation)
{
    // copy keys to temporary vector
    KeyVector temp(keys.begin(), keys.end());

    // permute the keys
    thrust::gather(keys.begin(), keys.end(), permutation.begin(), temp.begin());
}


thrust::host_vector<int> random_vector(size_t N)
{
    thrust::host_vector<int> vec(N);

    for (size_t i = 0; i < N; i++)
        vec[i] = rand() % 10;

    return vec;
}


