package design;

import java.util.*;

/**
 * Created by gouthamvidyapradhan on 20/08/2017.
 * <p>
 * Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#').
 * For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
 * Here are the specific rules:
 * <p>
 * The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
 * The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one).
 * If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
 * If less than 3 hot sentences exist, then just return as many as you can.
 * When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
 * Your job is to implement the following functions:
 * <p>
 * The constructor function:
 * <p>
 * AutocompleteSystem(String[] sentences, int[] times): This is the constructor.
 * The input is historical data. Sentences is a string array consists of previously typed sentences.
 * Times is the corresponding times a sentence has been typed. Your system should record these historical data.
 * <p>
 * Now, the user wants to input a new sentence. The following function will provide the next character the user types:
 * <p>
 * List<String> input(char c): The input c is the next character typed by the user.
 * The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#').
 * Also, the previously typed sentence should be recorded in your system.
 * The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
 * <p>
 * <p>
 * Example:
 * Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
 * The system have already tracked down the following sentences and their corresponding times:
 * "i love you" : 5 times
 * "island" : 3 times
 * "ironman" : 2 times
 * "i love leetcode" : 2 times
 * Now, the user begins another search:
 * <p>
 * Operation: input('i')
 * Output: ["i love you", "island","i love leetcode"]
 * Explanation:
 * There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree.
 * Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman".
 * Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
 * <p>
 * Operation: input(' ')
 * Output: ["i love you","i love leetcode"]
 * Explanation:
 * There are only two sentences that have prefix "i ".
 * <p>
 * Operation: input('a')
 * Output: []
 * Explanation:
 * There are no sentences that have prefix "i a".
 * <p>
 * Operation: input('#')
 * Output: []
 * Explanation:
 * The user finished the input, the sentence "i a" should be saved as a historical sentence in system.
 * And the following input will be counted as a new search.
 * <p>
 * Note:
 * The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
 * The number of complete sentences that to be searched won't exceed 100.
 * The length of each sentence including those in the historical data won't exceed 100.
 * Please use double-quote instead of single-quote when you write test cases even for a character input.
 * Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases.
 * <p>
 * Solution: Maintain a Trie (slightly modified) data-structure to all the input sentences where each node of the Trie
 * is a node containing a hash-map of child character and node and a TreeSet containing the sorted order of all the
 * possible child sentences starting from the current node. Maintain a cursor node 'curr' to indicate the current node
 * of input, if the input character is absent then simply mark curr as null indicating no further auto-complete terms possible.
 * On the other hand if the input character is present then simply pick the top 3 elements from the TreeSet object of curr
 * node.
 * Finally, use a StringBuilder to accumulate all the input characters and when a end of sentence is '#' is encountered
 * simply update the trie with new sentence and degree.
 */
public class AutocompleteSystem {

    private Map<String, Integer> hotTextMap; //Maintain a hash-map of sentences and degree
    private Trie curr, trie, root;
    private StringBuilder currSentence; //StringBuilder class to maintain current input sentence (until '#')

    /**
     * Main method
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        String[] sentences = {"i love you", "island", "ironman", "i love leetcode"};
        int[] degree = {5, 3, 2, 2};
        AutocompleteSystem autocomplete = new AutocompleteSystem(sentences, degree);
        List<String> result = autocomplete.input('i');
        result.forEach(System.out::println);
        result = autocomplete.input(' ');
        result.forEach(System.out::println);
        result = autocomplete.input('a');
        result.forEach(System.out::println);
        result = autocomplete.input('#');
        result.forEach(System.out::println);
    }

    /**
     * Initialize the trie data-structure
     *
     * @param sentences array of sentences
     * @param times     degree
     */
    public AutocompleteSystem(String[] sentences, int[] times) {
        hotTextMap = new HashMap<>();
        trie = new Trie();
        for (int i = 0; i < sentences.length; i++) {
            hotTextMap.put(sentences[i], times[i]);
            trie.insert(sentences[i]);
            trie.update(sentences[i]);
        }
        curr = trie;
        root = trie;
        currSentence = new StringBuilder();
    }

