LayoutEngine.cpp

#include "LayoutEngine.h"
#include "Debug.h"
#include <cstdio>
#include <chrono>
#include <algorithm>
#include <functional>

// Additional includes for layered layout algorithm
#include <map>
#include <set>
#include <vector>
#include <queue>

#define IMGUI_DEFINE_MATH_OPERATORS
#include <imgui.h>
#include <imgui_internal.h>

// Layout-detail debug print: in-degrees, layer assignment, dummy-node insertion, final layers.
// Only emits when --debug is active (gDebugEnabled). Errors/warnings use plain printf and always show.
#define LDBG(...) do { if (gDebugEnabled) printf(__VA_ARGS__); } while (0)

// Helper function: Calculate node width based on text length
static float CalculateNodeWidth(const GraphData::Node& node, float minWidth = 150.0f) {
    ImFont* font = ImGui::GetFont();
    if (!font) {
        printf("WARNING: ImGui font not available, using default width\n");
        return 150.0f;  // Fallback if font not initialized
    }

    float fontSize = ImGui::GetFontSize();

    // Measure TITLE text width
    ImVec2 titleSize = font->CalcTextSizeA(fontSize, FLT_MAX, 0.0f, node.name.c_str());
    float titlePadding = 24.0f;  // Left/right padding (12px each side)
    float iconSpace = node.isExpandable ? 28.0f : 0.0f;  // Space for +/- icon
    float titleWidth = titleSize.x + titlePadding + iconSpace;

    // Measure INPUT/OUTPUT label widths (this is what was missing!)
    float maxInputWidth = 0.0f;
    float maxOutputWidth = 0.0f;

    for (const auto& input : node.inputs) {
        ImVec2 labelSize = font->CalcTextSizeA(fontSize, FLT_MAX, 0.0f, input.name.c_str());
        // Add connector dot space + padding (from NodesInput constructor logic)
        float connectorDotSpace = (0.4f + 0.7f + 0.4f) * fontSize;  // padding + dot + padding
        float inputWidth = labelSize.x + connectorDotSpace + (0.4f * fontSize);  // extra padding
        maxInputWidth = std::max(maxInputWidth, inputWidth);
    }

    for (const auto& output : node.outputs) {
        ImVec2 labelSize = font->CalcTextSizeA(fontSize, FLT_MAX, 0.0f, output.name.c_str());
        // Add connector dot space + padding (from NodesOutput constructor logic)
        float connectorDotSpace = (0.4f + 0.7f + 0.4f) * fontSize;  // padding + dot + padding
        float outputWidth = labelSize.x + connectorDotSpace + (0.4f * fontSize);  // extra padding
        maxOutputWidth = std::max(maxOutputWidth, outputWidth);
    }

    // Node width = inputs + separator + outputs (from BuildNodeGeometry logic)
    float separator = 1.7f * fontSize;  // ImGuiNodesHSeparation
    float ioWidth = maxInputWidth + separator + maxOutputWidth;

    // Final width is the maximum of title width and I/O width
    float calculatedWidth = std::max(titleWidth, ioWidth);

    // Ensure minimum width
    return std::max(minWidth, calculatedWidth);
}

// World size ComputeGridLayout() produces for nodeCount nodes, without building or laying out a model.
// Grid nodes are homogeneous (same 5 in / 5 out ports; ids differ only in digit count) so every column
// is the same width and the geometry closes analytically. Mirrors ComputeGridLayout(): nodesPerRow =
// (int)sqrt(N), columns advance by width + horizontalSpacing, rows by height + verticalSpacing, with
// layoutPadding on all four sides (GetWorldBounds() adds the trailing half).
ImVec2 LayoutEngine::GridWorldSizeForNodeCount(int nodeCount) const {
    if (nodeCount <= 0) return ImVec2(0.0f, 0.0f);

    GraphData::Node probe = GraphData::MakeGridNode(nodeCount - 1);  // largest id = widest name
    const float w = CalculateNodeWidth(probe);

    int perRow = (int)std::sqrt((double)nodeCount);
    if (perRow < 1) perRow = 1;
    long long rows = ((long long)nodeCount + perRow - 1) / perRow;

    const float pad = 100.0f;
    double maxX = pad + (perRow - 1) * ((double)w + horizontalSpacing_) + w + pad;
    double maxY = pad + (rows - 1) * ((double)nodeHeight_ + verticalSpacing_) + nodeHeight_ + pad;
    return ImVec2((float)maxX, (float)maxY);
}

