current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 2 down vote favorite

I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example:

{
    "date": "1970-01-01 00:00:00",
    "foobar": "baz",
    "user": {
        "name": "foobar",
        "id": 2
    }
}

And the following library ruleset:

Hydrator hydrator = new Hydrator
hydrator.add("date", DateTime)
hydrator.add("foobar", String)
User user = hydrator.add("user", User)
user.add("name", String)
user.add("type", Integer)

DataSet data = hydrator.parse(jsonInput)

So far, it's working great. I have created a Node, and each Node can have children. I just walk through the entire JSON file, create Node instances for each key/value, and create the hierarchy. When i instance the node, i add some metadata. Then, in a big method, i walk through the entire node tree and hydrate depending on the metadata. However, i'm looking for an efficient way of doing this, since it ended up being a little slow.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

A fairly-standard post-order depth-first traversal should work nicely, in linear time on the number of nodes. The main trick is traversing your hydrator tree and data tree together. Post-order means all the dependencies will be instantiated before they're needed higher up. In pseudocode, it would look something like this:

traverse(hydrator_node, json_node)
  for each child of hydrator node
    throw error if json_node doesn't have matching child
    recursively call traverse(hydrator_child, json_child)

  instantiate current node
share|improve this answer
    
That's faster than level-order? I mean, instantiating the current node and then going to the recursive function. –  vinnylinux Jul 31 at 18:07
1  
The advantage of post-order is your dependencies get instantiated first. For example, you'll have name and id already hydrated when you go to make your user. If you use in-order or pre-order, you end up doing weird workarounds to update those dependencies later, which usually costs you speed. –  Karl Bielefeldt Jul 31 at 18:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.