#include <algorithm>
#include <execution>
#include <iostream>
#include <string_view>
#include <tuple>
#include <vector>

// Based on examples/weld_vertices.cu from the NVIDIA/Thrust repository on
// github.com

/*
 * This example "welds" triangle vertices together by taking as
 * input "triangle soup" and eliminating redundant vertex positions
 * and shared edges.  A connected mesh is the result.
 *
 *
 * Input: 9 vertices representing a mesh with 3 triangles
 *
 *  Mesh              Vertices
 *    ------           (2)      (5)--(4)    (8)
 *    | \ 2| \          | \       \   |      | \
 *    |  \ |  \   <->   |  \       \  |      |  \
 *    | 0 \| 1 \        |   \       \ |      |   \
 *    -----------      (0)--(1)      (3)    (6)--(7)
 *
 *   (vertex 1 equals vertex 3, vertex 2 equals vertex 5, ...)
 *
 * Output: mesh representation with 5 vertices and 9 indices
 *
 *  Vertices            Indices
 *   (1)--(3)            [(0,2,1),
 *    | \  | \            (2,3,1),
 *    |  \ |  \           (2,4,3)]
 *    |   \|   \
 *   (0)--(2)--(4)
 */

// define a 2d float vector
typedef std::tuple<float, float> vec2;
constexpr auto exec = std::execution::par_unseq;

void print(std::string_view desc, std::vector<vec2> const &vertices) {
    std::cout << desc << '\n';
    for (size_t i = 0; i < vertices.size(); ++i) {
        vec2 v = vertices[i];
        std::cout << " vertices[" << i << "] = (" << std::get<0>(v) << ','
                  << std::get<1>(v) << ')' << std::endl;
    }
    std::cout << '\n';
}

int main(void) {
    // allocate memory for input mesh representation
    std::vector<vec2> input(9);

    input[0] = vec2(0, 0);  // First Triangle
    input[1] = vec2(1, 0);
    input[2] = vec2(0, 1);
    input[3] = vec2(1, 0);  // Second Triangle
    input[4] = vec2(0, 1);
    input[5] = vec2(1, 1);
    input[6] = vec2(1, 1);  // Third Triangle
    input[7] = vec2(2, 0);
    input[8] = vec2(1, 0);

    // allocate space for output mesh representation
    std::vector<vec2> vertices = input;
    std::vector<int> indices(input.size());

    print("Before sort", vertices);

    // sort vertices to bring duplicates together
    std::sort(exec, vertices.begin(), vertices.end());

    print("After sort", vertices);

    // find unique vertices and erase redundancies
    vertices.erase(std::unique(exec, vertices.begin(), vertices.end()),
                   vertices.end());

    print("After erasing duplicates", vertices);

    // find index of each input vertex in the list of unique vertices

    // As the STL has no version of Thrusts lower_bound algorithm working with
    // multiple inputs/outputs, it had to be constructed using std::transform
    std::transform(exec, input.cbegin(), input.cend(), indices.begin(),
                   [vertices_b = vertices.cbegin(),
                    vertices_e = vertices.cend()](vec2 const &vertex) {
                       auto const it =
                           std::lower_bound(vertices_b, vertices_e, vertex);
                       return static_cast<int>(std::distance(vertices_b, it));
                   });

    // print output mesh representation
    std::cout << "Output Representation" << std::endl;
    for (size_t i = 0; i < indices.size(); ++i) {
        std::cout << " indices[" << i << "] = " << indices[i] << std::endl;
    }

    return 0;
}