;;; dag-draw-quality.el --- Dynamic graph quality analysis 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:

;; This module provides dynamic analysis of graph structure to calculate optimal
;; rank separation for hollow routing.  It implements the GKNV paper's recommendation
;; to "optionally increase separation between adjacent ranks to improve the slope
;; of nearly horizontal edges to make them more readable."
;;
;; The analysis considers:
;; - Edge convergence patterns (multiple edges to same destination)
;; - Edge density between ranks
;; - Horizontal routing distances
;; - ASCII grid constraints

;;; Code:

(require 'dash)
(require 'ht)
(require 'dag-draw-core)

;;; Edge Analysis Functions

(defun dag-draw--count-edges-between-ranks (graph rank1 rank2)
  "Count edges between RANK1 and RANK2 in GRAPH.

GRAPH is a `dag-draw-graph' structure.
RANK1 is an integer representing the source rank.
RANK2 is an integer representing the destination rank.

Returns the number of edges crossing from nodes in RANK1 to nodes in RANK2."
  (let ((edge-count 0))
    (dolist (edge (dag-draw-graph-edges graph))
      (let* ((nodes (dag-draw--edge-nodes graph edge))
             (from-node (car nodes))
             (to-node (cdr nodes))
             (from-rank (when from-node (dag-draw-node-rank from-node)))
             (to-rank (when to-node (dag-draw-node-rank to-node))))
        (when (and from-rank to-rank
                   (= from-rank rank1)
                   (= to-rank rank2))
          (setq edge-count (1+ edge-count)))))
    edge-count))

(defun dag-draw--max-edges-to-same-destination (graph from-rank to-rank)
  "Find maximum edge convergence on any single destination node.

GRAPH is a `dag-draw-graph' structure.
FROM-RANK is an integer representing the source rank.
TO-RANK is an integer representing the destination rank.

Analyzes edges from FROM-RANK to TO-RANK.

Returns the highest convergence count as an integer (max edges to one node)."
  (let ((destination-counts (ht-create)))

    ;; Count edges to each destination node
    (dolist (edge (dag-draw-graph-edges graph))
      (let* ((nodes (dag-draw--edge-nodes graph edge))
             (from-node (car nodes))
             (to-node (cdr nodes))
             (from-node-rank (when from-node (dag-draw-node-rank from-node)))
             (to-node-rank (when to-node (dag-draw-node-rank to-node))))
        (when (and from-node-rank to-node-rank
                   (= from-node-rank from-rank)
                   (= to-node-rank to-rank))
          (let ((dest-id (dag-draw-edge-to-node edge)))
            (ht-set! destination-counts dest-id
                     (1+ (or (ht-get destination-counts dest-id) 0)))))))

    ;; Find maximum convergence
    (let ((max-convergence 0))
      (ht-each (lambda (_dest-id count)
                 (setq max-convergence (max max-convergence count)))
               destination-counts)
      max-convergence)))

(defun dag-draw--max-horizontal-edge-distance (graph from-rank to-rank)
  "Calculate maximum horizontal distance for edges between ranks.

GRAPH is a `dag-draw-graph' structure.
FROM-RANK is an integer representing the source rank.
TO-RANK is an integer representing the destination rank.

Measures horizontal displacement (X-coordinate difference) for all edges
between the ranks.  Affects routing complexity and space requirements.

Returns maximum horizontal distance as a number."
  (let ((max-distance 0))
    (dolist (edge (dag-draw-graph-edges graph))
      (let* ((nodes (dag-draw--edge-nodes graph edge))
             (from-node (car nodes))
             (to-node (cdr nodes))
             (from-node-rank (when from-node (dag-draw-node-rank from-node)))
             (to-node-rank (when to-node (dag-draw-node-rank to-node))))
        (when (and from-node-rank to-node-rank
                   (= from-node-rank from-rank)
                   (= to-node-rank to-rank))
          (let* ((from-x (or (dag-draw-node-x-coord from-node) 0))
                 (to-x (or (dag-draw-node-x-coord to-node) 0))
                 (horizontal-distance (abs (- to-x from-x))))
            (setq max-distance (max max-distance horizontal-distance))))))
    max-distance))

;;; Rank Analysis Functions

(defun dag-draw--get-graph-ranks (graph)
  "Get list of all ranks present in GRAPH.

GRAPH is a `dag-draw-graph' structure with assigned ranks.

Returns sorted list of rank numbers (integers) in ascending order."
  (let ((ranks '()))
    (ht-each (lambda (_node-id node)
               (let ((rank (dag-draw-node-rank node)))
                 (when (and rank (not (member rank ranks)))
                   (push rank ranks))))
             (dag-draw-graph-nodes graph))
    (sort ranks #'<)))

(defun dag-draw--get-nodes-in-rank (graph rank)
  "Get list of all nodes in RANK of GRAPH.

GRAPH is a `dag-draw-graph' structure.
RANK is an integer representing the rank to query.

Returns list of `dag-draw-node' structures in RANK."
  (let ((nodes-in-rank '()))
    (ht-each (lambda (_node-id node)
               (when (and (dag-draw-node-rank node)
                          (= (dag-draw-node-rank node) rank))
                 (push node nodes-in-rank)))
             (dag-draw-graph-nodes graph))
    nodes-in-rank))

;;; Dynamic Spacing Calculation

(defun dag-draw--calculate-dynamic-rank-separation (graph from-rank to-rank)
  "Calculate required ASCII rows between FROM-RANK and TO-RANK.

GRAPH is a `dag-draw-graph' structure with layout complete.
FROM-RANK is an integer representing the source rank.
TO-RANK is an integer representing the destination rank.

Implements dynamic spacing following GKNV recommendation to increase
separation for better edge readability.  Considers edge convergence,
density, and horizontal routing distances.

Returns number of ASCII rows needed as an integer."
  (let* ((edges-between (dag-draw--count-edges-between-ranks graph from-rank to-rank))
         (max-convergence (dag-draw--max-edges-to-same-destination graph from-rank to-rank))
         (max-horizontal-distance (dag-draw--max-horizontal-edge-distance graph from-rank to-rank))

         ;; Base spacing: standard GKNV minimum per paper specification
         (base-spacing 2)

         ;; Additional spacing for convergence: +1 row for each additional converging edge
         (convergence-spacing (max 0 (1- max-convergence)))

         ;; Additional spacing for edge density: +1 row for every 3 edges crossing between ranks
         (density-spacing (/ edges-between 3))

         ;; Additional spacing for long horizontal routes: +1 row if routes are very long
         (distance-spacing (if (> max-horizontal-distance 300) 1 0)))

    (+ base-spacing convergence-spacing density-spacing distance-spacing)))

(defun dag-draw--calculate-max-required-rank-separation (graph)
  "Calculate maximum rank separation needed across all rank pairs.

GRAPH is a `dag-draw-graph' structure with layout complete.

Analyzes all adjacent rank pairs and returns the largest separation
requirement.  Ensures sufficient space for the most complex rank transition.

Returns maximum spacing in ASCII rows as an integer."
  (let ((ranks (dag-draw--get-graph-ranks graph)))
    (if (< (length ranks) 2)
        ;; Default spacing for graphs with 0 or 1 ranks
        2
      ;; Calculate spacing for each adjacent rank pair and take maximum
      (let ((max-spacing 2))
        (dotimes (i (1- (length ranks)))
          (let* ((from-rank (nth i ranks))
                 (to-rank (nth (1+ i) ranks))
                 (required-spacing (dag-draw--calculate-dynamic-rank-separation
                                    graph from-rank to-rank)))
            (setq max-spacing (max max-spacing required-spacing))))
        max-spacing))))

;;; ASCII Quality Assurance Functions

(defun dag-draw--validate-node-boundaries (ascii-grid nodes)
  "Validate edges terminate at node boundaries, not inside text areas.

ASCII-GRID is a list of strings representing the rendered graph.
NODES is a list of (node-id x y width height) specifications.

Checks that arrow characters appear only on boundaries, not inside
node text areas.

Returns hash table with `valid' (boolean) and `violations'
\(list) keys."
  (let ((result (ht-create))
        (violations '())
        (arrow-chars '(?▼ ?▲ ?▶ ?◀ ?↓ ?↑ ?→ ?←)))

    ;; Check each node's text area for arrow characters
    (dolist (node-spec nodes)
      (let* ((node-id (nth 0 node-spec))
             (x (nth 1 node-spec))
             (y (nth 2 node-spec))
             (width (nth 3 node-spec))
             (height (nth 4 node-spec)))

        ;; Check interior of node (excluding boundary)
        (when (> height 2)  ; Only check if node has interior
          (dotimes (row-offset (- height 2))  ; Skip top and bottom boundary
            (when (> width 2)  ; Only check if node has interior columns
              (dotimes (col-offset (- width 2))  ; Skip left and right boundary
                (let* ((grid-row (+ y row-offset 1))   ; +1 to skip top boundary
                       (grid-col (+ x col-offset 1))   ; +1 to skip left boundary
                       (row-string (when (< grid-row (length ascii-grid))
                                     (nth grid-row ascii-grid)))
                       (char-at-pos (when (and row-string (< grid-col (length row-string)))
                                      (aref row-string grid-col))))

                  ;; Check if arrow character found inside node
                  (when (and char-at-pos (memq char-at-pos arrow-chars))
                    (push (list :node node-id
                                :row grid-row
                                :col grid-col
                                :char char-at-pos
                                :violation "Arrow character inside node text area")
                          violations))))))))

    (ht-set! result 'valid (null violations))
    (ht-set! result 'violations violations))
    result))

(defun dag-draw--verify-edge-continuity (ascii-grid edges)
  "Verify edges are rendered continuously without gaps.

ASCII-GRID is a list of strings representing the rendered graph.
EDGES is a list of (edge-id from-node to-node start-x start-y
end-x end-y).

Checks that edge paths contain proper edge characters at all
positions without missing segments.

Returns hash table with `valid' (boolean) and `gaps' (list) keys."
  (let ((result (ht-create))
        (gaps '())
        (edge-chars '(?│ ?─ ?┌ ?┐ ?└ ?┘ ?┬ ?┴ ?├ ?┤ ?┼ ?▼ ?▲ ?▶ ?◀ ?↓ ?↑ ?→ ?←)))

    ;; Check each edge path for continuity
    (dolist (edge-spec edges)
      (let* ((edge-id (nth 0 edge-spec))
             (start-x (nth 3 edge-spec))
             (start-y (nth 4 edge-spec))
             (end-x (nth 5 edge-spec))
             (end-y (nth 6 edge-spec)))

        ;; For vertical edges, check each row between start and end
        (when (= start-x end-x)
          (let ((min-y (min start-y end-y))
                (max-y (max start-y end-y)))
            (dotimes (offset (1+ (- max-y min-y)))
              (let* ((check-y (+ min-y offset))
                     (check-x start-x)
                     (row-string (when (< check-y (length ascii-grid))
                                  (nth check-y ascii-grid)))
                     (char-at-pos (when (and row-string (< check-x (length row-string)))
                                   (aref row-string check-x))))

                ;; Check if expected edge character is missing
                (when (and row-string
                          (or (null char-at-pos)
                              (not (memq char-at-pos edge-chars))
                              (eq char-at-pos ?\s)))
                  (push (list :edge edge-id
                             :row check-y
                             :col check-x
                             :expected "vertical edge character"
                             :found (or char-at-pos "nil"))
                        gaps))))))

        ;; For horizontal edges, check each column between start and end
        (when (= start-y end-y)
          (let ((min-x (min start-x end-x))
                (max-x (max start-x end-x)))
            (dotimes (offset (1+ (- max-x min-x)))
              (let* ((check-x (+ min-x offset))
                     (check-y start-y)
                     (row-string (when (< check-y (length ascii-grid))
                                  (nth check-y ascii-grid)))
                     (char-at-pos (when (and row-string (< check-x (length row-string)))
                                   (aref row-string check-x))))

                ;; Check if expected edge character is missing
                (when (and row-string
                          (or (null char-at-pos)
                              (not (memq char-at-pos edge-chars))
                              (eq char-at-pos ?\s)))
                  (push (list :edge edge-id
                             :row check-y
                             :col check-x
                             :expected "horizontal edge character"
                             :found (or char-at-pos "nil"))
                        gaps))))))))

    (ht-set! result 'valid (null gaps))
    (ht-set! result 'gaps gaps)
    result))

(defun dag-draw--check-character-semantics (ascii-grid arrows)
  "Check box-drawing characters have correct directional meaning.

ASCII-GRID is a list of strings representing the rendered graph.
ARROWS is a list of (arrow-id x y direction) where direction is
a symbol: up, down, left, or right.

Verifies arrow characters match their intended direction.

Returns hash table with `valid' (boolean) and `semantic-errors'
\(list) keys."
  (let ((result (ht-create))
        (semantic-errors '())
        (direction-chars '((up    . (?▲ ?↑))
                          (down  . (?▼ ?↓))
                          (left  . (?◀ ?←))
                          (right . (?▶ ?→)))))
    
    ;; Check each arrow for correct directional character
    (dolist (arrow-spec arrows)
      (let* ((arrow-id (nth 0 arrow-spec))
             (x (nth 1 arrow-spec))
             (y (nth 2 arrow-spec))
             (expected-direction (nth 3 arrow-spec))
             (row-string (when (< y (length ascii-grid))
                          (nth y ascii-grid)))
             (char-at-pos (when (and row-string (< x (length row-string)))
                           (aref row-string x)))
             (expected-chars (cdr (assq expected-direction direction-chars))))
        
        ;; Check if character matches expected direction
        (when char-at-pos
          (unless (memq char-at-pos expected-chars)
            ;; Find what direction this character actually represents
            (let ((actual-direction nil))
              (dolist (dir-pair direction-chars)
                (when (memq char-at-pos (cdr dir-pair))
                  (setq actual-direction (car dir-pair))))
              
              (push (list :arrow arrow-id
                         :row y
                         :col x
                         :expected-direction expected-direction
                         :actual-direction actual-direction
                         :expected-chars expected-chars
                         :found-char char-at-pos)
                    semantic-errors))))))
    
    (ht-set! result 'valid (null semantic-errors))
    (ht-set! result 'semantic-errors semantic-errors)
    result))

;;; Graph Structure Analysis

(defun dag-draw--analyze-graph-complexity (graph)
  "Analyze graph complexity and return summary statistics.

GRAPH is a `dag-draw-graph' structure with layout complete.

Calculates metrics including node/edge counts, rank count, max convergence,
and average edges per rank transition.

Returns plist with complexity metrics for debugging and optimization."
  (let* ((ranks (dag-draw--get-graph-ranks graph))
         (total-nodes (dag-draw-node-count graph))
         (total-edges (dag-draw-edge-count graph))
         (max-convergence 0)
         (total-rank-transitions 0))

    ;; Analyze convergence across all rank pairs
    (when (>= (length ranks) 2)
      (dotimes (i (1- (length ranks)))
        (let* ((from-rank (nth i ranks))
               (to-rank (nth (1+ i) ranks))
               (convergence (dag-draw--max-edges-to-same-destination graph from-rank to-rank))
               (edge-count (dag-draw--count-edges-between-ranks graph from-rank to-rank)))
          (setq max-convergence (max max-convergence convergence))
          (setq total-rank-transitions (+ total-rank-transitions edge-count)))))

    (list :total-nodes total-nodes
          :total-edges total-edges
          :rank-count (length ranks)
          :max-convergence max-convergence
          :total-rank-transitions total-rank-transitions
          :avg-edges-per-transition (if (> (length ranks) 1)
                                        (/ (float total-rank-transitions) (1- (length ranks)))
                                      0))))

(defun dag-draw--debug-spacing-calculation (graph)
  "Debug helper to show spacing calculation details.

GRAPH is a `dag-draw-graph' structure with layout complete.

Prints analysis of graph structure and spacing requirements for each
rank transition.  Useful for understanding dynamic spacing decisions.

Returns maximum spacing in ASCII rows as an integer."
  (dag-draw--calculate-max-required-rank-separation graph))

(provide 'dag-draw-quality)

;;; dag-draw-quality.el ends here
