public class ODPCategoryReader extends DefaultHandler {

    private final ArrayList<String> topics;
    private final int level;

    public ODPCategoryReader(int param) {
        this.topics = new ArrayList<>();
        this.topics.add("Top");
        this.level = param;
    }

    public ArrayList<String> getTopics() {
        return topics;
    }

    @Override
    public void startElement(String uri,
            String localName, String qName, Attributes attributes)
            throws SAXException {
        if (qName.equalsIgnoreCase("DMOZ")) {
        } else if (qName.equalsIgnoreCase("Topic")) {
            String topicName = attributes.getValue("name");
            String[] split = topicName.split("/");
            if (split.length <= level) {
                topics.add(topicName);
            }
        } else if (qName.equalsIgnoreCase("content")) {
        }
    }

    @Override
    public void endElement(String uri,
            String localName, String qName) throws SAXException {
        if (qName.equalsIgnoreCase("DMOZ")) {
        } else if (qName.equalsIgnoreCase("Topic")) {
        } else if (qName.equalsIgnoreCase("content")) {
        }
    }

    @Override
    public void characters(char ch[],
            int start, int length) throws SAXException {
    }
} public class Helper {

    private static final TextTokenizer TOKENIZER = new TextTokenizer(true, true);

    /**
     * Generate a random number within a range.
     *
     * @param min
     * @param max
     * @return
     */
    public static int getRandom(int min, int max) {
        Random random = new Random();
        return random.nextInt(max - min) + min;
    }

    /**
     * Generate random number using poisson distribution.
     *
     * @param lambda average query length
     * @return
     */
    public static int getPoisson(double lambda) {
        int n = 1;
        double prob = 1.0;
        Random r = new Random();

        while (true) {
            prob *= r.nextDouble();
            if (prob < Math.exp(-lambda)) {
                break;
            }
            n += 1;
        }
        return n - 1;
    }

    /**
     *
     *
     * @param previousQuery
     * @param currentQuery
     * @return
     */
    public static boolean checkSameSession(UserQuery previousQuery, UserQuery currentQuery) {
        /**
         * Measuring the time difference between current query and last
         * submitted query in minutes.
         */
        double diffMinutes = 0;
        try {
            //in milliseconds
            long diff = currentQuery.getQuery_time().getTime() - previousQuery.getQuery_time().getTime();
            diffMinutes = diff / (60.0 * 1000);
        } catch (Exception ex) {
            Logger.getLogger(Helper.class.getName()).log(Level.SEVERE, null, ex);
        }
        /**
         * If time difference is less than 60 minutes between current query and
         * previous query, they belong to the same session .
         */
        return diffMinutes < 60;
    }

    public static boolean checkSameTask(UserQuery previousQuery, UserQuery currentQuery) {
        /**
         * Measuring the similarity between current query and last submitted
         * query in terms of similar tokens they have.
         */
        HashSet<String> currentQuTokens = new HashSet<>(TOKENIZER.TokenizeText(currentQuery.getQuery_text()));
        HashSet<String> prevQuTokens = new HashSet<>(TOKENIZER.TokenizeText(previousQuery.getQuery_text()));
        boolean isSimilar = false;
        int count = (currentQuTokens.size() > prevQuTokens.size() ? prevQuTokens.size() : currentQuTokens.size()) / 2;
        HashSet<String> intersection = new HashSet<>(currentQuTokens);
        intersection.retainAll(prevQuTokens);
        if (intersection.size() >= count) {
            isSimilar = true;
        }
        /**
         * If both queries have 50% similarity in terms of having similar
         * tokens, they belong to the same task .
         */
        return isSimilar;
    }

    public static UserQuery isInSessionTask(Session session, UserQuery currentQuery) {
        for (UserQuery query : session.getUser_queries()) {
            if (checkSameTask(query, currentQuery)) {
                return query;
            }
        }
        return null;
    }

    private static HashMap<String, Integer> computeTermFreq(List<String> tokens) {
        HashMap<String, Integer> termFreqMap = new HashMap<>();
        // computing term frequency of all the unique terms found in the document
        for (String tok : tokens) {
            if (termFreqMap.containsKey(tok)) {
                termFreqMap.put(tok, termFreqMap.get(tok) + 1);
            } else {
                termFreqMap.put(tok, 1);
            }
        }
        return termFreqMap;
    }

    private static ArrayList<ResultDoc> reRank(HashMap<String, Float> docScoreMap, ArrayList<ResultDoc> relDocs) {
        /**
         * Client side re-ranking using true user profile.
         */
        Map<String, Float> resultedMap = SortMap.sortMapByValue(docScoreMap, false);

        /**
         * Re-rank the documents by giving weight to the search engine rank and
         * the client side rank.
         */
        int i = 0;
        for (Map.Entry<String, Float> entry : resultedMap.entrySet()) {
            float score;
            // Giving 30% weight to client-side re-ranking and 70% to server-side ranking.
            if (entry.getValue() == 0) {
                score = 0.7f * (1.0f / (Integer.parseInt(entry.getKey()) + 1));
            } else {
                score = 0.3f * (1.0f / (i + 1)) + 0.7f * (1.0f / (Integer.parseInt(entry.getKey()) + 1));
            }
            docScoreMap.put(entry.getKey(), score);
            i++;
        }

        // sort the documents in descending order according to the new score assigned
        Map<String, Float> result = SortMap.sortMapByValue(docScoreMap, false);
        ArrayList<ResultDoc> retValue = new ArrayList<>();
        for (Map.Entry<String, Float> entry : result.entrySet()) {
            retValue.add(relDocs.get(Integer.parseInt(entry.getKey())));
        }

        return retValue;
    }

    /**
     * Method that re-ranks the result in the client side.
     *
     * @param history
     * @param relDocs all the relevant documents returned by the search engine
     * @return re-ranked resulting documents
     */
    public static ArrayList<ResultDoc> reRankResults(HashMap<String, Integer> history, ArrayList<ResultDoc> relDocs) {
        HashMap<String, Float> docScoreMap = new HashMap<>();
        HashMap<String, Integer> uniqueDocTerms;

        for (int i = 0; i < relDocs.size(); i++) {
            List<String> tokens = TOKENIZER.TokenizeText(relDocs.get(i).getContent());
            uniqueDocTerms = computeTermFreq(tokens);

            float docScore = 0;
            // smoothing parameter for linear interpolation
            float lambda = 0.1f;
            for (Map.Entry<String, Integer> entry : history.entrySet()) {
                if (!uniqueDocTerms.containsKey(entry.getKey())) {
                    continue;
                }
                // maximum likelihood calculation
                Double tokenProb = (uniqueDocTerms.get(entry.getKey()) * 1.0) / tokens.size();
                // probability from reference model for smoothing purpose
                Double refProb = StaticData.SmoothingReference.get(entry.getKey());
                if (refProb == null) {
                    refProb = 0.0;
                }
                // smoothing token probability using linear interpolation
                Double smoothedTokenProb = (1 - lambda) * tokenProb + lambda * refProb;
                smoothedTokenProb = smoothedTokenProb / (lambda * refProb);
                docScore = docScore + (entry.getValue() * (float) Math.log(smoothedTokenProb));
            }
            docScoreMap.put(String.valueOf(i), docScore);
        }

        // return re-ranked documents
        return reRank(docScoreMap, relDocs);
    }

    /**
     * Method that generate the id of all users for evaluation.
     *
     * @param folder folder path where all user search log resides
     * @param count
     * @return list of all user id
     */
    public static ArrayList<String> getAllUserId(String folder, int count) {
        ArrayList<String> allUserIds = new ArrayList<>();
        File dir = new File(folder);
        int userCount = 0;
        for (File f : dir.listFiles()) {
            if (f.isFile()) {
                String fileName = f.getName();
                fileName = fileName.substring(0, fileName.lastIndexOf("."));
                allUserIds.add(fileName);
                userCount++;
            }
            if (userCount == count) {
                break;
            }
        }
        return allUserIds;
    }

} public class DeploymentConfig {

    public static String AolIndexPath;
    public static String OdpIndexPath;
    public static String UserSearchLogPath;
    public static String ReferenceModelPath;
    public static String AolDocFreqRecord;
    public static String OdpHierarchyRecord;
    public static String BackgroundKnowledge;
    public static String TransitionMatrix;
    public static String TransitionProbability;
    public static String OutDirectory;
} public class RunTimeConfig {

    public static int NumberOfCoverQuery;
    public static int NumberOfThreads;
    public static int IntervalInHours;
    public static boolean ClientSideRanking;
    public static int TotalDocInWeb;
    public static boolean removeStopWordsInCQ;
    public static boolean doStemmingInCQ;
} public class OkapiBM25 extends SimilarityBase {

    double k1 = 1.2; // range 1.2 - 2
    double k2 = 750; // range 0 - 1000
    double b = 0.75; // range 0.75 - 1.2

    /**
     * Returns a score for a single term in the document.
     *
     * @param stats Provides access to corpus-level statistics
     * @param termFreq
     * @param docLength
     * @return 
     */
    @Override
    protected float score(BasicStats stats, float termFreq, float docLength) {
        float relevance;
        float part1 = (float) (Math.log((stats.getNumberOfDocuments() - stats.getDocFreq() + 0.5) / (stats.getDocFreq() + 0.5)) / Math.log(Math.E));
        float part2 = (float) (((k1 + 1) * termFreq) / ((k1 * (1 - b + b * (docLength / stats.getAvgFieldLength()))) + termFreq));
        float part3 = (float) (((k2 + 1) * 1) / (k2 + 1));
        relevance = part1 * part2 * part3;
        return relevance;
    }

    @Override
    public String toString() {
        return "Okapi BM25";
    }

} public class Searcher {

    private IndexSearcher indexSearcher;
    private final SpecialAnalyzer analyzer;

    /* User profile which is constructed and maintained in the server side */
    private Profile userProfile;
    /* Flag to turn on or off personalization */
    private boolean activatePersonalization = false;

    /**
     * Sets up the Lucene index Searcher with the specified index.
     *
     * @param indexPath The path to the desired Lucene index.
     */
    public Searcher(String indexPath) {
        analyzer = new SpecialAnalyzer(true, true);
        try {
            IndexReader reader = DirectoryReader.open(FSDirectory.open(new File(indexPath)));
            indexSearcher = new IndexSearcher(reader);
        } catch (IOException exception) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
        }
    }

    /**
     * Activate or deactivate personalization.
     *
     * @param flag
     */
    public void activatePersonalization(boolean flag) {
        activatePersonalization = flag;
    }

    /**
     * Initialize the user profile maintained by the server side.
     *
     * @param userId
     */
    public void initializeUserProfile(String userId) {
        userProfile = new Profile(userId);
    }

    /**
     * Update user profile based on the clicked document content.
     *
     * @param query
     * @param doc
     * @throws java.io.IOException
     */
    public void clickDocument(UserQuery query, ResultDoc doc) throws IOException {
        Intent intent = (Intent) userProfile.getNodeMap().get(query.getQuery_intent().getName());
        if (intent == null) {
            intent = new Intent(query.getQuery_intent().getName());
            userProfile.addIntent(intent);
        }
        intent.updateUsingClickedDoc(doc.getContent());
    }

    /**
     * Return user profile maintained by the server side.
     *
     * @return user profile
     */
    public Profile getUserProfile() {
        return userProfile;
    }

    /**
     * Sets ranking function for index searching.
     *
     * @param sim
     */
    public void setSimilarity(Similarity sim) {
        indexSearcher.setSimilarity(sim);
    }

    private void updateSessionInformation(UserQuery userQuery) {
        UserQuery lastSubmittedQuery = userProfile.getLastSubmittedQuery();
        boolean isSame = false;
        if (lastSubmittedQuery != null) {
            isSame = Helper.checkSameSession(lastSubmittedQuery, userQuery);
        }

        // current query and previous query (if any) are from different session
        if (!isSame) {
            if (lastSubmittedQuery != null) {
                // set end time of previous session
                userProfile.getLastSession().setEnd_time(lastSubmittedQuery.getQuery_time());
            }
            // start of a new user session
            Session session = new Session(userProfile.getSessions().size());
            session.setStart_time(userQuery.getQuery_time());
            userProfile.addSession(session);
        }
    }

    /**
     * The main search function. Searches the abstract field and returns a the
     * default number of results.
     *
     * @param userQuery
     * @return
     */
    public SearchResult search(UserQuery userQuery) {
        updateSessionInformation(userQuery);
        SearchQuery searchQuery = new SearchQuery(userQuery.getQuery_text(), Constants.DEFAULT_FIELD);
        BooleanQuery combinedQuery = new BooleanQuery();
        for (String field : searchQuery.fields()) {
            QueryParser parser = new QueryParser(Version.LUCENE_46, field, analyzer);
            try {
                Query textQuery = parser.parse(QueryParser.escape(searchQuery.queryText()));
                combinedQuery.add(textQuery, BooleanClause.Occur.MUST);
            } catch (ParseException exception) {
                Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
            }
        }
        return runSearch(combinedQuery, searchQuery, userQuery);
    }

    /**
     * The main search function. Searches the abstract field and returns a the
     * default number of results.
     *
     * @param query_text
     * @return
     */
    public SearchResult search(String query_text) {
        SearchQuery searchQuery = new SearchQuery(query_text, Constants.DEFAULT_FIELD);
        BooleanQuery combinedQuery = new BooleanQuery();
        for (String field : searchQuery.fields()) {
            QueryParser parser = new QueryParser(Version.LUCENE_46, field, analyzer);
            try {
                Query textQuery = parser.parse(QueryParser.escape(searchQuery.queryText()));
                combinedQuery.add(textQuery, BooleanClause.Occur.MUST);
            } catch (ParseException exception) {
                Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
            }
        }
        return runSearch(combinedQuery, searchQuery);
    }

    /**
     * Searches for a document content in the index.
     *
     * @param queryText the document title, a URL
     * @param field
     * @param retField
     * @return clicked document content
     */
    public ArrayList<String> search(String queryText, String field, String retField) {
        return runSearch(new SearchQuery(queryText, field), retField);
    }

    /**
     * Performs the actual Lucene search.
     *
     * @param luceneQuery
     * @param numResults
     * @return the SearchResult
     */
    private SearchResult runSearch(Query luceneQuery, SearchQuery searchQuery, UserQuery userQuery) {
        try {
            TopDocs docs = indexSearcher.search(luceneQuery, searchQuery.fromDoc() + searchQuery.numResults());
            ResultDoc[] hits;
            String field = searchQuery.fields().get(0);
            if (activatePersonalization) {
                /* Personalize result using entire user profile. */
                HashMap<String, Integer> tempMap = userProfile.getCompleteHistory();
                hits = Personalization.personalizeResults(indexSearcher, field, tempMap, docs.scoreDocs);
            } else {
                hits = Converter.convertToResultDoc(docs.scoreDocs, indexSearcher, field);
            }

            /* Updating the server side user profile with the query */
            userQuery.setQuery_intent(userProfile.addIntent(userQuery.getQuery_intent()));
            boolean success = userProfile.addQuery(userQuery);
            if (!success) {
                System.err.println("Failed to update server-side user profile and now exiting...");
                System.exit(1);
            }
            userProfile.getLastSession().addUser_queries(userQuery);

            SearchResult searchResult = new SearchResult(searchQuery, docs.totalHits);
            for (ResultDoc hit : hits) {
                searchResult.addResult(hit);
            }
            searchResult.trimResults(searchQuery.fromDoc());
            return searchResult;
        } catch (IOException exception) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
        }
        return new SearchResult(searchQuery);
    }

    /**
     * Performs the actual Lucene search.
     *
     * @param luceneQuery
     * @param numResults
     * @return the SearchResult
     */
    private SearchResult runSearch(Query luceneQuery, SearchQuery searchQuery) {
        try {
            TopDocs docs = indexSearcher.search(luceneQuery, searchQuery.fromDoc() + searchQuery.numResults());
            ScoreDoc[] hits = docs.scoreDocs;
            String field = searchQuery.fields().get(0);

            SearchResult searchResult = new SearchResult(searchQuery, docs.totalHits);
            for (ScoreDoc hit : hits) {
                Document doc = indexSearcher.doc(hit.doc);
                ResultDoc rdoc = new ResultDoc(hit.doc);
                String contents = doc.getField(field).stringValue();
                rdoc.setContent(contents);
                rdoc.setUrl(doc.getField("url").stringValue());
                rdoc.setTopic(doc.getField("topic").stringValue());
                searchResult.addResult(rdoc);
            }

            searchResult.trimResults(searchQuery.fromDoc());
            return searchResult;

        } catch (IOException ex) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, ex);
        }
        return new SearchResult(searchQuery);
    }

    /**
     * Searches and returns relevant document's content.
     *
     * @param searchQuery a clicked URL
     * @param indexableField content of this field needs to be returned
     * @return document's content
     */
    private ArrayList<String> runSearch(SearchQuery searchQuery, String indexableField) {
        Query luceneQuery = new TermQuery(new Term(searchQuery.fields().get(0), searchQuery.queryText()));
        ArrayList<String> returnedResult = new ArrayList<>();
        try {
            TotalHitCountCollector collector = new TotalHitCountCollector();
            indexSearcher.search(luceneQuery, collector);
            TopDocs docs = indexSearcher.search(luceneQuery, Math.max(1, collector.getTotalHits()));
            ScoreDoc[] hits = docs.scoreDocs;
            for (ScoreDoc hit : hits) {
                Document doc = indexSearcher.doc(hit.doc);
                String contents = doc.getField(indexableField).stringValue();
                returnedResult.add(contents);
            }
        } catch (IOException exception) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
        }

        return returnedResult;
    }

    /**
     * Searches and returns total hit count for given query terms.
     *
     * @param tokens
     * @param field
     * @return hit document's id
     */
    public int search(List<String> tokens, String field) {
        int hit_count = 0;
        BooleanQuery combinedQuery = new BooleanQuery();
        for (String token : tokens) {
            Query luceneQuery = new TermQuery(new Term(field, token));
            combinedQuery.add(luceneQuery, BooleanClause.Occur.MUST);
        }

        try {
            TotalHitCountCollector collector = new TotalHitCountCollector();
            indexSearcher.search(combinedQuery, collector);
            hit_count = collector.getTotalHits();
        } catch (IOException exception) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, exception);
        }
        return hit_count;
    }

} public class ClassifyIntent {

    private final Searcher SEARCHER;

    public ClassifyIntent() {
        this.SEARCHER = new Searcher(DeploymentConfig.OdpIndexPath);
        this.SEARCHER.setSimilarity(new OkapiBM25());
    }

    /**
     * Returns the best topic that characterize the given query.
     *
     * @param tokens
     * @param n size of the query
     * @return
     */
    private String getTopic(String queryText) {
        String bestTopic = null;
        ArrayList<ResultDoc> results = SEARCHER.search(queryText).getDocs();
        if (!results.isEmpty()) {
            HashMap<String, Double> topicMap = new HashMap<>();
            int rank = 1;
            for (ResultDoc rdoc : results) {
                double score = ((int) ((1.0 / rank) * 100)) / 100.0;
                if (topicMap.containsKey(rdoc.getTopic())) {
                    score += topicMap.get(rdoc.getTopic());
                    score = ((int) (score * 100)) / 100.0;
                    topicMap.put(rdoc.getTopic(), score);
                } else {
                    topicMap.put(rdoc.getTopic(), score);
                }
                rank++;
            }
            for (Map.Entry<String, Double> entry : SortMap.sortMapByValue(topicMap, false, 1).entrySet()) {
                bestTopic = entry.getKey();
            }
        }
        return bestTopic;
    }

    public Intent inferQueryIntent(UserQuery query) {
        String inferred_topic_name = getTopic(query.getQuery_text());
        if (inferred_topic_name == null) {
            /* if topic of the query can not be inferred */
            return null;
        }
        return new Intent(inferred_topic_name);
    }
} public class GenerateCoverQuery {

    private final TopicTree topicTree;
    private final TextTokenizer tokenizer;
    private final Searcher SEARCHER;
    private final GenerateQuery gQuery;

    public GenerateCoverQuery(TopicTree tree) {
        this.topicTree = tree;
        this.SEARCHER = new Searcher(DeploymentConfig.OdpIndexPath);
        this.SEARCHER.setSimilarity(new OkapiBM25());
        this.tokenizer = new TextTokenizer(RunTimeConfig.removeStopWordsInCQ, RunTimeConfig.doStemmingInCQ);
        this.gQuery = new GenerateQuery(SEARCHER, tokenizer);
    }

    /**
     *
     * @param probability
     *
     * @return
     */
    private int getBucketNumber(double probability, Double[] probArray) {
        for (int i = 0; i < probArray.length; i++) {
            if (probability >= probArray[i]) {
                return i + 1;
            }
        }
        return probArray.length;
    }

    /**
     * Generate a list of integers where the first value is the query length,
     * second value is the inferred topic number and the last one is the bucket
     * number from which the query belongs.
     *
     * @param queryTopicNode node of the topic tree from where query belongs to
     * @param query true user query
     * @return list of integers
     */
    private int getBucketNumber(TopicTreeNode queryTopicNode, UserQuery query) {
        Topic topic = queryTopicNode.getTopic();
        List<String> tokens = tokenizer.TokenizeText(query.getQuery_text());
        String modifiedQuery = "";
        for (String token : tokens) {
            modifiedQuery += token + " ";
        }
        modifiedQuery = modifiedQuery.trim();
        int query_length = tokens.size();
        query.setQuery_length(query_length);
        int bucket_num;

        topic.prepare(SEARCHER, queryTopicNode.getTopic_name(), query_length);
        switch (query_length) {
            case 1: {
                Double[] probArray = topic.getProbArrayUnigram();
                double prob = topic.getProbabilityUnigram(modifiedQuery);
//                double prob = topic.getProbabilityUnigram(modifiedQuery, queryTopicNode);
                bucket_num = getBucketNumber(prob, probArray);
                break;
            }
            case 2: {
                Double[] probArray = topic.getProbArrayBigram();
                double prob = topic.getProbabilityBigram(modifiedQuery, true);
//                double prob = topic.getProbabilityBigram(modifiedQuery, true, queryTopicNode);
                bucket_num = getBucketNumber(prob, probArray);
                break;
            }
            case 3: {
                Double[] probArray = topic.getProbArrayTrigram();
                double prob = topic.getProbabilityTrigram(modifiedQuery, true);
//                double prob = topic.getProbabilityTrigram(modifiedQuery, true, queryTopicNode);
                bucket_num = getBucketNumber(prob, probArray);
                break;
            }
            case 4: {
                Double[] probArray = topic.getProbArrayFourgram();
                double prob = topic.getProbabilityFourgram(modifiedQuery, true);
//                double prob = topic.getProbabilityFourgram(modifiedQuery, true, queryTopicNode);
                bucket_num = getBucketNumber(prob, probArray);
                break;
            }
            default: {
                Double[] probArray = topic.getProbArrayFourgram();
                double prob = topic.getProbabilityNgram(modifiedQuery, query_length);
//                double prob = topic.getProbabilityNgram(modifiedQuery, query_length, queryTopicNode);
                bucket_num = getBucketNumber(prob, probArray);
                break;
            }
        }

        topic.reset();
        return bucket_num;
    }

    /**
     * Computes and return a cover query topic.
     *
     * @param level
     * @param queryTopic
     * @param fromSibling
     * @return the cover query topic
     */
    private TopicTreeNode getCoverQueryTopic(TopicTreeNode queryTopic, boolean fromSibling) {
        ArrayList<TreeNode> listNodes = new ArrayList<>();
        if (fromSibling) {
            /**
             * Selecting a cover query topic only from sibling topics.
             */
            listNodes.addAll(queryTopic.getSiblings());
        } else {
            /**
             * Selecting a cover query topic from same level but from
             * non-sibling topics.
             */
            for (TreeNode node : topicTree.getNodesOfLevel(queryTopic.getNodeLevel())) {
                if (((TopicTreeNode) node.getParent()).getTopic_id() != ((TopicTreeNode) queryTopic.getParent()).getTopic_id()) {
                    listNodes.add(node);
                }
            }
        }
        if (listNodes.isEmpty()) {
            return null;
        }
        int topic = getRandom(0, listNodes.size());
        return (TopicTreeNode) listNodes.get(topic);
    }

    /**
     * Check if the user query is sequentially edited or not.
     *
     * @param previousQuTopic
     * @param currentQuTopic
     * @return
     */
    private int isSequentiallyEdited(UserQuery previousQuery, UserQuery currentQuery) {
        /**
         * Check if current query intent is the parent of previous query intent,
         * then sequential editing is true.
         */
        if (currentQuery.getQuery_intent().isParent(previousQuery.getQuery_intent())) {
            return 1;
        }
        /**
         * Check if current query intent is the child of previous query intent,
         * then sequential editing is true.
         */
        if (previousQuery.getQuery_intent().isParent(currentQuery.getQuery_intent())) {
            return -1;
        }
        /**
         * Current query topic is neither parent nor child of the previous query
         * topic, so return 0.
         */
        return 0;
    }

    private UserQuery generateCoverQuery(int buck_num, TopicTreeNode cover_node, UserQuery currentQuery, Profile profile) {
        int coverQuLen = Helper.getPoisson(currentQuery.getQuery_length());
        if (coverQuLen == 0) {
            return null;
        }
        UserQuery coverQuery;
        switch (coverQuLen) {
            case 1:
                coverQuery = gQuery.getCQfromUnigramLM(buck_num, cover_node, currentQuery, profile);
                break;
            case 2:
                coverQuery = gQuery.getCQfromBigramLM(buck_num, cover_node, currentQuery, profile);
                break;
            case 3:
                coverQuery = gQuery.getCQfromTrigramLM(buck_num, cover_node, currentQuery, profile);
                break;
            case 4:
                coverQuery = gQuery.getCQfromFourgramLM(buck_num, cover_node, currentQuery, profile);
                break;
            default:
                coverQuery = gQuery.getCQfromNgramLM(coverQuLen, buck_num, cover_node, currentQuery, profile);
                break;
        }
        return coverQuery;
    }

    public ArrayList<UserQuery> generateCoverQueries(Profile profile, UserQuery query) {
        ArrayList<UserQuery> coverQueries = new ArrayList<>();
        /* step 1. get the topic of user query */
        String topic_name = query.getQuery_intent().getName();
        TopicTreeNode topicNode = (TopicTreeNode) topicTree.getTreeNode(topic_name);

        /* step 2. infer the bucket number for the user query */
        if (topicNode == null) {
            System.err.println("Fatal Exception: Topic (" + topic_name + ") not found. Exiting...");
            System.exit(1);
        }
        int bucket_num = getBucketNumber(topicNode, query);

        /* step 3. check if the current query is sequentially edited */
        UserQuery lastSubmittedQuery = profile.getLastSubmittedQuery();
        int isSeqEdited = 0;
        if (lastSubmittedQuery != null) {
            isSeqEdited = isSequentiallyEdited(lastSubmittedQuery, query);
        }

        /* step 4. create required number of cover queries */
        int count = 0;
        ArrayList<UserQuery> previousCoverQueries = null;
        if (lastSubmittedQuery != null && isSeqEdited != 0) {
            previousCoverQueries = lastSubmittedQuery.getCover_queries();
        }

        boolean fromSiblingPossible = true;
        int numberOfAttempts = 0;
        while (true) {
            UserQuery coverQuery = null;
            if (isSeqEdited == 0) {
                /* Current query is not sequentially edited. */
                if (count < RunTimeConfig.NumberOfCoverQuery / 2 && fromSiblingPossible) {
                    /* Generating cover query from sibling topics. */
                    TopicTreeNode cover_node = getCoverQueryTopic(topicNode, true);
                    if (cover_node == null) {
                        fromSiblingPossible = false;
                    } else {
                        coverQuery = generateCoverQuery(bucket_num, cover_node, query, profile);
                    }
                } else {
                    /* Generating cover query from same level of original query but not from sibling topics. */
                    TopicTreeNode cover_node = getCoverQueryTopic(topicNode, false);
                    if (cover_node != null) {
                        coverQuery = generateCoverQuery(bucket_num, cover_node, query, profile);
                    }
                }

            } else {
                if (previousCoverQueries == null || count >= previousCoverQueries.size()) {
                    /* cover queries can't be generated based on previous cover queries */
                    isSeqEdited = 0;
                    continue;
                }
                /**
                 * Current query is sequentially edited, so cover queries will
                 * be generated based on previous cover query topics.
                 */
                if (isSeqEdited == 1) {
                    /**
                     * Cover query should be generated from parent topic of the
                     * previous cover query.
                     */
                    String parent_name = ((Intent) previousCoverQueries.get(count).getQuery_intent().getParent()).getName();
                    TopicTreeNode cover_node = (TopicTreeNode) topicTree.getTreeNode(parent_name);
                    coverQuery = generateCoverQuery(bucket_num, cover_node, query, profile);
                } else {
                    /**
                     * Cover query should be generated from child topic of the
                     * previous cover query.
                     */
                    List<TreeNode> childrens = previousCoverQueries.get(count).getQuery_intent().getChildrens();
                    if (!childrens.isEmpty()) {
                        int rand = -1;
                        for (int x = 0; x < childrens.size(); x++) {
                            rand = Helper.getRandom(0, childrens.size());
                            Topic topic = ((TopicTreeNode) childrens.get(rand)).getTopic();
                            if (!topic.isEmpty()) {
                                break;
                            } else {
                                rand = -1;
                            }
                        }
                        if (rand == -1) {
                            /* cover queries can't be generated from child topic of the previous query */
                            isSeqEdited = 0;
                        } else {
                            TopicTreeNode cover_node = ((TopicTreeNode) childrens.get(rand));
                            coverQuery = generateCoverQuery(bucket_num, cover_node, query, profile);
                        }
                    } else {
                        /* cover queries can't be generated from child topic of the previous query */
                        isSeqEdited = 0;
                    }
                }
            }

            if (coverQuery != null) {
                coverQuery.setQuery_time(query.getQuery_time());
                coverQueries.add(coverQuery);
                count++;
            }

            if (count == RunTimeConfig.NumberOfCoverQuery && isSeqEdited == 0) {
                break;
            } else if (isSeqEdited != 0 && previousCoverQueries != null && count == previousCoverQueries.size()) {
                break;
            } else if (numberOfAttempts == (RunTimeConfig.NumberOfCoverQuery * 10)) {
                break;
            }
            numberOfAttempts++;
        }

        return coverQueries;
    }
} public class TopicTree implements Tree {

    private HashMap<String, TreeNode> nodeMap;
    private final HashMap<Integer, List<TreeNode>> levelWiseNodeMap;

    public TopicTree() {
        this.nodeMap = new HashMap<>();
        this.levelWiseNodeMap = new HashMap<>();
    }

    public TopicTree(TopicTree tree) {
        this.nodeMap = new HashMap<>();
        this.nodeMap.putAll(tree.getNodeMap());
        this.levelWiseNodeMap = new HashMap<>();
        this.levelWiseNodeMap.putAll(tree.getLevelWiseNodeMap());
    }

    @Override
    public void setNodes(HashMap<String, TreeNode> nodeMap) {
        this.nodeMap = nodeMap;
    }

    public TreeNode getTreeNode(String name) {
        return this.nodeMap.get(name);
    }

    @Override
    public HashMap<String, TreeNode> getNodeMap() {
        return this.nodeMap;
    }

    public boolean exists(String node) {
        return nodeMap.containsKey(node);
    }

    @Override
    public void addNode(String nodePath, TreeNode node) {
        this.nodeMap.put(nodePath, node);
        if (levelWiseNodeMap.containsKey(node.getNodeLevel())) {
            levelWiseNodeMap.get(node.getNodeLevel()).add(node);
        } else {
            List<TreeNode> nodeList = new ArrayList<>();
            nodeList.add(node);
            levelWiseNodeMap.put(node.getNodeLevel(), nodeList);
        }
    }

    public List<TreeNode> getNodesOfLevel(int level) {
        return levelWiseNodeMap.get(level);
    }

    public HashMap<Integer, List<TreeNode>> getLevelWiseNodeMap() {
        return this.levelWiseNodeMap;
    }

} public class TopicTreeNode implements TreeNode {

    private TreeNode parent;
    private ArrayList<TreeNode> listOfChildren;
    private Topic topic;

    private int topic_id;
    private String topic_name;
    private int level;
    private double topicPrior;

    public TopicTreeNode(String name, int id) {
        this.topic_name = name;
        this.topic_id = id;
        this.topic = new Topic();
        this.listOfChildren = new ArrayList<>();
        topicPrior = -1;
    }

    @Override
    public TreeNode getParent() {
        return parent;
    }

    @Override
    public void setParent(TreeNode parent) {
        this.parent = parent;
    }

    @Override
    public List<TreeNode> getChildrens() {
        return listOfChildren;
    }

    public List<TreeNode> getSiblings() {
        ArrayList<TreeNode> siblings = new ArrayList<>();
        for (TreeNode node : parent.getChildrens()) {
            if (((TopicTreeNode) node).getTopic_id() != this.topic_id) {
                siblings.add(node);
            }
        }
        return siblings;
    }

    @Override
    public void setChildrens(List<TreeNode> childrens) {
        this.listOfChildren = new ArrayList<>(childrens);
    }

    @Override
    public void addChildren(TreeNode children) {
        this.listOfChildren.add(children);
    }

    @Override
    public void setNodeLevel(int level) {
        this.level = level;
    }

    @Override
    public int getNodeLevel() {
        return level;
    }

    public Topic getTopic() {
        return topic;
    }

    public void setTopic(Topic topic) {
        this.topic = topic;
    }

    public int getTopic_id() {
        return topic_id;
    }

    public void setTopic_id(int topic_id) {
        this.topic_id = topic_id;
    }

    public String getTopic_name() {
        return topic_name;
    }

    public void setTopic_name(String topic_name) {
        this.topic_name = topic_name;
    }

    public double getTopicPrior(int totalNodes) {
        if (topicPrior == -1) {
            computeTopicPrior(totalNodes);
        }
        return topicPrior;
    }

    public void setTopicPrior(double topicPrior) {
        this.topicPrior = topicPrior;
    }

    /**
     * Computes topic prior based on the number of nodes in the subtree rooted
     * at topic t divided by total number of nodes in the topic hierarchy.
     *
     * @param totalNodes
     */
    private void computeTopicPrior(int totalNodes) {
        if (topicPrior == -1) {
            double totalNodesInSubTree = 1;
            LinkedList<TreeNode> list = new LinkedList<>();
            list.addAll(listOfChildren);
            while (!list.isEmpty()) {
                TreeNode tNode = list.poll();
                list.addAll(tNode.getChildrens());
                totalNodesInSubTree++;
            }
            topicPrior = totalNodesInSubTree / totalNodes;
        }
    }

} public class ResultDoc {

    private final int _id;
    private String _title = "[no title]";
    private String _content = "[no content]";
    private String _modifiedContent = "[no modified content]";
    private String _docUrl = "[no url]";
    private boolean _isClicked = false;
    private String _topic = "[no topic]";
    private float _BM25Score;
    private float _personalizationScore;

    public ResultDoc() {
        _id = -1;
    }

    public float getBM25Score() {
        return _BM25Score;
    }

    public void setBM25Score(float _BM25Score) {
        this._BM25Score = _BM25Score;
    }

    public float getPersonalizationScore() {
        return _personalizationScore;
    }

    public void setPersonalizationScore(float _personalizationScore) {
        this._personalizationScore = _personalizationScore;
    }

    public ResultDoc(int id) {
        _id = id;
    }

    public int getId() {
        return _id;
    }

    public String getTitle() {
        return _title;
    }

    public ResultDoc setTitle(String nTitle) {
        _title = nTitle;
        return this;
    }

    public String getContent() {
        return _content;
    }

    public String getUrl() {
        return _docUrl;
    }

    public ResultDoc setContent(String nContent) {
        _content = nContent;
        return this;
    }

    public String getModifiedContent() {
        return _modifiedContent;
    }

    public void setModifiedContent(String _modifiedContent) {
        this._modifiedContent = _modifiedContent;
    }

    public ResultDoc setUrl(String nContent) {
        _docUrl = nContent;
        return this;
    }

    public ResultDoc setClicked() {
        _isClicked = true;
        return this;
    }

    public boolean isClicked() {
        return _isClicked;
    }

    public String getTopic() {
        return _topic;
    }

    public void setTopic(String _topic) {
        this._topic = _topic;
    }

} public class Session {

    private final int session_id;
    private Date start_time;
    private Date end_time;
    private ArrayList<UserQuery> user_queries;

    public Session(int id) {
        this.session_id = id;
        this.user_queries = new ArrayList<>();
    }

    public int getSession_id() {
        return session_id;
    }

    public Date getStart_time() {
        return start_time;
    }

    public void setStart_time(Date start_time) {
        this.start_time = start_time;
    }

    public Date getEnd_time() {
        return end_time;
    }

    public void setEnd_time(Date end_time) {
        this.end_time = end_time;
    }

    public void addUser_queries(UserQuery user_query) {
        this.user_queries.add(user_query);
    }

    public ArrayList<UserQuery> getUser_queries() {
        return user_queries;
    }

    public void setUser_queries(ArrayList<UserQuery> user_queries) {
        this.user_queries = user_queries;
    }

    public UserQuery checkRepeat(UserQuery query) {
        for (int i = user_queries.size() - 1; i >= 0; i--) {
            if (user_queries.get(i).getQuery_text().equals(query.getQuery_text())) {
                return user_queries.get(i);
            }
        }
        return null;
    }

    public boolean belongsTo(UserQuery query) {
        UserQuery lastQuery = user_queries.get(user_queries.size() - 1);
        return Helper.checkSameSession(lastQuery, query);
    }

} public class UserQuery {

    private int query_id;
    private String query_text;
    private Date query_time;
    private int query_length;
    private ArrayList<ResultDoc> relevant_documents;
    private ArrayList<UserQuery> cover_queries;
    private Intent query_intent;

    public UserQuery(int query_id, String query_text) {
        this.query_id = query_id;
        this.query_text = query_text;
        this.relevant_documents = new ArrayList<>();
        this.cover_queries = new ArrayList<>();
    }

    public int getQuery_id() {
        return query_id;
    }

    public void setQuery_id(int query_id) {
        this.query_id = query_id;
    }

    public String getQuery_text() {
        return query_text;
    }

    public void setQuery_text(String query_text) {
        this.query_text = query_text;
    }

    public Date getQuery_time() {
        return query_time;
    }

    public void setQuery_time(Date query_time) {
        this.query_time = query_time;
    }

    public int getQuery_length() {
        return query_length;
    }

    public void setQuery_length(int query_length) {
        this.query_length = query_length;
    }

    public ArrayList<ResultDoc> getRelevant_documents() {
        return relevant_documents;
    }

    public ResultDoc relDoc_Contains(ResultDoc rdoc) {
        for (ResultDoc clicked_doc : relevant_documents) {
            if (clicked_doc.getUrl().equals(rdoc.getUrl())) {
                return clicked_doc;
            }
        }
        return null;
    }

    public void setRelevant_documents(ArrayList<ResultDoc> clicked_documents) {
        this.relevant_documents = clicked_documents;
    }

    public void addRelevant_document(ResultDoc relDoc) {
        this.relevant_documents.add(relDoc);
    }

    public Intent getQuery_intent() {
        return query_intent;
    }

    public void setQuery_intent(Intent query_intent) {
        this.query_intent = query_intent;
    }

    public ArrayList<UserQuery> getCover_queries() {
        return cover_queries;
    }

    public void setCover_queries(ArrayList<UserQuery> cover_queries) {
        this.cover_queries = new ArrayList<>(cover_queries);
    }

    public void addCover_query(UserQuery cover_query) {
        this.cover_queries.add(cover_query);
    }

} public class Intent implements TreeNode {

    private TreeNode parent;
    private List<TreeNode> childrens;
    private int level;
    private final History history;

    private final TextTokenizer _tokenizer;

    private double totalQueryLength;
    private double totalQuery;
    private int totalTokens;

    private final String intentName;

    public Intent(String name) {
        history = new History();
        this.childrens = new ArrayList<>();

        this._tokenizer = new TextTokenizer(true, true);
        this.intentName = name;

        totalTokens = 0;
        totalQuery = 0;
        totalQueryLength = 0;
    }

    public String getName() {
        return this.intentName;
    }

    @Override
    public TreeNode getParent() {
        return this.parent;
    }

    @Override
    public void setParent(TreeNode node) {
        this.parent = node;
    }

    public boolean isParent(TreeNode node) {
        Intent intent = (Intent) node.getParent();
        if (intent == null) {
            return false;
        }
        return this.intentName.equals(((Intent) node.getParent()).getName());
    }

    @Override
    public List<TreeNode> getChildrens() {
        return this.childrens;
    }

    @Override
    public void setChildrens(List<TreeNode> childrens) {
        this.childrens = new ArrayList<>(childrens);
    }

    @Override
    public void addChildren(TreeNode children) {
        if (this.childrens != null) {
            this.childrens.add(children);
        } else {
            throw new NullPointerException("children is not initialized");
        }
    }

    @Override
    public void setNodeLevel(int level) {
        this.level = level;
    }

    @Override
    public int getNodeLevel() {
        return level;
    }

    public int getTotalTokenCount() {
        return totalTokens;
    }

    public History getHistory() {
        return history;
    }

    /**
     * Returns average length of all queries submitted by the user. Default
     * value is 3.
     *
     * @return average query length
     */
    public double getAvgQueryLength() {
        if (totalQuery == 0) {
            return 3;
        }
        return totalQueryLength / totalQuery;
    }

    /**
     * Update user profile by the user submitted query.
     *
     * @param queryText
     */
    public void updateUsingSubmittedQuery(String queryText) {
        List<String> qParts = _tokenizer.TokenizeText(queryText);
        totalQuery++;
        totalQueryLength = totalQueryLength + qParts.size();
        for (String qPart : qParts) {
            if (qPart.isEmpty()) {
                continue;
            }
            totalTokens++;
            history.addElementInQueryTerms(qPart, 1);
        }
    }

    public HashMap<String, Integer> getRecord(String text, boolean fromDoc) {
        List<String> tokens = _tokenizer.TokenizeText(text);
        HashMap<String, Integer> record = new HashMap<>();
        if (fromDoc) {
            /* To update user profile, select the top k tokens using tf-idf weight */
            int k = (int) (tokens.size() * 0.25);
            HashMap<String, Integer> retVal = selectTopKtokens(tokens, k);
            for (Map.Entry<String, Integer> entry : retVal.entrySet()) {
                if (record.containsKey(entry.getKey())) {
                    record.put(entry.getKey(), record.get(entry.getKey()) + entry.getValue());
                } else {
                    record.put(entry.getKey(), entry.getValue());
//                    record.put(entry.getKey(), 1);
                }
            }
        } else {
            for (String token : tokens) {
                if (token.isEmpty()) {
                    continue;
                }
                if (record.containsKey(token)) {
                    record.put(token, record.get(token) + 1);
                } else {
                    record.put(token, 1);
                }
            }
        }
        return record;
    }

    /**
     * Update user profile by the content of the user clicked document.
     *
     * @param content
     */
    public void updateUsingClickedDoc(String content) {
        List<String> tokens = _tokenizer.TokenizeText(content);
        /* To update user profile, select the top k tokens using tf-idf weight */
        int k = (int) (tokens.size() * 0.25);
        HashMap<String, Integer> retVal = selectTopKtokens(tokens, k);
        for (Map.Entry<String, Integer> entry : retVal.entrySet()) {
            // totalTokens += entry.getValue();
            // history.addElementInDocTerms(entry.getKey(), entry.getValue());
            history.addElementInDocTerms(entry.getKey(), 1);
            totalTokens++;
        }
    }

    /**
     * Method that returns the top k tokens from a list of tokens. Tokens are
     * ranked based on their tf-idf value.
     *
     * @param tokenList list of tokens
     * @param k return only the top k elements
     * @return top k tokens with their term frequency
     */
    private HashMap<String, Integer> selectTopKtokens(List<String> tokenList, int k) {
        HashMap<String, Integer> retValue = new HashMap<>();
        HashMap<String, Integer> tempMap = new HashMap<>();
        /* Stores tf-idf weight of all tokens */
        HashMap<String, Float> unsortedMap = new HashMap<>();
        for (String token : tokenList) {
            Integer n = tempMap.get(token);
            n = (n == null) ? 1 : ++n;
            tempMap.put(token, n);
        }
        for (Map.Entry<String, Integer> entry : tempMap.entrySet()) {
            Double idf = StaticData.IDFRecord.get(entry.getKey());
            if (idf == null) {
                idf = 0.0;
            }
            double tfIdfWeight = entry.getValue() * idf;
            unsortedMap.put(entry.getKey(), (float) tfIdfWeight);
        }
        Map<String, Float> temp = SortMap.sortMapByValue(unsortedMap, false, k);
        for (Map.Entry<String, Float> entry : temp.entrySet()) {
            retValue.put(entry.getKey(), tempMap.get(entry.getKey()));
        }
        return retValue;
    }

} public class Profile implements Tree {

    private final String userId;
    private HashMap<String, TreeNode> intents;
    private final ArrayList<UserQuery> submittedQueries;
    private int totalTokenCount;
    private final TreeNode root;

    private final ArrayList<Session> sessions;
    private final ArrayList<Task> in_session_tasks;

    public Profile(String id) {
        this.submittedQueries = new ArrayList<>();
        this.userId = id;
        this.intents = new HashMap<>();
        this.sessions = new ArrayList<>();
        this.in_session_tasks = new ArrayList<>();
        this.root = new Intent("Top");
        this.root.setNodeLevel(0);
        this.root.setParent(null);
    }

    public boolean isEmpty() {
        return submittedQueries.isEmpty();
    }

    public ArrayList<UserQuery> getSubmittedQueries() {
        return submittedQueries;
    }

    public UserQuery getLastSubmittedQuery() {
        if (submittedQueries.isEmpty()) {
            return null;
        }
        return submittedQueries.get(submittedQueries.size() - 1);
    }

    public UserQuery getQuery(int index) {
        if (index < submittedQueries.size()) {
            return submittedQueries.get(index);
        } else {
            return null;
        }
    }

    public boolean addQuery(UserQuery query) {
        this.submittedQueries.add(query);
        Intent query_intent = (Intent) intents.get(query.getQuery_intent().getName());
        if (query_intent == null) {
            System.err.println("Failed to update user profile!");
            return false;
        } else {
            query_intent.updateUsingSubmittedQuery(query.getQuery_text());
            for (ResultDoc doc : query.getRelevant_documents()) {
                if (doc.isClicked()) {
                    query_intent.updateUsingClickedDoc(doc.getContent());
                }
            }
            return true;
        }
    }

    public Intent addIntent(Intent intent) {
        if (!intentExists(intent.getName())) {
            String[] nodes = intent.getName().split("/");
            String temp = nodes[0];
            TreeNode parent = root;
            for (int i = 1; i < nodes.length; i++) {
                if (i == nodes.length - 1) {
                    intent.setParent(parent);
                    intent.setNodeLevel(parent.getNodeLevel() + 1);
                    parent.addChildren(intent);
                    intents.put(intent.getName(), intent);
                } else {
                    temp += "/" + nodes[i];
                    TreeNode node = new Intent(temp);
                    if (!intentExists(temp)) {
                        node.setParent(parent);
                        node.setNodeLevel(parent.getNodeLevel() + 1);
                        parent.addChildren(node);
                        intents.put(temp, node);
                    }
                    parent = node;
                }
            }
            return intent;
        } else {
            return (Intent) intents.get(intent.getName());
        }
    }

    public boolean intentExists(String intent_name) {
        return intents.containsKey(intent_name);
    }

    @Override
    public HashMap<String, TreeNode> getNodeMap() {
        return this.intents;
    }

    @Override
    public void addNode(String nodePath, TreeNode node) {
        this.intents.put(nodePath, node);
    }

    @Override
    public void setNodes(HashMap<String, TreeNode> nodeMap) {
        this.intents = nodeMap;
    }

    public String getUserId() {
        return userId;
    }

    public int getTotalTokenCount() {
        return totalTokenCount;
    }

    public HashMap<String, TreeNode> getIntents() {
        return intents;
    }

    public TreeNode getRoot() {
        return root;
    }

    public ArrayList<Session> getSessions() {
        return sessions;
    }

    public Session getLastSession() {
        if (sessions.isEmpty()) {
            return null;
        }
        return this.sessions.get(sessions.size() - 1);
    }

    public void addSession(Session sess) {
        this.sessions.add(sess);
    }

    public ArrayList<Task> getIn_session_tasks() {
        return in_session_tasks;
    }

    public Task getLastInSessionTask() {
        return this.in_session_tasks.get(in_session_tasks.size() - 1);
    }

    public void addInSessionTask(Task task) {
        this.in_session_tasks.add(task);
    }

    public HashMap<String, Integer> getCompleteHistory() {
        HashMap<String, Integer> completeHistory = new HashMap<>();
        totalTokenCount = 0;
        for (String key : intents.keySet()) {
            TreeNode node = intents.get(key);
            for (Map.Entry<String, Integer> entry : ((Intent) node).getHistory().getSelectedQueryTerms().entrySet()) {
                if (completeHistory.containsKey(entry.getKey())) {
                    completeHistory.put(entry.getKey(), completeHistory.get(entry.getKey()) + entry.getValue());
                } else {
                    completeHistory.put(entry.getKey(), entry.getValue());
                }
                totalTokenCount += entry.getValue();
            }
            for (Map.Entry<String, Integer> entry : ((Intent) node).getHistory().getSelectedDocTerms().entrySet()) {
                if (completeHistory.containsKey(entry.getKey())) {
                    completeHistory.put(entry.getKey(), completeHistory.get(entry.getKey()) + entry.getValue());
                } else {
                    completeHistory.put(entry.getKey(), entry.getValue());
                }
                totalTokenCount += entry.getValue();
            }
        }
        return completeHistory;
    }

    public HashMap<String, Integer> getBranchHistory(Intent intent) {
        HashMap<String, Integer> branchHistory = new HashMap<>();
        Intent target_intent = (Intent) intents.get(intent.getName());
        totalTokenCount = 0;
        while (target_intent != null) {
            for (Map.Entry<String, Integer> entry : target_intent.getHistory().getSelectedQueryTerms().entrySet()) {
                if (branchHistory.containsKey(entry.getKey())) {
                    branchHistory.put(entry.getKey(), branchHistory.get(entry.getKey()) + entry.getValue());
                } else {
                    branchHistory.put(entry.getKey(), entry.getValue());
                }
                totalTokenCount += entry.getValue();
            }
            for (Map.Entry<String, Integer> entry : target_intent.getHistory().getSelectedDocTerms().entrySet()) {
                if (branchHistory.containsKey(entry.getKey())) {
                    branchHistory.put(entry.getKey(), branchHistory.get(entry.getKey()) + entry.getValue());
                } else {
                    branchHistory.put(entry.getKey(), entry.getValue());
                }
                totalTokenCount += entry.getValue();
            }
            target_intent = (Intent) target_intent.getParent();
        }
        return branchHistory;
    }

    public HashMap<String, Integer> getSessionHistory(Intent intent) {
        HashMap<String, Integer> sessionHistory = new HashMap<>();
        Session currentSession = sessions.get(sessions.size() - 1);
        for (UserQuery query : currentSession.getUser_queries()) {
            for (Map.Entry<String, Integer> entry : intent.getRecord(query.getQuery_text(), false).entrySet()) {
                if (sessionHistory.containsKey(entry.getKey())) {
                    sessionHistory.put(entry.getKey(), sessionHistory.get(entry.getKey()) + entry.getValue());
                } else {
                    sessionHistory.put(entry.getKey(), entry.getValue());
                }
            }
            for (ResultDoc doc : query.getRelevant_documents()) {
                if (doc.isClicked()) {
                    for (Map.Entry<String, Integer> entry : intent.getRecord(doc.getContent(), true).entrySet()) {
                        if (sessionHistory.containsKey(entry.getKey())) {
                            sessionHistory.put(entry.getKey(), sessionHistory.get(entry.getKey()) + entry.getValue());
                        } else {
                            sessionHistory.put(entry.getKey(), entry.getValue());
                        }
                    }
                }
            }
        }
        return sessionHistory;
    }

    /**
     * Computes KL-Divergence between two different user profiles.
     *
     * @param comparedTo
     * @return KL-Divergence value
     */
    public float calculateKLDivergence(Profile comparedTo) {
        float klDiv = 0;
        float lambda = 0.1f;
        HashMap<String, Integer> thisProfile = getCompleteHistory();
        HashMap<String, Integer> profileCompared = comparedTo.getCompleteHistory();

        HashSet<String> keySet = new HashSet<>();
        keySet.addAll(thisProfile.keySet());
        keySet.addAll(profileCompared.keySet());

        for (String name : keySet) {
            Integer value = profileCompared.get(name);
            if (value == null) {
                value = 0;
            }
            Double tokenProb = (value * 1.0) / comparedTo.getTotalTokenCount();
            Double refProb = StaticData.SmoothingReference.get(name);
            if (refProb == null) {
                refProb = 0.0;
            }
            Double smoothedTokenProb = (1 - lambda) * tokenProb + lambda * refProb;
            Double p1 = smoothedTokenProb;

            Integer value2 = thisProfile.get(name);
            if (value2 == null) {
                value2 = 0;
            }
            Double tokenProb2 = (value2 * 1.0) / getTotalTokenCount();
            Double refProb2 = refProb;

            Double smoothedTokenProb2 = (1 - lambda) * tokenProb2 + lambda * refProb2;
            Double p2 = smoothedTokenProb2;
            if (p1 == 0) {
                continue;
            }
            if (p2 == 0) {
                continue;
            }
            klDiv = (float) (klDiv + p1 * Math.log(p1 / p2));
        }
        return klDiv;
    }

} public class Converter {

    public static Date convertStringToDate(String time) {
        SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date = null;
        try {
            date = formatter.parse(time);
        } catch (ParseException ex) {
            Logger.getLogger(Converter.class.getName()).log(Level.SEVERE, null, ex);
        }
        return date;
    }

    public static String convertStringToDate(Date time) {
        SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date = formatter.format(time);
        return date;
    }

    public static ResultDoc convertToResultDoc(ScoreDoc scoreDoc, IndexSearcher indexSearcher, String field) {
        ResultDoc rdoc = null;
        try {
            Document doc = indexSearcher.doc(scoreDoc.doc);
            rdoc = new ResultDoc(scoreDoc.doc);
            rdoc.setTitle("" + (scoreDoc.doc + 1));
            rdoc.setBM25Score(scoreDoc.score);
            String contents = doc.getField(field).stringValue();
            String clicked_url = doc.getField("clicked_url").stringValue();
            rdoc.setContent(contents);
            rdoc.setUrl(clicked_url);
        } catch (IOException ex) {
            Logger.getLogger(Converter.class.getName()).log(Level.SEVERE, null, ex);
        }
        return rdoc;
    }

    public static ResultDoc[] convertToResultDoc(ScoreDoc[] docs, IndexSearcher indexSearcher, String field) {
        ResultDoc resultDocs[] = new ResultDoc[docs.length];
        for (int i = 0; i < docs.length; i++) {
            resultDocs[i] = convertToResultDoc(docs[i], indexSearcher, field);
        }
        return resultDocs;
    }
}
import edu.virginia.cs.extra.ODPCategoryReader;
import edu.virginia.cs.extra.Helper;
import edu.virginia.cs.config.DeploymentConfig;
import edu.virginia.cs.config.RunTimeConfig;
import edu.virginia.cs.engine.OkapiBM25;
import edu.virginia.cs.engine.Searcher;
import edu.virginia.cs.model.ClassifyIntent;
import edu.virginia.cs.model.GenerateCoverQuery;
import edu.virginia.cs.model.TopicTree;
import edu.virginia.cs.model.TopicTreeNode;
import edu.virginia.cs.object.ResultDoc;
import edu.virginia.cs.object.Session;
import edu.virginia.cs.object.UserQuery;
import edu.virginia.cs.user.Intent;
import edu.virginia.cs.user.Profile;
import edu.virginia.cs.utility.Converter;
import java.io.IOException;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileReader;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.io.FileWriter;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;
import org.xml.sax.SAXException;
package edu.virginia.cs.main;




