AutoComplete

const fs = require('fs');

// trie node to store characters for trie
class TrieNode {
    constructor() {
        this.children = new Map();
        this.word = '';
        this.cost = -1;
    }
}

class Trie {
    constructor() {
        // create root node
        this.root = new TrieNode();
    }
    // add word to trie
    addWord(word, cost) {
        let cur = this.root;
        for (const c of word) {
            if (!cur.children.has(c)) {
                cur.children.set(c, new TrieNode());
            }
            cur = cur.children.get(c);
        }
        cur.cost = cost;
        cur.word = word;
    }
    // find words with prefix
    find(word) {
        let cur = this.root;
        for (const c of word) {
            if (!cur.children.has(c)) {
                return [];
            }
            cur = cur.children.get(c);
        }
        let res = [];
        this.dfs(cur, res);
        return res;
    }
    // dfs for words inside cur node
    dfs(node, res) {
        if (node.word) {
            res.push({ word: node.word, cost: node.cost });
        }
        // if child exist dfs
        for (let [key, child] of node.children) {
            this.dfs(child, res);
        }
    }
}

class AutoComplete {
    constructor(words) {
        this.trie = new Trie(words);
    }
    addWords(wordPairs) {
        for (let i = 0; i < wordPairs.length; i++) {
            let wordPair = wordPairs[i];
            this.trie.addWord(wordPair.word, wordPair.cost);
        }
    }
    find(text) {
        return this.trie.find(text);
    }
}

class AutoCompleteTest {
    constructor() {
        this.numberOfWords = 0;
        this.numberOfQuery = 0;
        this.autoComplete = new AutoComplete();
    }
    runTest() {
        this.parse();
        this.autoComplete.addWords(this.words);

        const ans = [];
        for (const qs of this.query) {
            let temp = this.autoComplete.find(qs);
            temp.sort((a, b) => {
                return a.cost - b.cost;
            });
            ans.push(temp);
        }

        console.log(ans);

    }
    parse() {
        let data = this.getDataFileContent();

        let arr = data.split('\n');
        this.numberOfWords = +arr.shift();
        this.numberOfQuery = +arr.shift();

        this.query = [];
        for (let i = 0; i < this.numberOfQuery; i++) {
            this.query.push(arr.pop());
        }


        this.words = [];
        for (let i = 0; i < arr.length; i++) {
            this.words.push({ word: arr[i], cost: i + 1 })
        }
    }
    getDataFileContent() {
        const content = fs.readFileSync('dataTestFile.data');
        return content.toString();
    }
}

let autoTest = new AutoCompleteTest();
autoTest.runTest();

// catc:
// catch (10)
// art:
// art (1)
// arts (4)
// articles (8)
// article (12)
// articulate (13)
// da:
// date (5)
// day (7)
// data (9)
// z:
// zone (2)
// zip (3)
// z (6)
// zoom (11)

// [
//     { word: 'art', cost: 1 },
//     { word: 'zone', cost: 2 },
//     { word: 'zip', cost: 3 },
//     { word: 'arts', cost: 4 },
//     { word: 'date', cost: 5 },
//     { word: 'z', cost: 6 },
//     { word: 'day', cost: 7 },
//     { word: 'articles', cost: 8 },
//     { word: 'data', cost: 9 },
//     { word: 'catch', cost: 10 },
//     { word: 'zoom', cost: 11 },
//     { word: 'article', cost: 12 },
//     { word: 'articulate', cost: 13 },
//     { word: 'articulation', cost: 14 }
//   ]