Looping over objects in Ruby efficiently?

Question

I have an array of @pages below

#<Page id: 1, url: "/location1", name: "Information", sort_order: 2, parent_id: nil>
#<Page id: 2, url: "/location2", name: "Information 2", sort_order: 2, parent_id: 4>
#<Page id: 3, url: "/location3", name: "Information 3", sort_order: 1, parent_id: >
#<Page id: 4, url: "/location4", name: "Information 4", sort_order: 1, parent_id: nil>
#<Page id: 5, url: "/location5", name: "Information 5", sort_order: 1, parent_id: 2>
#<Page id: 6, url: "/location6", name: "Information 6", sort_order: 3, parent_id: nil>

And i am trying to build a nav with these pages...Note this is just an example I really have 70 pages similar to this

I want the final outcome to look like this

<ul>
  <li><a href="/location4">Information 4</a>
    <ul>
      <li><a href="/location3">Information 3</a></li>
      <li><a href="/location2">Information 2</a>
        <ul><li><a href="/location5">Information 5</a></li></ul>
      </li>
    </ul>
  </li>
  <li><a href="/location1">Information 1</a></li>
  <li><a href="/location6">Information 6</a></li>
</ul>

So the parent_id will signal if the li has another child ul and li and the sort order is the ordering of the chil li's

I cant seem to wrap my brain around how i need to loop over @pages efficiently ...any ideas..

Answer 1

If you can use an extra gem, have a look at rubytree. Note that code sample below doesn't consider your sort_order attribute. You should however be able to weave in sort_order logical easily.

require 'tree'

class NavBuilder
    def initialize
        @pages     = Page.all
        @root      = Tree::TreeNode.new("SITEMAP", { :id => 0 })
        @processed = []
    end

    def pagetree
        pages_hash = {}
        @pages.each {|page| pages_hash[page.id] = page}

        @pages.each do |page|
            if page.parent_id.nil?
                if @root[page.id.to_s].nil?
                    @root << Tree::TreeNode.new(page.id.to_s, page)
                end 
            else
                parent_node = @root[page.parent_id.to_s]
                if parent_node.nil?
                    inserted = false
                    @root.each do |node| 
                        if page.parent_id == node.content[:id]
                            node << Tree::TreeNode.new(page.id.to_s, page)
                            inserted = true
                        end 
                    end 
                    if !inserted
                        @root << Tree::TreeNode.new(page.parent_id.to_s, pages_hash[page.parent_id]) << Tree::TreeNode.new(page.id.to_s, page)
                    end 
                else
                    parent_node << Tree::TreeNode.new(page.id.to_s, page)
                end 
            end
        end
    end

    def nav_html
        html = "<ul>"
        @root.each do |node|
            if node.content[:id] > 0
                html << html_tags(node.children.size,node)
            end 
        end 
        html << "</ul>"
    end 

    def html_tags(number_of_children,node)
        html = ""
        if !@processed.include?(node.content[:id])
            if number_of_children == 0
                html = "<li><a href=#{node.content.url}>#{node.content.name}</a></li>"
                @processed << node.content[:id]
            else
                html = "<li><a href=#{node.content.url}>#{node.content.name}</a>"
                html << "<ul>"
                node.children.each do |n|
                    html << html_tags(n.children.size,n)
                    @processed << node.content[:id]
                end 
                html << "</ul></li>"
            end     
        end 
        html
    end 
end 

nav = NavBuilder.new
nav.pagetree
puts nav.nav_html

# <ul>
#   <li><a href=/location1>Information 1</a></li>
#   <li><a href=/location4>Information 4</a>
#       <ul>
#           <li><a href=/location2>Information 2</a>
#               <ul><li><a href=/location5>Information 5</a></li></ul>
#           </li>
#           <li><a href=/location3>Information 3</a></li>
#       </ul>
#   </li>
#   <li><a href=/location6>Information 6</a></li>
# </ul>

Answer 2

Start with only top level Pages, i.e. Pages where parent_id == nil, ordered by sort_order

Define a children method that gets you all Pages where parent_id == self.id, ordered by sort_order

Then you should be able to do something like this:

def build_navigation(pages, html = nil)
  return "" if pages.length == 0

  navigation_html = html || ""
  navigation_html << "<ul>"

  pages.each do |page|
    navigation_html << li_tag(page)
    navigation_html << build_navigation(page.children, navigation_html)
  end

  navigation_html << "</ul>"
end

def li_tag(page)
  "<li><a href='#{page.name}'>#{page.name}</a></li>"
end

build_navigation(parent_pages).html_safe

Update: Slightly adapted so it works when you only want to do ONE query:

def all_pages
  # get all the pages from the DB
end

def parent_pages(pages)
  parents = pages.reject { |page| page.parent_id.nil? }
  sort(parents)
end

def children(parent, pages)
  children = pages.map { |page| page.parent_id == parent.id }
  sort(children)
end

def sort(pages)
  pages.sort { |a, b| a.sort_order <=> b.sort_order }      
end

def build_navigation(pages, html = nil)
  return "" if pages.length == 0

  navigation_html = html || ""
  navigation_html << "<ul>"

  pages.each do |page|
    navigation_html << li_tag(page)
    navigation_html << build_navigation(children(page, all_pages), navigation_html)
  end

  navigation_html << "</ul>"
end

def li_tag(page)
  "<li><a href='#{page.name}'>#{page.name}</a></li>"
end

build_navigation(parent_pages(all_pages)).html_safe