void LayoutEngine::ComputeGridLayout(const GraphData::DataModel& model) {
    auto start = std::chrono::high_resolution_clock::now();

    nodePositions_.clear();
    nodeSizes_.clear();

    // Only layout ACTIVE nodes (root + expanded children)
    std::vector<const GraphData::Node*> activeNodes = GetActiveNodes(model);

    // Add padding around the entire layout
    float layoutPadding = 100.0f;

    LDBG("\nComputeLayout: Calculating widths for %zu nodes\n", activeNodes.size());

    // First pass: Calculate node sizes and organize by column
    int numRows = (activeNodes.size() + nodesPerRow_ - 1) / nodesPerRow_;
    std::vector<float> columnMaxWidths(nodesPerRow_, 0.0f);

    for (size_t i = 0; i < activeNodes.size(); i++) {
        const GraphData::Node* node = activeNodes[i];  // Now a pointer!
        float nodeWidth = CalculateNodeWidth(*node);
        nodeSizes_[node->id] = ImVec2(nodeWidth, nodeHeight_);

        // Track max width per column
        int col = i % nodesPerRow_;
        columnMaxWidths[col] = std::max(columnMaxWidths[col], nodeWidth);
    }

    // Calculate cumulative X positions for each column
    std::vector<float> columnXPositions(nodesPerRow_);
    columnXPositions[0] = layoutPadding;
    for (int col = 1; col < nodesPerRow_; col++) {
        columnXPositions[col] = columnXPositions[col - 1] + columnMaxWidths[col - 1] + horizontalSpacing_;
    }

    // Second pass: Grid layout positioning using column positions
    for (size_t i = 0; i < activeNodes.size(); i++) {
        int col = i % nodesPerRow_;
        int row = i / nodesPerRow_;

        ImVec2 pos;
        pos.x = columnXPositions[col];
        pos.y = layoutPadding + row * (nodeHeight_ + verticalSpacing_);

        nodePositions_[activeNodes[i]->id] = pos;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    LDBG("LayoutEngine: Computed layout for %zu active nodes in %lld ms\n",
           activeNodes.size(), duration.count());
}

// Helper function: Insert dummy nodes for edges spanning multiple layers
// This breaks long edges into shorter segments (Sugiyama framework standard technique)
static void InsertDummyNodesForLongEdges(
    std::map<int, int>& nodeLayers,
    std::map<int, std::vector<int>>& outgoing,
    std::map<int, std::vector<int>>& incoming,
    std::vector<LayoutEngine::DummyNode>& dummyNodes,
    std::unordered_map<int, LayoutEngine::DummyNode>& dummyNodeById,
    int& nextDummyId,
    const std::map<int, const GraphData::Node*>& nodeById)
{
    LDBG("\n=== Inserting Dummy Nodes for Long Edges ===\n");

    // Collect all edges that need dummy nodes
    struct EdgeToSplit {
        int srcId;
        int dstId;
        int srcLayer;
        int dstLayer;
    };
    std::vector<EdgeToSplit> edgesToSplit;

    // Find edges spanning more than 1 layer
    for (const auto& [srcId, targets] : outgoing) {
        // Skip dummy nodes (they're already part of chains)
        if (srcId < 0) continue;

        int srcLayer = nodeLayers[srcId];
        for (int dstId : targets) {
            // Skip dummy nodes
            if (dstId < 0) continue;

            int dstLayer = nodeLayers[dstId];
            int span = dstLayer - srcLayer;

            if (span > 1) {
                LDBG("  Found long edge: Node %d (layer %d) -> Node %d (layer %d), span=%d\n",
                       srcId, srcLayer, dstId, dstLayer, span);
                edgesToSplit.push_back({srcId, dstId, srcLayer, dstLayer});
            }
        }
    }

    LDBG("Total long edges to split: %zu\n", edgesToSplit.size());

    // Split each long edge by inserting dummy nodes
    for (const EdgeToSplit& edge : edgesToSplit) {
        int span = edge.dstLayer - edge.srcLayer;
        int numDummies = span - 1;  // Number of intermediate layers

        LDBG("\n  Splitting edge %d->%d (span=%d, %d dummies needed)\n",
               edge.srcId, edge.dstId, span, numDummies);

        // Create dummy node chain
        std::vector<int> dummyChain;
        for (int i = 0; i < numDummies; i++) {
            LayoutEngine::DummyNode dummy;
            dummy.id = nextDummyId--;
            dummy.originalSrcId = edge.srcId;
            dummy.originalDstId = edge.dstId;
            dummy.rank = edge.srcLayer + 1 + i;  // Intermediate layer
            dummy.prevDummyId = (i == 0) ? -1 : dummyChain[i - 1];  // -1 if first dummy
            dummy.nextDummyId = -1;  // Will be set for all but last dummy

            dummyChain.push_back(dummy.id);
            dummyNodes.push_back(dummy);
            dummyNodeById[dummy.id] = dummy;
            nodeLayers[dummy.id] = dummy.rank;

            LDBG("    Created dummy %d at layer %d\n", dummy.id, dummy.rank);
        }

        // Link the chain (update nextDummyId for all but last)
        for (size_t i = 0; i < dummyChain.size() - 1; i++) {
            dummyNodeById[dummyChain[i]].nextDummyId = dummyChain[i + 1];
            // Update in vector as well
            for (auto& d : dummyNodes) {
                if (d.id == dummyChain[i]) {
                    d.nextDummyId = dummyChain[i + 1];
                    break;
                }
            }
        }

        // Remove original direct edge from adjacency lists
        auto& srcOutgoing = outgoing[edge.srcId];
        srcOutgoing.erase(std::remove(srcOutgoing.begin(), srcOutgoing.end(), edge.dstId), srcOutgoing.end());

        auto& dstIncoming = incoming[edge.dstId];
        dstIncoming.erase(std::remove(dstIncoming.begin(), dstIncoming.end(), edge.srcId), dstIncoming.end());

        // Add new edges through dummy chain
        // src -> dummy[0]
        outgoing[edge.srcId].push_back(dummyChain[0]);
        incoming[dummyChain[0]].push_back(edge.srcId);

        // dummy[i] -> dummy[i+1]
        for (size_t i = 0; i < dummyChain.size() - 1; i++) {
            outgoing[dummyChain[i]].push_back(dummyChain[i + 1]);
            incoming[dummyChain[i + 1]].push_back(dummyChain[i]);
        }

        // dummy[last] -> dst
        outgoing[dummyChain.back()].push_back(edge.dstId);
        incoming[edge.dstId].push_back(dummyChain.back());

        LDBG("    Edge chain: %d", edge.srcId);
        for (int dummyId : dummyChain) {
            LDBG(" -> %d", dummyId);
        }
        LDBG(" -> %d\n", edge.dstId);
    }

    LDBG("\nTotal dummy nodes created: %zu\n", dummyNodes.size());
}

void LayoutEngine::ComputeLayoutLayered(const GraphData::DataModel& model) {
    auto start = std::chrono::high_resolution_clock::now();

    nodePositions_.clear();
    nodeSizes_.clear();

    // Only layout ACTIVE nodes (root + expanded children)
    std::vector<const GraphData::Node*> activeNodes = GetActiveNodes(model);

    if (activeNodes.empty()) {
        LDBG("LayoutEngine: No active nodes to layout\n");
        return;
    }

    if (gDebugEnabled) {
        LDBG("\n=== ComputeLayoutLayered Debug ===\n");
        LDBG("Active nodes (%zu total):\n", activeNodes.size());
        for (const GraphData::Node* node : activeNodes) {
            LDBG("  Node %d: '%s' (parent=%d, expandable=%d)\n",
                   node->id, node->name.c_str(), node->parentId, node->isExpandable);
        }
    }

    // Build the edge list for active nodes, applying connection substitution for expanded
    // nodes. Node adjacency (outgoing/incoming/nodeById) is rebuilt inside LayoutNodesInternal.
    std::vector<LayoutEdge> edges;
    std::map<int, const GraphData::Node*> nodeById;  // for substitution lookups below
    for (const GraphData::Node* node : activeNodes) {
        nodeById[node->id] = node;
    }

    // Build edge lists with connection substitution for expanded nodes
    LDBG("\nProcessing connections (with substitution for expanded nodes):\n");
    int connectionCount = 0;
    int substitutedCount = 0;

    for (const auto& conn : model.GetConnections()) {
        //Actual_ are the real node data to use after substitution, vs conn.sourceNodeId
        // (which might be an expanded/inactive node)
        int actualSrcNodeId = conn.sourceNodeId;
        int actualSrcPort = conn.sourcePortIndex;
        int actualDstNodeId = conn.targetNodeId;
        int actualDstPort = conn.targetPortIndex;

        bool srcSubstituted = false;
        bool dstSubstituted = false;

        // Substitute source if it's expanded (not in active nodes)
        // Must do this because the expanded node dissapears and is replaced by the subgraph it represents
        if (nodeById.count(conn.sourceNodeId) == 0) {
            // Source node is not active (likely expanded) - find child that provides this output
            const GraphData::Node* child = model.FindChildProvidingOutputPort(
                conn.sourceNodeId, conn.sourcePortIndex);

            if (child && nodeById.count(child->id)) {
                actualSrcNodeId = child->id;
                actualSrcPort = model.FindChildPortIndex(child->parentOutputPortMap, conn.sourcePortIndex);
                srcSubstituted = true;
            } else {
                // No active child provides this port - skip connection
                continue;
            }
        }

        // Substitute target if it's expanded (not in active nodes)
        if (nodeById.count(conn.targetNodeId) == 0) {
            // Target node is not active (likely expanded) - find child that accepts this input
            const GraphData::Node* child = model.FindChildAcceptingInputPort(
                conn.targetNodeId, conn.targetPortIndex);

            if (child && nodeById.count(child->id)) {
                actualDstNodeId = child->id;
                actualDstPort = model.FindChildPortIndex(child->parentInputPortMap, conn.targetPortIndex);
                dstSubstituted = true;
            } else {
                // No active child accepts this port - skip connection
                continue;
            }
        }

        // Now we have actual active node IDs - add the connection
        if (nodeById.count(actualSrcNodeId) && nodeById.count(actualDstNodeId)) {
            const GraphData::Node* srcNode = nodeById[actualSrcNodeId];
            const GraphData::Node* dstNode = nodeById[actualDstNodeId];

            if (srcSubstituted || dstSubstituted) {
                LDBG("  [SUBSTITUTED] ");
                substitutedCount++;
            } else {
                LDBG("  ");
            }

            LDBG("%s (id=%d) -> %s (id=%d)",
                   srcNode->name.c_str(), actualSrcNodeId,
                   dstNode->name.c_str(), actualDstNodeId);

            if (srcSubstituted) {
                LDBG(" [src: %d->%d]", conn.sourceNodeId, actualSrcNodeId);
            }
            if (dstSubstituted) {
                LDBG(" [dst: %d->%d]", conn.targetNodeId, actualDstNodeId);
            }
            LDBG("\n");

            edges.push_back({actualSrcNodeId, actualDstNodeId});
            connectionCount++;
        }
    }
    LDBG("Total connections: %d (%d substituted)\n", connectionCount, substitutedCount);

    // Run the shared Sugiyama phases on the active graph, placed at world origin.
    LayoutResult result = LayoutNodesInternal(activeNodes, edges, ImVec2(0.0f, 0.0f));
    nodePositions_ = std::move(result.positions);
    nodeSizes_     = std::move(result.sizes);

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    LDBG("LayoutEngine: Computed layered layout for %zu active nodes in %lld ms\n",
           activeNodes.size(), duration.count());
}

// Shared Sugiyama coordinate assignment (Phases 1-4). Builds its own adjacency from the
// given nodes + edges, runs the algorithm, and returns positions/sizes offset by `origin`.
// Callers: full-graph layout (origin 0,0) and per-subgraph expand layout (origin = parent's
// fixed slot). Uses the member dummy-node containers, so only one layout may run at a time
// (fine: layout is synchronous).
LayoutEngine::LayoutResult LayoutEngine::LayoutNodesInternal(
    const std::vector<const GraphData::Node*>& activeNodes,
    const std::vector<LayoutEdge>& edges,
    ImVec2 origin) {

    LayoutResult out;
    std::map<int, ImVec2>& outPositions = out.positions;
    std::map<int, ImVec2>& outSizes     = out.sizes;

    // Rebuild adjacency from the node list + edges.
    std::map<int, std::vector<int>> outgoing;  // nodeId -> [target nodeIds]
    std::map<int, std::vector<int>> incoming;  // nodeId -> [source nodeIds]
    std::map<int, const GraphData::Node*> nodeById;
    for (const GraphData::Node* node : activeNodes) {
        nodeById[node->id] = node;
        outgoing[node->id] = {};
        incoming[node->id] = {};
    }
    for (const LayoutEdge& e : edges) {
        outgoing[e.src].push_back(e.dst);
        incoming[e.dst].push_back(e.src);
    }

    // Phase 1: Layer Assignment (Topological Sort with Longest Path)
    LDBG("\nPhase 1: Layer Assignment\n");
    std::map<int, int> nodeLayers;  // nodeId -> layer index
    std::map<int, int> inDegree;

    // Calculate in-degrees
    LDBG("In-degrees:\n");
    for (const GraphData::Node* node : activeNodes) {
        inDegree[node->id] = incoming[node->id].size();
        LDBG("  Node %d (%s): in-degree=%d\n",
               node->id, node->name.c_str(), inDegree[node->id]);
    }

    // BFS-based topological sort with layer assignment
    std::queue<int> queue;
    LDBG("\nStarting nodes (in-degree = 0):\n");
    for (const GraphData::Node* node : activeNodes) {
        if (inDegree[node->id] == 0) {
            queue.push(node->id);
            nodeLayers[node->id] = 0;  // Start at layer 0
            LDBG("  Node %d (%s) -> Layer 0\n", node->id, node->name.c_str());
        }
    }

    int maxLayer = 0;
    LDBG("\nLayer assignment process:\n");
    while (!queue.empty()) {
        int currentId = queue.front();
        queue.pop();

        int currentLayer = nodeLayers[currentId];
        const GraphData::Node* currentNode = nodeById[currentId];

        for (int targetId : outgoing[currentId]) {
            // Assign target to next layer (longest path)
            int proposedLayer = currentLayer + 1;
            if (nodeLayers.count(targetId) == 0 || nodeLayers[targetId] < proposedLayer) {
                const GraphData::Node* targetNode = nodeById[targetId];
                LDBG("  %s (layer %d) -> %s: assign layer %d\n",
                       currentNode->name.c_str(), currentLayer,
                       targetNode->name.c_str(), proposedLayer);
                nodeLayers[targetId] = proposedLayer;
                maxLayer = std::max(maxLayer, proposedLayer);
            }

            inDegree[targetId]--;
            if (inDegree[targetId] == 0) {
                queue.push(targetId);
            }
        }
    }

    // Handle cycles (nodes not yet assigned)
    LDBG("\nChecking for cycles:\n");
    for (const GraphData::Node* node : activeNodes) {
        if (nodeLayers.count(node->id) == 0) {
            nodeLayers[node->id] = maxLayer + 1;
            LDBG("  Node %d (%s) has cycle, placing at layer %d\n",
                   node->id, node->name.c_str(), maxLayer + 1);
        }
    }

    LDBG("\nFinal layer assignments:\n");
    for (const GraphData::Node* node : activeNodes) {
        LDBG("  Layer %d: Node %d (%s, parent=%d)\n",
               nodeLayers[node->id], node->id, node->name.c_str(), node->parentId);
    }

    // Insert dummy nodes for long edges
    dummyNodes_.clear();
    dummyNodeById_.clear();
    nextDummyId_ = -1;
    InsertDummyNodesForLongEdges(nodeLayers, outgoing, incoming, dummyNodes_,
                                  dummyNodeById_, nextDummyId_, nodeById);

    // Update maxLayer after dummy insertion (dummies may extend layer count)
    for (const auto& dummy : dummyNodes_) {
        maxLayer = std::max(maxLayer, dummy.rank);
    }

    // Phase 2: Organize nodes by layer
    LDBG("\nPhase 2: Organizing nodes by layer\n");
    std::vector<std::vector<int>> layers(maxLayer + 2);  // Extra layer for cycles

    // Add real nodes
    for (const GraphData::Node* node : activeNodes) {
        int layer = nodeLayers[node->id];
        layers[layer].push_back(node->id);
    }

    // Add dummy nodes (order doesn't matter here - Phase 3 crossing reduction will reorder)
    for (const auto& dummy : dummyNodes_) {
        layers[dummy.rank].push_back(dummy.id);
    }

    // Print layer organization
    for (size_t layerIdx = 0; layerIdx < layers.size(); layerIdx++) {
        if (layers[layerIdx].empty()) continue;
        LDBG("  Layer %zu (%zu nodes, including dummies):\n", layerIdx, layers[layerIdx].size());
        for (int nodeId : layers[layerIdx]) {
            if (nodeId < 0) {
                // Dummy node
                const auto& dummy = dummyNodeById_[nodeId];
                LDBG("    - Dummy %d: (edge %d->%d, layer=%d)\n",
                       dummy.id, dummy.originalSrcId, dummy.originalDstId, dummy.rank);
            } else {
                // Real node
                const GraphData::Node* node = nodeById[nodeId];
                LDBG("    - Node %d: %s (parent=%d)\n", nodeId, node->name.c_str(), node->parentId);
            }
        }
    }

    // Phase 3: Multi-pass barycenter crossing reduction
    LDBG("\nPhase 3: Multi-pass Barycenter Crossing Reduction\n");

    const int MAX_ITERATIONS = 24;  // Standard Sugiyama: 24 passes
    int bestCrossingCount = INT_MAX;
    std::vector<std::vector<int>> bestLayers = layers;

    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        bool isForwardPass = (iteration % 2 == 0);

        if (isForwardPass) {
            // Forward pass: sort by barycenter of incoming edges (top-down)
            for (int layerIdx = 1; layerIdx <= maxLayer; layerIdx++) {
                // (barycenter, originalEdgeKey, nodeId) - bundles dummy chains for readability
                std::vector<std::tuple<float, std::pair<int, int>, int>> nodeBarycenters;

                for (int nodeId : layers[layerIdx]) {
                    // Calculate barycenter (average position of neighbors in previous layer)
                    std::vector<int> neighborPositions;
                    for (int srcId : incoming[nodeId]) {
                        if (nodeLayers[srcId] == layerIdx - 1) {
                            auto it = std::find(layers[layerIdx - 1].begin(),
                                              layers[layerIdx - 1].end(), srcId);
                            if (it != layers[layerIdx - 1].end()) {
                                neighborPositions.push_back(it - layers[layerIdx - 1].begin());
                            }
                        }
                    }

                    float barycenter = 0.0f;
                    if (!neighborPositions.empty()) {
                        int sum = 0;
                        for (int pos : neighborPositions) sum += pos;
                        barycenter = static_cast<float>(sum) / neighborPositions.size();
                    } else {
                        // No incoming edges - keep current position
                        auto it = std::find(layers[layerIdx].begin(), layers[layerIdx].end(), nodeId);
                        barycenter = static_cast<float>(it - layers[layerIdx].begin());
                    }

                    // Secondary sort key: bundle dummy chains by original edge (improves readability)
                    std::pair<int, int> edgeKey = {0, 0};  // Real nodes get (0,0)
                    if (nodeId < 0) {  // Dummy node
                        auto it = dummyNodeById_.find(nodeId);
                        if (it != dummyNodeById_.end()) {
                            edgeKey = {it->second.originalSrcId, it->second.originalDstId};
                        }
                    }

                    nodeBarycenters.push_back({barycenter, edgeKey, nodeId});
                }

                // Sort by barycenter, then by edge key (keeps dummies from same edge together)
                std::sort(nodeBarycenters.begin(), nodeBarycenters.end());

                // Update layer
                layers[layerIdx].clear();
                for (const auto& [bc, edgeKey, nodeId] : nodeBarycenters) {
                    layers[layerIdx].push_back(nodeId);
                }
            }
        } else {
            // Backward pass: sort by barycenter of outgoing edges (bottom-up)
            for (int layerIdx = maxLayer - 1; layerIdx >= 0; layerIdx--) {
                // (barycenter, originalEdgeKey, nodeId) - bundles dummy chains for readability
                std::vector<std::tuple<float, std::pair<int, int>, int>> nodeBarycenters;

                for (int nodeId : layers[layerIdx]) {
                    // Calculate barycenter (average position of neighbors in next layer)
                    std::vector<int> neighborPositions;
                    for (int dstId : outgoing[nodeId]) {
                        if (nodeLayers[dstId] == layerIdx + 1) {
                            auto it = std::find(layers[layerIdx + 1].begin(),
                                              layers[layerIdx + 1].end(), dstId);
                            if (it != layers[layerIdx + 1].end()) {
                                neighborPositions.push_back(it - layers[layerIdx + 1].begin());
                            }
                        }
                    }

                    float barycenter = 0.0f;
                    if (!neighborPositions.empty()) {
                        int sum = 0;
                        for (int pos : neighborPositions) sum += pos;
                        barycenter = static_cast<float>(sum) / neighborPositions.size();
                    } else {
                        // No outgoing edges - keep current position
                        auto it = std::find(layers[layerIdx].begin(), layers[layerIdx].end(), nodeId);
                        barycenter = static_cast<float>(it - layers[layerIdx].begin());
                    }

                    // Secondary sort key: bundle dummy chains by original edge (improves readability)
                    std::pair<int, int> edgeKey = {0, 0};  // Real nodes get (0,0)
                    if (nodeId < 0) {  // Dummy node
                        auto it = dummyNodeById_.find(nodeId);
                        if (it != dummyNodeById_.end()) {
                            edgeKey = {it->second.originalSrcId, it->second.originalDstId};
                        }
                    }

                    nodeBarycenters.push_back({barycenter, edgeKey, nodeId});
                }

                // Sort by barycenter, then by edge key (keeps dummies from same edge together)
                std::sort(nodeBarycenters.begin(), nodeBarycenters.end());

                // Update layer
                layers[layerIdx].clear();
                for (const auto& [bc, edgeKey, nodeId] : nodeBarycenters) {
                    layers[layerIdx].push_back(nodeId);
                }
            }
        }

        // Count crossings every 4 iterations to check convergence
        if (iteration % 4 == 3) {
            int crossingCount = 0;
            for (int layerIdx = 0; layerIdx < maxLayer; layerIdx++) {
                // Count crossings between layer[layerIdx] and layer[layerIdx+1]
                for (size_t i = 0; i < layers[layerIdx].size(); i++) {
                    for (size_t j = i + 1; j < layers[layerIdx].size(); j++) {
                        int node1 = layers[layerIdx][i];
                        int node2 = layers[layerIdx][j];

                        // Check all edges from node1 and node2 to next layer
                        for (int dst1 : outgoing[node1]) {
                            if (nodeLayers[dst1] != layerIdx + 1) continue;
                            auto it1 = std::find(layers[layerIdx + 1].begin(),
                                               layers[layerIdx + 1].end(), dst1);
                            if (it1 == layers[layerIdx + 1].end()) continue;
                            int pos1 = it1 - layers[layerIdx + 1].begin();

                            for (int dst2 : outgoing[node2]) {
                                if (nodeLayers[dst2] != layerIdx + 1) continue;
                                auto it2 = std::find(layers[layerIdx + 1].begin(),
                                                   layers[layerIdx + 1].end(), dst2);
                                if (it2 == layers[layerIdx + 1].end()) continue;
                                int pos2 = it2 - layers[layerIdx + 1].begin();

                                // Crossing if node1 < node2 but dst1 > dst2
                                if (pos1 > pos2) {
                                    crossingCount++;
                                }
                            }
                        }
                    }
                }
            }

            LDBG("  Iteration %d: %d crossings\n", iteration + 1, crossingCount);

            if (crossingCount < bestCrossingCount) {
                bestCrossingCount = crossingCount;
                bestLayers = layers;
            }

            // Early exit if no crossings
            if (crossingCount == 0) {
                LDBG("  No crossings found - stopping early\n");
                break;
            }
        }
    }

    // Use best result
    layers = bestLayers;
    LDBG("Final crossing count: %d\n", bestCrossingCount);

    // Print crossing details per layer pair
    LDBG("\nCrossing breakdown by layer pair:\n");
    for (int layerIdx = 0; layerIdx < maxLayer; layerIdx++) {
        int layerCrossings = 0;
        for (size_t i = 0; i < layers[layerIdx].size(); i++) {
            for (size_t j = i + 1; j < layers[layerIdx].size(); j++) {
                int node1 = layers[layerIdx][i];
                int node2 = layers[layerIdx][j];

                for (int dst1 : outgoing[node1]) {
                    if (nodeLayers[dst1] != layerIdx + 1) continue;
                    auto it1 = std::find(layers[layerIdx + 1].begin(),
                                       layers[layerIdx + 1].end(), dst1);
                    if (it1 == layers[layerIdx + 1].end()) continue;
                    int pos1 = it1 - layers[layerIdx + 1].begin();

                    for (int dst2 : outgoing[node2]) {
                        if (nodeLayers[dst2] != layerIdx + 1) continue;
                        auto it2 = std::find(layers[layerIdx + 1].begin(),
                                           layers[layerIdx + 1].end(), dst2);
                        if (it2 == layers[layerIdx + 1].end()) continue;
                        int pos2 = it2 - layers[layerIdx + 1].begin();

                        if (pos1 > pos2) {
                            layerCrossings++;
                        }
                    }
                }
            }
        }
        if (layerCrossings > 0) {
            LDBG("  Layer %d->%d: %d crossings\n", layerIdx, layerIdx + 1, layerCrossings);
        }
    }

    // Phase 4: Coordinate Assignment (Left-to-Right flow with dynamic widths)
    LDBG("\nPhase 4: Coordinate Assignment\n");
    float layoutPadding = 100.0f;
    float layerSpacing = horizontalSpacing_ * 2.0f;  // More horizontal space between layers

    // First pass: Calculate node sizes and max width per layer
    std::vector<float> maxLayerWidths(layers.size(), 0.0f);
    float dummyNodeWidth = 0.0f;  // Dummy nodes are invisible (zero width)
    float dummyNodeHeight = nodeHeight_;  // Same height as real nodes for consistent spacing

    for (size_t layerIdx = 0; layerIdx < layers.size(); layerIdx++) {
        const auto& layer = layers[layerIdx];
        for (int nodeId : layer) {
            if (nodeId < 0) {
                // Dummy node - invisible, zero width
                outSizes[nodeId] = ImVec2(dummyNodeWidth, dummyNodeHeight);
                LDBG("  Dummy %d: width=%.1f (invisible)\n", nodeId, dummyNodeWidth);
            } else {
                // Real node
                const GraphData::Node* node = nodeById[nodeId];
                float nodeWidth = CalculateNodeWidth(*node);
                outSizes[nodeId] = ImVec2(nodeWidth, nodeHeight_);
                maxLayerWidths[layerIdx] = std::max(maxLayerWidths[layerIdx], nodeWidth);
                LDBG("  Node %d (%s): width=%.1f\n", nodeId, node->name.c_str(), nodeWidth);
            }
        }
    }

    // Second pass: Position nodes horizontally and compute initial vertical positions
    float currentX = layoutPadding;
    std::map<int, float> nodeYPositions;  // Temporary Y positions (will be refined)

    for (size_t layerIdx = 0; layerIdx < layers.size(); layerIdx++) {
        const auto& layer = layers[layerIdx];
        if (layer.empty()) continue;

        // Initial vertical positions (evenly spaced)
        float yStart = layoutPadding;
        for (size_t i = 0; i < layer.size(); i++) {
            int nodeId = layer[i];
            nodeYPositions[nodeId] = yStart + i * (nodeHeight_ + verticalSpacing_);
        }

        // Advance X position
        currentX += maxLayerWidths[layerIdx] + layerSpacing;
    }

    // Phase 3a: Barycenter-based vertical positioning to minimize edge bending
    // Alternate forward/backward passes to position nodes at median Y of neighbors
    LDBG("\nPhase 3a: Vertical Positioning (Barycenter)\n");
    const int NUM_PASSES = 8;  // Number of smoothing iterations
    for (int pass = 0; pass < NUM_PASSES; pass++) {
        bool isForwardPass = (pass % 2 == 0);

        if (isForwardPass) {
            // Forward pass: position based on incoming neighbors (left-to-right)
            for (int layerIdx = 1; layerIdx <= maxLayer; layerIdx++) {
                for (int nodeId : layers[layerIdx]) {
                    std::vector<float> neighborYs;

                    // Collect Y positions of incoming neighbors
                    for (int predId : incoming[nodeId]) {
                        if (nodeYPositions.find(predId) != nodeYPositions.end()) {
                            neighborYs.push_back(nodeYPositions[predId] + nodeHeight_ / 2.0f);
                        }
                    }

                    if (!neighborYs.empty()) {
                        // Position at median of neighbors (robust to outliers)
                        std::sort(neighborYs.begin(), neighborYs.end());
                        float medianY = neighborYs[neighborYs.size() / 2];
                        nodeYPositions[nodeId] = medianY - nodeHeight_ / 2.0f;
                    }
                }

                // Sort layer by Y position and apply spacing constraints (no overlap)
                std::vector<std::pair<float, int>> sortedNodes;
                for (int nodeId : layers[layerIdx]) {
                    sortedNodes.push_back({nodeYPositions[nodeId], nodeId});
                }
                std::sort(sortedNodes.begin(), sortedNodes.end());

                // Apply minimum spacing constraint
                float currentY = layoutPadding;
                for (auto& [oldY, nodeId] : sortedNodes) {
                    nodeYPositions[nodeId] = std::max(nodeYPositions[nodeId], currentY);
                    currentY = nodeYPositions[nodeId] + nodeHeight_ + verticalSpacing_;
                }
            }
        } else {
            // Backward pass: position based on outgoing neighbors (right-to-left)
            for (int layerIdx = maxLayer - 1; layerIdx >= 0; layerIdx--) {
                for (int nodeId : layers[layerIdx]) {
                    std::vector<float> neighborYs;

                    // Collect Y positions of outgoing neighbors
                    for (int succId : outgoing[nodeId]) {
                        if (nodeYPositions.find(succId) != nodeYPositions.end()) {
                            neighborYs.push_back(nodeYPositions[succId] + nodeHeight_ / 2.0f);
                        }
                    }

                    if (!neighborYs.empty()) {
                        // Position at median of neighbors
                        std::sort(neighborYs.begin(), neighborYs.end());
                        float medianY = neighborYs[neighborYs.size() / 2];
                        nodeYPositions[nodeId] = medianY - nodeHeight_ / 2.0f;
                    }
                }

                // Sort layer by Y position and apply spacing constraints
                std::vector<std::pair<float, int>> sortedNodes;
                for (int nodeId : layers[layerIdx]) {
                    sortedNodes.push_back({nodeYPositions[nodeId], nodeId});
                }
                std::sort(sortedNodes.begin(), sortedNodes.end());

                // Apply minimum spacing constraint
                float currentY = layoutPadding;
                for (auto& [oldY, nodeId] : sortedNodes) {
                    nodeYPositions[nodeId] = std::max(nodeYPositions[nodeId], currentY);
                    currentY = nodeYPositions[nodeId] + nodeHeight_ + verticalSpacing_;
                }
            }
        }
    }

    // Third pass: Normalize Y positions so topmost node starts at layoutPadding (top of viewport)
    float minY = 1e9f;
    for (const auto& [nodeId, y] : nodeYPositions) {
        minY = std::min(minY, y);
    }
    float yOffset = layoutPadding - minY;  // Shift to align top node with padding

    // Apply offset to all Y positions
    for (auto& [nodeId, y] : nodeYPositions) {
        y += yOffset;
    }

    // Fourth pass: Assign final X,Y positions
    currentX = layoutPadding;
    for (size_t layerIdx = 0; layerIdx < layers.size(); layerIdx++) {
        const auto& layer = layers[layerIdx];
        if (layer.empty()) continue;

        for (int nodeId : layer) {
            ImVec2 pos;
            pos.x = origin.x + currentX;
            pos.y = origin.y + nodeYPositions[nodeId];
            outPositions[nodeId] = pos;
        }

        // Advance X position by max width in this layer + spacing
        currentX += maxLayerWidths[layerIdx] + layerSpacing;
    }

    return out;
}

