// This file is part of libigl, a simple c++ geometry processing library.
// 
// Copyright (C) 2016 Alec Jacobson <alecjacobson@gmail.com>
// 
// This Source Code Form is subject to the terms of the Mozilla Public License 
// v. 2.0. If a copy of the MPL was not distributed with this file, You can 
// obtain one at http://mozilla.org/MPL/2.0/.
#include "extract_manifold_patches.h"
#include "unique_edge_map.h"
#include <cassert>
#include <limits>
#include <queue>

template<
  typename DerivedF,
  typename DerivedEMAP,
  typename uE2EType,
  typename DerivedP>
IGL_INLINE size_t igl::extract_manifold_patches(
  const Eigen::PlainObjectBase<DerivedF>& F,
  const Eigen::PlainObjectBase<DerivedEMAP>& EMAP,
  const std::vector<std::vector<uE2EType> >& uE2E,
  Eigen::PlainObjectBase<DerivedP>& P)
{
    assert(F.cols() == 3);
    const size_t num_faces = F.rows();

    auto edge_index_to_face_index = [&](size_t ei) { return ei % num_faces; };
    auto face_and_corner_index_to_edge_index = [&](size_t fi, size_t ci) {
        return ci*num_faces + fi;
    };
    auto is_manifold_edge = [&](size_t fi, size_t ci) -> bool {
        const size_t ei = face_and_corner_index_to_edge_index(fi, ci);
        return uE2E[EMAP(ei, 0)].size() == 2;
    };
    auto get_adj_face_index = [&](size_t fi, size_t ci) -> size_t {
        const size_t ei = face_and_corner_index_to_edge_index(fi, ci);
        const auto& adj_faces = uE2E[EMAP(ei, 0)];
        assert(adj_faces.size() == 2);
        if (adj_faces[0] == ei) {
            return edge_index_to_face_index(adj_faces[1]);
        } else {
            assert(adj_faces[1] == ei);
            return edge_index_to_face_index(adj_faces[0]);
        }
    };

    typedef typename DerivedP::Scalar Scalar;
    const Scalar INVALID = std::numeric_limits<Scalar>::max();
    P.resize(num_faces,1);
    P.setConstant(INVALID);
    size_t num_patches = 0;
    for (size_t i=0; i<num_faces; i++) {
        if (P(i,0) != INVALID) continue;

        std::queue<size_t> Q;
        Q.push(i);
        P(i,0) = num_patches;
        while (!Q.empty()) {
            const size_t fid = Q.front();
            Q.pop();
            for (size_t j=0; j<3; j++) {
                if (is_manifold_edge(fid, j)) {
                    const size_t adj_fid = get_adj_face_index(fid, j);
                    if (P(adj_fid,0) == INVALID) {
                        Q.push(adj_fid);
                        P(adj_fid,0) = num_patches;
                    }
                }
            }
        }
        num_patches++;
    }
    assert((P.array() != INVALID).all());

    return num_patches;
}

template<
  typename DerivedF,
  typename DerivedP>
IGL_INLINE size_t igl::extract_manifold_patches(
  const Eigen::PlainObjectBase<DerivedF>& F,
  Eigen::PlainObjectBase<DerivedP>& P)
{
  Eigen::MatrixXi E, uE;
  Eigen::VectorXi EMAP;
  std::vector<std::vector<size_t> > uE2E;
  igl::unique_edge_map(F, E, uE, EMAP, uE2E);
  return igl::extract_manifold_patches(F, EMAP, uE2E, P);
}

#ifdef IGL_STATIC_LIBRARY
// Explicit template instantiation
// generated by autoexplicit.sh
template unsigned long igl::extract_manifold_patches<Eigen::Matrix<int, -1, -1, 0, -1, -1>,   Eigen::Matrix<int, -1, 1, 0, -1, 1> >(Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&);
template size_t igl::extract_manifold_patches<Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, 1, 0, -1, 1>, unsigned long, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&);
template unsigned long igl::extract_manifold_patches<Eigen::Matrix<int, -1, 3, 1, -1, 3>, Eigen::Matrix<int, -1, 1, 0, -1, 1>, unsigned long, Eigen::Matrix<int, -1, 1, 0, -1, 1> >(Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 3, 1, -1, 3> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> >&); 
#ifdef WIN32
template unsigned __int64 igl::extract_manifold_patches<class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, unsigned __int64, class Eigen::Matrix<int, -1, 1, 0, -1, 1>>(class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class std::vector<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>, class std::allocator<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> &);
template unsigned __int64 igl::extract_manifold_patches<class Eigen::Matrix<int, -1, 3, 1, -1, 3>, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, unsigned __int64, class Eigen::Matrix<int, -1, 1, 0, -1, 1>>(class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 3, 1, -1, 3>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class std::vector<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>, class std::allocator<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> &);
#endif
#endif