Migrate tsort as bundled gems

2 files changed, 0 insertions, 492 deletions

diff --git a/lib/tsort.gemspec b/lib/tsort.gemspec
deleted file mode 100644
index 4e0ef0507d..0000000000
--- a/lib/tsort.gemspec
+++ /dev/null
@@ -1,35 +0,0 @@
-name = File.basename(__FILE__, ".gemspec")
-version = ["lib", Array.new(name.count("-")+1).join("/")].find do |dir|
-  break File.foreach(File.join(__dir__, dir, "#{name.tr('-', '/')}.rb")) do |line|
-    /^\s*VERSION\s*=\s*"(.*)"/ =~ line and break $1
-  end rescue nil
-end
-
-Gem::Specification.new do |spec|
-  spec.name          = name
-  spec.version       = version
-  spec.authors       = ["Tanaka Akira"]
-  spec.email         = ["akr@fsij.org"]
-
-  spec.summary       = %q{Topological sorting using Tarjan's algorithm}
-  spec.description   = %q{Topological sorting using Tarjan's algorithm}
-  spec.homepage      = "https://github.com/ruby/tsort"
-  spec.required_ruby_version = Gem::Requirement.new(">= 2.3.0")
-  spec.licenses      = ["Ruby", "BSD-2-Clause"]
-
-  spec.metadata["homepage_uri"] = spec.homepage
-  spec.metadata["source_code_uri"] = spec.homepage
-  spec.metadata["changelog_uri"] = "#{spec.homepage}/releases"
-
-  dir, gemspec = File.split(__FILE__)
-  excludes = %W[
-    :^/.git* :^/bin/ :^/test/ :^/spec/ :^/features/ :^/Gemfile :^/Rakefile
-    :^/#{gemspec}
-  ]
-  spec.files = IO.popen(%w[git ls-files -z --] + excludes, chdir: dir) do |f|
-    f.read.split("\x0")
-  end
-  spec.bindir        = "exe"
-  spec.executables   = spec.files.grep(%r{^exe/}) { |f| File.basename(f) }
-  spec.require_paths = ["lib"]
-end
diff --git a/lib/tsort.rb b/lib/tsort.rb
deleted file mode 100644
index 3c9635baa3..0000000000
--- a/lib/tsort.rb
+++ /dev/null
@@ -1,457 +0,0 @@
-# frozen_string_literal: true
-
-#--
-# tsort.rb - provides a module for topological sorting and strongly connected components.
-#++
-#
-
-#
-# TSort implements topological sorting using Tarjan's algorithm for
-# strongly connected components.
-#
-# TSort is designed to be able to be used with any object which can be
-# interpreted as a directed graph.
-#
-# TSort requires two methods to interpret an object as a graph,
-# tsort_each_node and tsort_each_child.
-#
-# * tsort_each_node is used to iterate for all nodes over a graph.
-# * tsort_each_child is used to iterate for child nodes of a given node.
-#
-# The equality of nodes are defined by eql? and hash since
-# TSort uses Hash internally.
-#
-# == A Simple Example
-#
-# The following example demonstrates how to mix the TSort module into an
-# existing class (in this case, Hash). Here, we're treating each key in
-# the hash as a node in the graph, and so we simply alias the required
-# #tsort_each_node method to Hash's #each_key method. For each key in the
-# hash, the associated value is an array of the node's child nodes. This
-# choice in turn leads to our implementation of the required #tsort_each_child
-# method, which fetches the array of child nodes and then iterates over that
-# array using the user-supplied block.
-#
-#   require 'tsort'
-#
-#   class Hash
-#     include TSort
-#     alias tsort_each_node each_key
-#     def tsort_each_child(node, &block)
-#       fetch(node).each(&block)
-#     end
-#   end
-#
-#   {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
-#   #=> [3, 2, 1, 4]
-#
-#   {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
-#   #=> [[4], [2, 3], [1]]
-#
-# == A More Realistic Example
-#
-# A very simple `make' like tool can be implemented as follows:
-#
-#   require 'tsort'
-#
-#   class Make
-#     def initialize
-#       @dep = {}
-#       @dep.default = []
-#     end
-#
-#     def rule(outputs, inputs=[], &block)
-#       triple = [outputs, inputs, block]
-#       outputs.each {|f| @dep[f] = [triple]}
-#       @dep[triple] = inputs
-#     end
-#
-#     def build(target)
-#       each_strongly_connected_component_from(target) {|ns|
-#         if ns.length != 1
-#           fs = ns.delete_if {|n| Array === n}
-#           raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
-#         end
-#         n = ns.first
-#         if Array === n
-#           outputs, inputs, block = n
-#           inputs_time = inputs.map {|f| File.mtime f}.max
-#           begin
-#             outputs_time = outputs.map {|f| File.mtime f}.min
-#           rescue Errno::ENOENT
-#             outputs_time = nil
-#           end
-#           if outputs_time == nil ||
-#              inputs_time != nil && outputs_time <= inputs_time
-#             sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
-#             block.call
-#           end
-#         end
-#       }
-#     end
-#
-#     def tsort_each_child(node, &block)
-#       @dep[node].each(&block)
-#     end
-#     include TSort
-#   end
-#
-#   def command(arg)
-#     print arg, "\n"
-#     system arg
-#   end
-#
-#   m = Make.new
-#   m.rule(%w[t1]) { command 'date > t1' }
-#   m.rule(%w[t2]) { command 'date > t2' }
-#   m.rule(%w[t3]) { command 'date > t3' }
-#   m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
-#   m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
-#   m.build('t5')
-#
-# == Bugs
-#
-# * 'tsort.rb' is wrong name because this library uses
-#   Tarjan's algorithm for strongly connected components.
-#   Although 'strongly_connected_components.rb' is correct but too long.
-#
-# == References
-#
-# R. E. Tarjan, "Depth First Search and Linear Graph Algorithms",
-# <em>SIAM Journal on Computing</em>, Vol. 1, No. 2, pp. 146-160, June 1972.
-#
-
-module TSort
-
-  # The version string.
-  VERSION = "0.2.0"
-
-  # Exception class to be raised when a cycle is found.
-  class Cyclic < StandardError
-  end
-
-  # Returns a topologically sorted array of nodes.
-  # The array is sorted from children to parents, i.e.
-  # the first element has no child and the last node has no parent.
-  #
-  # If there is a cycle, TSort::Cyclic is raised.
-  #
-  #   class G
-  #     include TSort
-  #     def initialize(g)
-  #       @g = g
-  #     end
-  #     def tsort_each_child(n, &b) @g[n].each(&b) end
-  #     def tsort_each_node(&b) @g.each_key(&b) end
-  #   end
-  #
-  #   graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
-  #   p graph.tsort #=> [4, 2, 3, 1]
-  #
-  #   graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
-  #   p graph.tsort # raises TSort::Cyclic
-  #
-  def tsort
-    each_node = method(:tsort_each_node)
-    each_child = method(:tsort_each_child)
-    TSort.tsort(each_node, each_child)
-  end
-
-  # Returns a topologically sorted array of nodes.
-  # The array is sorted from children to parents, i.e.
-  # the first element has no child and the last node has no parent.
-  #
-  # The graph is represented by _each_node_ and _each_child_.
-  # _each_node_ should have +call+ method which yields for each node in the graph.
-  # _each_child_ should have +call+ method which takes a node argument and yields for each child node.
-  #
-  # If there is a cycle, TSort::Cyclic is raised.
-  #
-  #   g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   p TSort.tsort(each_node, each_child) #=> [4, 2, 3, 1]
-  #
-  #   g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   p TSort.tsort(each_node, each_child) # raises TSort::Cyclic
-  #
-  def self.tsort(each_node, each_child)
-    tsort_each(each_node, each_child).to_a
-  end
-
-  # The iterator version of the #tsort method.
-  # <tt><em>obj</em>.tsort_each</tt> is similar to <tt><em>obj</em>.tsort.each</tt>, but
-  # modification of _obj_ during the iteration may lead to unexpected results.
-  #
-  # #tsort_each returns +nil+.
-  # If there is a cycle, TSort::Cyclic is raised.
-  #
-  #   class G
-  #     include TSort
-  #     def initialize(g)
-  #       @g = g
-  #     end
-  #     def tsort_each_child(n, &b) @g[n].each(&b) end
-  #     def tsort_each_node(&b) @g.each_key(&b) end
-  #   end
-  #
-  #   graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
-  #   graph.tsort_each {|n| p n }
-  #   #=> 4
-  #   #   2
-  #   #   3
-  #   #   1
-  #
-  def tsort_each(&block) # :yields: node
-    each_node = method(:tsort_each_node)
-    each_child = method(:tsort_each_child)
-    TSort.tsort_each(each_node, each_child, &block)
-  end
-
-  # The iterator version of the TSort.tsort method.
-  #
-  # The graph is represented by _each_node_ and _each_child_.
-  # _each_node_ should have +call+ method which yields for each node in the graph.
-  # _each_child_ should have +call+ method which takes a node argument and yields for each child node.
-  #
-  #   g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   TSort.tsort_each(each_node, each_child) {|n| p n }
-  #   #=> 4
-  #   #   2
-  #   #   3
-  #   #   1
-  #
-  def self.tsort_each(each_node, each_child) # :yields: node
-    return to_enum(__method__, each_node, each_child) unless block_given?
-
-    each_strongly_connected_component(each_node, each_child) {|component|
-      if component.size == 1
-        yield component.first
-      else
-        raise Cyclic.new("topological sort failed: #{component.inspect}")
-      end
-    }
-  end
-
-  # Returns strongly connected components as an array of arrays of nodes.
-  # The array is sorted from children to parents.
-  # Each elements of the array represents a strongly connected component.
-  #
-  #   class G
-  #     include TSort
-  #     def initialize(g)
-  #       @g = g
-  #     end
-  #     def tsort_each_child(n, &b) @g[n].each(&b) end
-  #     def tsort_each_node(&b) @g.each_key(&b) end
-  #   end
-  #
-  #   graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
-  #   p graph.strongly_connected_components #=> [[4], [2], [3], [1]]
-  #
-  #   graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
-  #   p graph.strongly_connected_components #=> [[4], [2, 3], [1]]
-  #
-  def strongly_connected_components
-    each_node = method(:tsort_each_node)
-    each_child = method(:tsort_each_child)
-    TSort.strongly_connected_components(each_node, each_child)
-  end
-
-  # Returns strongly connected components as an array of arrays of nodes.
-  # The array is sorted from children to parents.
-  # Each elements of the array represents a strongly connected component.
-  #
-  # The graph is represented by _each_node_ and _each_child_.
-  # _each_node_ should have +call+ method which yields for each node in the graph.
-  # _each_child_ should have +call+ method which takes a node argument and yields for each child node.
-  #
-  #   g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   p TSort.strongly_connected_components(each_node, each_child)
-  #   #=> [[4], [2], [3], [1]]
-  #
-  #   g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   p TSort.strongly_connected_components(each_node, each_child)
-  #   #=> [[4], [2, 3], [1]]
-  #
-  def self.strongly_connected_components(each_node, each_child)
-    each_strongly_connected_component(each_node, each_child).to_a
-  end
-
-  # The iterator version of the #strongly_connected_components method.
-  # <tt><em>obj</em>.each_strongly_connected_component</tt> is similar to
-  # <tt><em>obj</em>.strongly_connected_components.each</tt>, but
-  # modification of _obj_ during the iteration may lead to unexpected results.
-  #
-  # #each_strongly_connected_component returns +nil+.
-  #
-  #   class G
-  #     include TSort
-  #     def initialize(g)
-  #       @g = g
-  #     end
-  #     def tsort_each_child(n, &b) @g[n].each(&b) end
-  #     def tsort_each_node(&b) @g.each_key(&b) end
-  #   end
-  #
-  #   graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
-  #   graph.each_strongly_connected_component {|scc| p scc }
-  #   #=> [4]
-  #   #   [2]
-  #   #   [3]
-  #   #   [1]
-  #
-  #   graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
-  #   graph.each_strongly_connected_component {|scc| p scc }
-  #   #=> [4]
-  #   #   [2, 3]
-  #   #   [1]
-  #
-  def each_strongly_connected_component(&block) # :yields: nodes
-    each_node = method(:tsort_each_node)
-    each_child = method(:tsort_each_child)
-    TSort.each_strongly_connected_component(each_node, each_child, &block)
-  end
-
-  # The iterator version of the TSort.strongly_connected_components method.
-  #
-  # The graph is represented by _each_node_ and _each_child_.
-  # _each_node_ should have +call+ method which yields for each node in the graph.
-  # _each_child_ should have +call+ method which takes a node argument and yields for each child node.
-  #
-  #   g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc }
-  #   #=> [4]
-  #   #   [2]
-  #   #   [3]
-  #   #   [1]
-  #
-  #   g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
-  #   each_node = lambda {|&b| g.each_key(&b) }
-  #   each_child = lambda {|n, &b| g[n].each(&b) }
-  #   TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc }
-  #   #=> [4]
-  #   #   [2, 3]
-  #   #   [1]
-  #
-  def self.each_strongly_connected_component(each_node, each_child) # :yields: nodes
-    return to_enum(__method__, each_node, each_child) unless block_given?
-
-    id_map = {}
-    stack = []
-    each_node.call {|node|
-      unless id_map.include? node
-        each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
-          yield c
-        }
-      end
-    }
-    nil
-  end
-
-  # Iterates over strongly connected component in the subgraph reachable from
-  # _node_.
-  #
-  # Return value is unspecified.
-  #
-  # #each_strongly_connected_component_from doesn't call #tsort_each_node.
-  #
-  #   class G
-  #     include TSort
-  #     def initialize(g)
-  #       @g = g
-  #     end
-  #     def tsort_each_child(n, &b) @g[n].each(&b) end
-  #     def tsort_each_node(&b) @g.each_key(&b) end
-  #   end
-  #
-  #   graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
-  #   graph.each_strongly_connected_component_from(2) {|scc| p scc }
-  #   #=> [4]
-  #   #   [2]
-  #
-  #   graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
-  #   graph.each_strongly_connected_component_from(2) {|scc| p scc }
-  #   #=> [4]
-  #   #   [2, 3]
-  #
-  def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes
-    TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block)
-  end
-
-  # Iterates over strongly connected components in a graph.
-  # The graph is represented by _node_ and _each_child_.
-  #
-  # _node_ is the first node.
-  # _each_child_ should have +call+ method which takes a node argument
-  # and yields for each child node.
-  #
-  # Return value is unspecified.
-  #
-  # #TSort.each_strongly_connected_component_from is a class method and
-  # it doesn't need a class to represent a graph which includes TSort.
-  #
-  #   graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
-  #   each_child = lambda {|n, &b| graph[n].each(&b) }
-  #   TSort.each_strongly_connected_component_from(1, each_child) {|scc|
-  #     p scc
-  #   }
-  #   #=> [4]
-  #   #   [2, 3]
-  #   #   [1]
-  #
-  def self.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
-    return to_enum(__method__, node, each_child, id_map, stack) unless block_given?
-
-    minimum_id = node_id = id_map[node] = id_map.size
-    stack_length = stack.length
-    stack << node
-
-    each_child.call(node) {|child|
-      if id_map.include? child
-        child_id = id_map[child]
-        minimum_id = child_id if child_id && child_id < minimum_id
-      else
-        sub_minimum_id =
-          each_strongly_connected_component_from(child, each_child, id_map, stack) {|c|
-            yield c
-          }
-        minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
-      end
-    }
-
-    if node_id == minimum_id
-      component = stack.slice!(stack_length .. -1)
-      component.each {|n| id_map[n] = nil}
-      yield component
-    end
-
-    minimum_id
-  end
-
-  # Should be implemented by a extended class.
-  #
-  # #tsort_each_node is used to iterate for all nodes over a graph.
-  #
-  def tsort_each_node # :yields: node
-    raise NotImplementedError.new
-  end
-
-  # Should be implemented by a extended class.
-  #
-  # #tsort_each_child is used to iterate for child nodes of _node_.
-  #
-  def tsort_each_child(node) # :yields: child
-    raise NotImplementedError.new
-  end
-end