Source: Node.js

/*
 *  2016 Maciej Wiecierzewski
 */

/**
 * @constructor
 * @classdesc Syntax tree node
 * @param {type} symbol
 * @param {type} pos Position in the expression's string
 * @returns {Node}
 */
function Node(symbol, pos)
{
    this.parent = this;
    this.symbol = symbol;
    this.pos = pos;
    this.rule = null;
    this.allSymbols = null;
    this.children = [];
    this.order = 0;
    this.lastNode = 1;
    this.root = this;
}

/**
 * Recursively updates position when a node is inserted
 * @param {type} pos
 * @param {type} shift
 * @returns {undefined}
 */
Node.prototype.updatePos = function(pos, shift)
{
    if(this.pos >= pos) this.pos = this.pos + shift;

    for(var i = 0; i < this.children.length; i++)
    {
        this.children[i].updatePos(pos, shift);
    }
}


function nodeCompare(a, b)
{
    if(a.pos > b.pos) return 1;
    else if(a.pos == b.pos) return 0;
    else if(a.pos < b.pos) return -1;
}

/*
Node.prototype.addChild = function(node)
{
    node.parent = null;
    node.root = this.root;
    this.children.push(node);
    this.children.sort(nodeCompare);
}*/

/**
 * Appends child node
 * @param {Node} node
 */
Node.prototype.insertChild = function(node)
{
    node.parent = this;
    node.root = this.root;
    this.children.push(node);
}

/**
 * Updates the syntax tree when a rule is applied
 * @param {Rule} rule
 */
Node.prototype.setRule = function(rule)
{
    if(rule.operator === null)
        return;

    this.rule = rule;

    if(rule.string.length > 1)
    {
        this.root.updatePos(this.pos+1, rule.string.length-1);
    }

    for(var i = 0; i < rule.string.length; i++)
    {
        if(rule.string.charAt(i) !== rule.operator)
        {
            var child = new Node(rule.symbol, this.pos+i);
            this.insertChild(child);
            this.children.sort(nodeCompare);
        }
    }
}

/**
 * Returns the node having its symbol on particular position in the expression's string
 * @param {type} symbolPos
 * @returns {}
 */
Node.prototype.findNode = function(symbolPos)
{
    if(this.children.length == 0)
        return this;

    for(var i = this.children.length-1; i >= 0; i--)
    {
        if(this.children[i].pos <= symbolPos)
        {
            return this.children[i].findNode(symbolPos);
        }
    }

    console.log("+error");
    return this.children[0];
}

/** Counts the order; traverses the syntax tree in depth-first preordering  */
Node.prototype.figureOrder = function()
{
    this.order = this.root.lastNode++;

    for(var i = this.children.length-1; i >= 0; i--)
    {
        this.children[i].figureOrder();
    }
}

/**
 * Generates string from the syntax tree; recursive
 * @param {type} parentheses
 * @returns {String}
 */
Node.prototype.toString = function(parentheses)
{
    if(this.rule == null)
        return ".";
    
    if(parentheses === undefined)
        parentheses = {left: "(", right: ")"};

    var str = parentheses.left;

    var childNo = 0;
    for(var i = 0; i <  this.rule.string.length; i++)
    {
        if(this.rule.operator === null || this.rule.string.charAt(i) !== this.rule.operator)
        {
            if(childNo < this.children.length)
            {
                str += this.children[childNo].toString(parentheses);

                childNo++;
            }
        }
        else
            str += this.rule.string.charAt(i);
    }

    return str+parentheses.right;

    function isSymbol(str)
    {
        for(var i = 0; i < Node.allSymbols.length; i++)
        {
            if(Node.allSymbols[i].str === str)
                return true;
        }

        return false;
    }
}