13

As far as I understand, visitor pattern is often used to add methods to some hierarchy structure. But I still don't get it: see the example where I try to highlight left subtree:

subtree highlighting

Javascript tree implementation:

  function node(val) {
    this.value = val;
    this.left = this.right = null;
  }

  var tree = new node("A");
  tree.left = new node("B1");
  tree.right = new node("B2");
  tree.left.left = new node("C1");
  tree.left.right = new node("C2");

I think I am using visitor pattern highlighting:

node.prototype.accept = function(visitorObj) {
  visitorObj.visit(this);
}

function visitor() {
  var that = this;
  this.visit = function(tgt) {
    tgt.value = "*"+tgt.value;
  }
  this.highlight = function(tgt) {
    tgt.accept(that);
    if(tgt.left) that.highlight(tgt.left);
    if(tgt.right) that.highlight(tgt.right);
  }
}

(new visitor()).highlight(tree.left);

But why to use accept-visit methods, when it can be more straightforward?

function visitor() {
  var that = this;
  this.highlight = function(tgt) {
    tgt.value = "*"+tgt.value;
    if(tgt.left) that.highlight(tgt.left);
    if(tgt.right) that.highlight(tgt.right);
  }
}

(new visitor()).highlight(tree.left);

It is similar to this example. Does it mean that if language mix types (like javascript), there is no reason for accept-visit pair at all?

Community
  • 1
  • 1
Jan Turoň
  • 31,451
  • 23
  • 125
  • 169

1 Answers1

21

You missed something in the implementation. Imagine that the left and the right properties of the Node element were private. Then how would you highlight them in your implementation?

The visitor should not be aware of the tree structure and let the node element run the visitor on any sub-element which is a direct child. So your code should look like this:

node.prototype.accept = function(visitorObj) {
    visitorObj.visit(this);
    if (this.left) this.left.accept(visitorObj);
    if (this.right) this.right.accept(visitorObj);
}

function visitor() {
    var that = this;
    this.visit = function(tgt) {
        tgt.value = "*"+tgt.value;
    }
    this.highlight = function(tgt) {
        tgt.accept(that);
    }
}

(new visitor()).highlight(tree.left);

This way the visitor has no knowledge of the structure of the tree, it is generic and will work on any node that has the property "value".

Udi Cohen
  • 1,259
  • 9
  • 12
  • 1
    I was blinded with this mistake in J.Bishops' book. I spent hours meditating about it, now it is perfect clear - thanks a lot! – Jan Turoň Mar 22 '12 at 23:25
  • This is quite an old bump, but I'm struggling to work out the difference between what is written there, and this: ``` node.prototype.accept = function (visitor) { visitor(this); this.left && this.left.accept(visitor); this.right && this.right.accept(visitor); } ``` The main difference being that instead of passing an object with a visit method, you instead just pass a function. It seems like the visitor pattern examples you see all over are for languages without first-class functions, and just use the object to transport a method. What can your answer do that mine can't, if anything? – Tom Mar 31 '14 at 17:37
  • 1
    @Tom Where is your function going to collate values if it needs to? Since its a function it wont have a valid "this" (http://stackoverflow.com/questions/3127429/how-does-the-this-keyword-work). By using an object instead you can store anything you want in it. – Bae Nov 11 '15 at 06:37
  • @Bae. The function can close over variables. let array=[]; tgt.accept ((node) => array.push(node)). Often less verbosity that way. – Samuel Danielson Mar 09 '17 at 02:19
  • @Bae, but as I learned [here](https://www.cs.rice.edu/~cork/book/node62.html) the object would still be useful in JS for double dispatch. Rather than "if (x instanceof Foo)" in the visitor function, Nodes call visitor.forFoo in their accept method. The simply named "visit()" method would be for typed languages e.g. visitor.visit(Foo x). To Udi, the visitors in the resource I linked DO have knowledge of the tree, and they return values. I believe this is correct. How else would one implement an EvalVisitor? – Samuel Danielson Mar 10 '17 at 07:32