//
// This file is part of MorphoGraphX - http://www.MorphoGraphX.org
// Copyright (C) 2012-2015 Richard S. Smith and collaborators.
//
// If you use MorphoGraphX in your work, please cite:
//   http://dx.doi.org/10.7554/eLife.05864
//
// MorphoGraphX is free software, and is licensed under under the terms of the 
// GNU General (GPL) Public License version 2.0, http://www.gnu.org/licenses.
// 
#ifndef GRAPH_UTILS_HPP
#define GRAPH_UTILS_HPP

#include <Config.hpp>
#include <Misc.hpp>
#include <Subdivide.hpp>
#include <Attributes.hpp>

namespace mgx
{
  typedef std::pair<int, int> IntInt;
  typedef std::pair<IntInt, double> IntIntDouPair;
  typedef std::vector<Triangle> triVector;

  /**
   *  Subdivide triangle with a propagating bisection that gives good triangles
   *
   * \param S Graph to subdivide
   * \param v1 First vertex of the triangle to divide
   * \param v2 Second vertex of the triangle to divide
   * \param v3 Third vertex of the triangle to divide
   * \param selected If true, new vertices will be selected
   * \param vs If non-NULL, vertices inserted are appended
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool subdivideBisect(vvGraph &S, const vertex &v1, const vertex &v2, 
                                      const vertex &v3, VtxVec* vs = 0, Subdivide *sDiv = 0);

  /**
   * Splice the neighborhood of b into a (so we can delete b)
   *
   * \param S Graph to splice
   * \param a vertex whose neighborhood will change 
   * \param b vertex whose neighborhood will be added to a
   * \param sDiv subdivision object to propagate attributes
   *
   * \ingroup GraphUtils
   */
  template<typename GraphT> 
  bool spliceNhbs(GraphT &S, typename GraphT::vertex_t a, typename GraphT::vertex_t b)
  { 
    typename GraphT::vertex_t n = S.nextTo(b, a);
    typename GraphT::vertex_t pv = b;

    if(!S.edge(a,b) or !S.edge(b,a))
      return false;

    while(n != a) {
      if(!S.edge(a, n)) {
        S.spliceAfter(a, pv, n);
        S.spliceAfter(n, b, a);
      }
      pv = n;
      n = S.nextTo(b, n);
    }
    return true;
  }

  /**
   * Return the label for a triangle
   *
   * \param v1 vertices of the triangle
   * \param v2
   * \param v3
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT int getLabel(const vertex &v1, const vertex &v2, const vertex &v3);

  /**
   * Count labels for each vertex in the graph
   *
   * \param S Graph to count labels
   * \param labCount Map of vertex to label count
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool getLabelCount(const vvGraph &S, VtxIntMap &labCount);

  /**
   * Split an edge in the S graph
   *
   * \param S Graph with edge to split
   * \param a first vertex on edge to split
   * \param b second vertex on edge to split
   * \param sDiv subdivision object to propagate attributes
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool splitEdge(vvGraph &S, vertex v1, vertex v2, Subdivide *sDiv = 0);

  /**
   * Merge vertices, returns number of vertices deleted
   *
   * \param S Graph to subdivide
   * \param vs vector of vertices to merge
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT int mergeVertices(vvGraph &S, const VtxVec &vs);

  /**
   * Check for unlabeled vertices, border triangles and islands of label in preparation to make a cell mesh
   *
   * \param S Graph to check
   * \param select Select affected vertices
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool checkBorderTris(const vvGraph &S, bool select = true);

  /**
   * Check for unlabeled vertices, border triangles and islands of label in preparation to make a cell mesh
   *
   * \param S Graph to check
   * \param V Vector of cell centers to delete
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool deleteCells(vvGraph &S, const VtxVec &V);

  /**
   * Check for border triangles with all labels -1 and merge their vertices together
   *
   * \param S Graph to check
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT int fixBorderTris(vvGraph &S);

  /**
   * Convert a normal (MGXM) mesh to a cell (MGXC) mesh
   *
   * \param srcS Source graph
   * \param S destination graph
   * \param wallMax Distance to use for keeping points on walls
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool mgxmToMgxc(const vvGraph &srcS, vvGraph &S, double wallMax = 0);

  /**
   * Mark the cells and tissue margin vertices.
   *
   * \param M Vertices to mark
   * \param S Graph to mark
   * \param remborders If true, all vertices with -1 as label and not at the
   * border between cells will be marked as 0.
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void markMargins(vvGraph &M, vvGraph &S, bool remborders = true);

  /**
   * Mark the cells and tissue margin vertices.
   *
   * \param S vvGraph to mark
   * \param remborders If true, all vertices with -1 as label and not at the
   * border between cells will be marked as 0.
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void markMargins(vvGraph &S, bool remborders = true);

  /**
   * Mark the cells and tissue margin vertices.
   *
   * \param S vvGraph to mark
   * \param v Vertex to mark
   * \param remborders If true, all vertices with -1 as label and not at the
   * border between cells will be marked as 0.
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void markMargin(vvGraph &S, vertex v, bool remborders = true);

  /**
   * Set the normals in a graph
   *
   * \param S vvGraph to set normal on
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT int setNormals(const vvGraph &S);

  /**
   * Correct MGXC normals (happens for non-star shaped cells)
   *
   * \param S vvGraph to set normal on
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void correctNormals(vvGraph &S);

  /**
   * Set the normal in a single vertex
   *
   * \param S vvGraph to set normal on
   * \param v vertex to set
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool setNormal(const vvGraph &S, const vertex &v);

  /**
   * Set the normal in a single vertex
   *
   * \param S vvGraph to set normal on
   * \param v vertex to set
   * \param nrml calculated normal
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool calcNormal(const vvGraph &S, const vertex &v, Point3d &nrml);


  /**
   * calculate properties of the neighborhood of a vvGraph
   * such as: cell wall area, shared wall areas, nr of cells of a vertex and individual wall labels
   *
   * \param S vvGraph
   * \param tolerance max dis to treat vtxs as the same
   * \param info output information
   *
   */
  typedef std::map<Point3i, std::set<int> > Point3iIntSetMap;
  typedef std::pair<Point3i, std::set<int> > Point3iIntSetPair;

