2

I am using Ruby on Rails with the ClosureTree gem. I have a nested hash:

{
  :a00=>{
    :a10=>{
      :a20=>{}, 
      :a21=>{}
    }, 
    :a11=>{
      :a22=>{
        :a30=>{}, 
        :a31=>{}
      }
    }
  }
}

I want to find the value of any given key and all its 'super keys'. For example, for :a30, I want to find its value {} and the keys of the hashes it is nested in: [:a00, :a11, :a22].

I found "Finding Deeply Nested Hash Keys", which describes a method to satisfy the first part of my criteria, finding the key's value:

def deep_find(obj, key)
  return obj[key] if obj.respond_to?(:key?) && obj.key?(key)

  if obj.is_a? Enumerable
    found = nil
    obj.find { |*a| found = deep_find(a.last, key) }

    found
  end
end

However, I have not been able to come up with a way to find the 'super keys'.

the Tin Man
  • 158,662
  • 42
  • 215
  • 303
  • *"For example, for `:a30`, I want to find its value `{}` and the keys of the hashes it is nested in"* Could you explain why you already have the key `:a30` but not the full path `[:a00, :a11, :a22, :a30]`? Having the full path let's you easily access the value `tree.dig(*path)`. Maybe my question might be better formed as: How did you land in this scenario where you only have part of the path? – 3limin4t0r Mar 26 '20 at 17:51
  • Hi, the reason why I don't have the path is because I generate the nested hash from a model using the ```#hash_tree``` method from the ClosureTree gem. I then want to find the ancestor chain of the key without making any additional queries – John Stevenson Mar 26 '20 at 18:01
  • Do you have still access to the model instance itself so you can call `model.ancestry_path` ? Or does that produce additional queries? – 3limin4t0r Mar 26 '20 at 18:06

2 Answers2

2

I'd go with something like this:

def find_node_path(tree, search_key)
  return unless tree.is_a?(Hash)
  return [] if tree.key?(search_key)

  tree.each do |key, node|
    path = find_node_path(node, search_key)
    return [key, *path] if path
  end

  nil
end

path = find_node_path(tree, :a30)
#=> [:a00, :a11, :a22]

# retrieve value
value = tree.dig(*path, :a30)
#=> {}

This does the following, it returns nil if the current tree is not an hash, or if the search_key cannot be found in the current tree structure.

The method loops through all key/value-pairs of the hash, calling find_node_path recursively. If nil is returned it denotes that the search_key can't be found, thus jumping to the next iteration in the loop.

If the return value is not nil it means that the search_key is found at path in node relative to the tree. In this scenario, prepend the path with the key of the current iteration and return it.

Note: Although this solution does work if search_key is not unique in the structure. It will only return the first match found. Since this solution uses depth first it would return [:a1, :a2] when tree = {a1: {a2: {a3: {}}}, b1: {a3: {}}} for search_key = :a3.

3limin4t0r
  • 19,353
  • 2
  • 31
  • 52
  • this is exactly what I was looking for, thank you so much! all the keys are unique so that should be fine :) – John Stevenson Mar 26 '20 at 18:53
  • If you'd like to have the `search_key` in the returned path you only have to change `return [] if ...` to `return [search_key] if ...` – 3limin4t0r Mar 26 '20 at 18:56
1

Code

def extract(h,target_key)
  return [target_key, h[target_key]] if h.key?(target_key)
  h.each do |kk,v|
    next unless v.is_a?(Hash)
    arr = extract(v,target_key) 
    return [kk,*arr] unless arr.nil?
  end
  nil
end

Example

h = {
  :a00=>{
    :a10=>{
      :a20=>{1=>2}, 
      :a21=>{3=>4}
    }, 
    :a11=>{
      :a22=>{
        :a30=>{5=>6}, 
        :a31=>{7=>8}
      }
    }
  }
}

[:a00, :a10, :a20, :a21, :a11, :a22, :a30, :a31, 3, :a32].each do |k|
  puts ":#{k} -> #{extract(h,k) || "nil"}"
end

target_key -> extract(h, target_key)

:a00 -> [:a00, {:a10=>{:a20=>{1=>2}, :a21=>{3=>4}},
                :a11=>{:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}}]
:a10 -> [:a00, :a10, {:a20=>{1=>2}, :a21=>{3=>4}}]
:a20 -> [:a00, :a10, :a20, {1=>2}]
:a21 -> [:a00, :a10, :a21, {3=>4}]
:a11 -> [:a00, :a11, {:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}]
:a22 -> [:a00, :a11, :a22, {:a30=>{5=>6}, :a31=>{7=>8}}]
:a30 -> [:a00, :a11, :a22, :a30, {5=>6}]
:a31 -> [:a00, :a11, :a22, :a31, {7=>8}]
:3   -> [:a00, :a10, :a21, 3, 4]
:a32 -> nil

