Complex recursion in Node js

Question

I need help trying to recurse through this JSON object to build a query. I am doing so in JavaScript.

NodeJS

I have an object that looks like this

    {
      type: "and",
      left: {
        type: "eq",
        left: {
          type: "property",
          name: "City"
        },
        right: {
          type: "literal",
          value: "Seattle"
        }
      },
      right: {
        type: "and",
        left: {
          type: "eq",
          left: {
            type: "property",
            name: "State"
          },
          right: {
            type: "literal",
            value: "Washington"
          }
        },
        right: {
          type: "and",
          left: {
            type: "eq",
            left: {
              type: "property",
              name: "FirstName"
            },
            right: {
              type: "literal",
              value: "John"
            }
          },
          right: {
            type: "eq",
            left: {
              type: "property",
              name: "LastName"
            },
            right: {
              type: "literal",
              value: "Doe"
            }
          }
        }
      }
    };

Here is some of the code. The object above will be passed into the filter method below as querySchema.

I have been trying many different recipes to getting this to get this done. This is different from any recursion I have ever done.

var QueryBuilder = Class({
  constructor: function (model) {
  this.model = new model();
  },

  filter: function (querySchema) {
    var self = this;

    // recurse somewhere in here and run the conditions below somewhere in the midst
    // of the recursion.

    if (querySchema.hasOwnProperty(property)) {

      if (property == 'type' && querySchema[property] == 'and') {
        self.filter(querySchema.left);
      }


      if (querySchema.type == 'eq') {
        this.model.where(querySchema.left.name).equals(querySchema.right.);
      }

      if (querySchema.type == 'gt') {
        this.model.where(querySchema.left.name).gt(querySchema['right']);
      }
      if (querySchema.type == 'lt') {
        this.model.where(querySchema.left.name).lt(querySchema['right']);
      }
    }
  }
});

Any help is very much appreciated.

Welcome to the site! You will receive better answers if you explain why, exactly, you need help. What doesn't work? Are you getting error messages? If so, what are they? What happens, what did you expect to happen, and how are they different (if it isn't obvious)? — elixenide
– elixenide, Commented Jan 30, 2014 at 21:03
What is Class, what is model, what are those where methods? How would one compare properties against each other, are there any other types - what is the schema of your json? — Bergi
– Bergi, Commented Jan 30, 2014 at 21:07
Class is just an easy way to create prototypical inheritance and simple Class based syntax. Class and model don't matter. The goal is to recurse through the values in the object above and build the query. The is object is built from the query string. github.com/qraftlabs/node-odata-parser — user3254599
– user3254599, Commented Jan 30, 2014 at 21:35
@user3254599: OK, I see you cannot really change the output. However, how do you want to build a query - I suppose you don't mean a query string? Please explain what you expect the code to do. — Bergi
– Bergi, Commented Jan 30, 2014 at 21:41
This is an interesting model. Is type : 'or' allowed? Then you would want to make sure you handle it correctly. — Jess
– Jess, Commented Jan 30, 2014 at 21:43

Bergi · Accepted Answer · 2014-01-30 21:50:43Z

{
  type: "eq",
  left: {
    type: "property",
    name: "State"
  },
  right: {
    type: "literal",
    value: "Washington"
  }
}

You should not use right and left here (which suggests a tree of any type) when you can only compare properties with literal values.

{
  type: "and",
  left: …,
  right: {
    type: "and",
    left: …,
    right: {
      type: "and",
      left: …,
      right: …
    }
  }
};

Use an array if you can only represent a conjunction of clauses. It doesn't seem your model does support more than this, and it would make your filter method much easier (you wouldn't need to use recursion).

You don't seem to plan to change the format, but when my above assumptions are correct, then this should suffice:

filter: function (querySchema) {
  if (querySchema.type == 'and') {
    // standard binary tree traversal recursion:
    this.filter(querySchema.left);
    this.filter(querySchema.right);
  } else if (querySchema.type == 'eq') {
    this.model.where(querySchema.left.name).equals(querySchema.right.value);
  } else if (querySchema.type == 'gt') {
    this.model.where(querySchema.left.name).gt(querySchema.right.value);
  } else if (querySchema.type == 'lt') {
    this.model.where(querySchema.left.name).lt(querySchema.right.value);
  }
}

A more robust version (not changing the recursion, though) would be:

filter: function (querySchema) {
  var t = querySchema.type, l = querySchema.left, r = querySchema.right;
  if (t == 'and') {
    this.filter(l);
    this.filter(r);
  } else if (t == 'eq' || t == 'gt' || == 'lt') {
      if (l.type != "property" || r.type != "literal")
        throw new SyntaxError("Invalid comparison in query schema");
      this.model.where(l.name)[t=='eq'?'equals':t](r.value);
  } else
    throw new SyntaxError("Unknown type in query schema")
}

Good challenge. We answered at about the same time. I tested your code (changed output to a string) and it worked. Same basic algorithm as mine. +1

Jess · Accepted Answer · 2014-01-31 13:19:39Z

1

Here is an answer that takes your tree and uses recursion to return the result.

code:

#!/usr/bin/env node
var util = require('util');
util.puts("Convert tree to query!");
var tree = { /* your tree object */ };
var readNode = function(node) {

    if (node.type === "eq") {
        return "(" + node.left.name + " = '" + node.right.value + "')";
    }
    if (node.type === "and") {
        return readNode(node.left) + " and " + readNode(node.right);
    }

};
util.puts(readNode(tree));

output:

(City = 'Seattle') and (State = 'Washington') and (FirstName = 'John') and (LastName = 'Doe')

edited Jan 31, 2014 at 13:19

answered Jan 30, 2014 at 21:38

Jess

25.4k21 gold badges135 silver badges158 bronze badges

2 Comments

Bergi Over a year ago

It doesn't seem to handle lt and gt types. Btw, since OP said in the comments he got that syntax tree from a parser, I guess he doesn't want to convert it back into a string :-)

Jess Over a year ago

lt and gt are trivial to do. I don't have the model to play with so string output shows how the code needs to be written.

Collectives™ on Stack Overflow

Complex recursion in Node js

2 Answers 2

1 Comment

code:

output:

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

code:

output:

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related