public class Evaluate {

    private final Searcher _searcher;
    /* Storing a specific user's queries and corresponding all clicked documents */
    private List<UserQuery> userQueries;
    /* Storing a specific user's all queries */
    private ArrayList<String> listOfUserQuery;
    /* Storing a specific user's all queries */
    private ArrayList<String> listOfCoverQuery;
    /* Object for intent classification of the user query */
    private final ClassifyIntent classifyIntent;
    /* Object to generate cover queries for a specific user query */
    private final GenerateCoverQuery gCoverQuery;
    /* User profile which is constructed and maintained in the client side */
    private Profile profile;
    /* Total MAP for 'n' users that we are evaluating, ex. in our case, n = 1000 */
    private double totalMAP = 0.0;
    /* Total number of queries evaluated for 'n' users, ex. in our case, n = 1000 */
    private double totalQueries = 0.0;
    /* Total KL-Divergence for 'n' users that we are evaluating, ex. in our case, n = 1000 */
    private double totalKL = 0;
    /* Total mutual information for 'n' users that we are evaluating, ex. in our case, n = 1000 */
    private double totalNMI = 0;
    /* Total goodness of alignment score for 'n' users that we are evaluating, ex. in our case, n = 1000 */
    private double totalMet1 = 0;
    private double totalMet2 = 0;
    private double totalMet3 = 0;

