GraphQueueLogic.swift

//
//  GraphQueueLogic.swift
//
//
//  Created by Elliot Boschwitz on 6/8/24.
//

import Foundation

extension GraphTopologicalData {
    /// Finds non-cycle entry points into a cycle.
    func getNonCycleEntryNodes(to cycleNodeId: Node.ID) -> Set<Node.ID> {
        var connectedCycleNodes = self.getAllConnectedCycleNodes(to: cycleNodeId)
        connectedCycleNodes.insert(cycleNodeId)
        
        let nodes = connectedCycleNodes.flatMap { cycleNodeId in
            let directUpstreamNodes = self.findDirectlyConnectedUpstreamNodes(from: cycleNodeId)
            
            // Filter out cycle nodes to get non-cycle entry points
            return directUpstreamNodes.filter { !self.cycleContains($0) }
        }
        
        return Set(nodes)
    }

    mutating func getNextNodeToCalculate(for nodeIds: Set<Node.ID>,
                                         visitedNodes: Set<Node.ID>,
                                         willResetCyclePreferences: Bool) -> Node.ID? {
        if let nextNodeId = self.memoizedQueues[nodeIds] {
            return nextNodeId
        }

        // Cache ordered list for this set
        guard let nextNodeId = self.findNextNodeInGraphCalc(queuedNodeIds: nodeIds,
                                                            visitedNodes: visitedNodes,
                                                            willResetCyclePreferences: willResetCyclePreferences) else {
            return nil
        }
        
        self.memoizedQueues.updateValue(nextNodeId, forKey: nodeIds)
        return nextNodeId
    }
    
    /// Determines which node to priotize next in a graph calculation.
    /// In a node calculation, there must always be at least one node amongst a set which won't contain an upstream path
    /// from the other nodes. Therefore we can pick any node matching that criteria.
    /// The only exception is if the remaining nodes contain a cycle at its root.
    private mutating func findNextNodeInGraphCalc(queuedNodeIds: Set<Node.ID>,
                                                  visitedNodes: Set<Node.ID>,
                                                  willResetCyclePreferences: Bool) -> Node.ID? {
        if queuedNodeIds.isEmpty {
//#if DEV_DEBUG
//        log("TopologicalData.findNextNodeInGraphCalc: none")
//#endif
            return nil
        }
        
        // First check for a natural root node. If none, there must be an usptream cycle
        // preventing us from finding a natural root node.
        guard let nextNode = self.findNextNodeInDAG(queuedNodeIds: queuedNodeIds,
                                                    visitedNodes: visitedNodes) else {
            let cycleNode = self.findNextNodeInCycle(queuedNodeIds: queuedNodeIds,
                                                     visitedNodes: visitedNodes,
                                                     willResetCyclePreferences: willResetCyclePreferences)
            
//#if DEV_DEBUG
//        log("TopologicalData.findNextNodeInGraphCalc: cycle node \(cycleNode)")
//#endif
            return cycleNode
        }
        
//#if DEV_DEBUG
//        log("TopologicalData.findNextNodeInGraphCalc: non-cycle node \(nextNode)")
//#endif
        return nextNode
    }
    
    private mutating func findNextNodeInDAG(queuedNodeIds: Set<Node.ID>,
                                            visitedNodes: Set<Node.ID>) -> Node.ID? {
        for queuedNodeId in queuedNodeIds.sorted() {
            let allUpstreamParents = self.getAllUpstreamNodes(from: queuedNodeId)
            
            // Any node without matching upstream parents will work for the next node
            if allUpstreamParents.intersection(queuedNodeIds).isEmpty {
                return queuedNodeId
            }
        }
        
        // Return nil if no matches
        return nil
    }
        
    /// Fallback logic that runs if there's no natural root node amongst a set of node IDs.
    /// Logic runs as follows:
    /// 1. First prioritize cycle nodes with the fewest upstream parents amongst the other nodes in the set. This guarantees
    ///  grabbing the upstream-most cycle in the event there are multiple cycles encountered.
    /// 2. Tiebreakers resort to leveraging nodes in a cycle containing a direct connection to a node that was already visited
    ///  in a graph. This ensures cycle calculation starts at the "red edge".
    private mutating func findNextNodeInCycle(queuedNodeIds: Set<Node.ID>,
                                              visitedNodes: Set<Node.ID>,
                                              willResetCyclePreferences: Bool) -> Node.ID? {
        // There are cycle nodes involved if the above condition isn't hit. We'll prioritize
        // the cycle node with the fewest matching upstream parents to other nodes in the set.
        // Doing so guarantees the upstream-most cycle will be computed first.
        let allNodesInCycles = self.nodeCycles
            .flatMap { $0 }
        
        let sortedCycleNodes = Set(queuedNodeIds
            .filter { allNodesInCycles.contains($0) }
        // Sort by fewest matching upstream parents to queue
            .sorted { lhs, rhs in
                let lhsUpstreamParents = self.getAllUpstreamNodes(from: lhs).intersection(queuedNodeIds).count
                let rhsUpstreamParents = self.getAllUpstreamNodes(from: rhs).intersection(queuedNodeIds).count
                let isEqual  = lhsUpstreamParents == rhsUpstreamParents
                
                // otherwise use hash for consistent results
                return isEqual ? lhs.hashValue < rhs.hashValue : lhsUpstreamParents < rhsUpstreamParents
            }
        // Another sorting to guarantee consistent results
            .sorted())
        
        // Prioritize nodes in cycle which contain direct upstream parent to visited node
        // in this cycle (aka the "red edge")
        let connectedUpstreamCycleNodes = Set(sortedCycleNodes
            .filter {
                // Look for directly connected upstream node to cycle node
                let directUpstreamNodes = self.findDirectlyConnectedUpstreamNodes(from: $0)
                let containsUpstreamVisitedNode = !visitedNodes.intersection(directUpstreamNodes).isEmpty
                return containsUpstreamVisitedNode
            })
        
        let candidateRootCycleNodes = connectedUpstreamCycleNodes.isEmpty ? sortedCycleNodes : connectedUpstreamCycleNodes
        
        // Lazily update candidate root cycle nodes, which gets reset with updateTopologicalData fn
        self.allCandidateRootCycleNodes = self.allCandidateRootCycleNodes.union(candidateRootCycleNodes)
        
        let cycleNode = self.getCandidateRootCycleNode(candidates: candidateRootCycleNodes,
                                                       isMutating: willResetCyclePreferences)
        
#if DEV_DEBUG
        // log("TopologicalData.findNextNodeInGraphCalc: cycle node detected at \(cycleNode)")
#endif
        
        return cycleNode
    }
    
    mutating func getCandidateRootCycleNode(candidates: Set<Node.ID>,
                                            isMutating: Bool) -> Node.ID? {
        let previousMatchingCandidates = self.preferredRootCycleNodes.intersection(candidates)
        
        // Arbitrarily select first amongst multiple possible options
        guard let selection = previousMatchingCandidates.first else {
            // No preference made yet
            guard let newSelection = candidates.first else {
                // No candidates at all
                return nil
            }
            
            if isMutating {
                self.preferredRootCycleNodes.insert(newSelection)
            }
            return newSelection
        }
        
        // If multiple matches, remove all but first
        if isMutating && previousMatchingCandidates.count > 1 {
            var preferencesToRemove = previousMatchingCandidates
            preferencesToRemove.remove(selection)
            self.preferredRootCycleNodes = self.preferredRootCycleNodes.subtracting(preferencesToRemove)
        }
        
        return selection
    }
}