;;; dag-draw-ascii-grid.el --- ASCII grid management for dag-draw -*- lexical-binding: t -*-

;; Copyright (C) 2024, 2025

;; Author: Generated by Claude
;; Keywords: internal

;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;;; Commentary:

;; ASCII Grid Rendering - GKNV Adaptation
;;
;; BOUNDED CONTEXT: ASCII Rendering Context
;; UPSTREAM CONTEXT: GKNV Algorithm Context (via Coordinate Transform Layer)
;; LAYER: Rendering Implementation
;; AUTHORITY: doc/implementation-decisions.md (D5.1-D5.8)
;;
;; ASCII Grid Rendering - GKNV Adaptation:
;;
;; This module adapts the GKNV graph drawing algorithm for ASCII character grid
;; output.  The GKNV paper describes graphical (PostScript) output, so this module
;; implements ASCII-specific decisions from doc/implementation-decisions.md.
;;
;; ASCII Decisions: D5.1-D5.8 (Character-grid specific)
;; Algorithm: Junction character algorithm with context analysis
;;
;; Key Requirements:
;; - Unicode box-drawing characters (D5.2)
;; - 5 junction types: start-port, end-port, corner, merge/split, cross (D5.4)
;; - Walk-based local analysis for correct junction selection (D5.4)
;; - Arrows at port boundary (D5.5)
;; - Coordinate scaling X and Y independently (D5.1)
;;
;; Baseline Status: ✅ Compliant with ASCII adaptation decisions
;;
;; Note: GKNV paper does not cover ASCII rendering.  This module implements
;; the ASCII-specific decisions documented in implementation-decisions.md
;; while maintaining GKNV algorithm correctness for the underlying layout.
;;
;; See doc/implementation-decisions.md (D5.1-D5.8) for ASCII decision rationale.

;;; Code:

