What is this Hash-like/Tree-like Construct Called?

Question

I want to create a "Config" class that acts somewhere between a hash and a tree. It's just for storing global values, which can have a context.

Here's how I use it:

Config.get("root.parent.child_b") #=> "value"

Here's what the class might look like:

class Construct

  def get(path)
    # split path by "."
    # search tree for nodes
  end

  def set(key, value)
    # split path by "."
    # create tree node if necessary
    # set tree value
  end

  def tree
    {
      :root => {
        :parent => {
          :child_a => "value",
          :child_b => "another value"
        },
        :another_parent => {
          :something => {
            :nesting => "goes on and on"
          }
        }
      }
    }
  end

end

Is there a name for this kind of thing, somewhere between Hash and Tree (not a Computer Science major)? Basically a hash-like interface to a tree.

Something that outputs like this:

t = TreeHash.new
t.set("root.parent.child_a", "value")
t.set("root.parent.child_b", "another value")

desired output format:

t.get("root.parent.child_a") #=> "value"
t.get("root") #=> {"parent" => {"child_a" => "value", "child_b" => "another value"}}

instead of this:

t.get("root") #=> nil

or this (which you get the value from by calling {}.value)

t.get("root") #=> {"parent" => {"child_a" => {}, "child_b" => {}}}

Answer 1

I think this resembles a TreeMap data structure similar to the one in Java described here. It does the same thing (key/value mappings) but retrieval might be different since you are using the nodes themselves as the keys. Retrieval from the TreeMap described is abstracted from the implementation since, when you pass in a key, you don't know the exact location of it in the tree.

Hope that makes sense!

Answer 2

Er... it can certainly be done, using a hierarchical hash table, but why do you need the hierarchy? IF you only need exactly-matching get and put, why can't you just make a single hash table that happens to use a dot-separated naming convention?

That's all that's needed to implement the functionality you've asked for, and it's obviously very simple...

Answer 3

why use a hash-like interface at all? why not use chaining of methods to navigate your tree. for example config.root.parent.child_b and use instance methods and if needed method_missing() to implement them?

Answer 4

You can implement one in no-time:

class TreeHash < Hash
  attr_accessor :value

  def initialize
    block = Proc.new {|h,k| h[k] = TreeHash.new(&block)}
    super &block
  end

  def get(path)
    find_node(path).value
  end

  def set(path, value)
    find_node(path).value = value
  end

private

  def find_node(path)
    path.split('.').inject(self){|h,k| h[k]}
  end
end

You could improve implementation by setting unneeded Hash methods as a private ones, but it already works the way you wanted it. Data is stored in hash, so you can easily convert it to yaml.

---

EDIT:

To meet further expectations (and, convert to_yaml by default properly) you should use modified version:

class TreeHash < Hash
  def initialize
    block = Proc.new {|h,k| h[k] = TreeHash.new(&block)}
    super &block
  end

  def get(path)
    path.split('.').inject(self){|h,k| h[k]}
  end

  def set(path, value)
    path = path.split('.')
    leaf = path.pop
    path.inject(self){|h,k| h[k]}[leaf] = value
  end
end

This version is slight trade-off, as you cannot store values in non-leaf nodes.