NDCG

    //Relevance scores
    HashMap<String, Double> doc_relevance_scores = new HashMap<>();
    Integer even_odd = 0;

    /** Constructor */
    public Searcher(Index index, KGramIndex kgIndex)
    {
        this.index = index;
        this.kgIndex = kgIndex;
        hits_ranker = new HITSRanker(file_path_linksDavis, file_path_davisTitles, index);
    }

    private double log2(double x)
    {
        return (Math.log(x) / Math.log(2));
    }

    public void Caluclate_NDCG(PostingsList query_postings_list)
    {
        //DCG
        double dcg = 0.0;
        ArrayList<Double> dcg_arr = new ArrayList<>();
        System.err.println("");
        for(int a = 1; a <= 50; a++)
        {
            int query_doc_id = query_postings_list.get(a - 1).docID;
            String query_doc_name = getFileName(Index.docNames.get(query_doc_id));
            //if(query_doc_name.equals("Mathematics.f") && even_odd % 2 == 0) continue;
            if(doc_relevance_scores.containsKey(query_doc_name))
            {
                double rel_score = doc_relevance_scores.get(query_doc_name);
                double dcgp = rel_score / log2(a + 1);
                dcg_arr.add(dcgp);
                dcg += dcgp;
            }
            else
            {
                System.err.println("Key not found: " + query_doc_name);
            }
        }
        System.err.println("");
        System.err.println("\n" + "dcg: " + Double.toString(dcg));

        //IDCG
        double idcg = 0.0;
        ArrayList<Double> idcg_arr = new ArrayList<>();
        Collection<Double> temp = docs_and_scores.values();
        ArrayList<Double> sorted_relevance_scores = new ArrayList<>(temp);
        Collections.sort(sorted_relevance_scores, Collections.reverseOrder());
        for(int a = 1; a <= 50; a++)
        {
            double rel_score = sorted_relevance_scores.get(a);
            double idcgp = rel_score / log2(a + 1);
            idcg_arr.add(idcgp);
            idcg += idcgp;
        }
        System.err.println("idcg: " + Double.toString(idcg));

        //NDCG
        double ndcg = 0.0;
        for(int a = 0; a < 50; a++)
        {
            ndcg += dcg_arr.get(a) / idcg_arr.get(a);
        }
        System.err.println("ndcg: " + Double.toString(ndcg));
        System.err.println("even_odd: " + Integer.toString(even_odd) + "\n");
        //even_odd = (even_odd + 1) % 2;
    }

    public void Load_Relevance_Scores()
    {
        try {
            File file = new File("./ir/average_relevance.txt");
            FileReader fileReader = new FileReader(file);
            BufferedReader bufferedReader = new BufferedReader(fileReader);
            String readLine = "-1";
            while((readLine = bufferedReader.readLine()) != null)
            {
                String[] doc_score = readLine.split(" ");
                String doc_name = doc_score[0];
                double relevance_score = Integer.parseInt(doc_score[1]);
                doc_relevance_scores.put(doc_name, relevance_score);
            }
            bufferedReader.close();
            fileReader.close();
        } catch(Exception e){
            e.printStackTrace();
        }
    }

    /**
     *  Searches the index for postings matching the query.
     *  @return A postings list representing the result of the query.
     */
    public PostingsList search(Query query, QueryType queryType, RankingType rankingType, NormalizationType normType)
    {
        if (query.queryterm == null) return null;
        else if(query.queryterm.size() == 0) return null;
        else if(queryType == QueryType.INTERSECTION_QUERY) return IntersectionAlgorithm(query);
        else if(queryType == QueryType.PHRASE_QUERY) return PhraseAlgorithm(query);
        else if(queryType == QueryType.RANKED_QUERY)
        {
            if(rankingType == RankingType.TF_IDF)
            {
                PostingsList postings_list = TF_IDF_Algorithm(query, false, normType);
                boolean ndcg = true;
                if(ndcg == true) Caluclate_NDCG(postings_list);
                return postings_list;
            }
            else if(rankingType == RankingType.PAGERANK) return PAGERANK_Algorithm(query, false);
            else if(rankingType == RankingType.COMBINATION) return COMBINATION_Algorithm(query, normType);
            else if(rankingType == RankingType.HITSRANKER) return HITSRanker_Algorithm(query);
            else return null;
        }
        else return null;
    }