class MPTT ROOT_NODE = nil # Add an entry to the database reflecting the current @row_data hash at the # specified location, taking into consideration the preorder field as it # relates to any existing siblings def save(parent = ROOT_NODE) # Find the new location considering the preorder field l = get_prior_sibling_r(parent) + 1 # Make a space open_gap(l, l + 1) # Build the placeholder list for however many columns we have replacements = Array.new() 3.upto(@row_data.length + 2) { |n| replacements.push('$%d' % n) } cursor = @dbd.prepare( "INSERT INTO #{ @table } (#{ @columns['left'] }, #{ @columns['right'] }, #{ @row_data.keys.join(', ') }) VALUES ($1, $2, #{ replacements.join(', ') })") return cursor.exec(l, l + 1, @row_data.values) end # Delete a branch and all its children. I can't think of any situation # off-hand where reparenting would be preferable so I kept it simple. def delete() l, r = get_branch_dims() cursor = @dbd.prepare("DELETE FROM #{ @table } WHERE #{ @columns['left'] } >= $1 AND #{ @columns['right'] } <= $2") cursor.exec(l, r) close_gap(l, r) end # Move a branch and its children to a different location def move(parent) l, r = get_branch_dims() # Make l and r negative for a while so the entry is effectively # removed from the tree but its hierarchy is preserved invert_branch(l, r) # Put the tree in a stable state without this entry close_gap(l, r) # Figure out where it should be replaced dest_l = get_prior_sibling_r(parent) + 1 # Make room open_gap(dest_l, dest_l + r - l) # dest_l + r - 1 == dest_l + branch width == the new r # Use the offset between the old and new locations to put the # branch back in the opening we just made adjust_inverted(l, dest_l) end protected # Just figures out how many entries there are. # # MAX(r) seems to test faster than COUNT(*) in postgres 8.2 def tree_width() cursor = @dbd.prepare("SELECT COALESCE(MAX(#{ @columns['right'] }), 0) FROM #{ @table }") res = cursor.exec() return res[0][0].to_i end private # Use the difference between an old and new location to adjust a negated # branch so that it fits back in the tree. def adjust_inverted(old_l, new_l) offset = new_l - old_l cursor = @dbd.prepare( "UPDATE #{ @table } SET #{ @columns['left'] } = #{ @columns['left'] } * -1 + $1, #{ @columns['right'] } = #{ @columns['right'] } * -1 + $2 WHERE #{ @columns['left'] } < 0") cursor.exec(offset, offset) end # Make our left and right columns negative to get a branch out of the # way of other updates on the tree without compromising its # interrelationships def invert_branch(l, r) cursor = @dbd.prepare( "UPDATE #{ @table } SET #{ @columns['left'] } = #{ @columns['left'] } * -1, #{ @columns['right'] } = #{ @columns['right'] } * -1 WHERE #{ @columns['left'] } >= $1 AND #{ @columns['right'] } <= $2") cursor.exec(l, r) end # Opens and closes holes in the tree def adjust_gap(at_l, for_width) cursor = @dbd.prepare( "UPDATE #{ @table } SET #{ @columns['right'] } = #{ @columns['right'] } + $1 WHERE #{ @columns['right'] } >= $2") cursor.exec(for_width, at_l) cursor = @dbd.prepare( "UPDATE #{ @table } SET #{ @columns['left'] } = #{ @columns['left'] } + $1 WHERE #{ @columns['left'] } >= $2") cursor.exec(for_width, at_l) end # Convenience method for adjust_gap def close_gap(l, r) adjust_gap(l, -(r - l + 1)) end # Convenience method for adjust_gap def open_gap(l, r) adjust_gap(l, r - l + 1) end # Figure out where to place a new entry in a given parent considering # the preorder field. # # This is where most of the complexity is, and I'm confident both # branches could be done better. def get_prior_sibling_r(parent) if parent == ROOT_NODE # Argh. Thankfully this is rare. cursor = @dbd.prepare( "SELECT COALESCE(MAX(t1.#{ @columns['right'] }), 0) FROM #{ @table } AS t1 WHERE #{ @columns['preorder'] } <= $1 AND #{ @columns['id'] } IN (SELECT #{ @columns['id'] } FROM #{ @table } AS t2 WHERE (SELECT COUNT(*) FROM #{ @table } AS t3 WHERE t3.#{ @columns['left'] } < t2.#{ @columns['left'] } AND t3.#{ @columns['right'] } > t2.#{ @columns['right'] } ) = 0)") res = cursor.exec(@row_data[@columns['preorder']]) else # I think these two queries could be joined, although I # don't know if it would help. l, r = get_branch_dims(parent) cursor = @dbd.prepare( "SELECT COALESCE(MAX(#{ @columns['right'] }), $1) FROM #{ @table } WHERE #{ @columns['left'] } > $2 AND #{ @columns['right'] } < $3 AND #{ @columns['preorder'] } < $4") res = cursor.exec(l, l, r, @row_data[@columns['preorder']]) end return res[0][0].to_i end # Get the left and right for a given ID, or if none is given get ours. def get_branch_dims(id = nil) id = id.nil? ? @row_data[@columns['id']] : id raise 'Attempted to stat a nil id' if id.nil? cursor = @dbd.prepare( "SELECT #{ @columns['left'] }, #{ @columns['right'] } FROM #{ @table } WHERE #{ @columns['id'] } = $1 LIMIT 1"); res = cursor.exec(id) raise 'Attempted to stat nonexistent branch ID "%s"' % id if res.num_tuples == 0 return [res[0][0].to_i, res[0][1].to_i] endend