    /**
     * Accept input and return hot-text for the current char
     *
     * @param c char
     * @return List of top 3 hot-text
     */
    public List<String> input(char c) {
        List<String> result = new ArrayList<>();
        if (c == '#') {
            String sentence = currSentence.toString();
            if (hotTextMap.containsKey(sentence)) {
                //already a known sentence hence only update in necessary
                hotTextMap.put(sentence, hotTextMap.get(sentence) + 1);
                trie.update(sentence);
            } else {
                //insert a new sentence and update the degree
                hotTextMap.put(sentence, 1);
                trie.insert(sentence);
                trie.update(sentence);
            }
            currSentence = new StringBuilder(); //reset StringBuilder
            curr = root; //point to root of the trie
        } else {
            if (curr != null) {
                if (curr.containsChild(c)) {
                    List<String> hotText = curr.getSubtrie(c).getTop3HotText();
                    hotText.stream().forEach((x) -> result.add(currSentence.toString() + x)); //each node only returns
                    //the hot-text for the current and child nodes hence we have to attach the prefix string
                    curr = curr.getSubtrie(c);
                } else {
                    curr = null; //as soon as we encounter a empty node then set current to null indicating no further
                    //auto-complete terms are available
                }
            }
            currSentence.append(c);
        }
        return result;
    }

    /**
     * Class HotText to store the text and degree
     */
    private class HotText {
        private String text;
        private int degree;

        HotText(String text, int degree) {
            this.text = text;
            this.degree = degree;
        }

        private String getText() {
            return text;
        }

        private int getDegree() {
            return degree;
        }
    }

    /**
     * Class Trie
     */
    private class Trie {
        private Map<Character, Trie> map = new HashMap<>();
        private TreeSet<HotText> hotText =
                new TreeSet<>((HotText o1, HotText o2) -> {
                    int cmp = Integer.compare(o2.getDegree(), o1.getDegree());
                    return cmp == 0 ? o1.getText().compareTo(o2.getText()) : cmp;
                });

        /**
         * Get hot-text
         *
         * @return HotText
         */
        public TreeSet<HotText> getHotText() {
            return hotText;
        }

        /**
         * Return top 3 hottext
         *
         * @return hot text
         */
        private List<String> getTop3HotText() {
            List<String> hotText = new ArrayList<>();
            if (this.getHotText() != null) {
                this.getHotText().stream().limit(3).forEach((x) -> hotText.add(x.getText()));
            }
            return hotText;
        }

        /**
         * Inserts a word into the trie.
         */
        private void insert(String word) {
            if (word != null) {
                add(0, word, word.length());
            }
        }

        private void add(int i, String word, int length) {
            if (i < length) {
                char c = word.charAt(i);
                Trie subTrie = map.get(c);
                if (subTrie == null) {
                    subTrie = new Trie();
                    map.put(c, subTrie);
                }
                subTrie.add(i + 1, word, length);
            } else map.put(null, new Trie()); //use null to indicate end of string
        }

        /**
         * Update hottex and degree
         *
         * @param word word or sentence
         */
        private void update(String word) {
            if (word != null) {
                update(0, word, word.length());
            }
        }

        /**
         * Update trie
         *
         * @param i      curr position
         * @param word   sentence
         * @param length length
         * @return HotText
         */
        private HotText update(int i, String word, int length) {
            if (i < length) {
                char c = word.charAt(i);
                Trie subTrie = map.get(c);
                HotText subTrieHotText = subTrie.update(i + 1, word, length);
                HotText currHotText = new HotText(c + (subTrieHotText == null ? "" :
                        subTrieHotText.getText()), hotTextMap.get(word));
                updateHotText(subTrie, currHotText);
                return currHotText;
            }
            return null;
        }

        /**
         * Hot text update
         *
         * @param hotText hotText object
         */
        private void updateHotText(Trie trie, HotText hotText) {
            trie.getHotText().remove(new HotText(hotText.getText(), hotText.getDegree() - 1)); //remove already
            // contained hot-text and add new
            trie.getHotText().add(hotText);
        }

        /**
         * Contains child
         *
         * @param c char
         * @return true if it contains child, false otherwise
         */
        private boolean containsChild(char c) {
            return this.map.containsKey(c);
        }

        /**
         * Return child tree
         *
         * @param c char
         * @return child subTrie
         */
        private Trie getSubtrie(char c) {
            return this.map.get(c);
        }
    }
}