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

2009/11/26 Pieter Hugo <pieter@internext.co.za>:
> Hi Robert (and everyone else) - thanks for the well reasoned responses.
> I'll get the hang of it I'm sure
>
>> Why do you want to have two copies of your Array?
>
> I have a setup where I have Folder objects. A folder can have many other
> children (members) as sub folders, but it can also have many other
> folders as parents (groups it belongs to). I get this done via a
> crosslink table. When creating a new parent-child relationship I need to
> make sure that the child is not somehow an ancestor or the parent I am
> trying to subordinate it to (as I need to avoid circular reference)
>
> So I wrote the folder function:
>
>  def ancestors
>    ancestors = self.groups  #all the immediate parents are obviously
> ancestors
>  scanfolders = [] #set up a stack to iterate through,
>                         #looking for grandparents etc
>  scanfolders += ancestors #the stack starts with the current ancestors
>  if !scanfolders.nil? then
>    while scanfolders.length > 0 do # while there are items on the stack
>      scanitem = scanfolders.pop # get the last one and reduce the stack
>      if scanitem then
>        if !scanitem.groups.nil? then #if this item has parents
>                                            #add them to the stack
>         scanfolders += scanitem.groups
>         scanfolders.uniq!
>         ancestors += scanitem.groups #and record this item as an
>                                            #ancestor
>         ancestors.uniq!
>        end
>      end
>    end
>  end
>  return ancestors
>  end
>
> So - to answer the question - I need to arrays that are initially the
> same (direct parents), But the one will eventually contain all ancestors
> and the other will be empty after iterating through all ancestors and
> testing them for further ancestors.

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

require 'set'

def ancestor?(candidate)
  visited = Set.new
  queue = [self]

  until queue.empty?
    n = queue.shift

    if visited.add? n
      return true if candidate == n
      queue.concat(n.ancestors)
    end
  end

  false
end

Note: I prefer a BFS over a DFS in these cases because the stack depth
is far more limited than the memory:

10:26:50 ~$ ruby19 -e 'def r(x) p x; r(x+1) end; r 0' | tail -3
-e:1:in `r': stack level too deep (SystemStackError)
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
         ... 8175 levels...
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1:in `<main>'
8184
8185
8186
10:27:04 ~$ ruby -e 'def r(x) p x; r(x+1) end; r 0' | tail -3
-e:1:in `inspect': stack level too deep (SystemStackError)
        from -e:1:in `p'
        from -e:1:in `r'
        from -e:1:in `r'
        from -e:1
12623
12624
12625
10:27:08 ~$


Kind regards

robert

http://en.wikipedia.org/wiki/Breadth-first_search

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