Recursive print_group_tree() help

[draftomatic]

Hi all,

I'm writing a recursive method that will find all the groups in a tree-like fashion and print their names. I think I have something that works, but recursion always makes me nervous, so I'm hoping someone can check my reasoning... maybe it's not very optimized etc etc...

  #
  # recursively print the group tree
  #
  def print_group_tree()
    @model.definitions.each { |d|
      if (d.group? && d.instances[0].parent.is_a?(Sketchup;;Model) )
        if (d.instances[0].is_a?(Sketchup;;Group))   # Assume Groups are unique
          puts d.instances[0].name
          recurse_group(d.instances[0])
        end
      end
    }
  end

  def recurse_group(group)
    group.entities.select { |e| 
      e.is_a?(Sketchup;;Group) 
    }.each { |g| 
      puts g.name
      recurse_group(g) 
    }
  end

I'm making Groups unique before I run this, just to be sure (I know SketchUp can be touchy about Groups and uniqueness...)

Thanks!

[thomthom]

1. You're getting a tree of the entities in a model - would it not be better to start with model.entities instead of scanning model.definitions for instances with parent that is model?

2. Your code makes the assumption that all instances has instances, this might not be the case.

3. You can not assume groups are all unique - group definitions often has group instances. At least from what I observe from the models at our office and the warehouse.

4. if (d.group? && d.instances[0].parent.is_a?(Sketchup::Model) ) if (d.instances[0].is_a?(Sketchup::Group))
   Somewhat reduntant checks there - you first check the definition if it's a group, then you check it's instances. No need to that double check.

  def recurse_group(group)
    group.entities.select { |e|
      e.is_a?(Sketchup;;Group)
    }.each { |g|
      puts g.name
      recurse_group(g)
    }
  end

Could be made more efficient. At the moment you first scan the entities collection to filter out groups, then you scan those results again. Making double iteration over all groups.

  def recurse_group(group)
    group.entities.each { |e|
      next unless e.is_a?(Sketchup;;Group)
      puts e.name
      recurse_group(e)
    }
  end

There - small change, but ensure you only iterate each entity only once.

[honoluludesktop]

Tom, didn't know that a method can call itself. Boy I've got a lot to learn. What happens to the variables? Guess they are they recreated each time the method is called.

[draftomatic]

@thomthom said:

1. You're getting a tree of the entities in a model - would it not be better to start with model.entities instead of scanning model.definitions for instances with parent that is model?

Seems wasteful to iterate all of the entities when all I want is the Group tree. There will normally be less Definitions/Groups than Entities, no?

@unknownuser said:

2. Your code makes the assumption that all instances has instances, this might not be the case.

What if I purge the model before I run this code?

@model.definitions.purge_unused

@unknownuser said:

3. You can not assume groups are all unique - group definitions often has group instances. At least from what I observe from the models at our office and the warehouse.

I'm using this routine to make all Groups unique before I run this code:

    @model.definitions.each { |d|
      if (d.group?())
        d.instances.each { |i|
          i.make_unique
        }
      end
    }

[thomthom]

@draftomatic said:

Seems wasteful to iterate all of the entities when all I want is the Group tree. There will normally be less Definitions/Groups than Entities, no?

Yes, but you iterate the entities of the groups, so you're only skipping a few entities at the root. In most models I've seen, the root contains mostly groups or components, so there would be little to gain. You could be feeding your recursive method entities collections, starting with model. entities. You'd then have less code.

@draftomatic said:

What if I purge the model before I run this code?

You could, but it's only an extra check to verify there is instances. And maybe some users don't want their model purged without their knowing.

@honoluludesktop said:

Tom, didn't know that a method can call itself. Boy I've got a lot to learn. What happens to the variables? Guess they are they recreated each time the method is called.

method variables are local to each calling of the method, yes.
Beware of recursive methods though, if you call it too many time you end up with stack overflow - which will crash SU. Very easy to do if you iterate entities with recursive methods.

[draftomatic]

Thanks thomthom... is this better?

  def print_group_tree()
    @model.entities.each { |e|
      if (e.is_a?(Sketchup;;Group))
          puts e.name
          recurse_group(e)
      end
    }
  end
  
  def recurse_group(group)
    group.entities.each { |e|
      next unless e.is_a?(Sketchup;;Group)
      puts e.name
      recurse_group(e)
    }
  end

[thomthom]

Yes - though, is this just a framework of what it will do? As it is now it looks like it prints out the names in a pretty flat list...

I mean, the code traverses the model tree, but from the code I don't see any reason to do a tree traversal. A flat traversal of model.definitions would be the same?

What is the more abstract purpose of outputting the group names?

[draftomatic]

@thomthom said:

I mean, the code traverses the model tree, but from the code I don't see any reason to do a tree traversal. A flat traversal of model.definitions would be the same?

I'm writing an XML exporter that exports the Group tree along with the rest of the model... XML = tree.

Obviously my real code is doing more than just printing names. But it's top-secret!

[draftomatic]

@honoluludesktop said:

Tom, didn't know that a method can call itself. Boy I've got a lot to learn. What happens to the variables? Guess they are they recreated each time the method is called.

Look up "Recursion" =). Each call has its own scope.

Recursion (computer science) - Wikipedia

(en.wikipedia.org)

One of the best examples is computing the Fibonacci sequence.

[thomthom]

Righti'o!

[thomthom]

Recursing works generally for digging down the model tree with groups and components, but if you use it to process edges and faces - like traversing connected geometry, then you will run into stack overflow.

[honoluludesktop]

tt, This recursive stuff really works! Below drills down into component instances. Now, on to add groups.

def get_ci(ci_array)
  entities = Sketchup.active_model.entities
  entities.each do |ent|
    if ent.is_a? Sketchup;;ComponentInstance
      ci_array.push ent
    end
  end
  return ci_array
end

def explode_ci_array(ci_array)
  ci_sub_array=[]
  ci_array.each do |ci|
    if ci.is_a? Sketchup;;ComponentInstance
      ci_sub_array=ci.explode
    end
  end
  return ci_sub_array
end

ci_array=[]
found = false
while found == false
  ci_array=get_ci(ci_array)
  ci_array=explode_ci_array(ci_array)
  if ci_array[0] == nil
    found = true
  end
end