(require 'ht)
(require 'dag-draw)
(require 'dag-draw-core)
(require 'dag-draw-coord-transform)
(require 'dag-draw-ascii-junctions)

;; dag-draw-point, dag-draw-point-create, dag-draw-point-x, dag-draw-point-y
;; are now defined in dag-draw.el

;;; Customization

;;; Dynamic Scale Calculation

(defun dag-draw--calculate-optimal-ascii-scale (graph target-width target-height)
  "Calculate optimal scale factor for converting world coordinates to ASCII grid.

GRAPH is a `dag-draw-graph' structure.
TARGET-WIDTH and TARGET-HEIGHT are integers
representing desired grid dimensions.

Analyzes graph complexity (node count, edge density, hierarchy depth) and
calculates a scale factor that balances resolution
with fitting in the ASCII area.
More complex graphs need smaller scale to fit in available space.

Following GKNV paper Section 1.2: coordinates should use '72 units per inch'
for high resolution, but ASCII has ~5 characters per inch, requiring dynamic
scaling based on graph complexity.

Returns a float representing the optimal scale factor."
  (let* ((node-count (dag-draw-node-count graph))
         (edge-count (dag-draw-edge-count graph))

         ;; Enhanced complexity analysis
         (node-size-factor (dag-draw--calculate-node-size-complexity graph))
         (edge-density-factor (dag-draw--calculate-edge-density-factor graph))
         (hierarchy-depth-factor (dag-draw--estimate-hierarchy-depth graph))

         ;; Combined complexity factor with weighted components
         (complexity-factor (+ (* node-count 0.15)
                              (* edge-count 0.08)
                              (* node-size-factor 0.1)
                              (* edge-density-factor 0.05)
                              (* hierarchy-depth-factor 0.02)))

         ;; Base scale calculation: balance between resolution and fitting
         ;; More complex graphs need smaller scale to fit in ASCII area
         (base-scale (/ 1.0 (max 1.0 (+ 1.5 complexity-factor))))

         ;; Adjust for target dimensions - larger ASCII area allows larger scale
         (dimension-factor (/ (+ target-width target-height) 200.0))
         (adjusted-scale (* base-scale dimension-factor))

         ;; Minimum scale to prevent coordinate collapse (GKNV aesthetic A2)
         (min-scale 0.02)

         ;; Maximum scale to maintain readability
         (max-scale 0.4))

    ;; Validate against coordinate collapse (GKNV aesthetic A2)
    (let ((validated-scale (max min-scale (min max-scale adjusted-scale))))
      (dag-draw--validate-scale-prevents-collapse graph validated-scale target-width target-height))))

(defun dag-draw--validate-scale-prevents-collapse (graph scale target-width target-height)
  "Validate that SCALE prevents coordinate collapse per GKNV aesthetic A2.

GRAPH is a `dag-draw-graph' structure.
SCALE is a float representing the current scale factor.
TARGET-WIDTH and TARGET-HEIGHT are integers representing grid dimensions.

Simulates grid positioning with current scale and checks if any two nodes
would collapse to the same grid position.  If collapse is detected, increases
scale slightly and recursively validates again.

Only validates when nodes have actual coordinates set (after GKNV layout).

Returns an adjusted scale factor (float) that ensures no two nodes collapse
to the same grid position."
  (if (or (= (dag-draw-node-count graph) 0)
          ;; Only validate if nodes have coordinates (after GKNV layout)
          (not (dag-draw--graph-has-positioned-nodes graph)))
      scale
    (let* ((nodes (ht-values (dag-draw-graph-nodes graph)))
           (positions (ht-create))
           (collapse-detected nil))

      ;; Simulate grid positioning with current scale
      (dolist (node nodes)
        (let* ((world-x (dag-draw-node-x-coord node))
               (world-y (dag-draw-node-y-coord node)))
          (when (and world-x world-y)  ; Only check nodes with coordinates
            (let* ((grid-x (round (* world-x scale)))
                   (grid-y (round (* world-y scale)))
                   (grid-pos (format "%d,%d" grid-x grid-y)))

              (if (ht-get positions grid-pos)
                  (setq collapse-detected t)
                (ht-set! positions grid-pos t))))))

      (if collapse-detected
          ;; Increase scale slightly to prevent collapse
          (let ((anti-collapse-scale (* scale 1.15))) ; Smaller increment
            (if (< anti-collapse-scale 0.4)
                ;; Recursively validate the adjusted scale
                (dag-draw--validate-scale-prevents-collapse graph anti-collapse-scale target-width target-height)
              ;; If we can't prevent collapse, return minimum viable scale
              0.02))
        ;; No collapse detected - scale is valid
        scale))))

(defun dag-draw--graph-has-positioned-nodes (graph)
  "Check if GRAPH has nodes with positioned coordinates after layout.

GRAPH is a `dag-draw-graph' structure.

Returns t if at least one node has both x-coord and y-coord set, nil otherwise."
  (let ((has-positioned nil))
    (ht-each (lambda (_node-id node)
               (when (and (dag-draw-node-x-coord node)
                         (dag-draw-node-y-coord node))
                 (setq has-positioned t)))
             (dag-draw-graph-nodes graph))
    has-positioned))

(defun dag-draw--calculate-node-size-complexity (graph)
  "Calculate complexity factor based on node size variations.

GRAPH is a `dag-draw-graph' structure.

Calculates average node size and size variance.  Graphs with larger or more
varied node sizes need smaller scale factors to fit properly.

Returns a float representing the normalized complexity factor."
  (if (= (dag-draw-node-count graph) 0)
      0.0
    (let* ((total-size 0)
           (size-variance 0)
           (nodes (ht-values (dag-draw-graph-nodes graph))))

      ;; Calculate average node size
      (dolist (node nodes)
        (setq total-size (+ total-size
                           (dag-draw-node-x-size node)
                           (dag-draw-node-y-size node))))

      (let ((avg-size (/ total-size (* 2.0 (length nodes)))))
        ;; Calculate size variance for complexity
        (dolist (node nodes)
          (let ((node-size (/ (+ (dag-draw-node-x-size node)
                                 (dag-draw-node-y-size node)) 2.0)))
            (setq size-variance (+ size-variance
                                  (expt (- node-size avg-size) 2)))))

        ;; Return normalized complexity factor
        (/ (sqrt (/ size-variance (length nodes))) 50.0)))))

(defun dag-draw--calculate-edge-density-factor (graph)
  "Calculate edge density complexity factor.

GRAPH is a `dag-draw-graph' structure.

Higher edge density relative to node count indicates more complex layout
requirements.  Calculates the ratio of actual edges to maximum possible edges.

Returns a float representing the scaled density factor."
  (let ((node-count (dag-draw-node-count graph)))
    (if (<= node-count 1)
        0.0
      (let* ((edge-count (dag-draw-edge-count graph))
             (max-possible-edges (* node-count (1- node-count)))
             (density (if (> max-possible-edges 0)
                         (/ (float edge-count) max-possible-edges)
                       0.0)))
        ;; Scale density to reasonable complexity factor
        (* density 2.0)))))

(defun dag-draw--estimate-hierarchy-depth (graph)
  "Estimate hierarchy depth for complexity calculation.

GRAPH is a `dag-draw-graph' structure.

Finds source nodes and calculates maximum depth reachable from each.
Deeper hierarchies may need different scaling considerations.

Returns a float representing the estimated maximum hierarchy depth."
  (if (= (dag-draw-node-count graph) 0)
      0.0
    (let ((source-nodes (dag-draw-get-source-nodes graph)))
      (if (null source-nodes)
          ;; No clear hierarchy (cycles or disconnected) - moderate complexity
          1.0
        ;; Simple depth estimation: count nodes at different distances from sources
        (let ((max-depth 0))
          (dolist (source source-nodes)
            (let ((depth (dag-draw--calculate-max-depth-from-node graph source)))
              (setq max-depth (max max-depth depth))))
          max-depth)))))

(defun dag-draw--calculate-max-depth-from-node (graph start-node)
  "Calculate maximum depth reachable from START-NODE in GRAPH.

GRAPH is a `dag-draw-graph' structure.
START-NODE is a symbol representing a node ID.

Performs depth-first search to find the maximum depth of any path
starting from START-NODE.

Returns an integer representing the maximum depth."
  (let ((visited (ht-create))
        (max-depth 0))
    (dag-draw--depth-first-search graph start-node visited 0
                                 (lambda (depth)
                                   (setq max-depth (max max-depth depth))))
    max-depth))

(defun dag-draw--depth-first-search (graph node visited current-depth callback)
  "Perform depth-first search from NODE, calling CALLBACK with depth.

GRAPH is a `dag-draw-graph' structure.
NODE is a symbol representing the current node ID.
VISITED is a hash table tracking visited nodes (modified in place).
CURRENT-DEPTH is an integer representing the current depth level.
CALLBACK is a function accepting one argument (depth) called for
each visited node."
  (unless (ht-get visited node)
    (ht-set! visited node t)
    (funcall callback current-depth)
    (let ((successors (dag-draw-get-successors graph node)))
      (dolist (successor successors)
        (dag-draw--depth-first-search graph successor visited (1+ current-depth) callback)))))

;;; ASCII Scaling Helper Functions

;; DELETED: Coordinate transformation functions - obsolete in ASCII-first architecture
;; - dag-draw--world-to-grid-coord
;; - dag-draw--grid-to-world-coord
;; - dag-draw--world-to-grid-size

(defun dag-draw--get-node-center-grid (node min-x min-y scale &optional graph)
  "Get node center coordinates in grid space for edge routing.

NODE is a `dag-draw-node' structure.
MIN-X and MIN-Y are numbers representing the minimum world coordinates.
SCALE is a float representing the coordinate scale factor.
GRAPH is an optional `dag-draw-graph' structure for adjusted position lookup.

Converts GKNV world coordinates to grid coordinates.  If GRAPH is provided and
contains adjusted positions for this node, uses those instead of
raw coordinates.

Returns a `dag-draw-point' structure with grid coordinates."
  (let* ((node-id (dag-draw-node-id node))
         ;; GKNV Pass 3 Authority: Only use algorithm-assigned coordinates
         ;; Section 4: "The third pass finds optimal coordinates for nodes"
         (gknv-x (dag-draw-node-x-coord node))
         (gknv-y (dag-draw-node-y-coord node))
         ;; Get adjusted coordinates from layout algorithm
         (adjusted-coords (and graph
                               (dag-draw-graph-adjusted-positions graph)
                               (ht-get (dag-draw-graph-adjusted-positions graph) node-id))))

    (if adjusted-coords
        ;; Use adjusted coordinates from GKNV layout algorithm
        (dag-draw-point-create
         :x (+ (nth 0 adjusted-coords) (/ (nth 2 adjusted-coords) 2.0))
         :y (+ (nth 1 adjusted-coords) (/ (nth 3 adjusted-coords) 2.0)))
      ;; Use GKNV Pass 3 coordinates - convert world coordinates to grid coordinates
      (let* ((world-x (or gknv-x 0))
             (world-y (or gknv-y 0))
             (grid-x (dag-draw--world-to-grid-coord world-x min-x scale))
             (grid-y (dag-draw--world-to-grid-coord world-y min-y scale)))
        (dag-draw-point-create :x grid-x :y grid-y)))))

;;; ASCII Coordinate Context Layer (moved to dag-draw-coord-transform.el)
;; All coordinate transformation functions have been extracted to dag-draw-coord-transform.el

;;; ASCII Grid Creation

(defun dag-draw--create-ascii-grid (width height)
  "Create empty ASCII grid of given WIDTH and HEIGHT.

WIDTH and HEIGHT are integers representing grid dimensions in characters.

Returns a 2D vector where each row is a vector of characters, all initialized
to space characters."
  (let ((grid (make-vector height nil)))
    (dotimes (y height)
      (aset grid y (make-vector width ?\s)))  ; Fill with spaces
    grid))

;;; Node Collision Detection

(defun dag-draw--would-violate-hierarchy (graph node-id proposed-y current-drawn-nodes)
  "Check if moving NODE-ID to PROPOSED-Y would violate hierarchical ordering.

GRAPH is a `dag-draw-graph' structure.
NODE-ID is a symbol representing the node to check.
PROPOSED-Y is an integer representing the proposed grid Y coordinate.
CURRENT-DRAWN-NODES is a list of already-positioned nodes, each element is
a list (node-id x y width height).

Checks if the proposed position would violate rank ordering: lower-rank nodes
should appear above (smaller Y) higher-rank nodes.

Returns t if hierarchy would be violated, nil otherwise."
  (when graph
    (let ((node (dag-draw-get-node graph node-id))
          (violates-hierarchy nil))
      (when node
        (let ((node-rank (or (dag-draw-node-rank node) 0)))
          ;; Check against all other drawn nodes
          (dolist (drawn-info current-drawn-nodes)
            (let* ((other-node-id (nth 0 drawn-info))
                   (other-y (nth 2 drawn-info))
                   (other-node (dag-draw-get-node graph other-node-id))
                   (other-rank (when other-node (or (dag-draw-node-rank other-node) 0))))
              (when other-rank
                ;; Lower ranks should have lower Y coordinates (appear higher on screen)
                (cond
                 ;; Current node has lower rank but would be positioned below other node
                 ((and (< node-rank other-rank) (>= proposed-y other-y))
                  (setq violates-hierarchy t))
                 ;; Current node has higher rank but would be positioned above other node
                 ((and (> node-rank other-rank) (<= proposed-y other-y))
                  (setq violates-hierarchy t)))))))
        violates-hierarchy))))

(defun dag-draw--rectangles-overlap (rect1 rect2)
  "Check if two rectangles overlap or are too close.

RECT1 and RECT2 are lists of the form (x1 y1 x2 y2) where all coordinates
are integers in grid space.

Includes a minimum gap of 5 characters to prevent text corruption and ensure
readable spacing.

Returns t if the rectangles overlap or are within minimum gap, nil otherwise."
  (let ((x1-1 (nth 0 rect1)) (y1-1 (nth 1 rect1)) (x2-1 (nth 2 rect1)) (y2-1 (nth 3 rect1))
        (x1-2 (nth 0 rect2)) (y1-2 (nth 1 rect2)) (x2-2 (nth 2 rect2)) (y2-2 (nth 3 rect2))
        (min-gap 5)) ; Optimal minimum gap - prevents text corruption and ensures readable spacing
    ;; Rectangles overlap or are too close if they're within min-gap distance
    (and (<= x1-1 (+ x2-2 min-gap)) (<= x1-2 (+ x2-1 min-gap))  ; x proximity
         (<= y1-1 (+ y2-2 min-gap)) (<= y1-2 (+ y2-1 min-gap))))) ; y proximity

(defun dag-draw--resolve-node-collision (x y width height drawn-nodes &optional graph node-id)
  "Resolve node collision by finding a non-overlapping position.

X and Y are integers representing the proposed grid position.
WIDTH and HEIGHT are integers representing node dimensions in grid units.
DRAWN-NODES is a list of rectangles, each (x1 y1 x2 y2 node-id).
GRAPH is an optional `dag-draw-graph' structure for hierarchy-aware resolution.
NODE-ID is an optional symbol representing the node being positioned.

Searches in expanding radius with directional priorities (horizontal movement
first to preserve hierarchical ordering).  If GRAPH and NODE-ID are provided,
ensures resolved position doesn't violate rank ordering.

Returns a list (adjusted-x adjusted-y) where coordinates are integers
representing a non-overlapping grid position with safe spacing."
  ;; Debug output removed for cleaner production code
  (let ((min-spacing 3)  ; Reduced spacing for better test compatibility
        (current-rect (list x y (+ x width -1) (+ y height -1)))
        (max-attempts 20)
        (attempt 0)
        (best-x x)
        (best-y y))

    ;; Check if current position has any overlaps
    (let ((has-collision nil))
      (dolist (drawn-rect drawn-nodes)
        (when (dag-draw--rectangles-overlap current-rect drawn-rect)
          (setq has-collision t)))

      ;; If no collision, return original position
      (if (not has-collision)
          (list x y)

        ;; HIERARCHY-AWARE collision resolution: prioritize horizontal movement
        ;; to preserve GKNV hierarchical ordering
        (let ((position-found nil)
              (search-directions '((1 0)   ; right (PRIORITY 1)
                                   (-1 0)  ; left (PRIORITY 2)
                                   (0 1)   ; down (PRIORITY 3)
                                   (0 -1)  ; up (PRIORITY 4)
                                   (1 1)   ; diagonal down-right
                                   (-1 1)  ; diagonal down-left
                                   (1 -1)  ; diagonal up-right
                                   (-1 -1) ; diagonal up-left
                                   )))
          (while (and (< attempt max-attempts) (not position-found))
            (setq attempt (1+ attempt))

            ;; Try each direction at increasing distances
            (dolist (direction search-directions)
              (unless position-found
                (let* ((dir-x (car direction))
                       (dir-y (cadr direction))
                       (test-x (+ x (* dir-x attempt min-spacing)))
                       (test-y (+ y (* dir-y attempt min-spacing)))
                       (test-rect (list test-x test-y (+ test-x width -1) (+ test-y height -1)))
                       (collision-free t))

                  ;; Ensure position is within reasonable bounds (positive coordinates)
                  (when (and (>= test-x 0) (>= test-y 0))
                    (dolist (drawn-rect drawn-nodes)
                      (when (dag-draw--rectangles-overlap test-rect drawn-rect)
                        (setq collision-free nil)))

                    ;; HIERARCHY CHECK: Ensure proposed position doesn't violate rank ordering
                    (when (and collision-free graph node-id)
                      (let ((drawn-node-info (mapcar (lambda (rect)
                                                       ;; rect format: (x1 y1 x2 y2 node-id)
                                                       (when (>= (length rect) 5)
                                                         (list (nth 4 rect) (nth 0 rect) (nth 1 rect)
                                                               (- (nth 2 rect) (nth 0 rect))
                                                               (- (nth 3 rect) (nth 1 rect)))))
                                                     drawn-nodes)))
                        (setq drawn-node-info (delq nil drawn-node-info))  ; Remove any nils
                        (when (dag-draw--would-violate-hierarchy graph node-id test-y drawn-node-info)
                          (setq collision-free nil))))

                    (when collision-free
                      (setq best-x test-x
                            best-y test-y
                            position-found t)))))))

          (list best-x best-y))))))


;;; Grid Coordinate Utilities

(defun dag-draw--center-aware-round (grid-coord)
  "Round grid coordinate to ensure proper centering for arrow placement.

GRID-COORD is a number (possibly float) representing a grid coordinate.

For ports that should be centered on node boundaries, this ensures the arrow
lands at the true visual center of the box, not the mathematical center.

Returns an integer grid coordinate."
  (round grid-coord))

(defun dag-draw--ascii-grid-to-string (grid)
  "Convert ASCII GRID to string representation.

GRID is a 2D vector of characters.

Converts each row to a string and joins with newlines.  Handles CJK/wide
characters correctly by normalizing display width across all rows.

Returns a string containing the complete ASCII representation."
  ;; Handle empty grid case
  (if (= (length grid) 0)
      ""
    ;; First pass: convert all rows to trimmed strings and find max display width
    (let* ((row-strings (mapcar (lambda (row)
                                  (string-trim-right (apply #'string (append row nil))))
                                grid))
           (display-widths (mapcar #'string-width row-strings))
           (max-display-width (apply #'max display-widths)))
      ;; Second pass: pad each row to max display width
      (mapconcat (lambda (row-str)
                   (let* ((current-width (string-width row-str))
                          (padding-needed (- max-display-width current-width)))
                     (if (> padding-needed 0)
                         (concat row-str (make-string padding-needed ?\s))
                       row-str)))
                 row-strings
                 "\n"))))

;;; Junction Character Enhancement (moved to dag-draw-ascii-junctions.el)
;; All junction-related functions have been extracted to dag-draw-ascii-junctions.el

;;; Edge Analysis for Junction Detection (moved to dag-draw-ascii-junctions.el)

;;; Local Grid Context Analysis (moved to dag-draw-ascii-junctions.el)

(provide 'dag-draw-ascii-grid)

;;; dag-draw-ascii-grid.el ends here
