/*
 * The MIT License
 *
 *  Copyright (c) 2010 Mike de Boer
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a copy
 *  of this software and associated documentation files (the "Software"), to deal
 *  in the Software without restriction, including without limitation the rights
 *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *  copies of the Software, and to permit persons to whom the Software is
 *  furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in
 *  all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *  THE SOFTWARE.
 */

 // Translated to Typescript

 class Trie {
    constructor(
        private stem: string = "",
        private sorting = Trie.SORT_DESC) {
    }
    public nstem = this.stem.charCodeAt(0);
    private wordCount = 0;
    private prefixCount = 0;
    public children: Trie[] = [];
    private meta = [];

    private static SORT_ASC = 0x0001;
    private static SORT_DESC = 0x0002;
    private static SORT_NONE = 0x0004;

    /**
     * Add a word to the existing dictionary. If a trie node doesn't exist
     * yet, it is created with that character as its stem.
     * Since an add is already an expensive action, compared to adding nodes to
     * native Javascript containers like Array or Object, inserting a trie
     * node in lexical order is relatively cheap.
     * Please refer to the test suite to compare performance in your browser(s).
     *
     * @param {String} word Remainder of the word that is added to the root trie
     * @param {Object} meta Metadata associated with a word
     * @return  {void}
     */
    add(word: string, meta: { word?: string }): void {
        if (word) {
            let t;
            const s = this.sorting;
            let i = 0;
            const k = word.charAt(0);
            const c = this.children;
            let l = c.length;
            meta = meta || {};
            if (!meta.word)
                meta.word = word;
            // check if a child with stem 'k' already exists:
            for (; i < l; ++i) {
                if (c[i].stem == k) {
                    t = c[i];
                    break;
                }
            }
            if (!t) {
                ++this.prefixCount;
                t = new Trie(k, s);
                if (!s || !c.length || s & Trie.SORT_NONE) {
                    c.push(t);
                }
                else if (s & Trie.SORT_DESC) {
                    i = l;
                    do {
                        if (--i < 0) {
                            c.unshift(t);
                            break;
                        }
                    } while (c[i].stem > k)
                    if (i >= 0)
                        c.splice(i + 1, 0, t);
                }
                else {
                    i = 0, --l;
                    do {
                        if (++i > l) {
                            c.unshift(t);
                            break;
                        }
                    } while (c[i].stem > k)
                    if (i <= l)
                        c.splice(i, 0, t);
                }
            }
            t.add(word.substring(1), meta);
        }
        else {
            this.meta.push(meta);
            ++this.wordCount;
        }
    }

    /**
     * Update a word in the dictionary. This update implementation is
     * implemented like a file rename action as on a filesystem: add a node
     * with the new name and remove the outdated, 'old' version.
     *
     * @param {String} sOld the old word to be replaced by the word provided
     *                      by 'sNew'
     * @param {String} sNew the new word to be added to the dictionary
     * @param {Object} meta Metadata associated with a word
     * @return  {void}
     */
    update(sOld: string, sNew: string, meta: object): void {
        this.remove(sOld);
        this.add(sNew, meta);
    }

    /**
     * Remove a word from the dictionary. This function uses the
     * walker, which is a generic implementation of a tree walker.
     *
     * @param {String} word the word to remove
     * @return  {void}
     */
    remove(word: string): void {
        walker(word, this, (trie, idx) => {
            trie.children.splice(idx, 1);
        });
    }

    /**
     * Find a trie node that is paired with a word or prefix 's'. Like the
     * {@link remove} function, this function also uses the walker.
     *
     * @param {string}   prefix the word or prefix to search for in the dictionary
     * @return  {Trie}
     */
    find(prefix: string): Trie {
        return walker(prefix, this, (trie, idx) => trie.children[idx]);
    }

    /**
     * @alias {find}
     *
     * @param {String} prefix the word or prefix to search for in the dictionary
     * @return  {Trie}
     */
    findPrefix(prefix: string): Trie {
        // AFAIK, this is just an alias of find, because that returns a trie rootnode.
        // From that rootnode, it's easy to create a list of disambiguations.
        return this.find(prefix);
    }

    /**
     * Retrieve a direct child node of this dictionary with 'prefix'.
     *
     * @param {String} prefix s the word or prefix to search for in the
     *                          children of this dictionary
     * @return  {Trie}
     */
    getChild(prefix: string): Trie {
        let i = 0;
        const c = this.children;
        const l = c.length;
        for (; i < l; ++i) {
            if (c[i].stem == prefix)
                return c[i];
        }

        return null;
    }

    /**
     * A version of {@link getChild} with a Boolean return type.
     *
     * @param {String} prefix s the word or prefix to search for in the
     *                          children of this dictionary
     * @return  {Boolean}
     */
    hasChild(prefix: string): boolean {
        return this.getChild(prefix) !== null;
    }

    /**
     * Resort this dictionary in lexical order, either in an ascending or
     * descending direction.
     * Since it uses the native {@link Array#sort} method, sorting speed can
     * be considered linear O(n) to the size of the trie, i.e. the word count.
     * Please refer to the test suite to compare performance in your browser(s).
     *
     * @param {Number} direction sorting direction. Possible values:
     *                 {@link Trie#SORT_ASC}
     *                 {@link Trie#SORT_DESC}
     * @return  {void}
     */
    sort(direction: number): void {
        if (typeof direction == "undefined")
            direction = Trie.SORT_DESC;
        if (!this.prefixCount || this.sorting === direction) return;
        this.sorting = direction;
        if (direction & Trie.SORT_NONE) return;
        const c = this.children;
        let i = c.length - 1;
        const m = direction & Trie.SORT_ASC ? sortAsc : sortDesc;
        c.sort(m);
        for (; i >= 0; --i)
            c[i].sort(direction);
    }

    /**
     * Retrieve the Array of words that originate from this trie.
     * The main use-case for this function is for implementations of the
     * type-ahead user experience pattern, but can be used to other ends as
     * well, of course.
     * The performance of this function still needs to be profiled against
     * alternatives, like pre-caching the words Array per Trie when it's
     * instantiated.
     *
     * @return  {Array}
     */
    getWords(): Array<any> {
        let words = [];
        const c = this.children;
        let i = 0;
        const l = c.length;
        for (; i < l; ++i) {
            if (c[i].wordCount) {
                words = words.concat(c[i].meta.map(meta => meta.word));
            }
            words = words.concat(c[i].getWords());
        }
        return words;
    }

    /**
     * Retrieve the prefix count of the applied argument
     *
     * @param {String} word the prefix or word-completing stem
     * @return  {Number}
     */
    getPrefixCount(word: string): number {
        return walker(word, this, (trie, idx) => trie.children[idx].prefixCount) || 0;
    }

    /**
     * Retrieve the word count of the applied argument
     *
     * @param {String} word the prefix or word-completing stem
     * @return  {Number}
     */
    getWordCount(word: string): number {
        return walker(word, this, (trie, idx) => trie.children[idx].wordCount) || 0;
    }

    /**
     * Overrides Object.prototype.toString to deliver a more context sensitive
     * String representation of a Trie.
     *
     * @return {String}
     */
    toString(): string {
        return `[Trie] '${this.stem}': {\n    stem: ${this.stem},\n    prefixCount: ${this.prefixCount},\n    wordCount: ${this.wordCount},\n    metadata: ${JSON.stringify(this.meta)},\n    children: [Array]{${this.children.length}}\n}`;
    }

    /**
     * Load this Trie instance with properties from `json`; a serialized old(er)
     * version.
     *
     * @param {Object} json A serialized version of a Trie
     * @return  {void}
     */
    fromJSON(json: any): void {
        STATIC_PROPS.forEach(prop => {
            this[prop] = json[prop];
        });
        this.children = json.children.map(data => {
            const child = new Trie();
            child.fromJSON(data);
            return child;
        });
    }

    /**
     * Serialize this Trie instance to a JSON blob that may be stringified
     * and used at convenience.
     *
     * @return {Object}
     */
    toJSON(): object {
        const json = {
            children: this.children.map(child => child.toJSON())
        };
        STATIC_PROPS.forEach(prop => {
            json[prop] = this[prop];
        });
        return json;
    }
}

