// sudo apt-get update
// sudo apt-get install libcgal-dev build-essential
// (there may be other libraries needed for boot and gmp and mpfr, but I had those installed already)
// g++ -O3 -std=c++17 main.cpp -o svg_skeleton -lCGAL -lboost_thread -lboost_system -lgmp -lmpfr

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <memory>
#include <algorithm>
#include <cstring>
// CGAL Includes for Straight Skeleton and Polygon Validation
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point2;
typedef CGAL::Polygon_2<Kernel> Polygon2;
typedef CGAL::Polygon_with_holes_2<Kernel> PolygonWithHoles2;
typedef CGAL::Straight_skeleton_2<Kernel> StraightSkeleton;
// ============================================================================
// C-Compatible Structural Declarations & Data Types
// ============================================================================
struct Vertex {
  double x, y;
};
struct Contour {
  std::vector<Vertex> vertices;
};
struct SVGPolygonData {
  std::vector<Contour> contours;
  std::string viewBox;
  std::string width;
  std::string height;
};
struct SkeletonSegment {
  Vertex p1;
  Vertex p2;
};
// ============================================================================
// SVG Parsing Component (C-style string manipulation)
// ============================================================================
void trim(std::string& s) {
  s.erase(s.begin(), std::find_if(s.begin(), s.end(), [](unsigned char ch) { return !std::isspace(ch); }));
  s.erase(std::find_if(s.rbegin(), s.rend(), [](unsigned char ch) { return !std::isspace(ch); }).base(), s.end());
}
std::vector<Vertex> parsePointsString(const std::string& pointsStr) {
  std::vector<Vertex> vertices;
  std::stringstream ss(pointsStr);
  double x, y;
  char comma;
  while (ss >> x) {
    if (ss >> comma && comma == ',') {
      if (ss >> y) {
        vertices.push_back({x, y});
      }
    } else {
      // Support space-separated coordinates if comma is omitted
      ss.putback(comma);
      if (ss >> y) {
        vertices.push_back({x, y});
      }
    }
  }
  return vertices;
}

void parsePathD(const std::string& dAttr, std::vector<Contour>& contours) {
  // Sanitize commas out of the path string entirely by turning them into spaces
  std::string sanitized = dAttr;
  std::replace(sanitized.begin(), sanitized.end(), ',', ' ');

  std::stringstream ss(sanitized);
  std::string token;
  char cmd = ' ';
  double x = 0, y = 0;
  Contour currentContour;

  while (ss >> token) {
    // Check if the token is a command letter
    if (token.size() == 1 && std::isalpha(token[0])) {
      cmd = token[0];
            
      if (cmd == 'Z' || cmd == 'z') {
        if (!currentContour.vertices.empty()) {
          contours.push_back(currentContour);
          currentContour.vertices.clear();
        }
        cmd = ' '; // Reset active command state
      }
      continue;
    }

    // If we have numbers but no active command state, skip them
    if (cmd == ' ') continue;

    // Process coordinates based on the active command state
    if (cmd == 'M' || cmd == 'm') {
      if (!currentContour.vertices.empty()) {
        contours.push_back(currentContour);
        currentContour.vertices.clear();
      }
      double nx = std::stod(token);
      double ny;
      if (ss >> ny) {
        if (cmd == 'm' && !contours.empty()) {
          x += nx; y += ny;
        } else {
          x = nx; y = ny;
        }
        currentContour.vertices.push_back({x, y});
        // Implicit subsequent coordinate pairs are treated as line segments
        cmd = (cmd == 'M') ? 'L' : 'l';
      }
    } 
    else if (cmd == 'L' || cmd == 'l') {
      double nx = std::stod(token);
      double ny;
      if (ss >> ny) {
        if (cmd == 'l') {
          x += nx; y += ny;
        } else {
          x = nx; y = ny;
        }
        currentContour.vertices.push_back({x, y});
      }
    }
    else if (cmd == 'H' || cmd == 'h') {
      double nx = std::stod(token);
      if (cmd == 'h') x += nx; else x = nx;
      currentContour.vertices.push_back({x, y});
    }
    else if (cmd == 'V' || cmd == 'v') {
      double ny = std::stod(token);
      if (cmd == 'v') y += ny; else y = ny;
      currentContour.vertices.push_back({x, y});
    }
    else {
      std::cerr << "Error: Unsupported SVG token or curve command '" << cmd << "' detected.\n";
      exit(1);
    }
  }

  if (!currentContour.vertices.empty()) {
    contours.push_back(currentContour);
  }
}

