13 Sep 2009

Awesome nested sets (HOWTO)

Geplaatst door jhaagmans @ 15:20 in Ruby on Rails Dit artikel uitprinten

Most of you will probably know about acts_as_tree. It’s a very simple tree implementation which can help you organize your categories, for example. Combined with acts_as_list, child category can even be organized amonst themselves. However, it’s not really nice and there are better plugins to do it.

One example is awesome_nested_set. A nested set created with that plugin doesn’t use a tree structure, but actually a nested structure, using a left and a right value, making it possible to easily navigate through your set. A nested set element can have a parent, a child, but also has descendants and ancestors. This way you can load your entire nested set using just one query.

Let’s look at the implementation. First, we need to install awesome_nested_set:

# script/plugin install awesome_nested_set

It’s that easy!

Now before the magic starts, we need to create three table columns in our categories table, these are parent_id, lft and rgt:

# script/generate migration AddNestingToCategory parent_id:integer lft:integer rgt:integer
# rake db:migrate

Now we want to include these nested sets in your model:

class Category < ActiveRecord::Base
  acts_as_nested_set
end

Again, very easy!

Now there’s a thing I didn’t think about before writing this. When doing this for categories, you will probably always load up all categories. However, let’s say you have a multilingual blog and have your categories stored under the root element, which has the language abbreviation as a name. Let’s make an index action in our controller loading up all these root elements.

class CategoriesController < ApplicationController
  def index
    @root_categories = Categories.roots
  end
end

Now, I don’t have to tell you how this works, do I? And I probably also won’t have to show you how this would look in your views, right? Let’s say clicking on these names sends us to the show_category_path, with the id being the root element’s id, where we will load the category with all its descendants:

class CategoriesController < ApplicationController
  def index
    @root_categories = Categories.roots
  end
 
  def show
    @categories = Categories.find_by_id(params[:id]).self_and_descendants
  end
end

Here I tell it to find the right root element and load all its descendants including itself. Now why would I do that? I already have the root element, can’t I call its children directly from the view like you would do in acts_as_tree and descend from there? Yes, that’s true, but that will generate a number of individual queries, while this will only generate one.

Now, forget all you’ve ever done with acts_as_tree, because you will probably make mistakes. The beauty of these nested sets is in the lft and rgt values. Make sure your collection is sorter by the lft value. I’m quite sure acts_as_nested_set does this for you, but always check these things. If you now insert the following into your view:

<ul>
  <%- @categories.each do |category| -%>
    <li>
      <%= category.name %>
    </li>
  <%- end -%>
</ul>

This will show every category in a list, but disregards all nesting. For the nesting to work and not generate alot of queries, you will need to do something like this (highly untested and awful coding, please check back with improvements and I wil add them!):

<%- active_parents = [] -%>
<ul>
  <%- @categories.each do |category| -%>
    <%- active_parents.each do |p| -%>
      <%- if !category.is_descendant_of(p) -%>
        <%- active_parents.delete(p) -%>
        <%= '</ul></li>' %>
      <%- end -%>
    <%- end -%>
  <li>
    <%= category.name %>
    <%- if category.leaf? -%>
      </li>
    <%- else -%>
      <%- active_parents << category.id -%>
      <%= '<ul>' %>
    <%- end -%>
  <%- end -%>
</ul>

Well, that’s a mouth full. But it does what we want. Let’s go through it, so you’ll understand. It makes an array for all the parents that are “open”, so to say. Every element that’s not a leaf (and thus has children) gets added to this array until we come across an element that is no descendant from one of these parents. The parent gets deleted from the active_parents array and we end the list for the now closed parent.

Why does this work? It’s not that hard to understand: when you order a nested set by its lft value, any child element will come directly after its parent or its siblings in the actual nested order. So when you come across an element that’s not a child of an active parent, the active parent element will have run out of children.

Also make sure to check out the Rails API page about Nested Sets. It may help you understand how to interpret a nested set.

Good luck and please, comment! If you have any improvements on the example above, please share them. Don’t copy-paste-and-run ;)

6 Comments

6 Reacties op “Awesome nested sets (HOWTO)”

  1. Mateniaop 29 Jun 2010 om 12:59

    Mistake found in first section –

    @root_categories = Category.roots (not categories.roots)

  2. free streaming adult movieop 30 Nov 2010 om 04:10

    prl, mgpmo xu yzlgnxnu w exphd.
    nbnq wkpgnibw f un c!
    vgh free xxx porn
    , ozuf wc zm w eoev k.
    magthq qvoffd ztlw s wzyc. fyy, raw tube
    , cmhc b pftkfzas v qdkytt wn cded scs.

    xpo ae tww.

  3. Ricoop 26 Feb 2011 om 13:38

    Found 2 mistakes:
    – <%- active_parents < should be <%- active_parents < (no id)
    – should be

    Your article was pretty helpfull though, thanks!

  4. Ricoop 26 Feb 2011 om 13:39

    My comment got messed up a little bit, this is what i meant:
    if !category.is_descendant_of(p) should be if !category.is_descendant_of?(p)
    active_parents << category.id should be active_parents << category

  5. KennBYNCop 06 May 2017 om 18:16

    Zithromax Treatment For Chlamydia Valtex Nex Day Vendo Viagra Malaga Dogs And Amoxicillin Vente Kamagra En Suisse Best Generic Cialis Website viagra Comprar Cialis En Girona Amoxicillin Prescription 5cc Dose Of Amoxicillin Vente Du Kamagra Au Maroc Diflucan (Fluconazole)

Trackback URI | Reacties RSS

Reageer