module FastTree::Model

Public Instance Methods

add_child(node) click to toggle source

Instance Methods

# File lib/fast_tree/model.rb, line 148
def add_child(node)
  # bulk update nodes by a sql query
  _update_nodes(r_ptr, r_ptr, "r_ptr >= #{r_ptr}")

  # child node's pointer
  node.l_ptr = r_ptr
  node.r_ptr = r_ptr + 1
  node.depth = depth + 1
  node.save
end
children() click to toggle source
# File lib/fast_tree/model.rb, line 275
def children
  self.class.where(self.class.arel_table[:l_ptr].gt(l_ptr))
            .where(self.class.arel_table[:r_ptr].lt(r_ptr))
            .where(depth: depth + 1)
end
copy_to(node) click to toggle source
# File lib/fast_tree/model.rb, line 170
def copy_to(node)
  # create empty space into which subtree embedded
  _update_nodes(node.l_ptr, node.r_ptr, "r_ptr >= #{node.r_ptr}", width + 1)

  # self and node may be updated by shifting
  self.reload
  node.reload

  bias = node.r_ptr - r_ptr - 1
  base_depth = depth
  self.subtree.each do |st_node|
    attributes = st_node.attributes.to_h
    attributes.delete("id")
    attributes["l_ptr"] += bias
    attributes["r_ptr"] += bias
    attributes["depth"] += node.depth - base_depth + 1
    self.class.create(attributes)
  end
end
create_child(attributes = {}, &block) click to toggle source
# File lib/fast_tree/model.rb, line 159
def create_child(attributes = {}, &block)
  # bulk update nodes by a sql query
  _update_nodes(r_ptr, r_ptr, "r_ptr >= #{r_ptr}")

  # create child
  attributes[:l_ptr] = r_ptr
  attributes[:r_ptr] = r_ptr + 1
  attributes[:depth] = depth + 1
  self.class.create(attributes, &block)
end
has_children?() click to toggle source
# File lib/fast_tree/model.rb, line 260
def has_children?
  l_ptr != r_ptr - 1
end
leaf?() click to toggle source
# File lib/fast_tree/model.rb, line 256
def leaf?
  l_ptr == r_ptr - 1
end
move_to(node) click to toggle source
# File lib/fast_tree/model.rb, line 190
def move_to(node)
  # NOTE:
  # copy_to and remove change node ids
  # move operation should change nothing but left and right pointers

  # create empty spaces under the node
  _update_nodes(node.r_ptr, node.r_ptr, "r_ptr >= #{node.r_ptr}", width + 1)

  self.reload
  node.reload

  # remember where the node were
  empty_space_left = self.l_ptr
  empty_space_right = self.r_ptr

  # move subtree under the given node
  bias = node.r_ptr - r_ptr - 1
  base_depth = depth
  self.subtree.each do |st_node|
    st_node.l_ptr += bias
    st_node.r_ptr += bias
    st_node.depth += node.depth - base_depth + 1
    st_node.save
  end

  self.reload
  node.reload

  # fill (virtual) empty spaces that will be created by moving subtree
  _update_nodes(empty_space_left, empty_space_right, "r_ptr > #{empty_space_right}", - (width + 1))
end
parent() click to toggle source

Getter Methods

# File lib/fast_tree/model.rb, line 268
def parent
  self.class.where(self.class.arel_table[:l_ptr].lt(l_ptr))
            .where(self.class.arel_table[:r_ptr].gt(r_ptr))
            .where(depth: depth - 1)
            .try(:first)
end
path() click to toggle source
# File lib/fast_tree/model.rb, line 233
def path
  self.class.where(self.class.arel_table[:l_ptr].lteq(l_ptr))
            .where(self.class.arel_table[:r_ptr].gteq(r_ptr))
            .order(l_ptr: :asc)
end
print_subtree() click to toggle source
remove() click to toggle source
# File lib/fast_tree/model.rb, line 222
def remove
  # remove subtree
  n_destroyed = self.class.find_subtree_by_root(self).destroy_all

  # fill empty space
  _update_nodes(l_ptr, r_ptr, "r_ptr >= #{r_ptr}", - (width + 1))

  # return count of destroyed nodes
  n_destroyed
end
root?() click to toggle source

Boolean Methods

# File lib/fast_tree/model.rb, line 252
def root?
  self.l_ptr == 0
end
width() click to toggle source
# File lib/fast_tree/model.rb, line 243
def width
  r_ptr - l_ptr
end

Protected Instance Methods

_update_nodes(left, right, condition, diff = 2) click to toggle source
# File lib/fast_tree/model.rb, line 284
      def _update_nodes(left, right, condition, diff = 2)
        #
        # Possible patterns
        #
        #     left         right
        # --------------------------
        # <---> |            |         ... 1.
        #     <----->        |         ... 2.
        #       |  <----->   |         ... 3.
        #       |         <----->      ... 4.
        #       |            | <---->  ... 5.
        #   <------------------->      ... 6.
        #       |            |
        #
        #
        # 1: do nothing
        #   l_ptr <- l_ptr
        #   r_ptr <- r_ptr
        #
        # 2: do nothing (illegal node)
        #   l_ptr <- l_ptr
        #   r_ptr <- r_ptr
        #
        # 3: move diff - 1 to the right
        #   l_ptr <- l_ptr + diff - 1
        #   r_ptr <- r_ptr + diff - 1
        #
        # 4: do nothing (illegal node)
        #   l_ptr <- l_ptr
        #   r_ptr <- r_ptr
        #
        # 5: move diff to the right
        #   l_ptr <- l_ptr + diff
        #   r_ptr <- r_ptr + diff
        #
        # 6: move right endpoint by diff to the right
        #   l_ptr <- l_ptr
        #   r_ptr <- r_ptr + diff
        #

        #
        # NOTE:
        # Due to performance reason,
        # use raw SQL query to move nodes
        #

        sql = <<-"EOS"
UPDATE #{self.class.to_s.underscore.pluralize}
SET l_ptr = CASE
              WHEN l_ptr > #{right}
                THEN l_ptr + #{diff}
              WHEN l_ptr > #{left}
                AND r_ptr < #{right}
                THEN l_ptr + #{diff - 1}
              ELSE l_ptr
            END,
    r_ptr = CASE
              WHEN l_ptr <= #{left}
                AND r_ptr >= #{right}
                THEN r_ptr + #{diff}
              WHEN l_ptr > #{right}
                THEN r_ptr + #{diff}
              WHEN l_ptr > #{left}
                AND r_ptr < #{right}
                THEN r_ptr + #{diff - 1}
              ELSE
                r_ptr
            END
WHERE #{condition}
        EOS

        ActiveRecord::Base.connection.execute(sql)
      end