module FastTree::Model
Public Instance Methods
add_child(node)
click to toggle source
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
# File lib/fast_tree/model.rb, line 239 def print_subtree self.class.print_subtree(self) end
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