//
// Created by 罗炳国 on 2023/11/24.
//

#ifndef PFJ_CODE032_TOPK_H
#define PFJ_CODE032_TOPK_H
#include "commonHeader.h"

// topK问题

/**
 * Top K Frequent Words II
 * Implement three methods for Topk Class:
 * TopK(k). The constructor.
 * add(word). Add a new word.
 * topk(). Get the current top k frequent words.
 * LintCode题目：https://www.lintcode.com/problem/550/
 * */


class code032_topK {
public:
    code032_topK(int K) {
        this->k = K;
    }



    void add(string &str) {
        auto iter = strNodeMap.find(str);
        if (iter == strNodeMap.end()) {
            strNodeMap[str] = new Node(str, 1);
        }
    }

    vector<string> topK() {
        vector<string> ans;

        return ans;
    }

private:
    struct Node {
        string str;
        int times;
        Node(string &str, int times) : str(str), times(times) {
        }
    };

    struct dataCmp {
        bool operator() (const struct Node * &a, const struct Node *&b) {
            if (a->times > b->times)
                return true;
            if (a->times == b->times)
                return a->str.compare(b->str) < 0;
            return false;
        }
    };

    struct dataCmp1 {
        bool operator() (const struct Node &a, const struct Node &b) {
            if (a.times > b.times)
                return true;
            if (a.times == b.times)
                return a.str.compare(b.str) < 0;
            return false;
        }
    };

    bool dataItemCmp(struct Node *a, struct Node *b) {
        if (a->times > b->times)
            return true;
        if (a->times == b->times)
            return a->str.compare(b->str) < 0;
        return false;
    }
private:
    // 堆使用，记录节点与索引下标
    unordered_map<struct Node *, int> nodeIndex;
    // 优化项，记录当前位于堆中的节点
    set<struct Node , struct dataCmp1> treeSet;
    // 记录 string与内部的节点之间的关系，利用这个关系更新词频
    unordered_map<string, struct Node *> strNodeMap;
    // 初始化即固定的参数K
    int k;

};

void topKtest() {
    class code032_topK tk(2);
    vector<string> strs {"a", "b", "fd", "fd", "gh", "jk", "gh", "jk", "jk", "gh"};
    vector<string> ans;
    for (auto &str : strs) {
        tk.add(str);
        ans = tk.topK();
        vecShow(ans);
    }
}



#endif//PFJ_CODE032_TOPK_H