From: Robert Klemme <shortcutter@...>
Date: 2009-11-26T19:16:40+09:00
Subject: Re: Difference between << and += for Strings and Arrays. Bug?

2009/11/26 Robert Klemme <shortcutter@googlemail.com>:
> As far as I can see you only need an inclusion check not the complete
> list of ancestors.  A simple iterative solution with a BFS could do
> the job for you

Here's a more modularized version:

require 'set'

def ancestor_bfs
 visited = Set.new
 queue = [self]

 until queue.empty?
   n = queue.shift

   if visited.add? n
     yield n
     queue.concat(n.ancestors)
   end
 end

 false
end

def ancestor?(candidate)
  ancestor_bfs {|n| return true if candidate == n}
  false
end

# or even without a method but still fast exit when the node is found:
folder.to_enum(:ancestor_bfs).any? {|n| candidate == n}

# fully modularized

def bfs(next_meth, start = self)
 visited = Set.new
 queue = [start]

 until queue.empty?
   n = queue.shift

   if visited.add? n
     yield n
     queue.concat(n.send(next_meth))
   end
 end

 false
end

def bfs_ancestors(&b)
  bfs(:ancestors, &b)
end

Now you can do

class Integer
  def n; [self * 2, self * 2 + 1] end
end

irb(main):057:0> bfs(:n, 3) {|x| p x; break if x > 20}
3
6
7
12
13
14
15
24
=> nil
irb(main):058:0>

:-)

Cheers

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/