  // object to return output information of neighborhoodGraph
  // currently used by cellmaker (label walls) and cellatlas (wall areas)
  struct NhbdGraphInfo{

    // cell label -> wall area of cell
    std::map<int,double> cellWallArea;

    // cell label -> wall area of cell that is not shared with other cells
    std::map<int,double> outsideWallArea;

    // cell label 1, cell label 2 -> shared wall area between the cells
    std::map<IntInt, double> sharedWallArea;

    // cell label 1, cell label 2 -> set of tri pairs that are identical
    std::map<IntInt, std::set<std::pair<Triangle,Triangle> > > sharedTris;

    // vertex -> unique wall label 
    std::map<vertex, int> vtxNewLabelMap;
    // vertex -> number of cells this vtx belongs to
    std::map<vertex, int> vtxCellCounterMap;

    // map from two labels to their wall label (0 for second label if outside)
    std::map<IntInt, int> allWalls;
  };
  mgx_EXPORT bool neighborhoodGraph(const vvGraph& S, double tolerance, NhbdGraphInfo& info, bool throwError = true);

  /**
   * return ALL labels of a vvGraph
   * originally in CellAtlas, now also used in other AddOns
   *
   * \param S vvGraph
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT std::vector<int> findAllLabels(const vvGraph& S);
  mgx_EXPORT std::set<int> findAllLabelsSet(const vvGraph& S);

  /**
   * return ALL labels of selected vertices of a vvGraph
   * originally in CellAtlas, now also used in other AddOns
   *
   * \param S vvGraph
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT std::set<int> findAllSelectedLabels(const vvGraph& S);


  /**
   * creates a wall map with the neighboring cells as key (pair) and the wall length as value
   *
   * \param S vvGraph
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void neighborhood2D(vvGraph& S, std::map<IntInt, double>& neighMap, QString weightType = "", bool ignoreOutside = true);
  mgx_EXPORT vertex nearestVertexOnMesh(const Point3d& targetPoint, const vvGraph& S);
  mgx_EXPORT Point3d nearestPointOnMesh(const Point3d& targetPoint, const vvGraph& S);



  // dijkstra on vvGraph with selected cells
  mgx_EXPORT std::map<int, double> dijkstra
  (vvGraph& S, std::map<IntInt, double>& wallAreas, std::set<int>& selectedCells,
   bool equalWeights, double cutOffDistance, double wallThreshold);

  // dijkstra with selected cells
  mgx_EXPORT std::map<int, double> dijkstra
  (std::set<int>& allCellLabels, std::map<IntInt, double>& wallAreas, std::set<int>& selectedCells,
   bool equalWeights, double cutOffDistance, double wallThreshold);

  // dijkstra with initial values
  mgx_EXPORT std::map<int, double> dijkstra
  (std::set<int>& allCellLabels, std::map<IntInt, double>& wallAreas, std::map<int, double>& initialCells,
   bool equalWeights, double cutOffDistance, double wallThreshold);

  mgx_EXPORT std::set<int> aStar
  (std::vector<int>& uniqueLabels, std::map<int, Point3d>& cellCentroids, std::map<IntInt, double>& wallAreas,
   int label1, int label2, double wallThreshold, bool equalWeights);





  /**
   * shoots rays from the cell centroid along a direction and checks if it hits any of the cell triangles
   * too avoid shooting through the edge between triangles the centroid point is varied slightly if nothing is hit
   *
   * returns true if a triangle got hit and writes the intersection point
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT bool findIntersectPoint(Point3d coordCellCentroid, Point3d& dirVec, std::vector<Triangle>& cellTriangles, int& stopCounter, Point3d& intersectP);

  /**
   * estimates the size of the cell in a given direction by shooting two rays in a specified direction and its opposite
   *
   * returns the cell size
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT double estimateCellLength(int currentLabel, Point3d coordCellCentroid, Point3d& dirVec, triVector& cellTriangles);

  
  /**
   * goes through all triangles of the vvGraph and builds up a map from label to triangle vector
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT void generateLabelTriangleMap(const vvGraph& S, std::map<int, triVector>& cellTriangles);

  /**
   * goes through all vertices of the vvGraph and builds up a map from label to vertex vector
   *
   * \ingroup GraphUtils
   */
  mgx_EXPORT std::map<int, std::vector<vertex> > generateLabelVertexMap(const vvGraph& S);

   // return the border vtxs of a 2D cell
   mgx_EXPORT void findBorderVerticesOfCell(vvGraph& S, int cellLabel, std::set<vertex>& verticesCell, std::vector<vertex>& borderVerticesOrdered);

   mgx_EXPORT void findBorderVerticesOfCellsCombined(vvGraph& S, std::set<int> cellLabels, std::set<vertex>& verticesCells, std::vector<vertex>& borderVerticesOrdered);

   mgx_EXPORT Point3i triIndex(Point3i t);
   mgx_EXPORT int vIndex(const Point3d &pos, Point3dIntMap &vMap, float tolerance);

   // used for circular histogram processes
   mgx_EXPORT int getKeyOfMaxValue(const std::map<int, double>& mapToTest);
   mgx_EXPORT std::map<int,int> shiftMap(std::map<int, double>& mapToShift, int shift);

}
#endif
