Statistics.hpp

#ifndef STATISTICS_HPP
#define STATISTICS_HPP
#include <iostream>
#include <vector>
#include <string>
#include "MetroGraph.hpp" 

struct BSTNode {
    int station_id; // 站点ID (用来存是谁)
    int frequency;  // 查询频次 (用来排序: 左小右大)
    BSTNode *left;
    BSTNode *right;

    BSTNode(int id, int freq) 
        : station_id(id), frequency(freq), left(nullptr), right(nullptr) {}
};
class Statistics {
private:
    BSTNode* root;
    std::vector<int> current_freq; 
    BSTNode* insert(BSTNode* node, int id, int freq) {
        if (node == nullptr) {
            return new BSTNode(id, freq);
        }
        bool go_left = false;
        if (freq < node->frequency) {
            go_left = true;
        } else if (freq == node->frequency) {
            if (id < node->station_id) go_left = true;
            else go_left = false;
        } else {
            go_left = false;
        }

        if (go_left) {
            node->left = insert(node->left, id, freq);
        } else {
            node->right = insert(node->right, id, freq);
        }
        return node;
    }

    BSTNode* findMin(BSTNode* node) {
        while (node->left != nullptr) node = node->left;
        return node;
    }

    BSTNode* remove(BSTNode* node, int id, int freq) {
        if (node == nullptr) return nullptr;

        // 1. 先定位节点位置 (逻辑同插入)
        bool go_left = false;
        if (freq < node->frequency) go_left = true;
        else if (freq == node->frequency && id < node->station_id) go_left = true;
        else go_left = false;

        // 如果找到了目标节点 (频次和ID都对上了)
        if (node->frequency == freq && node->station_id == id) {
            // 情况A: 没有子节点 或 只有一个子节点
            if (node->left == nullptr) {
                BSTNode* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                BSTNode* temp = node->left;
                delete node;
                return temp;
            }
            
            // 情况B: 有两个子节点
            // 策略：用右子树里的最小节点(后继)替换当前节点
            BSTNode* temp = findMin(node->right);
            
            // 复制数据
            node->station_id = temp->station_id;
            node->frequency = temp->frequency;
            
            // 删掉那个被复制的替身节点
            node->right = remove(node->right, temp->station_id, temp->frequency);
        } 
        // 没找到，继续递归找
        else if (go_left) {
            node->left = remove(node->left, id, freq);
        } else {
            node->right = remove(node->right, id, freq);
        }
        
        return node;
    }

    // ------------------------------------------------
    // 私有辅助函数：反向中序遍历 (获取 Top-K)
    // 顺序：右子树 -> 根 -> 左子树 (从大到小)
    // ------------------------------------------------
    void reverse_inorder(BSTNode* node, int& k, MetroGraph* g) {
        if (node == nullptr || k <= 0) return;

        // 1. 先访问大的 (右边)
        reverse_inorder(node->right, k, g);

        // 2. 访问根 (打印)
        if (k > 0) {
            std::cout << "   - " << g->GetName(node->station_id) 
                      << " (查询 " << node->frequency << " 次)\n";
            k--; // 计数器减一
        }

        // 3. 再访问小的 (左边)
        reverse_inorder(node->left, k, g);
    }

public:
    Statistics() : root(nullptr) {}

    // 初始化：根据站点总数分配数组大小
    void Init(int total_stations) {
        current_freq.assign(total_stations + 10, 0); // 多给点空间防止越界
    }

    // 核心功能：更新某个站点的热度
    void Update(int station_id) {
        if (station_id < 0 || station_id >= current_freq.size()) return;

        int old_freq = current_freq[station_id];

        // 1. 如果它以前被查过 (在树里)，先把它删掉
        if (old_freq > 0) {
            root = remove(root, station_id, old_freq);
        }

        // 2. 频次 +1
        int new_freq = old_freq + 1;
        current_freq[station_id] = new_freq;

        // 3. 以新频次重新插入树中
        root = insert(root, station_id, new_freq);
    }
    void PrintTopK(int k, MetroGraph* g) {
        std::cout << "\n历史查询频度 Top-" << k << " 排行榜:\n";
        if (root == nullptr) {
            std::cout << "   (暂无查询记录)\n";
        } else {
            // 需要传入 graph 指针是为了把 ID 转成中文站名
            int count = k;
            reverse_inorder(root, count, g);
        }
        std::cout << "--------------------------------\n";
    }
};
#endif