Forum: Ruby on Rails Help enhancing acts_as_nested_set

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
unknown (Guest)
on 2006-05-31 21:05
(Received via mailing list)
I'm trying to enhance acts_as_nested_set.  Well actually I already have,
but I've done a hack up job of it.  I would like to contribute these
enhancements back, but I need a little help.

I'm a complete newbie to this stuff.  The only thing I new before coming
into this project was vanilla HTML.  So over the course of two weeks
I've
picked up Ruby, Rails, MySQL, Apache and Lighttpd.  I had never done any
database stuff before either.  Suffice to say Rails is amazing.  There
is
no way I could have come as far as I have this fast, if it weren't for
Rails.  Enough of the brown nosing, on to the the real stuff.

My application needs to store store hierarchical data, and I need to
access
it in the manner which a nested set is ideally suited.  It's not a staff
org chart, but the logical structure of this data is the same.
act_as_nested_set is a bit feature light.  I found I needed a few more
features.

Enhancements:
Multiple root level objects
Moving objects around
A clipboard of sorts (I call it a cellar)

I have all of this working, but as I have attempted to clean up the code
I'm running into my limited understanding of Ruby and Rails.  I'm having
trouble with what is a class method where it should be defined and
instance
methods and how they are accessible.  Probably your typical stuff for
newbie rubies.

Here's a snippet from nested_set.rb.  I wanted to add some more class
methods and had trouble accessing the left_col_name, etc. methods.  I
first
converted them into class methods by prepending "self." in front of
them,
only to discover that the instance methods lost the ability to access
them.
So I ended up defining them twice as you can see below.  I am woefully
lacking in my understanding of how this stuff gets mixed in, and the
difference between eval, class_eval, and module_eval.  I'm beginning to
become quite productive on the application development side of things,
but
I feel I'm still at the buzz-word stage when it comes to understanding
the
guts of Ruby and Rails.  Help!   At the far bottom of this messgae I'll
include the entire nested_set.rb file I created.  Sorry if this is not
the
best way to post to this forum.

        def acts_as_nested_set(options = {})
          configuration = { :parent_column => "parent_id", :left_column
=>
"lft", :right_column => "rgt"}

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

          class_eval <<-EOV
            include ActiveRecord::Acts::NestedSet::InstanceMethods
            def self.left_col_name() "#{configuration[:left_column]}"