LayoutEngine::LayoutResult LayoutEngine::LayoutSubgraph(const GraphData::DataModel& model,
                                                        int parentId, ImVec2 origin) {
    const GraphData::Node* parent = model.GetNode(parentId);
    if (!parent || parent->childNodeIds.empty()) {
        return LayoutResult{};  // nothing to lay out
    }

    // Gather the child nodes.
    std::vector<const GraphData::Node*> children;
    children.reserve(parent->childNodeIds.size());
    std::set<int> childSet(parent->childNodeIds.begin(), parent->childNodeIds.end());
    for (int cid : parent->childNodeIds) {
        const GraphData::Node* c = model.GetNode(cid);
        if (c) children.push_back(c);
    }

    // Internal edges only: connections whose BOTH endpoints are children of this parent.
    // (External edges route to the parent's ports and are handled by the full layout / SPH.)
    std::vector<LayoutEdge> edges;
    for (const auto& conn : model.GetConnections()) {
        if (childSet.count(conn.sourceNodeId) && childSet.count(conn.targetNodeId)) {
            edges.push_back({conn.sourceNodeId, conn.targetNodeId});
        }
    }

    // LayoutNodesInternal clears+rebuilds the member dummy containers, which GetEdgeRoutePoints
    // reads every frame for global edge routing. This subgraph pass would clobber the global
    // dummies (and no full relayout follows an SPH expand to restore them). We don't need the
    // subgraph's dummies anyway, so save the global state and restore it after.
    auto savedDummyNodes   = dummyNodes_;
    auto savedDummyById    = dummyNodeById_;
    int  savedNextDummyId  = nextDummyId_;

    LayoutResult result = LayoutNodesInternal(children, edges, origin);

    dummyNodes_    = std::move(savedDummyNodes);
    dummyNodeById_ = std::move(savedDummyById);
    nextDummyId_   = savedNextDummyId;

    return result;
}

