Using a tree instead of a linked list

tree_paths.rb

class TreeNode
  attr_reader :datum, :children

  def initialize(datum)
    @datum, @children = datum, []
  end
    
  def child_for(datum)
    @children.find { |child| datum == child.datum }
  end
  
  def ensure_child_for(datum)
    child = child_for(datum) || TreeNode.new(datum)
    @children << child unless @children.include? child
    child
  end
  
  def add_branch(data)
    data.inject(self) { |tree, datum| tree.ensure_child_for datum }
  end
  
  def branches
    return [self] if leaf?
    @children.flat_map { |child| child.branches }.map { |branch| [self, *branch] }
  end
  
  def leaf?
    @children.empty?
  end

  def inspect
    "#<TreeNode datum: #{datum.inspect}, children: #{@children.map(&:datum)}>"
  end
end

# =====  Setup  =====
# The tree is written in a way where we can use it to store whatever we like
# In our case, it is used to store path information from a web request.
# So if you go to https://github.com/JoshCheek/music-with-sonic-pi/blob/master/Readme.md#make-music-with-ruby
# The path information would be /JoshCheek/music-with-sonic-pi/blob/master/Readme.md
# We could parse that into ['JoshCheek', 'music-with-sonic-pi', 'blob', 'master', 'Readme.md']
# and each of the elements in this array would have a tree that would match it.
# For simplicity, though, we'll just use paths /1a/2a/3a through /1c/2c/3c (27 all together)
#
# In reality, we're doing this because we would want different pieces of code to run for each different place the user ends up.
# But in our case, we're ignoring this, because we're just interested in how the tree lets us locate the node more efficiently.
root = TreeNode.new ''
%w[1a 1b 1c].product(%w[2a 2b 2c]).product(%w[3a 3b 3c]).map(&:flatten).each do |path_segments|
  path_segments.map { |s| "/#{s}" }.join # => "/1a/2a/3a", "/1a/2a/3b", "/1a/2a/3c", "/1a/2b/3a", "/1a/2b/3b", "/1a/2b/3c", "/1a/2c/3a", "/1a/2c/3b", "/1a/2c/3c", "/1b/2a/3a", "/1b/2a/3b", "/1b/2a/3c", "/1b/2b/3a", "/1b/2b/3b", "/1b/2b/3c", "/1b/2c/3a", "/1b/2c/3b", "/1b/2c/3c", "/1c/2a/3a", "/1c/2a/3b", "/1c/2a/3c", "/1c/2b/3a", "/1c/2b/3b", "/1c/2b/3c", "/1c/2c/3a", "/1c/2c/3b", "/1c/2c/3c"
  root.add_branch path_segments
end

# This is the structure of our tree
def visualize(tree)
  children = tree.children.map { |child| child.children.empty? ? child.datum : visualize(child) }
  { tree.datum => children }
end
visualize(root)
# => {""=>
#      [{"1a"=>
#         [{"2a"=>["3a", "3b", "3c"]},
#          {"2b"=>["3a", "3b", "3c"]},
#          {"2c"=>["3a", "3b", "3c"]}]},
#       {"1b"=>
#         [{"2a"=>["3a", "3b", "3c"]},
#          {"2b"=>["3a", "3b", "3c"]},
#          {"2c"=>["3a", "3b", "3c"]}]},
#       {"1c"=>
#         [{"2a"=>["3a", "3b", "3c"]},
#          {"2b"=>["3a", "3b", "3c"]},
#          {"2c"=>["3a", "3b", "3c"]}]}]}


# =====  Searching through paths sequentiallly  =====
# Say someone makes a GET request to /1c/2c/3a (We're ignoring the GET)
# If we search sequentially, we can find the correct node
# But we have to search through 25 places before we find it.
root.branches.map { |branch| branch.map(&:datum).join("/") } # => ["/1a/2a/3a", "/1a/2a/3b", "/1a/2a/3c", "/1a/2b/3a", "/1a/2b/3b", "/1a/2b/3c", "/1a/2c/3a", "/1a/2c/3b", "/1a/2c/3c", "/1b/2a/3a", "/1b/2a/3b", "/1b/2a/3c", "/1b/2b/3a", "/1b/2b/3b", "/1b/2b/3c", "/1b/2c/3a", "/1b/2c/3b", "/1b/2c/3c", "/1c/2a/3a", "/1c/2a/3b", "/1c/2a/3c", "/1c/2b/3a", "/1c/2b/3b", "/1c/2b/3c", "/1c/2c/3a", "/1c/2c/3b", "/1c/2c/3c"]
    .index("/1c/2c/3a")                                      # => 24


# =====  How we search through it as a tree  =====
# But if the first path segment is "1c", then I can ignore all children of "1a" and "1b", (there are 18 of them!)
root               # => #<TreeNode datum: "", children: ["1a", "1b", "1c"]>
  .child_for('1c') # => #<TreeNode datum: "1c", children: ["2a", "2b", "2c"]>
  .child_for('2c') # => #<TreeNode datum: "2c", children: ["3a", "3b", "3c"]>
  .child_for('3a') # => #<TreeNode datum: "3a", children: []>


# =====  The savings of searching as a tree
# So we look at the 3 children of the root to find 1c, then 1c's 3 children to find 2c, then the first child of 2c to find 3a
# 3 + 3 + 1 = 7, so we look in 7 places instead of 25.
# This savings compounds the greater we get. A worst case scenario of 10x10x10, sequentially is 1000 checks, but with our tree, is 30!
def find_node(node, data)
  # In reality, we'd push that algorithm into the tree, I'm doing it out here so that we can see the work
  return node if data.empty?
  child = node.children.find do |child|
    child # the 7 nodes we check
    # => #<TreeNode datum: "1a", children: ["2a", "2b", "2c"]>
    #    ,#<TreeNode datum: "1b", children: ["2a", "2b", "2c"]>
    #    ,#<TreeNode datum: "1c", children: ["2a", "2b", "2c"]>
    #    ,#<TreeNode datum: "2a", children: ["3a", "3b", "3c"]>
    #    ,#<TreeNode datum: "2b", children: ["3a", "3b", "3c"]>
    #    ,#<TreeNode datum: "2c", children: ["3a", "3b", "3c"]>
    #    ,#<TreeNode datum: "3a", children: []>
    child.datum == data.first
  end
  find_node child, data.drop(1)
end

find_node root, %w[1c 2c 3a] # => #<TreeNode datum: "3a", children: []>