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