void LayoutEngine::ToggleExpand(int nodeId) {
    if (expandedNodes_.count(nodeId)) {
        expandedNodes_.erase(nodeId);
        expandOrder_.erase(std::remove(expandOrder_.begin(), expandOrder_.end(), nodeId), expandOrder_.end());
        LDBG("LayoutEngine: Node %d collapsed\n", nodeId);
    } else {
        expandedNodes_.insert(nodeId);
        expandOrder_.push_back(nodeId);  // most-recently-expanded -> back (topmost)
        LDBG("LayoutEngine: Node %d expanded\n", nodeId);
    }
}

void LayoutEngine::ExpandNode(int nodeId) {
    if (!expandedNodes_.count(nodeId)) {
        expandedNodes_.insert(nodeId);
        expandOrder_.push_back(nodeId);  // most-recently-expanded -> back (topmost)
    }
    LDBG("LayoutEngine: Node %d expanded\n", nodeId);
}

void LayoutEngine::CollapseNode(int nodeId) {
    expandedNodes_.erase(nodeId);
    expandOrder_.erase(std::remove(expandOrder_.begin(), expandOrder_.end(), nodeId), expandOrder_.end());
    LDBG("LayoutEngine: Node %d collapsed\n", nodeId);
}

int LayoutEngine::GetExpandOrder(int nodeId) const {
    for (size_t i = 0; i < expandOrder_.size(); i++) {
        if (expandOrder_[i] == nodeId) return (int)i;  // higher index = more recent = on top
    }
    return -1;
}

