嵌入對象的路徑

Question

給定一個嵌套的數組或哈希作爲接收者和一些對象作爲參數，如果接收者包含該對象，那麼返回該對象的出現路徑的最佳方式是什麼？我將路徑定義爲導向該對象的數組索引或散列鍵。參數對象永遠不會是任何散列鍵，並且永遠不會出現多次。例如，我想到：

[ 
    :a, 
    [:b, :c, {:d => :foo}], 
    :e, 
] 
.path_to(:foo) # => [1, 2, :d] 

{ 
    :a => [3, "foo"], 
    :b => 5, 
    :c => 2, 
} 
.path_to(3) # => [:a, 0] 

當沒有發生，返回nil：

[:foo, "hello", 3] 
.path_to(:bar) => nil 

如果沒有一個有一個合理的答案來了，那麼我將不久後我自己的答案。

Answer 1

沒有什麼喜歡一點遞歸。

require 'minitest/autorun' 

class Array 
    def path_to(obj) 
    # optimize this 
    Hash[self.each.with_index.to_a.map {|k,v| [v,k]}].path_to(obj) 
    end 
end 

class Hash 
    def path_to(obj) 
    inverted = self.invert 
    if inverted[obj] 
     [inverted[obj]] 
    else 
     self.map {|k, v| 
     if v.respond_to?(:path_to) 
      if res = v.path_to(obj) 
      [k] + res 
      end 
     end 
     }.find {|path| 
     path and path[-1] != nil 
     } 
    end 
    end 
end 

describe "path_to" do 
    it "should work with really simple arrays" do 
    [:a, :e,].path_to(:a).must_equal [0] 
    end 
    it "should work with simple arrays" do 
    [:a, [:b, :c], :e,].path_to(:c).must_equal [1, 1] 
    end 
    it "should work with arrays" do 
    [:a, [:b, :c, {:d => :foo}], :e,].path_to(:foo).must_equal [1, 2, :d] 
    end 
    it "should work with simple hashes" do 
    {:d => :foo}.path_to(:foo).must_equal [:d] 
    end 
    it "should work with hashes" do 
    ({:a => [3, "foo"], :b => 5, :c => 2,}.path_to(3).must_equal [:a, 0]) 
    end 
end 

Answer 2

在這裏，你是我自己的遞歸解決方案。我相信它可以得到改善，但這是一個很好的開始，並且按照要求正常工作。

# path.rb 
module Patheable 
    def path_to item_to_find 
    path = [] 
    find_path(self, item_to_find, path) 
    result = path.empty? ? nil : path 
    result.tap { |r| puts r.inspect } # just for testing 
    end 

    private 

    def find_path(current_item, item_to_find, result) 
    if current_item.is_a?(Array) 
     current_item.each_with_index do |value, index| 
     find_path(value, item_to_find, result.push(index)) 
     end 
    elsif current_item.is_a?(Hash) 
     current_item.each do |key, value| 
     find_path(value, item_to_find, result.push(key)) 
     end 
    else 
     result.pop unless current_item == item_to_find 
    end 
    end 
end 

class Array 
    include Patheable 
end 

class Hash 
    include Patheable 
end 

[ 
    :a, 
    [:b, :c, {:d => :foo}], 
    :e, 
].path_to(:foo) # => [1, 2, :d] 

{ 
    :a => [3, "foo"], 
    :b => 5, 
    :c => 2, 
}.path_to(3) # => [:a, 0] 

[:foo, "hello", 3].path_to(:bar) # => nil 
#end path.rb 

# example of use 
$ ruby path.rb 
[1, 2, :d] 
[:a, 0] 
nil 

Answer 3

這是我想出來的答案。

class Object 
    def path_to obj; end 
end 

class Array 
    def path_to obj 
    if i = index(obj) then return [i] end 
    a = nil 
    _, i = to_enum.with_index.find{|e, _| a = e.path_to(obj)} 
    a.unshift(i) if i 
    end 
end 

class Hash 
    def path_to obj 
    if value?(obj) then return [key(obj)] end 
    a = nil 
    kv = find{|_, e| a = e.path_to(obj)} 
    a.unshift(kv.first) if kv 
    end 
end