var STATIC_PROPS = ["stem", "nstem", "sorting", "wordCount", "prefixCount", "meta"];

/**
 * NOT named after Johnny, but merely after the verb 'to walk'.
 * This function walks along a Trie top-down until it finds the node which
 * fully represents the term/ prefix/ word that was searched for.
 * It passes the parent node of the found Trie and its index to a callback
 * function. It passes the parent node, because otherwise Trie mutation would
 * become increasingly more difficult.
 *
 * An earlier implementation of this function used a naive recursive algorithm,
 * but my friend - @ejpbruel - has shown me that you can simply rewrite any form
 * of tail-recursion to an inner loop.
 *
 * @param {String}   word   the word or prefix to search for
 * @param {Trie}     trie   the root trie node to walk through
 * @param {Function} method callback function to which the results of the
 *                          walker are passed
 * @return  {mixed}
 * @memberOf Trie
 */
function walker(word: string, trie: Trie, method: Function) {
    if (!word || !trie || !method) return null;
    let ch;
    let c;
    let l;
    let i;
    let prev;

    while (word.length > 0) {
        ch = word.charAt(0),
            c = trie.children,
            l = c.length,
            i = 0;
        for (; i < l; ++i) {
            if (ch == c[i].stem)
                break;
        }
        if (i == l)
            return null; // not found
        word = word.substring(1),
            prev = trie,
            trie = c[i];
    }
    return method(prev, i);
}

/**
 * Sorting helper function that can be passed to Array.sort().
 * The result of this helper will be that all nodes will be sorted in
 * ascending lexical order.
 *
 * @param {Trie} a first element for comparison
 * @param {Trie} b second element for comparison
 * @return  {Number}
 * @memberOf Trie
 */
function sortAsc(a: Trie, b: Trie): number {
    const s1 = a.nstem;
    const s2 = b.nstem;
    return (s1 < s2) ? 1 : (s1 > s2) ? -1 : 0;
}

/**
 * Sorting helper function that can be passed to Array.sort().
 * The result of this helper will be that all nodes will be sorted in
 * descending lexical order.
 *
 * @param {Trie} a first element for comparison
 * @param {Trie} b second element for comparison
 * @return  {Number}
 * @memberOf Trie
 */
function sortDesc(a: Trie, b: Trie): number {
    const s1 = a.nstem;
    const s2 = b.nstem;
    return (s1 > s2) ? 1 : (s1 < s2) ? -1 : 0;
}