bool LayoutEngine::IsExpanded(int nodeId) const {
    return expandedNodes_.count(nodeId) > 0;
}

std::vector<const GraphData::Node*> LayoutEngine::GetActiveNodes(const GraphData::DataModel& model) const {
    std::vector<const GraphData::Node*> activeNodes;

    // Helper lambda for recursive traversal
    std::function<void(int)> addNodeAndChildren = [&](int nodeId) {
        const GraphData::Node* node = model.GetNode(nodeId);
        if (!node) return;

        // If expanded, REPLACE parent with children (don't add parent)
        if (IsExpanded(nodeId) && node->isExpandable) {
            for (int childId : node->childNodeIds) {
                addNodeAndChildren(childId);
            }
        } else {
            // Not expanded (or not expandable): add this node
            activeNodes.push_back(node);  // Store pointer, not copy!
        }
    };

    // Start with all root nodes (parentId == -1)
    for (size_t i = 0; i < model.GetNodeCount(); i++) {
        const GraphData::Node* node = model.GetNode(i);
        if (node && node->parentId == -1) {
            addNodeAndChildren(node->id);
        }
    }

    return activeNodes;
}

bool LayoutEngine::IsNodeActive(int nodeId, const GraphData::DataModel& model) const {
    const GraphData::Node* node = model.GetNode(nodeId);
    if (!node) return false;

    // Root nodes are always active
    if (node->parentId == -1) return true;

    // Check if all ancestors are expanded
    int currentId = node->parentId;
    while (currentId != -1) {
        const GraphData::Node* parent = model.GetNode(currentId);
        if (!parent) return false;

        if (!IsExpanded(currentId)) return false;  // Parent collapsed, we're hidden

        currentId = parent->parentId;
    }

    return true;  // All ancestors expanded
}

