Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Jeremy Kemper September 11, 2007
file 211 lines (187 sloc) 9.693 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
module ActiveRecord
  module Acts #:nodoc:
    module NestedSet #:nodoc:
      def self.included(base)
        base.extend(ClassMethods)
      end

      # This +acts_as+ extension provides Nested Set functionality. Nested Set is similiar to Tree, but with
      # the added feature that you can select the children and all of their descendents with
      # a single query. A good use case for this is a threaded post system, where you want
      # to display every reply to a comment without multiple selects.
      #
      # A Google search for "Nested Set" should point you to in the right direction to explain the
      # database theory. I figured out a bunch of this from
      # http://threebit.net/tutorials/nestedset/tutorial1.html
      #
      # Instead of picturing a leaf node structure with children pointing back to their parent,
      # the best way to imagine how this works is to think of the parent entity surrounding all
      # of its children, and its parent surrounding it, etc. Assuming that they are lined up
      # horizontally, we store the left and right boundries in the database.
      #
      # Imagine:
      # root
      # |_ Child 1
      # |_ Child 1.1
      # |_ Child 1.2
      # |_ Child 2
      # |_ Child 2.1
      # |_ Child 2.2
      #
      # If my cirlces in circles description didn't make sense, check out this sweet
      # ASCII art:
      #
      # ___________________________________________________________________
      # | Root |
      # | ____________________________ ____________________________ |
      # | | Child 1 | | Child 2 | |
      # | | __________ _________ | | __________ _________ | |
      # | | | C 1.1 | | C 1.2 | | | | C 2.1 | | C 2.2 | | |
      # 1 2 3_________4 5________6 7 8 9_________10 11_______12 13 14
      # | |___________________________| |___________________________| |
      # |___________________________________________________________________|
      #
      # The numbers represent the left and right boundries. The table then might
      # look like this:
      # ID | PARENT | LEFT | RIGHT | DATA
      # 1 | 0 | 1 | 14 | root
      # 2 | 1 | 2 | 7 | Child 1
      # 3 | 2 | 3 | 4 | Child 1.1
      # 4 | 2 | 5 | 6 | Child 1.2
      # 5 | 1 | 8 | 13 | Child 2
      # 6 | 5 | 9 | 10 | Child 2.1
      # 7 | 5 | 11 | 12 | Child 2.2
      #
      # So, to get all children of an entry, you
      # SELECT * WHERE CHILD.LEFT IS BETWEEN PARENT.LEFT AND PARENT.RIGHT
      #
      # To get the count, it's <tt>(LEFT - RIGHT + 1)/2</tt>, etc.
      #
      # To get the direct parent, it falls back to using the +PARENT_ID+ field.
      #
      # There are instance methods for all of these.
      #
      # The structure is good if you need to group things together; the downside is that
      # keeping data integrity is a pain, and both adding and removing an entry
      # require a full table write.
      #
      # This sets up a +before_destroy+ callback to prune the tree correctly if one of its
      # elements gets deleted.
      #
      module ClassMethods
        # Configuration options are:
        #
        # * +parent_column+ - specifies the column name to use for keeping the position integer (default: +parent_id+)
        # * +left_column+ - column name for left boundry data, default +lft+
        # * +right_column+ - column name for right boundry data, default +rgt+
        # * +scope+ - restricts what is to be considered a list. Given a symbol, it'll attach <tt>_id</tt>
        # (if it hasn't already been added) and use that as the foreign key restriction. It's also possible
        # to give it an entire string that is interpolated if you need a tighter scope than just a foreign key.
        # Example: <tt>acts_as_nested_set :scope => 'todo_list_id = #{todo_list_id} AND completed = 0'</tt>
        def acts_as_nested_set(options = {})
          configuration = { :parent_column => "parent_id", :left_column => "lft", :right_column => "rgt", :scope => "1 = 1" }

          configuration.update(options) if options.is_a?(Hash)

          configuration[:scope] = "#{configuration[:scope]}_id".intern if configuration[:scope].is_a?(Symbol) && configuration[:scope].to_s !~ /_id$/

          if configuration[:scope].is_a?(Symbol)
            scope_condition_method = %(
def scope_condition
if #{configuration[:scope].to_s}.nil?
"#{configuration[:scope].to_s} IS NULL"
else
"#{configuration[:scope].to_s} = \#{#{configuration[:scope].to_s}}"
end
end
)
          else
            scope_condition_method = "def scope_condition() \"#{configuration[:scope]}\" end"
          end

          class_eval <<-EOV
