/**
 * @author      Justus van den Berg (jfwberg@gmail.com)
 * @date        May 2022
 * @copyright   (c) 2024 Justus van den Berg
 * @license     MIT (See LICENSE file in the project root)
 * @description Class contains a basic topological (graph) sort algorithm for Apex
 *              It's not 100% perfect, but does the job for most simple graph sorts.
 *              It has two additional methods, one for creating an ordered list of all
 *              nodes in the graph sorted by dependency and a second one to create
 *              a report of any errors or issues with the graph
 *
 * @use case    The main use case is to sort sObjects and their relationships to create
 *              the order of loading during data migrations or data restores
 * 
 * @relatedCode https://www.thiscodeworks.com/salesforce-apex-get-all-sobjects-with-data-and-sort-them-topologically/66fdbe1192e2590014ee4673
 * @blog        https://medium.com/@justusvandenberg/programmatically-find-the-order-to-load-salesforce-objects-in-a-data-migration-using-apex-1f65841531fb
 */
@SuppressWarnings('PMD.ExcessiveParameterList')
public with sharing class SortUtil {
 
    // Warning message templates
    private static final String SELF_DEPENDENCY_WARNING	   = 'Node "{0}" has a dependency on itself';
    private static final String DUO_DEPENDENCY_WARNING	   = 'Node "{0}" and "{1}" have a dependency on each other.';
    private static final String CYL_DEPENDENCY_WARNING	   = 'Node "{0}" has a cylindrical relationship on path "{1}".';
    private static final String MISSING_DEPENDENCY_WARNING = 'Node "{0}" depends on node "{1}" but Node "{1}" does not exist in the dependencies Map';
 
    // Create a map to hold any warnings
    private static Map<Object, String[]> warningMap = new Map<Object, String[]>();
 
 
    /**
     * @description Sort a graph topologically
     * @param nodeDependenciesMap the map containing the node and all of it's dependencies
     * @return      A sorted list of the nodes based on the dependency
     */
    public static Set<Node> topologicalSort(Map<Object,Set<Object>> nodeDependenciesMap){
        
        // Validate graph first to create the initial warning messages
        // Execute the topological sorting and return the details
        return new TopologicalSort(
            nodeDependenciesMap,
            validateGraph(nodeDependenciesMap)
        ).getSortedResult();
    }
 
 
    /**
     * @description A methods that analyses the data map and generates
     *              warnings for missing, circular or self dependencies
     * @param nodeDependenciesMap The main node/dependencies map
     * @return      A map with (potential) warnings for each node
     */
    private static Map<Object, String[]> validateGraph(Map<Object,Set<Object>> nodeDependenciesMap){
 
        // Iterate each node
        for(Object node : nodeDependenciesMap.keySet()){
 
            for(Object dependency : nodeDependenciesMap.get(node)){
 
                // If a referenced dependency does not exist in the data map add a warning
                if(!nodeDependenciesMap.containsKey(dependency)){
                    addWarning(
                        node, 
                        String.format(MISSING_DEPENDENCY_WARNING, new String[]{
                            node.toString(),
                            dependency.toString()
                        })
                    );
                    
                    // If the depended node does not exists in the data map there is no point to check for self or circular dependencies
                    // so continue to the next dependency
                    continue;
                }
 
                // If there is a dependency to the same node, add a warning
                if(node == dependency){
                    addWarning(
                        node,
                        String.format(
                            SELF_DEPENDENCY_WARNING,
                            new String[]{node.toString()}
                        )
                    );
 
                    // If the depended node is self referencing, there is no need to look for a duo dependency as
                    // technically it already is a duo reference
                    continue;
                }
                    
                // If there is a duo dependency between the dependency and the node, add a warning message (ie they point at each other)
                if(nodeDependenciesMap.get(dependency).contains(node)){
                    addWarning(
                        node,
                        String.format(
                            DUO_DEPENDENCY_WARNING,
                            new String[]{node.toString(),dependency.toString()}
                        )
                    );
                }
            }
        }
        return warningMap;
    }
 
 
    /**
     * @description Method that adds a warning to a specific node in the warning maps
     * @param node       The node object
     * @param warning    The warning message
     */
    private static void addWarning(Object node, String warning){
        
        // Create new map entry if it doesn't exist
        if(!warningMap.containsKey(node)){
           warningMap.put(node,new String[]{});
        }
 
        // Add warning to the map
        warningMap.get(node).add(warning);
    }
 
 
    /**
     * description Class to perform a topological sort
     */
    private with sharing class TopologicalSort{
        
        // Start the order for the nodes. We use a zro index so start at -1
        private Integer nodeOrder = -1;
 
        // A set with the sorted result
        private transient Set<Node> sortedResult = new Set<Node>{};
 
        // The map containing the warnings
        private transient Map<Object, String[]> warningsMap = new Map<Object, String[]>();
 
 
        /**
         * @description Constructor that that the map with nodes and their dependencies
         * @param nodeDependenciesMap The main input node / dependencies map
         * @param warningsMap         The map containing the warning messages
         */
        private TopologicalSort(Map<Object, Set<Object>> nodeDependenciesMap, Map<Object, String[]> warningsMap){
            
            // Assign the warning map
            this.warningsMap = warningsMap;
 
            // Start the sorting
            visit(
                nodeDependenciesMap,
                nodeDependenciesMap.keySet(),
                new Set<Object>{},
                new Set<Object>{},
                ''
            );
        }
 
 
        /**
         * @description Method to get the sorted results
         * @return The result from the topological sort
         */
        private Set<Node> getSortedResult(){
            return this.sortedResult;
        }
 
 
        /**
         * @description Method to pass through i.e. visit each node in the graph
         * @param nodeDependenciesMap The main map with the nodes and their dependencies
         * @param dependencies        The dependencies for this specific node
         * @param dead                Set with nodes that have been visited
         * @param pending             Set with nodes that have not been visited
         * @param nodePath            The path that has led to the node
         */
        @SuppressWarnings('PMD.CognitiveComplexity')
        private void visit(Map<Object,Set<Object>> nodeDependenciesMap, Set<Object> dependencies, Set<Object> dead, Set<Object> pending, String nodePath ){
            
            // If there are no dependencies nothing needs to happen
            if(dependencies == null){return;}
            
            // Check all dependencies for this node
            for(Object node : dependencies){
 
                String childNodePath = nodePath + (!String.isBlank(nodePath) ? + '.' : '') + node;
                
                // If the node has not been visited before
                if(!dead.contains(node)){
                    if (!pending.contains(node)){
                        pending.add(node);
                    }else{
                        // Circular relationship
                        addWarning(
                            node,
                            String.format(
                                CYL_DEPENDENCY_WARNING,
                                new String[]{node.toString(),childNodePath}
                            )
                        );
                        return;
                    }
 
                    // recursively call this function for every child of the current node
                    visit(nodeDependenciesMap, nodeDependenciesMap.get(node), dead, pending, childNodePath);
 
                    // If the node is still pending, remove it
                    if (pending.contains(node)){
                        pending.remove(node);
                    }
 
                    // Indicate that this node has been visited
                    dead.add(node);
 
                    // Increment the order, it starts at -1, so the first node will be 0
                    this.nodeOrder++;
 
                    // Add the node to the end of the sorted list
                    this.sortedResult.add(new Node(
                        this.nodeOrder,
                        node,
                        childNodePath.split('\\.').size() -1,
                        childNodePath,
                        this.warningsMap.get(node)
                    ));   
                }
            }
        }
    }
 
 
    /**
     * @description Class that represents a node in a graph that can be topologically sorted
     */
    @SuppressWarnings('PMD.ExcessiveParameterList')
    public with sharing class Node implements comparable{
        
        // Public variables
        public Integer  order;
        public Object   node;
        public Integer  depth;
        public String   path;
        public String[] warnings;
 
        /**
         * @description The main constructor
         * @param order     The order in the graph
         * @param node      The node itself
         * @param depth     The node depth
         * @param path      The path it took to get to the node
         * @param warnings  List of warnings for the node
         */
        
        public Node(Integer order, Object node, Integer depth, String path, String[] warnings){
            this.order    = order;
            this.node     = node;
            this.depth    = depth;
            this.path     = path;
            this.warnings = warnings;
        }
 
        /**
         * @description Interface for compare method to sort based on order
         * @param compareTo The Node to compare against
         * @return      -1,0 or 1
         */
        public Integer compareTo (Object compareTo) {
            return (this.order > ((Node)compareTo).order) ? 1 : (this.order < ((Node)compareTo).order) ? -1 : 0;
        }
    }
}