ImVec2 LayoutEngine::GetNodePosition(int nodeId) const {
    auto it = nodePositions_.find(nodeId);
    if (it != nodePositions_.end()) {
        return it->second;
    }
    return ImVec2(0, 0);
}

ImVec2 LayoutEngine::GetNodeSize(int nodeId) const {
    auto it = nodeSizes_.find(nodeId);
    if (it != nodeSizes_.end()) {
        return it->second;
    }
    return ImVec2(nodeWidth_, nodeHeight_);
}

bool LayoutEngine::HasNodePosition(int nodeId) const {
    return nodePositions_.find(nodeId) != nodePositions_.end();
}

ImRect LayoutEngine::GetWorldBounds() const {
    if (nodePositions_.empty()) {
        return ImRect(ImVec2(0, 0), ImVec2(0, 0));
    }

    ImVec2 min(FLT_MAX, FLT_MAX);
    ImVec2 max(-FLT_MAX, -FLT_MAX);

    for (const auto& [id, pos] : nodePositions_) {
        ImVec2 size = nodeSizes_.at(id);

        min.x = std::min(min.x, pos.x);
        min.y = std::min(min.y, pos.y);
        max.x = std::max(max.x, pos.x + size.x);
        max.y = std::max(max.y, pos.y + size.y);
    }

    LDBG("LayoutEngine::GetWorldBounds: Before padding - min=(%.0f, %.0f), max=(%.0f, %.0f)\n",
           min.x, min.y, max.x, max.y);

    // Add padding to the right and bottom edges
    float layoutPadding = 100.0f;
    max.x += layoutPadding;
    max.y += layoutPadding;

    LDBG("LayoutEngine::GetWorldBounds: After padding - min=(%.0f, %.0f), max=(%.0f, %.0f)\n",
           min.x, min.y, max.x, max.y);

    min.x = 0.0f;
    min.y = 0.0f;

    return ImRect(min, max);
}

