//
// Copyright (c) 2017 Rasmus Barringer
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//

#ifndef ADJACENCY_H
#define ADJACENCY_H

#include <stdint.h>

// Computes adjacency information from an index buffer (mapping triangle edges to their neighbor).
// The adjacency buffer must be able to hold index_count elements.
void compute_adjacency(const uint32_t* indices, unsigned index_count, uint32_t* adjacency);

#ifdef ADJACENCY_IMPLEMENTATION

#include <stdlib.h>
#include <string.h>
#include <algorithm>

namespace {
    struct AdjacencyEdge {
        uint64_t edge_id;
        uint32_t triangle_edge;
    };

    static inline bool operator < (AdjacencyEdge a, AdjacencyEdge b) {
        return a.edge_id < b.edge_id;
    }

    static inline uint64_t adjacency_edge_id(unsigned v0, unsigned v1) {
        return v0 > v1 ? v0 | ((uint64_t)v1 << 32) : v1 | ((uint64_t)v0 << 32);
    }
}

void compute_adjacency(const uint32_t* indices, unsigned index_count, uint32_t* adjacency) {
    memset(adjacency, 0xff, sizeof(adjacency[0])*index_count);

    AdjacencyEdge* edges = (AdjacencyEdge*)malloc(sizeof(AdjacencyEdge)*index_count);

    for (unsigned i = 0; i < index_count; i += 3) {
        unsigned v0 = indices[i+0];
        unsigned v1 = indices[i+1];
        unsigned v2 = indices[i+2];

        AdjacencyEdge edge0 = { adjacency_edge_id(v1, v2), i+0 };
        AdjacencyEdge edge1 = { adjacency_edge_id(v2, v0), i+1 };
        AdjacencyEdge edge2 = { adjacency_edge_id(v0, v1), i+2 };

        edges[i+0] = edge0;
        edges[i+1] = edge1;
        edges[i+2] = edge2;
    }

    std::sort(edges, edges + index_count);

    for (unsigned i = 0; i+1 < index_count; ++i) {
        if (edges[i+0].edge_id == edges[i+1].edge_id) {
            unsigned e0 = edges[i+0].triangle_edge;
            unsigned e1 = edges[i+1].triangle_edge;

            adjacency[e0] = e1;
            adjacency[e1] = e0;

            ++i;
        }
    }

    free(edges);
}

#endif

#endif