Explanation

In my experience the only useful way to explain how a recursive method works is to show the result of salting the method with puts statements and running an example. Moreover, to keep things straight when examining the output it's necessary to indent the output each a method calls itself and "undent" the output whenever the method returns. I've done that below for my method extract. It requires time and patience to go through the calculations that are performed, but anyone doing so should gain a solid understanding of how this method works, and perhaps also learn something about recursive methods generally. There's no need, of course, to understand the code below that displays the calculations that are performed.

INDENT = 6
$col = 4-INDENT
def indent
  $col += INDENT
end
def undent
  $col -= INDENT
end
def prn
  print " "*$col
end
def divide
  puts "#<p></p>"
end

def extract(h,target_key)
  divide
  indent
  prn; puts "entering extract"
  prn; puts "h=#{h}"
  prn; puts "h.key?(#{target_key}) = #{h.key?(target_key)}"
  if h.key?(target_key)
    prn; puts "returning #{[target_key, h[target_key]]}"
    undent
    divide
    return [target_key, h[target_key]]
  end
  h.each do |kk,v|
    prn; puts "  kk=#{kk}"
    prn; puts "  v=#{v}"
    prn; puts "  v.is_a?(Hash) = #{v.is_a?(Hash)}"
    prn; puts "  skip key" unless v.is_a?(Hash)  
    next unless v.is_a?(Hash)
    prn; puts "  call extract(#{v},target_key)"
    arr = extract(v,target_key)
    prn; puts "  arr=#{arr.nil? ? "nil" : arr} returned"
    if arr
       prn; puts "  target key found"
       prn; puts "  returning [#{[kk,*arr]}]"
       undent
       divide  
       return [kk,*arr]
    end
  end
  prn; puts "returning nil"
  undent
  divide 
  nil
end

extract(h,:a30)

entering extract
h={:a00=>{:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}}
h.key?(a30) = false
  kk=a00
  v={:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}
  v.is_a?(Hash) = true
  call extract({:a10=>{:a20..., :a31=>{7=>8}}}},target_key)

      entering extract
      h={:a10=>{:a20=>{1=>2},...,:a31=>{7=>8}}}}
      h.key?(a30) = false
        kk=a10
        v={:a20=>{1=>2}, :a21=>{3=>4}}
        v.is_a?(Hash) = true
        call extract({:a20=>{1=>2}, :a21=>{3=>4}},target_key)

            entering extract
            h={:a20=>{1=>2}, :a21=>{3=>4}}
            h.key?(a30) = false
              kk=a20
              v={1=>2}
              v.is_a?(Hash) = true
              call extract({1=>2},target_key)

                  entering extract
                  h={1=>2}
                  h.key?(a30) = false
                    kk=1
                    v=2
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
              kk=a21
              v={3=>4}
              v.is_a?(Hash) = true
              call extract({3=>4},target_key)

                  entering extract
                  h={3=>4}
                  h.key?(a30) = false
                    kk=3
                    v=4
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
            returning nil

        arr=nil returned
        kk=a11
        v={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
        v.is_a?(Hash) = true
        call extract({:a22=>{:a30..., :a31=>{7=>8}}},target_key)

            entering extract
            h={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
            h.key?(a30) = false
              kk=a22
              v={:a30=>{5=>6}, :a31=>{7=>8}}
              v.is_a?(Hash) = true
              call extract({:a30=>{5=>6},
                :a31=>{7=>8}},target_key)

                  entering extract
                  h={:a30=>{5=>6}, :a31=>{7=>8}}
                  h.key?(a30) = true
                  returning [:a30, {5=>6}]

              arr=[:a30, {5=>6}] returned
              target key found
              returning [[:a22, :a30, {5=>6}]]

        arr=[:a22, :a30, {5=>6}] returned
        target key found
        returning [[:a11, :a22, :a30, {5=>6}]]

  arr=[:a11, :a22, :a30, {5=>6}] returned
  target key found
  returning [[:a00, :a11, :a22, :a30, {5=>6}]]

  #=> [:a00, :a11, :a22, :a30, {5=>6}]
Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
  • 2
    Although the answer looks fine code wise, I can't give this an upvote without any explanation. – 3limin4t0r Mar 27 '20 at 00:05
  • @3limin4t0r, that's a fair comment. To my mind, explanations of recursive methods is an all-or-nothing affair. The "all" option leads the reader through the calculations, step-by-step; the "nothing" alternative leaves it to the reader to work it out. Alas, the "all" option is quite time-consuming for the explainer. As a student, I prefer the learning-by-digging approach, frustrating as it can be, but I recognize that I am in the minority. I therefore have provided a detailed explaination. – Cary Swoveland Mar 27 '20 at 02:42