git @ Cat's Eye Technologies yoob.js / master src / yoob / tree.js
master

Tree @master (Download .tar.gz)

tree.js @master — raw · history · blame 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
 * This file is part of yoob.js version 0.3
 * Available from https://github.com/catseye/yoob.js/
 * This file is in the public domain.  See http://unlicense.org/ for details.
 */
if (window.yoob === undefined) yoob = {};

yoob.Tree = function(type, children) {
  this.type = type;
  this.value = undefined;
  /*
   * If this is set to a string, this Tree node is a variable.
   */
  this.variable = undefined;
  this.children = children;
  if (this.children === undefined) {
    this.children = [];
  }

  // chain methods
  this.setValue = function(value) {
    this.value = value;
    return this;
  };
  this.setVariable = function(variable) {
    this.variable = variable;
    return this;
  };

  this.toString = function() {
    var s = this.type + "("
    if (this.value !== undefined) {
      s += "'" + this.value + "'";
    }
    if (this.children !== undefined && this.children.length > 0) {
      s + " ";
      for (var i = 0; i < this.children.length; i++) {
        if (this.children[i] !== undefined) {
          s += this.children[i].toString();
          if (i < this.children.length - 1)
            s += " ";
        }
      }
    }
    return s + ")";
  };
  
  this.equals = function(tree) {
    if (this.type !== tree.type) {
      return false;
    }
    if (this.value !== tree.value) {
      return false;
    }
    if (this.children.length !== tree.children.length) {
      return false;
    }
    for (var i = 0; i < this.children.length; i++) {
      if (!this.children[i].equals(tree.children[i])) {
        return false;
      }
    }
    return true;
  };

  this.match = function(tree, unifier) {
    if (unifier === undefined) {
      unifier = {};
    }

    if (this.variable !== undefined) {
      var existing = unifier[this.variable];
      if (existing === undefined) {
        unifier[this.variable] = tree;
        return unifier;
      } else {
        return unifier[this.variable].match(tree, unifier);
      }
    }

    if (this.type !== tree.type) {
      return false;
    }
    if (this.value !== tree.value) {
      return false;
    }
    if (this.children.length !== tree.children.length) {
      return false;
    }
    for (var i = 0; i < this.children.length; i++) {
      if (!this.children[i].match(tree.children[i], unifier)) {
        return false;
      }
    }
    return unifier;
  };

  /*
   * Returns a new Tree with all the variables in the original
   * 'this' Tree replaced with their bound values in the unifier.
   */
  this.subst = function(unifier) {
    if (this.variable !== undefined) {
      var existing = unifier[this.variable];
      if (existing !== undefined) {
        return existing;
      } else {
        return this;
      }
    }
    var t = new yoob.Tree(this.type).setValue(this.value);
    for (var i = 0; i < this.children.length; i++) {
      t.children.push(this.children[i].subst(unifier));
    }
    return t;
  };
};