Pfad zu einem eingebetteten Objekt

Question

Ein verschachteltes Array oder ein Hash als Empfänger und ein Objekt als Argument vorausgesetzt, was ist der beste Weg, um den Pfad zu einem Vorkommen des Objekts zurückzugeben, wenn der Empfänger das Objekt enthält, oder nil? Ich definiere Pfad als ein Array von Array-Indizes oder Hash-Schlüssel, die zu dem Objekt führt. Das Argument-Objekt wird niemals einer der Hash-Schlüssel sein und wird niemals mehr als einmal erscheinen. Zum Beispiel habe ich erwarten:

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

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

Wenn kein Auftreten, Rückkehr nil:

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

Wenn niemand mit einer angemessenen Antwort kommt, dann werde ich kurz meine eigene Antwort posten.

Answer 1

Nichts wie ein bisschen Rekursion.

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

Hier sind Sie meine eigene rekursive Lösung. Ich bin sicher, dass es verbessert werden könnte, aber es ist ein guter Anfang und funktioniert genau wie verlangt.

# 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

Dies ist die Antwort, die ich mir ausgedacht habe.

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