std::vector<ImVec2> LayoutEngine::GetEdgeRoutePoints(int srcId, int dstId) const {
    std::vector<ImVec2> points;

    // Mode 0: BezierDirect - always return 2 points (ignore dummy nodes)
    if (edgeRenderMode_ == 0) {
        if (HasNodePosition(srcId) && HasNodePosition(dstId)) {
            points.push_back(GetNodePosition(srcId));
            points.push_back(GetNodePosition(dstId));
        }
        return points;
    }

    // For all other modes (Polyline, CatmullRom, BezierChain), use dummy nodes if available
    // Check if this edge has dummy nodes (walk the dummy chain)
    // Look for a dummy with originalSrcId==srcId and originalDstId==dstId
    const DummyNode* firstDummy = nullptr;
    for (const auto& dummy : dummyNodes_) {
        if (dummy.originalSrcId == srcId && dummy.originalDstId == dstId && dummy.prevDummyId == -1) {
            firstDummy = &dummy;
            break;
        }
    }

    if (firstDummy == nullptr) {
        // No dummy chain - direct edge, return just src and dst positions
        if (HasNodePosition(srcId) && HasNodePosition(dstId)) {
            points.push_back(GetNodePosition(srcId));
            points.push_back(GetNodePosition(dstId));
        }
        return points;
    }

    // Dummy chain exists - walk through it
    points.push_back(GetNodePosition(srcId));  // Start at source

    // Walk the chain using nextDummyId links
    int currentDummyId = firstDummy->id;
    while (currentDummyId != -1) {
        if (HasNodePosition(currentDummyId)) {
            points.push_back(GetNodePosition(currentDummyId));
        }

        // Get next dummy in chain
        auto it = dummyNodeById_.find(currentDummyId);
        if (it != dummyNodeById_.end()) {
            currentDummyId = it->second.nextDummyId;
        } else {
            break;  // Chain broken
        }
    }

    points.push_back(GetNodePosition(dstId));  // End at destination

    return points;
}