end
            def left_col_name() "#{configuration[:left_column]}" end

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

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

          def find_all
            self.find(:all, :conditions => "#{left_col_name} > 0",
:order
=> "#{left_col_name} ASC")
          end

          def find_roots
            self.find(:all, :conditions => "#{parent_column} = 0 AND
#{left_col_name} > 0", :order => "#{left_col_name} ASC")
          end

          def root_count
            self.find(:all, :conditions => "#{parent_column} = 0 AND
#{left_col_name} > 0").length
          end

          def find_cellar
            self.find(:first, :conditions => "#{parent_column} = 0 AND
#{left_col_name} < 0")
          end

          def add_root (node)
            node.reload
            raise "Node already in the hierarchy, try move?" unless
node.unknown?
            self.transaction {
                begin
                  # get the next lft value to use for a new root node
                  last = self.find(:first, :order => "#{right_col_name}
DESC")
                  lft_val = last[right_col_name]
                    rescue ActiveRecord::RecordNotFound
                  lft_val = 0
                end
                node[left_col_name] = lft_val + 1
                node[right_col_name] = lft_val + 2
                node[parent_column] = 0

                # What do to do about validation?
                node.save
              }
            end

        end

Ryan







My full nested_set.rb::::



module ActiveRecord
  module Acts #:nodoc:
    module NestedSet #:nodoc:
      def self.append_features(base)
        super
        base.extend(ClassMethods)
      end

      # This acts 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 in the
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 (LEFT - RIGHT + 1)/2, 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 trigger 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"
        def acts_as_nested_set(options = {})
          configuration = { :parent_column => "parent_id", :left_column
=>
"lft", :right_column => "rgt"}

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

          class_eval <<-EOV
            include ActiveRecord::Acts::NestedSet::InstanceMethods
            def self.left_col_name() "#{configuration[:left_column]}"
end
            def left_col_name() "#{configuration[:left_column]}" end

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

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

          def find_all
            self.find(:all, :conditions => "#{left_col_name} > 0",
:order
=> "#{left_col_name} ASC")
          end

          def find_roots
            self.find(:all, :conditions => "#{parent_column} = 0 AND
#{left_col_name} > 0", :order => "#{left_col_name} ASC")
          end

          def root_count
            self.find(:all, :conditions => "#{parent_column} = 0 AND
#{left_col_name} > 0").length
          end

          def find_cellar
            self.find(:first, :conditions => "#{parent_column} = 0 AND
#{left_col_name} < 0")
          end

          def add_root (node)
            node.reload
            raise "Node already in the hierarchy, try move?" unless
node.unknown?
            self.transaction {
                begin
                  # get the next lft value to use for a new root node
                  last = self.find(:first, :order => "#{right_col_name}
DESC")
                  lft_val = last[right_col_name]
                    rescue ActiveRecord::RecordNotFound
                  lft_val = 0
                end
                node[left_col_name] = lft_val + 1
                node[right_col_name] = lft_val + 2
                node[parent_column] = 0

                # What do to do about validation?
                node.save
              }
            end

        end
      end

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

        # Returns true is this is a child node
        def child?
          !(self[parent_column] == 0) && (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 self.unknown?
          ## Make self a root node if it, too is unknown
          self.class.add_root self
        end

          if child.unknown?
            # OK, add as the last child into self
            # we need to add and shift everything else to the right
            self.class.transaction {
              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.update_all( "#{left_col_name} =
(#{left_col_name}
+ 2)",  "#{left_col_name} >= #{right_bound}" )
              self.class.update_all( "#{right_col_name} =
(#{right_col_name} + 2)",  "#{right_col_name} >= #{right_bound}" )
              self.save
              child.save
            }
        else
          raise "Child already inserted into hierarchy, try move?"
        end
        end

        def is_child_of? (item)
          (self[left_col_name] > item[left_col_name] &&
self[left_col_name]
< item[right_col_name])
        end

      def is_in_cellar?
          (self[right_col_name] < 0)
        end

        def is_cellar_empty?
          self.class.find(:first, :conditions => "#{parent_column} = 0
AND
#{right_col_name} < 0").nil?
        end

        def empty_cellar
          self.class.transaction {
            self.class.delete_all( "#{right_col_name} < 0" )
          }
        end

        def move_to_cellar (force = false)
          self.reload
          raise "item not properly nested" unless !unknown?

          raise "cellar not empty" unless is_cellar_empty? || force ==
true

          empty_cellar if !is_cellar_empty?

          self.class.transaction {
            right_bound = self[right_col_name]
            move_amount = right_bound + 1
            size = right_bound - self[left_col_name] + 1
            # Move self to cellar
            self.class.update_all( "#{right_col_name} =
(#{right_col_name}
- #{move_amount}), #{left_col_name} = (#{left_col_name} -
#{move_amount})",
"#{left_col_name} >= #{self[left_col_name]} AND #{left_col_name} <=
#{self[right_col_name]}" )
            self.reload
            # Close gap after moving self
            self.class.update_all( "#{right_col_name} =
(#{right_col_name}
- #{size} )",  "#{right_col_name} > #{right_bound}" )
            self.class.update_all( "#{left_col_name} = (#{left_col_name}
-
#{size})",  "#{left_col_name} > #{right_bound}" )
            self[parent_column] = 0
            self.save
          }
        true
        end

        def move (where, target, option = nil)
          self.reload
          target.reload
          if (target.unknown? || target.is_in_cellar? ||
target.is_child_of?(self) )
            raise "Invalid desitination"
          end
          self.class.transaction {
            size = self[right_col_name] - self[left_col_name] + 1
            case where
            when 'into'
              case option
              when 'front'
                dest = target[left_col_name] + 1
                bound_for_left_match = dest
                bound_for_right_match = dest
                new_parent = target.id
              when 'back'
                dest = target[right_col_name]
                bound_for_left_match = dest + 1
                bound_for_right_match = dest
                new_parent = target.id
              else raise "invalid option = #{option}"
              end
            when 'before'
              dest = target[left_col_name]
              bound_for_left_match = dest
              bound_for_right_match = dest
              new_parent = target[parent_column]
            when 'after'
              dest = target[right_col_name] + 1
              bound_for_left_match = dest
              bound_for_right_match = dest
              new_parent = target[parent_column]
            else raise "invalid where = #{where}"
            end
            #Make hole to move into
            self.class.update_all( "#{left_col_name} = (#{left_col_name}
+
#{size})",  "#{left_col_name} >= #{bound_for_left_match}" )
            self.class.update_all( "#{right_col_name} =
(#{right_col_name}
+ #{size} )",  "#{right_col_name} >= #{bound_for_right_match}" )
            self.reload

            #Move into hole
            right_bound = self[right_col_name]
            move_amount = dest - self[left_col_name]
            self.class.update_all( "#{right_col_name} =
(#{right_col_name}
+ #{move_amount}), #{left_col_name} = (#{left_col_name} +
#{move_amount})",
"#{left_col_name} >= #{self[left_col_name]} AND #{left_col_name} <=
#{self[right_col_name]}" )

            unless self.is_in_cellar?
              #Close the hole left by move
              self.class.update_all( "#{left_col_name} =
(#{left_col_name}
- #{size})",  "#{left_col_name} >= #{right_bound}" )
              self.class.update_all( "#{right_col_name} =
(#{right_col_name} - #{size} )",  "#{right_col_name} >= #{right_bound}"
)
            end

            self.reload
            self[parent_column] = new_parent
            self.save
          }
        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.find(:all, :conditions => "(#{left_col_name} BETWEEN
#{self[left_col_name]} and #{self[right_col_name]})", :order =>
"#{left_col_name} ASC" )
        end

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

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

      # Returns the number of direct children of this object
      def direct_children_count
          self.class.find(:all, :conditions => "#{parent_column} =
#{self.id}").length
        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.transaction {
            self.class.delete_all( "#{left_col_name} >
#{self[left_col_name]} and #{right_col_name} < #{self[right_col_name]}"
)
            self.class.update_all( "#{left_col_name} = (#{left_col_name}
-
#{dif})",  "#{left_col_name} >= #{self[right_col_name]}" )
            self.class.update_all( "#{right_col_name} =
(#{right_col_name}
- #{dif} )",  "#{right_col_name} >= #{self[right_col_name]}" )
          }
        end
      end
    end
  end
end
Jean-Christophe M. (Guest)
on 2006-07-04 12:55
(Received via mailing list)
Hi Ryan,


Le 31 mai 06, à 19:00, removed_email_address@domain.invalid a écrit :
> I'm trying to enhance acts_as_nested_set.  Well actually I already
> have,
> but I've done a hack up job of it.  I would like to contribute these
> enhancements back, but I need a little help.

I posted a patch some months ago:
http://dev.rubyonrails.org/ticket/2795

I converted it to a plugin, I'll release soon a public svn uri for this.
Maybe you could help correct it instead of redo the job ?

Jean-Christophe M.
--
Symétrie, édition de musique et services multimédia
30 rue Jean-Baptiste Say
69001 LYON (FRANCE)
tél +33 (0)478 29 52 14
fax +33 (0)478 30 01 11
web www.symetrie.com
This topic is locked and can not be replied to.