Adding an item to a hierarchical data structure

Question

What I need to do is create a new object, modify it using a recursive function, then merge it with another object, and do this all in such a way that the values of the new object take precedence over the values in the object I'm merging it with.

Currently, my code works, but I'd like to have more readable code, particularly this statement for the add operation:

@set.merge!(
 update(@set, insert(parent, id), @set[parent][1] + 1)
)

I've already refactored quite a bit, but I feel like there's a functional way, or at least more readable way, to write what I current have. I want it to be something like: new object → update it → merge it.

Here is the whole class with tests:

# Nested set for comments, for making it easy to load all comments in a list, sorted according to their nesting,
# and for nesting to be indicated.
class Database 
 def initialize
 @set = {}
 @largest = -1
 end 
 def fetch
 #Need Better syntax for this.
 @set.to_a.sort { |el1, el2| el1[1][0] <=> el2[1][0] }
 end 
 def add(parent: nil, id: -1)
 if parent
 @set.merge!(
 update(@set, insert(parent, id), @set[parent][1] + 1)
 )
 else
 @set[id] = [@largest+1, @largest+2]
 end
 @largest += 2
 @set
 end 
 private 
 def insert(parent_id, id)
 parent_range = @set[parent_id]
 {
 parent_id => [parent_range[0], parent_range[1] + 2],
 id => [parent_range[1], parent_range[1] + 1]
 }
 end 
 # O(n) * 2^n
 def update(old_state, state, target)
 # optimization for this:
 id,range = old_state.to_a.select{ |entry| entry[1][0] == target || entry[1][1] == target }[0]
 # better readability for this:
 if range && !state[id] 
 state[id] = 
 range.index(target) == 0 ? range.map{|n| n + 2} : [range[0], range[1] + 2]
 2.times do |i|
 update(old_state, state, range[i] + 1) if range[i] != state[id][i] 
 end
 end
 state
 end
end 
d = Database.new
d.add({id: 1, parent: nil })
d.add({id: 2, parent: nil })
d.add({id: 3, parent: nil })
p d.fetch == [
 [1, [0, 1]], 
 [2, [2,3]], 
 [3, [4,5]],
 ]
d.add({id: 4, parent: 1 })
d.add({id: 5, parent: 2 })
d.add({id: 6, parent: 3 })
p d.fetch == [
 [1, [0, 3]], 
 [4, [1, 2]], 
 [2, [4,7]], 
 [5, [5,6]], 
 [3, [8,11]],
 [6, [9,10]],
 ]
d.add({id: 7, parent: 1 })
d.add({id: 8, parent: 7 })
# Final output.
# 1
# 4
# 7
# 8
# 2
# 5
# 3
# 6
p d.fetch == [
 [1, [0, 7]], 
 [4, [1, 2]], 
 [7, [3, 6]], 
 [8, [4, 5]], 
 [2, [8,11]], 
 [5, [9,10]], 
 [3, [12,15]],
 [6, [13,14]],
 ]

UPDATE: Will probably just do this:

 insert(parent, id)
 .yield_self { |obj| update(@set, obj, @set[parent][1] + 1) }
 .yield_self { |updated_set| @set.merge!(updated_set) }

Answer 1

Rubocop Report

Rubocop was able to correct a lot of style and layout offenses. 1 file inspected, 59 offenses detected, 53 offenses corrected.

The following offenses remain:

• Metrics/LineLength: Line is too long. [112/80]
• Metrics/AbcSize: Assignment Branch Condition size for update is too high. [24.1/15]
• Style/MultipleComparison: Avoid comparing a variable with multiple items in a conditional, use Array#include? instead.
• Metrics/LineLength: Line is too long. [99/80]
• Style/NumericPredicate: Use range.index(target).zero? instead of range.index(target) == 0.
• Metrics/LineLength: Line is too long. [85/80]

Fixing Offenses

LineLength and MultipleComparison offense:

# optimization for this:
id,range = old_state.to_a.select{ |entry| entry[1][0] == target || entry[1][1] == target }[0]

id, range = old_state.to_a.select do |entry|
 [entry[1][0], entry[1][1]].include?(target)[0]
end

LineLength + NumericPredicate offense:

state[id] = 
 range.index(target) == 0 ? range.map{|n| n + 2} : [range[0], range[1] + 2]

 state[id] =
 if range.index(target).zero?
 range.map { |n| n + 2 }
 else
 [range[0], range[1] + 2]

After refactoring, we get a new issue that our method got too big. The complexity is still too high.

• Metrics/AbcSize: Assignment Branch Condition size for update is too high. [25.06/15]
• Metrics/MethodLength: Method has too many lines. [15/10]

We are adviced to break up this method. It's doing a bit too much. So we'll put the next part in another method.

 state[id] =
 if range.index(target).zero?
 range.map { |n| n + 2 }
 else
 [range[0], range[1] + 2]
 end
 2.times do |i|
 update(old_state, state, range[i] + 1) if range[i] != state[id][i]
 end

 def update_range(old_state, state, target, id, range)
 state[id] =
 if range.index(target).zero?
 range.map { |n| n + 2 }
 else
 [range[0], range[1] + 2]
 end
 2.times do |i|
 update(old_state, state, range[i] + 1) if range[i] != state[id][i]
 end
 end

There are no offenses remaining and complexity is within bounds.

Refactored Code

# frozen_string_literal: true
# Nested set for comments, for making it easy to load all comments in a
# list, sorted according to their nesting, and for nesting to be indicated.
class Database
 def initialize
 @set = {}
 @largest = -1
 end
 def fetch
 @set.to_a.sort { |el1, el2| el1[1][0] <=> el2[1][0] }
 end
 def add(parent: nil, id: -1)
 if parent
 @set.merge!(
 update(@set, insert(parent, id), @set[parent][1] + 1)
 )
 else
 @set[id] = [@largest + 1, @largest + 2]
 end
 @largest += 2
 @set
 end
 private
 def insert(parent_id, id)
 parent_range = @set[parent_id]
 {
 parent_id => [parent_range[0], parent_range[1] + 2],
 id => [parent_range[1], parent_range[1] + 1]
 }
 end
 # O(n) * 2^n
 def update(old_state, state, target)
 id, range = old_state.to_a.select do |entry|
 [entry[1][0], entry[1][1]].include?(target)[0]
 end
 update_range(old_state, state, target, id, range) if range && !state[id]
 state
 end
 def update_range(old_state, state, target, id, range)
 state[id] =
 if range.index(target).zero?
 range.map { |n| n + 2 }
 else
 [range[0], range[1] + 2]
 end
 2.times do |i|
 update(old_state, state, range[i] + 1) if range[i] != state[id][i]
 end
 end
 end