summaryrefslogtreecommitdiff
path: root/lib/tsort.rb
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2003-04-21 21:14:08 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2003-04-21 21:14:08 +0000
commit808e9289e6031eba0241e7be159669f8fd0073a3 (patch)
tree194c29d11e24af14890004cf358d5cc8d1406c2d /lib/tsort.rb
parent3939629ddf939e62a5811ffa1f067f0efbc961a6 (diff)
* lib/resolv.rb (Resolv::DNS::Resource#hash): use XOR to accumulate
hash value. * lib/tsort.rb (TSort#each_strongly_connected_component): don't use block argument. (each_strongly_connected_component_from): ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@3710 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib/tsort.rb')
-rw-r--r--lib/tsort.rb26
1 files changed, 22 insertions, 4 deletions
diff --git a/lib/tsort.rb b/lib/tsort.rb
index 7832030..3bf8c33 100644
--- a/lib/tsort.rb
+++ b/lib/tsort.rb
@@ -199,18 +199,20 @@ module TSort
result
end
- def each_strongly_connected_component(&block)
+ def each_strongly_connected_component
id_map = {}
stack = []
tsort_each_node {|node|
unless id_map.include? node
- each_strongly_connected_component_from(node, id_map, stack, &block)
+ each_strongly_connected_component_from(node, id_map, stack) {|c|
+ yield c
+ }
end
}
nil
end
- def each_strongly_connected_component_from(node, id_map={}, stack=[], &block)
+ def each_strongly_connected_component_from(node, id_map={}, stack=[])
minimum_id = node_id = id_map[node] = id_map.size
stack_length = stack.length
stack << node
@@ -221,7 +223,9 @@ module TSort
minimum_id = child_id if child_id && child_id < minimum_id
else
sub_minimum_id =
- each_strongly_connected_component_from(child, id_map, stack, &block)
+ each_strongly_connected_component_from(child, id_map, stack) {|c|
+ yield c
+ }
minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
end
}
@@ -286,6 +290,20 @@ if __FILE__ == $0
assert_equal([[0], [1]],
a.strongly_connected_components.map {|nodes| nodes.sort})
end
+
+ def orphaned_proc(block_str)
+ eval "lambda {#{block_str}}"
+ end
+
+ def test_orphaned_break
+ a = [[1], [2], []]
+ @n = 0
+ x = orphaned_proc %{|c| @n += 1; break :break_value}
+ assert_nothing_raised {
+ assert_equal(:break_value, a.each_strongly_connected_component(&x))
+ }
+ assert_equal(1, @n)
+ end
end
end