SVGPolygonData loadSVG(const std::string& filename) {
  std::ifstream file(filename);
  if (!file.is_open()) {
    std::cerr << "Error: Could not open input file " << filename << "\n";
    exit(1);
  }

  // Read the ENTIRE file into a single memory block to handle multi-line paths safely
  std::stringstream buffer;
  buffer << file.rdbuf();
  std::string fileContent = buffer.str();

  SVGPolygonData data;

  // Quick extraction of global attributes
  size_t svgPos = fileContent.find("<svg");
  if (svgPos != std::string::npos) {
    size_t svgEnd = fileContent.find(">", svgPos);
    std::string svgTag = fileContent.substr(svgPos, svgEnd - svgPos);
        
    size_t vbPos = svgTag.find("viewBox=\"");
    if (vbPos != std::string::npos) {
      size_t vbEnd = svgTag.find("\"", vbPos + 9);
      data.viewBox = svgTag.substr(vbPos + 9, vbEnd - (vbPos + 9));
    }
    size_t wPos = svgTag.find("width=\"");
    if (wPos != std::string::npos) {
      size_t wEnd = svgTag.find("\"", wPos + 7);
      data.width = svgTag.substr(wPos + 7, wEnd - (wPos + 7));
    }
    size_t hPos = svgTag.find("height=\"");
    if (hPos != std::string::npos) {
      size_t hEnd = svgTag.find("\"", hPos + 8);
      data.height = svgTag.substr(hPos + 8, hEnd - (hPos + 8));
    }
  }

  if (fileContent.find("transform=") != std::string::npos) {
    std::cerr << "Error: Core transforms detected. Please flatten your SVG file first.\n";
    exit(1);
  }

  // Process primitive attributes out of the full content block
  size_t pos = 0;
  while (pos < fileContent.size()) {
    size_t pathPos = fileContent.find("<path", pos);
    size_t polyPos = fileContent.find("<polygon", pos);
    size_t linePos = fileContent.find("<polyline", pos);

    size_t nextPos = std::min({pathPos, polyPos, linePos});
    if (nextPos == std::string::npos) break;

    size_t tagEnd = fileContent.find(">", nextPos);
    if (tagEnd == std::string::npos) break;

    std::string elementTag = fileContent.substr(nextPos, tagEnd - nextPos + 1);

    if (nextPos == pathPos) {
      size_t dPos = elementTag.find("d=\"");
      if (dPos != std::string::npos) {
        size_t dEnd = elementTag.find("\"", dPos + 3);
        std::string dStr = elementTag.substr(dPos + 3, dEnd - (dPos + 3));
        parsePathD(dStr, data.contours);
      }
    } else { // polygon or polyline
      size_t pPos = elementTag.find("points=\"");
      if (pPos != std::string::npos) {
        size_t pEnd = elementTag.find("\"", pPos + 8);
        std::string ptsStr = elementTag.substr(pPos + 8, pEnd - (pPos + 8));
        std::vector<Vertex> v = parsePointsString(ptsStr);
        if (!v.empty()) data.contours.push_back({v});
      }
    }
    pos = tagEnd + 1;
  }

  return data;
}


