Как рекурсивно искать по самореферентным подтемам?

Question

Если у меня есть самоссылочный класс Topic, и я хочу рекурсивно пройтись по всем моим подтемам, какой хороший способ Ruby это сделать:

@category.topics.all(:parent_id => topic.id).each do |subtopic|
    subtopic.delete_tags
    @category.topics.all(:parent_id => subtopic.id).each do |subsubtopic|
    subsubtopic.delete_tags
        @category.topics.all(:parent_id => subsubtopic.id).each do |subsubsubtopic|
        subsubtopic.delete_tags
            @category.topics.all(:parent_id => subsubsubtopic.id).each do |subsubsubsubtopic|
            subsubsubtopic.delete_tags
            end
        end
    end
end

Answer 1

Это класс модели ActiveRecord? Если это так, вы должны быть в состоянии выполнить рекурсию через дочерние объекты, используя что-то вроде следующего кода:

class Topic
  has_many :topics
  belongs_to :parent, :classname => "Topic", :foreign_key => 'parent_id'

  # ...other model class logic...
  def delete_tags_recursive
    delete_tags
    topics.each {|subtopic| subtopic.delete_tags_recursive }
  end
end

Это дает дополнительное преимущество, позволяя вам использовать методы topics и parent, созданные декораторами has_many и belongs_to, чтобы легко обходить дерево тем.

Answer 2

Как то так?

class Topic
  def delete_subtopic_tags
    all(:parent_id => self.id).each do |subtopic|
      subtopic.delete_subtopic_tags
      subtopic.delete_tags
    end
  end
end

Answer 3

Я не знаю Ruby, но если у вас есть удобная реализация хеш-таблицы и связанного списка, я бы сделал это примерно так (в псевдокоде Java-ish):

Topic currentTopic = topic;
list.add(currentTopic);
hashtable.add(currentTopic);
while (list.empty() == false) {
    for (Topic t : currentTopic.getSubtopics()) {
        if (hashtable.contains(t) == false) {
            list.add(t);
            hashtable.add(t);
        }
    }
    visit(currentTopic);
    list.remove(currentTopic);
    currentTopic = list.getFirst();
}

Главное здесь - сохранить список хеш-таблиц, чтобы вы могли легко убедиться, что вы никогда не посетите тему дважды. Кроме этого, это, по сути, реализация поиска в ширину . visit () делает все, что вам нужно для каждой отдельной темы.