    private final NMICalculation computeNMI;
    private final cIndex metric1;
    private final tIndex_v1 metric2;
    private final tIndex_v2 metric3;

    public Evaluate() {
        this._searcher = new Searcher(DeploymentConfig.AolIndexPath);
        this._searcher.setSimilarity(new OkapiBM25());
        // setting the flag to enable personalization
        this._searcher.activatePersonalization(true);
        TopicTree tree = createTopicTree(4);
        if (tree == null) {
            System.err.println("Failed to load ODP category hierarchy");
            System.exit(1);
        }
        this.gCoverQuery = new GenerateCoverQuery(tree);
        this.classifyIntent = new ClassifyIntent();
        this.computeNMI = new NMICalculation(DeploymentConfig.AolIndexPath);
        this.metric1 = new cIndex(RunTimeConfig.IntervalInHours);
        this.metric2 = new tIndex_v1(RunTimeConfig.IntervalInHours);
        this.metric3 = new tIndex_v2(RunTimeConfig.IntervalInHours);
    }

    /**
     * Loads language models up to level 'param' from all language models of
     * DMOZ categories.
     *
     * @param filename
     * @param depth depth of the hierarchy
     * @return list of language models
     */
    private TopicTree createTopicTree(int depth) {
        TopicTree topicTree = null;
        try {
            SAXParserFactory factory = SAXParserFactory.newInstance();
            SAXParser saxParser = factory.newSAXParser();

            ArrayList<String> topics = null;
            try {
                FileInputStream fis = new FileInputStream(DeploymentConfig.OdpHierarchyRecord);
                ODPCategoryReader odpCatReader = new ODPCategoryReader(depth);
                saxParser.parse(fis, odpCatReader);
                topics = odpCatReader.getTopics();
            } catch (SAXException | IOException ex) {
                Logger.getLogger(MultiThread.class.getName()).log(Level.SEVERE, null, ex);
            }

            if (topics == null) {
                return topicTree;
            }

            topicTree = new TopicTree();
            int node_id = 0;

            for (String currentTopic : topics) {
                String[] split = currentTopic.split("/");
                int level = split.length - 1;

                TopicTreeNode node = new TopicTreeNode(currentTopic, node_id);
                node.setNodeLevel(level);

                if (split.length >= 2) {
                    String parent = currentTopic.substring(0, currentTopic.lastIndexOf("/"));
                    if (topicTree.exists(parent)) {
                        node.setParent(topicTree.getTreeNode(parent));
                        topicTree.getTreeNode(parent).addChildren(node);
                    } else {
                        System.err.println("Problem while loading ODP topic hierarchy...");
                        System.exit(1);
                    }
                } else {
                    node.setParent(null);
                }

                topicTree.addNode(currentTopic, node);
                node_id++;
            }

        } catch (ParserConfigurationException | SAXException ex) {
            Logger.getLogger(MultiThread.class.getName()).log(Level.SEVERE, null, ex);
        }
        return topicTree;
    }