// ============================================================================
// Computational Geometry Backend (CGAL Validation & Straight Skeleton)
// ============================================================================
std::vector<SkeletonSegment> computeSkeleton(SVGPolygonData& data) {
  if (data.contours.empty()) {
    std::cerr << "Error: No valid polygonal contours found in input file.\n";
    exit(1);
  }

  std::vector<Polygon2> cgalContours;

  for (auto& contour : data.contours) {
    Polygon2 poly;
    for (const auto& v : contour.vertices) {
      poly.push_back(Point2(v.x, v.y));
    }

    // Clean trailing duplicate if polygon explicit closing duplicated head
    if (poly.size() > 1 && poly.vertex(0) == poly.vertex(poly.size() - 1)) {
      poly.erase(poly.vertices_end() - 1);
    }

    // Basic validation checks
    if (poly.size() < 3) {
      std::cerr << "Error: Degenerate contour contains less than 3 unique vertices.\n";
      exit(1);
    }
    if (!poly.is_simple()) {
      std::cerr << "Error: Self-intersecting or complex contour topology detected.\n";
      exit(1);
    }

    cgalContours.push_back(poly);
  }

  // Identify Outer Boundary vs Holes via area sizing and containment metrics
  // CGAL mandates Counter-Clockwise (CCW) for outer boundaries, Clockwise (CW) for holes.
  int outerIdx = -1;
  double maxArea = -1.0;

  for (size_t i = 0; i < cgalContours.size(); ++i) {
    double currentArea = std::abs(cgalContours[i].area());
    if (currentArea > maxArea) {
      maxArea = currentArea;
      outerIdx = i;
    }
  }

  Polygon2 outerPoly = cgalContours[outerIdx];
  if (outerPoly.is_clockwise_oriented()) {
    outerPoly.reverse_orientation();
  }

  PolygonWithHoles2 fullPolygon(outerPoly);

  for (size_t i = 0; i < cgalContours.size(); ++i) {
    if (static_cast<int>(i) == outerIdx) continue;

    Polygon2 hole = cgalContours[i];
    if (hole.is_counterclockwise_oriented()) {
      hole.reverse_orientation();
    }
    fullPolygon.add_hole(hole);
  }

  // Execute the Interior Straight Skeleton Calculation
  auto skeleton = CGAL::create_interior_straight_skeleton_2(fullPolygon);
  
  // Map internal halfedge records back to flat segment structs
  std::vector<SkeletonSegment> outputSegments;
  for (auto e = skeleton->halfedges_begin(); e != skeleton->halfedges_end(); ++e) {
    // Check if it's a skeleton edge (bisector) and handle the twin halfedge to prevent duplicates
    if (e->is_bisector() && &(*e) < &(*e->opposite())) {
      Vertex p1 = { e->opposite()->vertex()->point().x(), e->opposite()->vertex()->point().y() };
      Vertex p2 = { e->vertex()->point().x(), e->vertex()->point().y() };
      outputSegments.push_back({p1, p2});
    }
  }
  return outputSegments;
}
// ============================================================================
// SVG Generation & Output Writer
// ============================================================================

void writeSVG(const std::string& filename, const SVGPolygonData& originalData, 
              const std::vector<SkeletonSegment>& segments, bool overlayOriginal) {
  std::ofstream file(filename);
  if (!file.is_open()) {
    std::cerr << "Error: Could not open output file " << filename << "\n";
    exit(1);
  }

  // Write valid XML declaration and explicit global W3 Namespace
  file << "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n";
  file << "<svg xmlns=\"http://www.w3.org/2000/svg\"";

  // Fixed: Corrected scope variables from 'data' to 'originalData'
  if (!originalData.width.empty()) file << " width=\"" << originalData.width << "\"";
  if (!originalData.height.empty()) file << " height=\"" << originalData.height << "\"";
  if (!originalData.viewBox.empty()) file << " viewBox=\"" << originalData.viewBox << "\"";
  file << ">\n";

  
  // Optional background layout overlay for debugging purposes
  if (overlayOriginal) {
    file << " \n";
    for (const auto& contour : originalData.contours) {
      file << " <polygon points=\"";
      for (const auto& v : contour.vertices) {
        file << v.x << "," << v.y << " ";
      }
      file << "\" fill = \"#e0e0e0\" stroke = \"#999999\" stroke-width = \"1\" stroke-dasharray = \"4\" />\n";
    }
  }
  // Output calculated straight skeleton features
  file << " \n";
  file << " <g stroke=\"blue\" stroke-width=\"1.5\" stroke-linecap=\"round\">\n";
  for (const auto& seg : segments) {
    file << " <line x1=\"" << seg.p1.x << "\" y1=\"" << seg.p1.y << "\" x2 = \"" << seg.p2.x << "\" y2 = \"" << seg.p2.y << "\" />\n";
  }
  file << "  </g>\n";
  file << "</svg>\n";
}
// ============================================================================
// Execution Entry Point & CLI Interface
// ============================================================================
int main(int argc, char* argv[]) {
  bool overlay = false;
  std::string input;
  std::string output;
  
  if (argc < 3) {
    std::cerr << "Usage: " << argv[0] << " [--overlay] <input.svg> <output.svg>\n";
    return 1;
  }
  
  int argIdx = 1;
  if (std::strcmp(argv[argIdx], "--overlay") == 0) {
    overlay = true;
    argIdx++;
  }

  if (argc - argIdx < 2) {
    std::cerr << "Error: Missing input or output file paths.\n";
    return 1;
  }
  
  input = argv[argIdx];
  output = argv[argIdx + 1];
  
  // Execution Chain
  SVGPolygonData inputData = loadSVG(input);
  std::vector skeleton = computeSkeleton(inputData);
  writeSVG(output, inputData, skeleton, overlay);
  
  std::cout << "Success: Skeleton generated successfully via CGAL backend.\n";
  return 0;
}