#include <iostream>
#include <vector>

using namespace std;

class BPTree; // 前向声明

// B+树节点类
class Node {
    bool isLeaf; // 标记是否为叶节点
    vector<int> keys; // 存储键
    vector<Node*> children; // 存储子节点指针
    Node* next; // 指向下一个叶节点

    friend class BPTree;

public:
    Node(bool isLeaf) : isLeaf(isLeaf), next(nullptr) {}
};

// B+树类
class BPTree {
    Node* root;
    int t; // 最小度数, 每个节点必须至少有t-1个键

public:
    BPTree(int _t) : root(nullptr), t(_t) {}

    // 插入键到B+树中
    void insert(int key);

    // 搜索键在B+树中
    Node* search(int key);

    // 打印B+树
    void printTree(Node* node, int space);

private:
    // 插入内部
    void insertInternal(int key, Node** cursor, Node* child);

    // 分裂节点
    Node* split(Node* cursor);
};

void BPTree::insert(int key) {
    if (root == nullptr) {
        root = new Node(true);
        root->keys.push_back(key);
    } else {
        Node* cursor = root;
        Node* parent = nullptr;

        while (!cursor->isLeaf) {
            parent = cursor;
            for (int i = 0; i < cursor->keys.size(); i++) {
                if (key < cursor->keys[i]) {
                    cursor = cursor->children[i];
                    break;
                }
                if (i == cursor->keys.size() - 1) {
                    cursor = cursor->children[i+1];
                    break;
                }
            }
        }

        if (cursor->keys.size() < 2 * t - 1) {
            int i = 0;
            while (key > cursor->keys[i] && i < cursor->keys.size()) i++;
            cursor->keys.insert(cursor->keys.begin() + i, key);
        } else {
            // Node splitting
            vector<int> virtualNode(cursor->keys);
            virtualNode.insert(lower_bound(virtualNode.begin(), virtualNode.end(), key), key);
            int median = virtualNode[t];

            Node* newLeaf = new Node(true);
            Node* temp = cursor->next;
            cursor->next = newLeaf;
            newLeaf->next = temp;

            cursor->keys.resize(t);
            newLeaf->keys.assign(virtualNode.begin() + t, virtualNode.end());

            if (parent == nullptr) {
                Node* newRoot = new Node(false);
                newRoot->keys.push_back(median);
                newRoot->children.push_back(cursor);
                newRoot->children.push_back(newLeaf);
                root = newRoot;
            } else {
                insertInternal(median, &parent, newLeaf);
            }
        }
    }
}

void BPTree::insertInternal(int key, Node** cursor, Node* child) {
    if ((*cursor)->keys.size() < 2 * t - 1) {
        int i = 0;
        while (key > (*cursor)->keys[i] && i < (*cursor)->keys.size()) i++;
        (*cursor)->keys.insert((*cursor)->keys.begin() + i, key);
        (*cursor)->children.insert((*cursor)->children.begin() + i + 1, child);
    } else {
        vector<int> virtualKey((*cursor)->keys);
        vector<Node*> virtualChildren((*cursor)->children);
        
        int pos = lower_bound(virtualKey.begin(), virtualKey.end(), key) - virtualKey.begin();
        virtualKey.insert(virtualKey.begin() + pos, key);
        virtualChildren.insert(virtualChildren.begin() + pos + 1, child);

        int medianIdx = t - 1;
        Node* newInternal = new Node(false);
        newInternal->keys.assign(virtualKey.begin() + medianIdx + 1, virtualKey.end());
        newInternal->children.assign(virtualChildren.begin() + medianIdx + 1, virtualChildren.end());

        (*cursor)->keys.resize(medianIdx);
        (*cursor)->children.resize(medianIdx + 1);

        if ((*cursor) == root) {
            Node* newRoot = new Node(false);
            newRoot->keys.push_back(virtualKey[medianIdx]);
            newRoot->children.push_back(*cursor);
            newRoot->children.push_back(newInternal);
            root = newRoot;
        } else {
            insertInternal(virtualKey[medianIdx], cursor, newInternal);
        }
    }
}

Node* BPTree::search(int key) {
    Node* cursor = root;
    while (cursor != nullptr && !cursor->isLeaf) {
        int i = 0;
        while (i < cursor->keys.size() && key > cursor->keys[i]) i++;
        cursor = cursor->children[i];
    }

    if (cursor != nullptr) {
        for (int i = 0; i < cursor->keys.size(); i++) {
            if (cursor->keys[i] == key) {
                return cursor;
            }
        }
    }
    return nullptr; // key not found
}

void BPTree::printTree(Node* node, int space) {
    if (node == nullptr) return;
    space += 10;
    for (int i = node->keys.size(); i >= 0; i--) {
        if (!node->isLeaf && i < node->keys.size())
            printTree(node->children[i + 1], space);
        if (i < node->keys.size())
            cout << setw(space) << node->keys[i] << "\n";
    }
    if (!node->isLeaf)
        printTree(node->children[0], space);
}

int main() {
    BPTree tree(3);  // 创建一个最小度数为3的B+树

    // 插入键值
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(6);
    tree.insert(12);
    tree.insert(30);
    tree.insert(7);
    tree.insert(17);

    // 打印树
    cout << "B+树结构:\n";
    tree.printTree(tree.root, 0);

    // 搜索键值
    if (tree.search(6)) {
        cout << "找到键6\n";
    } else {
        cout << "键6未找到\n";
    }

    return 0;
}