    /**
     * Main method that executes the entire pipeline.
     *
     * @param allUserId
     * @param threadId
     * @return
     * @throws java.lang.Throwable
     */
    public String startEvaluation(ArrayList<String> allUserId, String threadId) throws Throwable {
        int countUsers = 0;
        FileWriter writer = new FileWriter(DeploymentConfig.OutDirectory + threadId + ".txt");
        for (String userId : allUserId) {
            countUsers++;
            // initializing user profile of the server side and setting the reference model
            _searcher.initializeUserProfile(userId);

            // required for calculating mutual information between user queris and cover queries
            listOfUserQuery = new ArrayList<>();
            listOfCoverQuery = new ArrayList<>();

            // generate the clicked urls for evaluation
            loadUserJudgements(userId);
            // initialization for client side user profile
            profile = new Profile(userId);

            double meanAvgPrec = 0.0;
            // Number of queries evaluated
            int numQueries = 0;

            /**
             * query contains query plus the timestamp when the query was
             * submitted.
             */
            for (UserQuery query : userQueries) {
                /**
                 * If a user query has at least one corresponding clicked
                 * document, then we evaluate it, otherwise not.
                 *
                 */
                if (!query.getRelevant_documents().isEmpty()) {
                    UserQuery lastSubmittedQuery = profile.getLastSubmittedQuery();
                    boolean isSame = false;
                    if (lastSubmittedQuery != null) {
                        isSame = Helper.checkSameSession(lastSubmittedQuery, query);
                    }

                    // current query and previous query (if any) are from different session
                    if (!isSame) {
                        if (lastSubmittedQuery != null) {
                            // set end time of previous session
                            profile.getLastSession().setEnd_time(lastSubmittedQuery.getQuery_time());
                        }
                        // start of a new user session
                        Session session = new Session(profile.getSessions().size());