Nested Dictionary Navigation

Question

I have a nested dictionary/hash structure in Ruby like this:

d = {
 :foo => {
   :hoo => nil,
   :baz => {
     # ...
   },
 },

 :bar => {
   :doo => { 
      # ...
   },
   :loo => nil, 
 },

 # ...
}

Every individual dictionary is of unknown size. Its keys are symbols and its values are either nil or another dictionary. I am trying to write two methods:

down() takes the current dictionary and a valid key as arguments and returns a pointer to that value (either nil or another dictionary).
up() takes the current dictionary and returns a pointer to the outer dictionary it is contained within.

down() is straightforward (it is the same as d[:foo]), but I am hesitant to just use d[:foo] because up() is basically impossible without storing some additional structural/navigation information about d as down() is called.

The return values cannot be a copy of anything in d, they must be pointers. I am still confused about which situations are pass-by-value vs pass-by-ref in Ruby, but I do know all of its "effectively a pointer" variables are mutable.

Update:

When I say "takes the current dictionary" I am just referring to some variable dict such that dict = d or dict = (some child of d). dict is either a dictionary or nil. For example:

d = # ...

dict = down(d, :foo)
# dict is now the current dictionary and points to {:hoo=>nil,:baz=>{}} in d

dict2 = down(dict, :baz)
# down() "takes the current dictionary" (dict) 
# then returns a new current dictionary (dict2)

In my attempts at a solution, it has seemed essential that some additional entity is keeping track of the level at which the current dictionary resides.

I've removed the unrelated information about your future Rust port — questions should be focused. When you get there, you may be interested in [How do I express mutually recursive data structures in safe Rust?](https://stackoverflow.com/a/36168919/155423) — Shepmaster, Mar 19 '20 at 02:09
When you say "takes the current dictionary" is the current dictionary, or for that matter, any dictionary, described by an array such as `[:foo, :hoo]` or are all the keys at all the levels unique, so that, for example, if `:goo` is a dictionary we need to keep track of its ancestors? It might be more convenient to write `:hoo=>[]` rather than `:hoo=>nil` if it has no children. — Cary Swoveland, Mar 19 '20 at 03:38
@CarySwoveland When I say "the current dictionary" I just mean its a variable pointing to some dictionary inside `d`. Also if `:hoo=>[]` is better I have no special reason to use `nil` so by all means... — springworks00, Mar 19 '20 at 04:30
You may wish to look at [Is Ruby pass-by-reference or pass-by-value?](https://mixandgo.com/learn/is-ruby-pass-by-reference-or-pass-by-value). — Cary Swoveland, Mar 19 '20 at 05:03
Your question is extremely unclear. What do you mean by "pointer"? Ruby does not have a concept called "pointer", so if you are introducing your own concepts, you need to provide a clear, objective, complete, precise, unambiguous definition of what you mean by that concept, otherwise it will be impossible to answer the question. Also, you wrote "I am still confused about which situations are pass-by-value vs pass-by-ref in Ruby", but there is actually nothing confusing about this, since Ruby simply does not support pass-by-reference at all, so *all* situations are *always* pass-by-value. — Jörg W Mittag, Mar 19 '20 at 07:17

Cary Swoveland · Accepted Answer · 2020-03-19T07:27:07.270

I'm not certain I fully understand the question but perhaps you are looking for something like the following, which is just a linked list and not a nested hash of dictionaries, but I think this is more typical of what is done in Ruby.

class Dictionary
  attr_accessor :name, :up, :down
  def initialize(name, up)
    @name = name
    @up = up
    @down = []
    up.down << self unless up.nil?
  end
end

We begin by creating the top Dictionary.

top = Dictionary.new("top", nil)
  #=> #<Dictionary:0x000056dd361bcd48 @name="top", @up=nil, @down=[]>

Now let's create a child of top.

top_foo = Dictionary.new("foo", top)
  #=> #<Dictionary:0x000056dd361ce458 @name="foo",
  #     @up=#<Dictionary:0x000056dd361bcd48 @name="top", @up=nil,
  #       @down=[#<Dictionary:0x000056dd361ce458 ...>]>,
  #     @down=[]>

Look at return value carefully. The value of top_foo's instance variable @up is the instance of Dictionary named top. We can see this more clearly as follows:

top_foo.up.name
  #=> "top"
top_foo.down
  #=> []

Let's see how top.down (formerly an empty array) has changed.

top.down.map(&:name)
  #=> ["foo"]

Now create another child of top.

top_goo = Dictionary.new("goo", top)
  #=> #<Dictionary:0x000056dd3611a480 @name="goo",
  #     @up=#<Dictionary:0x000056dd35eed180 @name="top",...
  #     @down=[]> 
top_goo.up.name
  #=> "top" 
top_goo.down
  #=> []

top.down.map(&:name)
  #=> ["foo", "goo"]

Now create a child of top_foo:

top_foo_who = Dictionary.new("who", top_foo)
  #=> #<Dictionary:0x000056dd36171488 @name="who",
  #     @up=#<top_foo instance>

top_foo_who.name
  #=> "who"
top_foo_who.up.name
  #=> "foo"
top_foo_who.down
  #=> []

top_foo.down.map(&:name)
  #=> "foo"

Suppose we wish to go from top_foo_who to top.

start = top_foo_who
dict = loop do
  break start if start.up.nil?
  start = start.up
end
  #=> #<Dictionary:...>

dict.name
  #=> "top" 
dict.down.map(&:name)
  #=> ["foo", "goo"]

If we wanted to go from top to top_foo, by the name "foo", we could write:

idx = top.down.map(&:name).index("foo")
  #=> 0
dict = top.down[idx]      
  #=> #<Dictionary...>
dict.name
  #=> "foo"

Nested Dictionary Navigation

1 Answers1