include ActiveRecord::Acts::NestedSet::InstanceMethods

#{scope_condition_method}

def left_col_name() "#{configuration[:left_column]}" end

def right_col_name() "#{configuration[:right_column]}" end

def parent_column() "#{configuration[:parent_column]}" end

EOV
        end
      end

      module InstanceMethods
        # Returns +true+ is this is a root node.
        def root?
          parent_id = self[parent_column]
          (parent_id == 0 || parent_id.nil?) && (self[left_col_name] == 1) && (self[right_col_name] > self[left_col_name])
        end

        # Returns +true+ is this is a child node
        def child?
          parent_id = self[parent_column]
          !(parent_id == 0 || parent_id.nil?) && (self[left_col_name] > 1) && (self[right_col_name] > self[left_col_name])
        end

        # Returns +true+ if we have no idea what this is
        def unknown?
          !root? && !child?
        end

        # Adds a child to this object in the tree. If this object hasn't been initialized,
        # it gets set up as a root node. Otherwise, this method will update all of the
        # other elements in the tree and shift them to the right, keeping everything
        # balanced.
        def add_child( child )
          self.reload
          child.reload

          if child.root?
            raise "Adding sub-tree isn\'t currently supported"
          else
            if ( (self[left_col_name] == nil) || (self[right_col_name] == nil) )
              # Looks like we're now the root node! Woo
              self[left_col_name] = 1
              self[right_col_name] = 4

              # What do to do about validation?
              return nil unless self.save

              child[parent_column] = self.id
              child[left_col_name] = 2
              child[right_col_name]= 3
              return child.save
            else
              # OK, we need to add and shift everything else to the right
              child[parent_column] = self.id
              right_bound = self[right_col_name]
              child[left_col_name] = right_bound
              child[right_col_name] = right_bound + 1
              self[right_col_name] += 2
              self.class.base_class.transaction {
                self.class.base_class.update_all( "#{left_col_name} = (#{left_col_name} + 2)", "#{scope_condition} AND #{left_col_name} >= #{right_bound}" )
                self.class.base_class.update_all( "#{right_col_name} = (#{right_col_name} + 2)", "#{scope_condition} AND #{right_col_name} >= #{right_bound}" )
                self.save
                child.save
              }
            end
          end
        end

        # Returns the number of nested children of this object.
        def children_count
          return (self[right_col_name] - self[left_col_name] - 1)/2
        end

        # Returns a set of itself and all of its nested children
        def full_set
          self.class.base_class.find(:all, :conditions => "#{scope_condition} AND (#{left_col_name} BETWEEN #{self[left_col_name]} and #{self[right_col_name]})" )
        end

        # Returns a set of all of its children and nested children
        def all_children
          self.class.base_class.find(:all, :conditions => "#{scope_condition} AND (#{left_col_name} > #{self[left_col_name]}) and (#{right_col_name} < #{self[right_col_name]})" )
        end

        # Returns a set of only this entry's immediate children
        def direct_children
          self.class.base_class.find(:all, :conditions => "#{scope_condition} and #{parent_column} = #{self.id}", :order => left_col_name)
        end

        # Prunes a branch off of the tree, shifting all of the elements on the right
        # back to the left so the counts still work.
        def before_destroy
          return if self[right_col_name].nil? || self[left_col_name].nil?
          dif = self[right_col_name] - self[left_col_name] + 1

          self.class.base_class.transaction {
            self.class.base_class.delete_all( "#{scope_condition} and #{left_col_name} > #{self[left_col_name]} and #{right_col_name} < #{self[right_col_name]}" )
            self.class.base_class.update_all( "#{left_col_name} = (#{left_col_name} - #{dif})", "#{scope_condition} AND #{left_col_name} >= #{self[right_col_name]}" )
            self.class.base_class.update_all( "#{right_col_name} = (#{right_col_name} - #{dif} )", "#{scope_condition} AND #{right_col_name} >= #{self[right_col_name]}" )
          }
        end
      end
    end
  end
end
Something went wrong with that request. Please try again.