#### libremiliacr
#### Copyright(C) 2020-2024 Remilia Scarlet <remilia@posteo.jp>
####
#### This program is free software: you can redistribute it and/or modify
#### it under the terms of the GNU General Public License as published
#### the Free Software Foundation, either version 3 of the License, or
#### (at your option) any later version.
####
#### This program is distributed in the hope that it will be useful,
#### but WITHOUT ANY WARRANTY; without even the implied warranty of
#### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
#### GNU General Public License for more details.
####
#### You should have received a copy of the GNU General Public License
#### along with this program.If not, see<http:####www.gnu.org/licenses/.>

module RemiLib
  # A simple way to specify dependencies between items.  This particular
  # implementation does not support circular references.
  module DependencyGraph
    class CircularDependencyError < Exception
    end

    # A single item within a `DependencyGraph`.  This wraps a single data item
    # of type `T`, associating it with a particular name of type `N`.
    #
    # When resolving dependencies, for each item of type `T`, a procedure of
    # type `Proc(N, T, Nil)` will be called.
    class Node(N, T)
      # The name associated with this dependency.
      getter name : N

      # The data associated with this dependency.
      getter data : T

      # The other things that this node depends on.
      getter deps : Array(Node(N, T)) = [] of Node(N, T)

      # Creates a new `Node`.
      def initialize(@name : N, @data : T)
      end

      # Adds a new dependency for this node.  Returns `self`.
      def <<(dep : Node(N, T))
        @deps << dep
        self
      end

      # Resolves the dependencies for this node, then runs `fn`.
      def resolve(fn : Proc(N, T, Nil), resolved : Array(Node(N, T)), seen : Array(Node(N, T))) : Nil
        # Mark this as seen
        seen << self

        # Loop through this node's dependencies
        @deps.each do |dep|
          # Only process nodes that are unresolved
          unless resolved.includes?(dep)
            # Check for circular dependencies
            if seen.includes?(dep)
              raise CircularDependencyError.new("Circular dependency: #{self.name} => #{dep.name}")
            end

            # Resolve the dependency
            dep.resolve(fn, resolved, seen)
          end
        end

        # This node is now resolved
        resolved << self

        # Call the function for processing this node
        fn.call(@name, @data)
      end

      # Resolves the dependencies for this node.  Unlike `#resolve`, this
      # doesn't run anything, and instead is used simply to determine the order
      # of dependency resolution.
      def dryRun(resolved : Array(Node(N, T)), seen : Array(Node(N, T))) : Nil
        # Mark this as seen
        seen << self

        # Loop through this node's dependencies
        @deps.each do |dep|
          # Only process nodes that are unresolved
          unless resolved.includes?(dep)
            # Check for circular dependencies
            if seen.includes?(dep)
              raise CircularDependencyError.new("Circular dependency: #{self.name} => #{dep.name}")
            end

            # Resolve the dependency
            dep.dryRun(resolved, seen)
          end
        end

        # This node is now resolved
        resolved << self
      end
    end

    # Resolves the dependency graph, calling `fn` for each item in the graph in
    # the order of their dependencies.  Returns the number of dependencies that
    # were resolved.
    def self.run(root : Node(N, T), fn : Proc(N, T, Nil)) : Int forall N, T
      seen = [] of Node(N, T)
      resolved = [] of Node(N, T)
      root.resolve(fn, resolved, seen)
    end

    # Resolves the dependency graph, calling `fn` for each item in the graph in
    # the order of their dependencies.  Returns the number of dependencies that
    # were resolved.
    def self.run(fn : Proc(N, T, Nil), *deps : Node(N, T)) : Nil forall N, T
      seen = [] of Node(N, T)
      resolved = [] of Node(N, T)

      deps.each do |dep|
        dep.resolve(fn, resolved, seen)
      end
    end

    # Resolves the dependency graph, calling `fn` for each item in the graph in
    # the order of their dependencies.  Returns the number of dependencies that
    # were resolved.
    def self.run(fn : Proc(N, T, Nil), deps : Array(Node(N, T))) : Nil forall N, T
      seen = [] of Node(N, T)
      resolved = [] of Node(N, T)

      deps.each do |dep|
        dep.resolve(fn, resolved, seen)
      end
    end

    # Resolves the dependency graph, then returns the order for the dependencies
    # as an array of `N`.  Essentially, a dry run.
    def self.getOrder(*deps : Node(N, T)) : Array(N) forall N, T
      seen = [] of Node(N, T)
      resolved = [] of Node(N, T)

      deps.each do |dep|
        dep.dryRun(resolved, seen)
      end

      resolved.map &.name
    end

    # Resolves the dependency graph, then returns the order for the dependencies
    # as an array of `N`.  Essentially, a dry run.
    def self.getOrder(deps : Array(Node(N, T))) : Array(N) forall N, T
      seen = [] of Node(N, T)
      resolved = [] of Node(N, T)

      deps.each do |dep|
        dep.dryRun(resolved, seen)
      end

      resolved.map &.name
    end
  end
end
