// FIXME eol and quote ( > ) with quote level

/** @type {function(string):string} */
var formatText = (function() {
    /**
     * @param {string} c
     * @return {boolean}
     **/
    function isAlphadec(c) {
        return ((c >= 'A' && c <= 'Z') ||
            (c >= 'a' && c <= 'z') ||
            (c >= '0' && c <= '9') ||
            "àèìòùÀÈÌÒÙáéíóúýÁÉÍÓÚÝâêîôûÂÊÎÔÛãñõÃÑÕäëïöüÿÄËÏÖÜŸçÇßØøÅåÆæœ".indexOf(c) !== -1);
    }

    /**
     * @constructor
     * @param {MsgBranch!} _parent
    **/
    function MsgTextLeaf(_parent) {
        /** @type {string} */
        this.text = "";

        /** @const @type {MsgBranch} */
        this._parent = _parent;
    }

    /**
     * @constructor
     * @param {MsgBranch|MsgTree} _parent
     * @param {number} triggerIndex
     * @param {string=} trigger
     */
    function MsgBranch(_parent, triggerIndex, trigger) {
        /** @const @type {number} */
        this.triggerIndex = triggerIndex;

        /** @type {MsgBranch|MsgTextLeaf|null} */
        this.lastNode = null;

        /** @type {Array<MsgBranch|MsgTextLeaf>} */
        this.subNodes = [ ];

        /** @const @type {string} */
        this.trigger = trigger || '';

        /** @type {boolean} */
        this.isLink = this.trigger === '<';

        /** @type {boolean} */
        this.isBold = this.trigger === '*';

        /** @type {boolean} */
        this.isItalic = this.trigger === '_';

        /** @type {boolean} */
        this.isStrike = this.trigger === '~' || this.trigger === '-';

        /** @type {boolean} */
        this.isQuote = this.trigger === '>' || this.trigger === "&gt;";

        /** @type {boolean} */
        this.isEmoji = this.trigger === ':';

        /** @type {boolean} */
        this.isCode = this.trigger === '`';

        /** @type {boolean} */
        this.isCodeBlock = this.trigger === '```';

        /** @type {boolean} */
        this.isEol = this.trigger === '\n';

        /** @const @type {MsgBranch|MsgTree} */
        this._parent = _parent;

        /** @type {MsgBranch|null} */
        this.prevTwin = null;

        /** @type {boolean|number} */
        this.terminated = this.isEol ? triggerIndex : false;
    }

    /** @return {boolean} */
    MsgBranch.prototype.checkIsBold = function() {
        return (this.isBold && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsBold());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsItalic = function() {
        return (this.isItalic && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsItalic());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsStrike = function() {
        return (this.isStrike && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsStrike());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsQuote = function() {
        return (this.isQuote && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsQuote());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsEmoji = function() {
        return (this.isEmoji && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsEmoji());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsCode = function() {
        return (this.isCode && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsCode());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsCodeBlock = function() {
        return (this.isCodeBlock && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsCodeBlock());
    };

    MsgBranch.prototype.containsUnterminatedBranch = function() {
        for (var i =0, nbBranches = this.subNodes.length; i < nbBranches; i++) {
            if (this.subNodes[i] instanceof MsgBranch && (
                    !this.subNodes[i].terminated || this.subNodes[i].containsUnterminatedBranch()))
                return true;
        }
        return false;
    };

    /**
     * Check if this token closes the branch
     * In this case, finishWith should return the new leave
     * Exemple: `_text *bold_ bold continue*` should be
     * + root
     * | italic
     *   | "text"
     *   | bold
     *     | "bold"
     * | bold
     *   | "bold continue"
     * and this function will return a "bold" branch
     *
     * @param {string} str
     * @param {number} i
     * @return {boolean|MsgBranch}
    **/
    MsgBranch.prototype.finishWith = function(str, i) {
        if (this.trigger === '<' && str[i] === '>')
            return true;

        if (str.substr(i, this.trigger.length) === this.trigger) {
            if (this.lastNode && this.containsUnterminatedBranch()) // sub nodes contains at least one branch wich should be replicated
                return this.lastNode.makeNewBranchFromThis();
            else if (this.hasContent()) // self or any prevTwin has Content
                return true;
            // else no content, should not be finished now
        }
        if (str[i] === '\n' && this.isEol)
            return true;
        return false;
    };

    /**
     * @return {boolean}
    **/
    MsgBranch.prototype.hasContent = function() {
        var _this = this;
        while (_this) {
            for (var i = 0, nbNodes = _this.subNodes.length; i < nbNodes; i++)
                if (_this.subNodes[i] instanceof MsgBranch || _this.subNodes[i].text.length)
                    return true;
            // self or any prevTwin has Content
            _this = _this.prevTwin;
        }
        return false;
    };

    /**
     * @return {MsgBranch}
    **/
    MsgBranch.prototype.makeNewBranchFromThis = function() {
        var other = new MsgBranch(this._parent, this.triggerIndex, this.trigger);
        other.prevTwin = this;
        if (this.lastNode && this.lastNode instanceof MsgBranch) {
            other.lastNode = this.lastNode.makeNewBranchFromThis();
            other.subNodes = [ other.lastNode ];
        }
        return other;
    };

    /**
     * Check if this token is compatible with this branch
     * @param {string} str
     * @param {number} i
     * @return {boolean}
    **/
    MsgBranch.prototype.isAcceptable = function(str, i) {
        if (this.isEmoji && (str[i] === ' ' || str[i] === '\t'))
            return false;
        if ((this.isEmoji || this.isLink || this.isBold || this.isItalic || this.isStrike || this.isCode) &&
            str[i] === '\n')
            return false;
        return true;
    };

    /**
     * Check if str[i] is a trigger for a new node
     * if true, return the trigger
     * @param {string} str
     * @param {number} i
     * @return {string|null}
    **/
    MsgBranch.prototype.isNewToken = function(str, i) {
        if (this.isCode || this.isEmoji || this.isCodeBlock)
            return null;
        if (!this.lastNode || this.lastNode.terminated || this.lastNode instanceof MsgTextLeaf) {
            var nextIsAlphadec = isAlphadec(str[i +1])
                ,prevIsAlphadec = isAlphadec(str[i -1]);

            if (str.substr(i, 3) === '```')
                return '```';
            if (str.substr(i, 4) === "&gt;") // FIXME AND begining of line OR begining of QUOTED
                return "&gt;";
            if (str[i] === '>') // FIXME AND begining of line OR begining of QUOTED
                return str[i];
            if (['`', '\n'].indexOf(str[i]) !== -1)
                return str[i];
            if (['*', '~', '-', '_' ].indexOf(str[i]) !== -1 && (nextIsAlphadec || ['*', '~', '-', '_', '<', '&'].indexOf(str[i+1]) !== -1))
                return str[i];
            if ([':', '<'].indexOf(str[i]) !== -1 && nextIsAlphadec)
                return str[i];
        }
        return null;
    };

    /** @return {number} */
    MsgTextLeaf.prototype.addChar = function(str, i) {
        this.text += str[i];
        return 1;
    };

    /**
     * Parse next char
     * @param {string} str
     * @param {number} i
     * @return {number}
    **/
    MsgBranch.prototype.addChar = function(str, i) {
        var isFinished = (this.lastNode && this.lastNode.finishWith) ? this.lastNode.finishWith(str, i) : null;

        if (isFinished) {
            var lastTriggerLen = this.lastNode.trigger.length;
            this.lastNode.terminate(this.lastNode.triggerIndex, i);
            if (isFinished instanceof MsgBranch) {
                this.lastNode = isFinished;
                this.subNodes.push(isFinished);
            }
            return lastTriggerLen;
        } else {
            if (!this.lastNode || this.lastNode.terminated || this.lastNode instanceof MsgTextLeaf || this.lastNode.isAcceptable(str, i)) {
                var isNewToken = this.isNewToken(str, i);
                if (isNewToken) {
                    this.lastNode = new MsgBranch(this, i, isNewToken);
                    this.subNodes.push(this.lastNode);
                    return this.lastNode.trigger.length;
                } else {
                    if (!this.lastNode || this.lastNode.terminated) {
                        this.lastNode = new MsgTextLeaf(this);
                        this.subNodes.push(this.lastNode);
                    }
                    return this.lastNode.addChar(str, i);
                }
            } else {
                // last branch child is not compatible with this token.
                // So, lastBranch is not a branch
                var revertTo = this.lastNode.triggerIndex +1;

                this.getRoot().cancelTerminate(this.lastNode.triggerIndex);
                // Add a new "escaped" node to replace trigger
                this.lastNode = new MsgTextLeaf(this);
                this.lastNode.addChar(str, revertTo -1); // Add "escaped" trigger
                this.subNodes.pop();
                this.subNodes.push(this.lastNode);

                // return negative value to start parsing again
                return revertTo -i;
            }
        }
    };

    MsgBranch.prototype.terminate = function(triggerIndex, terminateAtIndex) {
        var _this = this;
        while (_this) {
            _this.terminated = terminateAtIndex;
            _this = _this.prevTwin;
        }
    };

    MsgBranch.prototype.getRoot = function() {
        var branch = this;
        while (branch._parent && branch._parent instanceof MsgBranch)
            branch = branch._parent;
        return branch;
    };

    /**
     * @param {number} unTerminatedIndex
    **/
    MsgBranch.prototype.cancelTerminate = function(unTerminatedIndex) {
        if (this.terminated && this.terminated >= unTerminatedIndex)
            this.terminated = false;
        this.subNodes.forEach(function(node) {
            if (node instanceof MsgBranch) {
                node.cancelTerminate(unTerminatedIndex);
            }
        });
    };

    /**
     * @return {string}
    **/
    MsgTextLeaf.prototype.innerHTML = function() {
        return this._parent.checkIsEmoji() ? (':' +this.text +':') : (this.text);
    };

    /**
     * @return {string}
    **/
    MsgTextLeaf.prototype.outerHTML = function() {
        var tagName = 'span'
            ,classList = [];

        if (this._parent.checkIsCodeBlock()) {
            // TODO syntax highlight
            // TODO line breaks
            classList.push('codeblock');
        } else if (this._parent.checkIsCode()) {
            classList.push('code');
        } else {
            if (this.isLink)
                tagName = 'a';
            if (this._parent.checkIsBold())
                classList.push('bold');
            if (this._parent.checkIsItalic())
                classList.push('italic');
            if (this._parent.checkIsStrike())
                classList.push('strike');
            if (this._parent.checkIsEmoji())
                classList.push('emoji'); // FIXME emoji
        }
        return '<' +tagName +(classList.length ? ' class="' +classList.join(' ') +'"' : '') +'>' +this.innerHTML() +'</' +tagName +'>';
    };

    MsgBranch.prototype.outerHTML = function() {
        var html = "";

        if (this.isQuote)
            html += '<span class="quote">';
        if (this.isEol)
            html += '<br/>';

        this.subNodes.forEach(function(node) {
            html += node.outerHTML();
        });

        if (this.isQuote)
            html += '</span>';
        return html;
    };

    /**
     * @constructor
     * @param {string} text
     */
    function MsgTree(text) {
        /** @const @type {string} */
        this.text = text;

        /** @type {MsgBranch|null} */
        this.root = null;
    }

    MsgTree.prototype.parseFrom = function(i) {
        for (var textLen = this.text.length; i < textLen;)
            i += this.root.addChar(this.text, i);
        this.eof();
    };

    MsgTree.prototype.parse = function() {
        this.root = new MsgBranch(this, 0);
        this.parseFrom(0);
    };

    /** @param {MsgBranch} root */
    MsgTree.prototype.getFirstUnterminated = function(root) {
        for (var i =0, nbBranches = root.subNodes.length; i < nbBranches; i++) {
            var branch = root.subNodes[i];

            if (branch instanceof MsgBranch) {
                if (!branch.terminated) {
                    return branch;
                } else {
                    var unTerminatedChild = this.getFirstUnterminated(branch);
                    if (unTerminatedChild)
                        return unTerminatedChild;
                }
            }
        }
        return null;
    };

    /**
     * @param {MsgBranch} branch
     * @param {boolean} next kill this branch or all the next ones ?
    **/
    MsgTree.prototype.revertTree = function(branch, next) {
        if (branch._parent instanceof MsgBranch) {
            branch._parent.subNodes.splice(branch._parent.subNodes.indexOf(branch) +(next ? 1 : 0));
            branch._parent.lastNode = branch._parent.subNodes[branch._parent.subNodes.length -1];
            this.revertTree(branch._parent, true);
        }
    };

    MsgTree.prototype.eof = function() {
        // FIXME merge of same block-branches (opti + quoted)
        var unterminated = this.getFirstUnterminated(this.root);

        if (unterminated) {
            // We have a first token, but never closed
            // kill that branch
            this.revertTree(unterminated, false);

            // "unterminate" all branch that will be closed in the future
            this.root.cancelTerminate(unterminated.triggerIndex);

            // Add a new text leaf containing trigger
            var textNode = new MsgTextLeaf(unterminated._parent);
            textNode.addChar(this.text, unterminated.triggerIndex);
            unterminated._parent.subNodes.push(textNode);
            unterminated._parent.lastNode = textNode;

            // Restart parsing
            this.parseFrom(unterminated.triggerIndex +1);
        }
        // Else no problem
    };

    /**
     * @return {string}
    **/
    MsgTree.prototype.toHTML = function() {
        return this.root ? this.root.outerHTML() : "";
    };

    return function(text) {
        var root = new MsgTree(text);
        root.parse();
        return (root.toHTML());
    };
})();

if (typeof module !== "undefined") module.exports.formatText = formatText;