From: Brian Candler <b.candler@...>
Date: 2009-11-26T18:17:22+09:00
Subject: Re: Difference between << and += for Strings and Arrays. Bug?

Pieter Hugo wrote:
> So I wrote the folder function:
> 
>   def ancestors

For me the natural way to do this would be recursively, but an iterative 
solution is of course fine, and probably more efficient anyway.

As for your problem of not modifying the 'groups' array you are looking 
at, I'd suggest:

    scanfolders = []
    scanfolders.concat(ancestors)
    ...
    scanfolders.concat(scanitem.groups)

This creates a new array (scanfolders), then mutates that array by 
tacking on the contents of some other array, without modifying that 
other array. The first two lines could also be scanfolders = 
ancestors.dup of course.

Not that there's anything really wrong with scanfolders += foo. It's 
just that if you're going to be mutating this array (with pop), then you 
might as well go for mutation across the board. It's also more efficient 
if this array becomes large, as there's less array copying and object 
creation going on.

>   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

I observe that this condition is *always* true, since scanfolders is 
never nil, so can be removed.

Other ways you can simplify your code:

>     while scanfolders.length > 0 do # while there are items on the stack

one option:  until scanfolders.empty?

>     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 your scanfolders never contains any nil items (and I don't see why it 
should), then all three lines could shrink to

  while scanitem = scanfolders.pop

>         if !scanitem.groups.nil? then #if this item has parents
>                                             #add them to the stack

  if scanitem.groups

>          scanfolders += scanitem.groups
>          scanfolders.uniq!
>          ancestors += scanitem.groups #and record this item as an
>                                             #ancestor
>          ancestors.uniq!

The problem I see here is that you might already have scanned a folder 
and popped it from scanfolders, then add it back again, therefore 
scanning it extra times unnecessarily. I can't convince myself whether 
there is a possibility of ending up in an infinite loop.

One solution is to keep an explicit mark of folders you have traversed 
(e.g. a hash of folder => true)

But since everything you've added to scanfolders has been added to 
ancestors already, it may be sufficient to do:

    scanfolders += scanitem.groups
    scanfolders -= ancestors
    ancestors += scanitem.groups

Or something like that. Actually I'm not sure if there's a mutating 
version of -=

Regards,

Brian.
-- 
Posted via http://www.ruby-forum.com/.