// Generated by CoffeeScript 1.9.0
(function() {
  var Box, DICT_FLAG, DictFlag, HIDDEN_VAR_PREFIX, TreeTin, VarTin, Variable, bind, bind_tins, box, boxit, extern, g_hidden_var_counter, get_tin, isHiddenVar, k, map, removeListVars, str, toJson, types, unboxit, _unify;

  if (typeof module === 'undefined') {
    window.unify = {};
  }

  extern = function(name, o) {
    if (typeof module === 'undefined') {
      return window.unify[name] = o;
    } else {
      return module.exports[name] = o;
    }
  };

  str = function(o) {
    if (typeof o === "undefined") {
      return "undefined";
    } else if (o === null) {
      return "null";
    } else {
      return o.toString();
    }
  };

  map = function(arr, func) {
    var i, _i, _len, _results;
    _results = [];
    for (_i = 0, _len = arr.length; _i < _len; _i++) {
      i = arr[_i];
      _results.push(func(i));
    }
    return _results;
  };

  types = {
    isUndef: function(o) {
      return typeof o === "undefined";
    },
    isBool: function(o) {
      return typeof o === "boolean";
    },
    isArray: function(o) {
      return (o != null) && Array.isArray(o);
    },
    isStr: function(o) {
      return typeof o === "string";
    },
    isNum: function(o) {
      return typeof o === "number" && !isNaN(o);
    },
    isObj: function(o) {
      return o !== null && !types.isArray(o) && typeof o === "object";
    },
    isValueType: function(o) {
      return types.isBool(o) || types.isStr(o) || types.isNum(o);
    },
    isFunc: function(o) {
      return !!(o && o.constructor && o.call && o.apply);
    },
    isInt: function(o) {
      return isNum(o) && o === Math.floor(o);
    }
  };

  for (k in types) {
    types[k].maxDepth = 1;
  }

  toJson = function(elem) {
    var e, ret;
    if (types.isArray(elem)) {
      return "[" + (map(elem, function(i) {
        return toJson(i);
      }).join()) + "]";
    }
    if (types.isStr(elem)) {
      return "\"" + elem + "\"";
    }
    ret = str(elem);
    if (types.isObj(elem) && ret === "[object Object]") {
      return "{" + (((function() {
        var _results;
        _results = [];
        for (e in elem) {
          _results.push(e + ':' + toJson(elem[e]));
        }
        return _results;
      })()).join()) + "}";
    }
    return ret;
  };

  DictFlag = (function() {
    function DictFlag() {}

    DictFlag.prototype.toString = function() {
      return "DICT_FLAG";
    };

    return DictFlag;

  })();

  DICT_FLAG = new DictFlag();

  Box = (function() {
    function Box(v) {
      if (types.isValueType(v) || v === null) {
        this.value = v;
      } else {
        throw "Can only box value types, not " + (toJson(v));
      }
    }

    Box.prototype.toString = function() {
      return toJson(this.value);
    };

    return Box;

  })();

  g_hidden_var_counter = 1;

  HIDDEN_VAR_PREFIX = "__HIDDEN__";

  isHiddenVar = function(name) {
    return name.substring(0, HIDDEN_VAR_PREFIX.length) === HIDDEN_VAR_PREFIX;
  };

  Variable = (function() {
    function Variable(name, _at_typeFunc) {
      this.typeFunc = _at_typeFunc != null ? _at_typeFunc : null;
      this.isListVar = name[0] === "$";
      if (this.isListVar) {
        name = name.substring(1);
      }
      if (name === "_") {
        this.name = HIDDEN_VAR_PREFIX + g_hidden_var_counter;
        g_hidden_var_counter += 1;
      } else {
        this.name = name;
      }
    }

    Variable.prototype.isHiddenVar = function() {
      return isHiddenVar(this.name);
    };

    Variable.prototype.toString = function() {
      return "Variable(" + (toJson(this.name)) + ")";
    };

    return Variable;

  })();

  TreeTin = (function() {
    function TreeTin(_at_node, _at_varlist) {
      this.node = _at_node;
      this.varlist = _at_varlist;
      this.changes = [];
    }

    TreeTin.prototype.toString = function() {
      return toJson(this.node);
    };

    TreeTin.prototype.get = function(varName, maxDepth) {
      var vartin;
      vartin = this.varlist[varName];
      if (!vartin) {
        throw "Variable " + varName + " not in this tin";
      }
      vartin = vartin.endOfChain();
      if (!vartin.node) {
        return new Variable(vartin.name);
      } else {
        return unboxit(vartin.node, vartin.varlist, maxDepth);
      }
    };

    TreeTin.prototype.getAll = function(maxDepth) {
      var j, key;
      j = {};
      for (key in this.varlist) {
        if (!isHiddenVar(key)) {
          j[key] = this.get(key, maxDepth);
        }
      }
      return j;
    };

    TreeTin.prototype.unbox = function(maxDepth) {
      return unboxit(this.node, this.varlist, maxDepth);
    };

    TreeTin.prototype.unify = function(tin) {
      var changes, success;
      changes = [];
      if (!(tin instanceof TreeTin)) {
        tin = box(tin);
      }
      success = _unify(this.node, this.varlist, tin.node, tin.varlist, changes);
      if (success) {
        this.changes.push.apply(this.changes, changes);
        this.changes.push.apply(tin.changes, changes);
        return [this, tin];
      } else {
        map(changes, function(change) {
          return change();
        });
        return null;
      }
    };

    TreeTin.prototype.bind = function(varName, expr) {
      var changes, vartin;
      vartin = this.varlist[varName].endOfChain();
      if (!vartin.isfree()) {
        return null;
      }
      if (!(expr instanceof TreeTin)) {
        expr = box(expr);
      }
      changes = [];
      if (bind(vartin, expr.node, expr.varlist, changes)) {
        this.changes.push.apply(this.changes, changes);
        this.changes.push.apply(expr.changes, changes);
        return [this, expr];
      }
      return null;
    };

    TreeTin.prototype.rollback = function() {
      map(this.changes, function(change) {
        return change();
      });
      this.changes.splice(0, this.changes.length);
    };

    return TreeTin;

  })();

  VarTin = (function() {
    function VarTin(_at_name, _at_node, _at_varlist, _at_typeFunc) {
      this.name = _at_name;
      this.node = _at_node != null ? _at_node : null;
      this.varlist = _at_varlist != null ? _at_varlist : null;
      this.typeFunc = _at_typeFunc != null ? _at_typeFunc : null;
      this.chainlength = 1;
    }

    VarTin.prototype.endOfChain = function() {
      var t;
      t = this;
      while (t.varlist instanceof VarTin) {
        t = t.varlist;
      }
      return t;
    };

    VarTin.prototype.isfree = function() {
      var t;
      t = this.endOfChain();
      return t.node === null && t.varlist === null;
    };

    VarTin.prototype.isHiddenVar = function() {
      return isHiddenVar(this.name);
    };

    VarTin.prototype.toString = function() {
      return "VarTin(" + (toJson(this.name)) + ")";
    };

    VarTin.prototype.unbox = function(maxDepth) {
      if (this.node) {
        return unboxit(this.node, this.varlist, maxDepth);
      } else {
        return new Variable(this.name);
      }
    };

    return VarTin;

  })();

  unboxit = function(tree, varlist, maxDepth) {
    var e, error, hash, tin, _i, _len, _ref;
    if (maxDepth == null) {
      maxDepth = -1;
    }
    if (maxDepth === 0) {
      return tree;
    }
    if (types.isArray(tree)) {
      if (tree.length > 0 && tree[tree.length - 1] === DICT_FLAG) {
        hash = new Object();
        _ref = tree.slice(0, tree.length - 1);
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          e = _ref[_i];
          hash[unboxit(e[0], varlist, maxDepth - 1)] = unboxit(e[1], varlist, maxDepth - 1);
        }
        return hash;
      } else {
        return map(tree, function(i) {
          return unboxit(i, varlist, maxDepth - 1);
        });
      }
    } else if (tree instanceof Box) {
      return tree.value;
    } else if (tree instanceof Variable) {
      if (varlist !== void 0) {
        try {
          tin = get_tin(varlist, tree);
        } catch (_error) {
          error = _error;
          return tree;
        }
        if ((tin.node != null) && (tin.varlist != null)) {
          return unboxit(tin.node, tin.varlist, maxDepth - 1);
        } else {
          return tree;
        }
      } else {
        return tree;
      }
    } else {

    }
    throw "Unrecognized type '" + (typeof tree) + "' in unbox.";
  };

  boxit = function(elem, varlist) {
    var a, hasListVar, key, ret;
    if (elem instanceof Variable) {
      if (varlist[elem.name] != null) {
        if ((elem.typeFunc != null) && (varlist[elem.name].typeFunc != null)) {
          if (elem.typeFunc !== varlist[elem.name].typeFunc) {
            throw "A single variable can not be defined with two diffrent types!";
          }
        } else if (elem.typeFunc != null) {
          varlist[elem.name].typeFunc = elem.typeFunc;
        }
      } else {
        varlist[elem.name] = new VarTin(elem.name, null, null, elem.typeFunc);
      }
      return elem;
    } else if (elem instanceof Box) {
      return elem;
    } else if (types.isArray(elem)) {
      hasListVar = false;
      ret = map(elem, function(i) {
        if (i instanceof Variable && i.isListVar) {
          if (hasListVar) {
            throw "There can only be one list variable in an array!";
          }
          hasListVar = true;
        }
        return boxit(i, varlist);
      });
      ret.hasListVar = hasListVar;
      return ret;
    } else if (types.isObj(elem)) {
      a = [];
      for (key in elem) {
        a.push([boxit(key, varlist), boxit(elem[key], varlist)]);
      }
      a.push(DICT_FLAG);
      return a.sort();
    } else if (types.isValueType(elem || elem === null)) {
      return new Box(elem);
    } else {
      return "Unrecognized type '" + (typeof elem) + "' in box.";
    }
  };

  box = function(elem) {

    /* This function boxes an object. Before an object can be processed it must be "boxed" this consits of wrapping all value types in objects and converting all objects to arrays. */
    var tree, varlist;
    if (elem instanceof TreeTin) {
      return elem;
    }
    varlist = {};
    tree = boxit(elem, varlist);
    return new TreeTin(tree, varlist);
  };

  get_tin = function(varlist, node) {
    if (!node instanceof Variable) {
      throw "Node must be a Variable to get_tin!";
    }
    if ((varlist != null ? varlist[node.name] : void 0) != null) {
      return varlist[node.name];
    }
    throw "Couldn't find node " + node.name + " in varlist " + varlist + "!";
  };

  bind = function(t, node, varlist, changes) {
    var called, unboxed;
    t = t.endOfChain();
    if (!t.isfree()) {
      return false;
    }
    if (t.typeFunc !== null) {
      unboxed = unboxit(node, varlist, t.typeFunc.maxDepth);
      if (unboxed instanceof Variable && Variable.typeFunc !== t.typeFunc) {
        return false;
      } else if (!t.typeFunc(unboxed)) {
        return false;
      }
    }
    t.node = node;
    t.varlist = varlist;
    called = false;
    changes.push(function() {
      if (called) {
        return;
      }
      called = true;
      t.node = null;
      t.varlist = null;
      t.chainlength = 1;
    });
    return true;
  };

  bind_tins = function(t1, t2, changes) {
    if (!t1.isfree() && !t2.isfree()) {
      return false;
    } else if (t1.isfree() && !t2.isfree()) {
      return bind(t1, t2.node, t2.varlist, changes);
    } else if (!t1.isfree() && t2.isfree()) {
      return bind(t2, t1.node, t1.varlist, changes);
    } else if (t2.chainlength < t1.chainlength) {
      t2.chainlength += 1;
      return bind(t2, null, t1, changes);
    } else {
      t1.chainlength += 1;
      return bind(t1, null, t2, changes);
    }
  };

  _unify = function(n1, v1, n2, v2, changes) {
    var idx, idx1, idx2, n1RealLength, n2RealLength, t1, t2;
    if (changes == null) {
      changes = [];
    }
    if (n1 === void 0 && n2 === void 0) {
      return true;
    } else if (n1 === null && n2 === null) {
      return true;
    } else if (n1 === null || n2 === null) {
      return false;
    } else if (n1 instanceof Variable && n2 instanceof Variable) {
      t1 = get_tin(v1, n1);
      t2 = get_tin(v2, n2);
      if (bind_tins(t1, t2, changes)) {
        return true;
      }
      return _unify(t1.node, t1.varlist, t2.node, t2.varlist, changes);
    } else if (n1 instanceof Variable) {
      t1 = get_tin(v1, n1);
      if (bind(t1, n2, v2, changes)) {
        return true;
      }
      return _unify(t1.node, t1.varlist, n2, v2, changes);
    } else if (n2 instanceof Variable) {
      return _unify(n2, v2, n1, v1, changes);
    } else if (n1 instanceof Box && n2 instanceof Box) {
      return n1.value === n2.value;
    } else if (types.isArray(n1) && types.isArray(n2)) {
      n1RealLength = n1.length - (n1.hasListVar ? 1 : 0);
      n2RealLength = n2.length - (n2.hasListVar ? 1 : 0);
      if (n1RealLength === n2RealLength) {
        if (n1.hasListVar) {
          n1 = removeListVars(n1, v1, changes);
          if (!n1) {
            return false;
          }
        }
        if (n2.hasListVar) {
          n2 = removeListVars(n2, v2, changes);
          if (!n2) {
            return false;
          }
        }
        idx = 0;
        while (idx < n1.length) {
          if (!_unify(n1[idx], v1, n2[idx], v2, changes)) {
            return false;
          }
          idx++;
        }
        return true;
      }
      if (n1RealLength > n2RealLength) {
        return _unify(n2, v2, n1, v1, changes);
      }
      n2 = removeListVars(n2, v2, changes);
      if (!n2) {
        return false;
      }
      idx1 = 0;
      idx2 = 0;
      while (idx2 < n2.length) {
        if (n1[idx1] instanceof Variable && n1[idx1].isListVar) {
          if (!_unify(n1[idx1], v1, n2.slice(idx2, idx2 + n2RealLength - n1RealLength), v2, changes)) {
            return false;
          }
          idx2 += n2RealLength - n1RealLength - 1;
        } else if (!_unify(n1[idx1], v1, n2[idx2], v2, changes)) {
          return false;
        }
        idx1++;
        idx2++;
      }
      return true;
    }
    return n1 === n2;
  };

  removeListVars = function(arr, varList, changes) {
    var i, ret, _i, _len;
    ret = [];
    for (_i = 0, _len = arr.length; _i < _len; _i++) {
      i = arr[_i];
      if (i instanceof Variable && i.isListVar) {
        if (!_unify(i, varList, [], [], changes)) {
          return false;
        }
      } else {
        ret.push(i);
      }
    }
    return ret;
  };

  extern("box", box);

  extern("variable", function(name, typeFunc) {
    return new Variable(name, typeFunc);
  });

  extern("TreeTin", TreeTin);

  extern("VarTin", VarTin);

  extern("Box", Box);

  extern("DICT_FLAG", DICT_FLAG);

  extern("toJson", toJson);

  extern("Variable", Variable);

  extern("types", types);

}).call(this);