void LayoutEngine::Clear() {
    nodePositions_.clear();
    nodeSizes_.clear();
}

ImRect LayoutEngine::GetNodeBounds(int nodeId) const {
    if (!HasNodePosition(nodeId)) {
        return ImRect(ImVec2(0, 0), ImVec2(0, 0));
    }
    ImVec2 pos = nodePositions_.at(nodeId);
    ImVec2 size = nodeSizes_.at(nodeId);
    return ImRect(pos, pos + size);
}

std::vector<ImRect> LayoutEngine::GetChangedRegions(const std::map<int, ImVec2>& oldPositions,
                                                     const std::vector<GraphData::Connection>& connections) const {
    std::vector<ImRect> regions;

    // Detect if this is a single-node drag (skip expensive "new nodes" check)
    bool isUpdateADrag = oldPositions.size() == 1;

    //Only iterate through moved nodes
    for (const auto& [id, oldPos] : oldPositions) {
        if (nodePositions_.count(id)) {
            // Node still exists - check if it moved
            ImVec2 newPos = nodePositions_.at(id);
            if (oldPos != newPos) {
                // Node moved - mark both old and new positions dirty
                ImVec2 size = nodeSizes_.at(id);
                regions.push_back(ImRect(oldPos, oldPos + size));
                regions.push_back(ImRect(newPos, newPos + size));
            }
        } else {
            // Node disappeared (was expanded, now collapsed)
            ImVec2 size(nodeWidth_, nodeHeight_);
            regions.push_back(ImRect(oldPos, oldPos + size));
        }
    }

    // Check for newly appeared nodes (were collapsed, now expanded), skipping for single-node drag
    if (!isUpdateADrag) {
        for (const auto& [id, newPos] : nodePositions_) {
            if (!oldPositions.count(id)) {
                // New node appeared
                ImVec2 size = nodeSizes_.at(id);
                regions.push_back(ImRect(newPos, newPos + size));
            }
        }
    }

    // STEP 2: Add edge bounding boxes for all moved nodes
    // This fixes the edge culling bug where edges crossing tiles weren't marked dirty
    for (const auto& [movedNodeId, oldPos] : oldPositions) {
        // Find all connections involving this moved node
        for (const auto& conn : connections) {
            if (conn.sourceNodeId == movedNodeId || conn.targetNodeId == movedNodeId) {
                // Get source and dest positions
                ImVec2 srcPos, dstPos;

                if (nodePositions_.count(conn.sourceNodeId) && nodePositions_.count(conn.targetNodeId)) {
                    srcPos = nodePositions_.at(conn.sourceNodeId);
                    dstPos = nodePositions_.at(conn.targetNodeId);

                    // Calculate edge bounding box (with control point offset ±50)
                    float minX = ImMin(srcPos.x, dstPos.x) - 50.0f;
                    float maxX = ImMax(srcPos.x, dstPos.x) + 50.0f;
                    float minY = ImMin(srcPos.y, dstPos.y);
                    float maxY = ImMax(srcPos.y, dstPos.y);

                    regions.push_back(ImRect(ImVec2(minX, minY), ImVec2(maxX, maxY)));
                }
            }
        }
    }

    return regions;
}

void LayoutEngine::SetGridParameters(float nodeW, float nodeH, float hSpacing, float vSpacing) {
    nodeWidth_ = nodeW;
    nodeHeight_ = nodeH;
    horizontalSpacing_ = hSpacing;
    verticalSpacing_ = vSpacing;
}