Глубокое превращение хэша в плоский массив путей

Question

Я хотел бы получить советы и примеры того, как можно преобразовать различные структуры, например:

h = {
    friend: [:id, :name],
    meta: {
        board: [:id, :name],
        column: [:id, :name, users: [:id, :name]]
    },
    trello: [:id, :name]
}

в массив, как это:

[[:friend, :id],
 [:friend, :name],
 [:meta, :board, :id],
 [:meta, :board, :name],
 [:meta, :column, :id],
 [:meta, :column, :name],
 [:meta, :column, :users, :id],
 [:meta, :column, :users, :name],
 [:trello, :id],
 [:trello, :name]]

Каждый элемент этого массива является полным путем.

Answer 1

Это довольно стандартная проблема обхода дерева .Вы можете использовать DFS через рекурсию:

# for Array.wrap; It's needed in pure ruby script, not in Rails
require 'active_support/all'

def deep_flatten(tree, path, result)
  tree.each do |key, value|
    Array.wrap(value).each do |e|
      if e.is_a? Hash
        deep_flatten(e, path + [key], result)
      else
        result << path + [key, e]
      end
    end
  end
end

tree = {
  friend: [:id, :name],
  meta: {
    board: [:id, :name],
    column: [:id, :name, users: [:id, :name]]
  },
  trello: [:id, :name]
}

result = []
deep_flatten(tree, [], result)
result.each do |line|
  puts line.inspect
end

Он выводит:

[:friend, :id]
[:friend, :name]
[:meta, :board, :id]
[:meta, :board, :name]
[:meta, :column, :id]
[:meta, :column, :name]
[:meta, :column, :users, :id]
[:meta, :column, :users, :name]
[:trello, :id]
[:trello, :name]

Array.wrap

Answer 2

Код

def doit(obj)
  case obj
  when Hash
    obj.each_with_object([]) do |(k,v),a|
      case v
      when Symbol
        a << v
      else
        doit(v).each { |aa| a << [k, *aa] }
      end
    end
  else
    obj.each_with_object([]) do |v,a|
      case v
      when Symbol
        a << v
      else
        doit(v).each { |aa| a << aa }
      end
    end
  end
end

Пример

Для хэша h, приведенного в вопросе, получаются следующие результаты.

doit(h)
  #=> [[:friend, :id], [:friend, :name],
  #    [:meta, :board, :id], [:meta, :board, :name], [:meta, :column, :id],
  #    [:meta, :column, :name], [:meta, :column, :users, :id],
  #    [:meta, :column, :users, :name],
  #    [:trello, :id], [:trello, :name]] 

Пояснение

Операции, выполняемые рекурсивными методами, всегда трудно объяснить.По моему опыту, лучший способ - засолить код с помощью операторов puts.Однако одного этого недостаточно, поскольку при просмотре выходных данных трудно отслеживать уровень рекурсии, на котором получены конкретные результаты, когда метод вызывает сам себя и какую версию он возвращает.Решение этой проблемы состоит в том, чтобы сделать отступы и отступы для результатов, что я и сделал ниже.

INDENT = 4

@col = -INDENT

def indent
  @col += INDENT
end

def undent
  @col -= INDENT
end

def pu(s)
  print " "*@col
  puts s
end

def doit(obj)
  begin                                                  # rem
    indent                                               # rem
    pu "passed obj = #{obj}"                             # rem   
    case obj
    when Hash
      pu "processing hash..."                            # rem
      obj.each_with_object([]) do |(k,v),a|
        pu "k=#{k}, v=#{v}, a=#{a}"
        case v
        when Symbol
          a << v
        else
          doit(v).each { |aa| a << [k, *aa] }
        end
      end
    else

      pu "processing array..."                           # rem
      obj.each_with_object([]) do |v,a|
        pu "v = #{v}"                                    # rem
        pu "a = #{a}"                                    # rem
        case v
        when Symbol
          pu "v is a symbol"                             # rem
          a << v
        else
          pu "calling doit(v). v is a hash or an array"  # rem
          doit(v).each { |aa| a << aa }
        end
      end
    end.
    tap { |o| pu "returning #{o}" }                      # rem
  ensure                                                 # rem
    undent                                               # rem
  end
end

Строки, заканчивающиеся # rem (для «удаления») - это строки, которые я добавил в метод.

doit(h)

приводит к отображению следующего.

passed obj = {:friend=>[:id, :name], :meta=>{:board=>[:id, :name],
              :column=>[:id, :name, {:users=>[:id, :name]}]}, :trello=>[:id, :name]}
processing hash...
k=friend, v=[:id, :name], a=[]
    passed obj = [:id, :name]
    processing array...
    v = id
    a = []
    v is a symbol
    v = name
    a = [:id]
    v is a symbol
    returning [:id, :name]

k=meta, v={:board=>[:id, :name], :column=>[:id, :name, {:users=>[:id, :name]}]},
a=[[:friend, :id], [:friend, :name]]
    passed obj = {:board=>[:id, :name],
                  :column=>[:id, :name, {:users=>[:id, :name]}]}
    processing hash...
    k=board, v=[:id, :name], a=[]
        passed obj = [:id, :name]
        processing array...
        v = id
        a = []
        v is a symbol
        v = name
        a = [:id]
        v is a symbol
       returning [:id, :name]

    k=column, v=[:id, :name, {:users=>[:id, :name]}],
    a=[[:board, :id], [:board, :name]]
        passed obj = [:id, :name, {:users=>[:id, :name]}]
        processing array...
        v = id
        a = []
        v is a symbol
        v = name
        a = [:id]
        v is a symbol
        v = {:users=>[:id, :name]}
        a = [:id, :name]
        calling doit(v). v is a hash or an array
            passed obj = {:users=>[:id, :name]}
            processing hash...
            k=users, v=[:id, :name], a=[]
                passed obj = [:id, :name]
                processing array...
                v = id
                a = []
                v is a symbol
                v = name
                a = [:id]
                v is a symbol
                returning [:id, :name]
            returning [[:users, :id], [:users, :name]]
        returning [:id, :name, [:users, :id], [:users, :name]]
    returning [[:board, :id], [:board, :name], [:column, :id], [:column, :name],     
               [:column, :users, :id], [:column, :users, :name]]

k=trello, v=[:id, :name], a=[[:friend, :id], [:friend, :name], [:meta, :board, :id],
 [:meta, :board, :name], [:meta, :column, :id], [:meta, :column, :name],
 [:meta, :column, :users, :id], [:meta, :column, :users, :name]]
    passed obj = [:id, :name]
    processing array...
    v = id
    a = []
    v is a symbol
    v = name
    a = [:id]
    v is a symbol
    returning [:id, :name]
returning [[:friend, :id], [:friend, :name], [:meta, :board, :id],
           [:meta, :board, :name], [:meta, :column, :id], [:meta, :column, :name],
           [:meta, :column, :users, :id], [:meta, :column, :users, :name],
           [:trello, :id], [:trello, :name]]

 #=> [[:friend, :id], [:friend, :name], [:meta, :board, :id], [:meta, :board, :name],
      [:meta, :column, :id], [:meta, :column, :name], [:meta, :column, :users, :id],
      [:meta, :column, :users, :name], [:trello, :id], [:trello, :name]]