14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# File 'lib/ritsu/utility/instance_dependencies.rb', line 14
def dependencies_between(name)
name = name.to_s.singularize
dependency_set_name = "dependency_#{name.pluralize}"
module_eval " attr_reader :\#{dependency_set_name}\n attr_accessor :topological_order\n \n def \#{dependency_set_name}\n @\#{dependency_set_name} ||= Ritsu::Utility::CheckUponAddSet.new do |s,dependency|\n validate_dependency_\#{name}(dependency)\n self.class.invalidate_topological_orders\n end\n end\n \n def depends_directly_on_\#{name}?(instance)\n \#{dependency_set_name}.include?(instance)\n end\n \n def depends_on_\#{name}?(instance)\n visited = Set.new [self]\n queue = [self]\n\n # Perform a breadth first search\n while !visited.include?(instance) && !queue.empty?\n u = queue.shift\n u.\#{dependency_set_name}.each do |v|\n if !visited.include?(v)\n queue << v\n visited << v\n end\n end\n end\n\n visited.delete(self)\n visited.include?(instance)\n end\n \n def validate_dependency_\#{name}(instance)\n instance_name = instance.name\n if instance == self\n raise ArgumentError.new(\"'\\\#{instance.name}' is the same as the dependent \#{name}\")\n end\n if instance.depends_on_\#{name}?(self)\n raise ArgumentError.new(\"including '\\\#{instance.name}' will create a circular dependency\")\n end\n if !instance.can_be_depended_on?\n raise ArgumentError.new(\"'\\\#{instance.name}' cannot be dependend on\")\n end\n end\n \n def self.recompute_topological_orders\n indegrees = {}\n instances.each { |instance| indegrees[instance] = 0 }\n instances.each do |instance|\n instance.\#{dependency_set_name}.each do |dependency|\n indegrees[dependency] += 1\n end\n end\n\n last_order = instances.length-1\n indegree_zero = instances.select { |instance| indegrees[instance] == 0 }\n while !indegree_zero.empty?\n u = indegree_zero.shift\n u.topological_order = last_order\n last_order -= 1\n u.\#{dependency_set_name}.each do |v|\n indegrees[v] -= 1\n if indegrees[v] == 0\n indegree_zero << v\n end\n end\n end\n \n @topological_orders_computed = true\n end\n \n def self.topological_orders_computed?\n @topological_order_computed ||= false\n end\n\n def self.compute_topological_orders\n if !topological_orders_computed?\n recompute_topological_orders\n end\n end\n\n def self.invalidate_topological_orders\n @topological_order_computed = false\n end\n \n def can_be_depended_on?\n raise NotImplementedError.new\n end\n RUBY\nend\n"
|