database.hpp

#ifndef DATABASE
#define DATABASE

#include <exception>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <fstream>
#include "linked_hash_map.hpp"
#include "utility.hpp"
#include "vector.hpp"

template<class keys,class T>
class database
{
private:
    class data{
    public:
        keys key;
        T value;
        data(){}
        data(const keys &obj,const T &value_){
            key=obj;
            value=value_;
        }
        friend bool operator < (const data &obj1,const data &obj2){
            if(obj1.key<obj2.key)return true;
            if(obj1.key == obj2.key && obj1.value < obj2.value)return true;
            return false;
        }
        friend bool operator > (const data &obj1,const data &obj2){
            return obj2<obj1;
        }
        friend bool operator == (const data &obj1,const data &obj2){
            return (!(obj1<obj2))&&(!(obj2<obj1));
        }
        friend bool operator >= (const data &obj1,const data &obj2){
            return !(obj1<obj2);
        }
        friend bool operator <= (const data &obj1,const data &obj2){
            return !(obj2<obj1);
        }
    };
    static const int size_of_block=20;
    class start
    {
    public:
        int pos_of_root;
        int num_of_block;
        start(){
            pos_of_root=1;
            num_of_block=1;
        }
        start(int pos_of_root_,int num_of_block_)
            :pos_of_root(pos_of_root_),num_of_block(num_of_block_){}
    };
    enum nodetype{index,leaf};
    class node
    {
    public:
        nodetype type;
        int pos_of_fa;
        int now_num;
        int edge[size_of_block+1];
        data value[size_of_block];
        int front_pos,back_pos;
        node(){
            type=leaf;
            now_num=0;
            pos_of_fa=0;
            front_pos=0;
            back_pos=0;
            memset(edge,0,sizeof(edge));
        }
    };
    class LinkedHashMap {
    public:
        //LinkedHashMap节点定义
        struct Node {
            int key;
            node* value;
            Node* prev;
            Node* next;

            Node()
                : prev(nullptr), next(nullptr) {}

            Node(const int& k, const node*& v)
                : key(k), value(v), prev(nullptr), next(nullptr) {}
        };
        // 哈希表节点定义
        struct Nodes {
            int key;
            Node* value;
            Nodes* next;

            Nodes(const int& k,Node* v)
                : key(k), value(v), next(nullptr) {}
        };
        class MyUnorderedMap {
        public:
            // 构造函数
            const static size_t TableSize=2048;
            MyUnorderedMap() {
                table = new Nodes*[TableSize]();
            }
            // 析构函数
            ~MyUnorderedMap() {
                clear();
                delete[] table;
            }

            // 插入键值对
            void insert(const int& key, const node*& value) {
                int index = hashFunction(key);
                Nodes* newNode = new Nodes(key, value);
                newNode->next = table[index];
                table[index] = newNode;
            }

            // 删除键值对
            void erase(const int& key) {
                int index = hashFunction(key);
                Nodes* currNode = table[index];
                Nodes* prevNode = nullptr;

                while (currNode != nullptr) {
                    if (currNode->key == key) {
                        if (prevNode != nullptr)
                            prevNode->next = currNode->next;
                        else
                            table[index] = currNode->next;

                        delete currNode;
                        break;
                    }

                    prevNode = currNode;
                    currNode = currNode->next;
                }
            }

            // 获取值
            Node*& operator[](const int& key) {
                int index = hashFunction(key);
                Nodes* currNode = table[index];

                while (currNode != nullptr) {
                    if (currNode->key == key)
                        return currNode->value;

                    currNode = currNode->next;
                }

                Nodes* newNode = new Nodes(key,nullptr);
                newNode->next = table[index];
                table[index] = newNode;

                return newNode->value;
            }

            // 判断键是否存在
            bool contains(const int& key) const {
                int index = hashFunction(key);
                Nodes* currNode = table[index];

                while (currNode != nullptr) {
                    if (currNode->key == key)
                        return true;

                    currNode = currNode->next;
                }

                return false;
            }

            // 获取键值对数量
            size_t size() const {
                size_t count = 0;

                for (int i = 0; i < TableSize; i++) {
                    Nodes* currNode = table[i];
                    while (currNode != nullptr) {
                        count++;
                        currNode = currNode->next;
                    }
                }

                return count;
            }

            // 清空哈希表
            void clear() {
                for (int i = 0; i < TableSize; i++) {
                    Nodes* currNode = table[i];
                    while (currNode != nullptr) {
                        Nodes* nextNode = currNode->next;
                        delete currNode;
                        currNode = nextNode;
                    }
                    table[i] = nullptr;
                }
            }


            // 哈希表节点定义
            

            Nodes** table;  // 哈希表数组

            // 哈希函数
            int hashFunction(const int& key) const {
                return std::hash<int>()(key) % TableSize;
            }
        };
        // 构造函数
        LinkedHashMap() {
            head = new Node();
            tail = new Node();
            head->next = tail;
            tail->prev = head;
        }

        // 析构函数
        ~LinkedHashMap() {
            clear();
            delete head;
            delete tail;
        }

        // 插入键值对
        void insert(const int& key, const node*& value) {
            if (map.contains(key)) {
                // 键已存在，更新值并将节点移到链表头部
                Node* node = map[key];
                node->value = value;
                moveToHead(node);
            } else {
                // 键不存在，创建新节点并插入到链表头部
                Node* node = new Node(key, value);
                map[key] = node;
                insertToHead(node);

                // 检查容量是否超出限制
                if (map.size() > capacity) {
                    // 超出限制，移除链表尾部的节点
                    Node* tailNode = removeTail();
                    map.erase(tailNode->key);
                    delete tailNode->value;
                    delete tailNode;
                }
            }
        }

        // 删除键值对
        void erase(const int& key) {
            if (map.contains(key)) {
                Node* node = map[key];
                removeNode(node);
                map.erase(key);
                delete node;
            }
        }

        // 获取值
        node* operator[](const int& key) {//危险，要先contains一下才能用！！！
            Node* node = map[key];
            moveToHead(node);
            return node->value;
        }

        // 判断键是否存在
        bool contains(const int& key) const {
            return map.contains(key);
        }

        // 获取键值对数量
        size_t size() const {
            return map.size();
        }

        // 清空链表和哈希表
        void clear() {
            for (int i = 0; i < map.TableSize; i++) {
                Nodes* currNode = map.table[i];
                while (currNode != nullptr) {
                    Nodes* nextNode = currNode->next;
                    delete currNode->value->value;
                    delete currNode->value;
                    delete currNode;
                    currNode = nextNode;
                }
                map.table[i] = nullptr;
            }
            head->next = tail;
            tail->prev = head;
        }

        // 链表节点定义
        
    private:
        Node* head;  // 链表头节点
        Node* tail;  // 链表尾节点
        MyUnorderedMap map;  // 哈希表，用于快速查找节点
        static const size_t capacity = 2048;  // 容量限制，可以根据需求进行调整

        // 将节点插入到链表头部
        void insertToHead(Node* node) {
            node->next = head->next;
            node->prev = head;
            head->next->prev = node;
            head->next = node;
        }

        // 将节点移动到链表头部
        void moveToHead(Node* node) {
            removeNode(node);
            insertToHead(node);
        }

        // 移除节点
        void removeNode(Node* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }

        // 移除链表尾部的节点
        Node* removeTail() {
            Node* tailNode = tail->prev;
            removeNode(tailNode);
            return tailNode;
        }
    };
    std::fstream opfile;
    start head;
    LinkedHashMap map;
    //int cnt=0;
    void getstart(start &st){
        opfile.seekg(0);
        opfile.read(reinterpret_cast<char*>(&st),sizeof(start));
    }
    void writestart(start &st){
        opfile.seekp(0);
        opfile.write(reinterpret_cast<char*>(&st),sizeof(start));
    }
    void getnode(node *&obj,int num) {
        if(!map.contains(num)){
            node* newNode = new node();
            map.insert(num,newNode);
            opfile.seekg(sizeof(start) + (num-1)*sizeof(node));
            opfile.read(reinterpret_cast<char*>(newNode),sizeof(node));
        }
        obj=map[num];
    }
    void writenode(node &obj,int num){
        opfile.seekp(sizeof(start)+(num-1)*sizeof(node));
        opfile.write(reinterpret_cast<char*>(&obj),sizeof(node));
    }
    int finds(const keys &key,int num){
        node temp;
        getnode(temp,num);
        if(temp.type == leaf)return num;
        int l = 0, r = temp.now_num - 1, mid;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (temp.value[mid].key < key)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return finds(key,temp.edge[r+1]);
    }
    int find_pos(const data &obj,int num){
        node temp;
        getnode(temp,num);
        if(temp.type==leaf)return num;
        else{
            int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,obj)-temp.value;
            //if(temp.edge[t]>head.num_of_block)std::cout<<114514<<std::endl;
            return find_pos(obj,temp.edge[t]);
        }
    }
    void updatefather(int pos,int fa_pos){
        node temp;
        getnode(temp,pos);
        temp.pos_of_fa=fa_pos;
        writenode(temp,pos);
    }
    void updateleft(int pos,int left){
        if(pos==0)return;
        node temp;
        getnode(temp,pos);
        temp.back_pos=left;
        writenode(temp,pos);
    }
    void updateright(int pos,int right){
        if(pos==0)return;
        node temp;
        getnode(temp,pos);
        temp.front_pos=right;
        writenode(temp,right);
    }
    void flashindex(int fa_pos,int son_pos,const data &obj){
        node temp;
        getnode(temp,fa_pos);
        int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,obj)-temp.value;
        for(int i=temp.now_num;i>t;i--){
            temp.value[i]=temp.value[i-1];
            temp.edge[i+1]=temp.edge[i];
        }//proofed
        temp.value[t]=obj;
        temp.edge[t+1]=son_pos;
        temp.now_num++;
        writenode(temp,fa_pos);
        if(temp.now_num==size_of_block){
            node temp2;
            int mid=size_of_block/2;
            temp2.now_num=mid-1;
            for(int i=mid+1;i<size_of_block;i++){
                temp2.value[i-mid-1]=temp.value[i];
                temp2.edge[i-mid-1]=temp.edge[i];
                updatefather(temp.edge[i],head.num_of_block+1);
            }
            temp2.edge[mid-1]=temp.edge[size_of_block];
            updatefather(temp.edge[size_of_block],head.num_of_block+1);
            temp.now_num=mid;
            temp2.type=index;
            if(temp.pos_of_fa==0){
                temp.pos_of_fa=head.num_of_block+2;
                temp2.pos_of_fa=head.num_of_block+2;
                writenode(temp,fa_pos);
                writenode(temp2,head.num_of_block+1);
                head.num_of_block++;
                node temp3;
                temp3.edge[0]=fa_pos;
                temp3.edge[1]=head.num_of_block;
                temp3.value[0]=temp.value[mid];
                temp3.now_num=1;
                temp3.type=index;
                writenode(temp3,head.num_of_block+1);
                head.num_of_block++;
                head.pos_of_root=head.num_of_block;
            }
            else{
                temp2.pos_of_fa=temp.pos_of_fa;
                writenode(temp,fa_pos);
                writenode(temp2,head.num_of_block+1);
                head.num_of_block++;
                flashindex(temp.pos_of_fa,head.num_of_block,temp.value[mid]);
            }
        }
    }
    void devideleaf(int pos){
        node temp1;
        getnode(temp1,pos);
        node temp2;
        temp2.back_pos=pos;
        temp2.front_pos=temp1.front_pos;
        updateleft(temp1.front_pos,head.num_of_block+1);
        temp1.front_pos=head.num_of_block+1;
        for(int i=0;i<size_of_block/2;i++)temp2.value[i]=temp1.value[size_of_block/2+i];
        temp2.now_num=size_of_block/2;
        temp1.now_num=size_of_block/2;
        if(temp1.pos_of_fa==0){
            temp1.pos_of_fa=head.num_of_block+2;
            temp2.pos_of_fa=head.num_of_block+2;
            writenode(temp1,pos);
            writenode(temp2,head.num_of_block+1);
            head.num_of_block++;
            node temp3;
            temp3.now_num=1;
            temp3.edge[0]=pos;
            temp3.edge[1]=head.num_of_block;
            temp3.value[0]=temp2.value[0];
            temp3.type=index;
            writenode(temp3,head.num_of_block+1);
            head.num_of_block++;
            head.pos_of_root=head.num_of_block;
        }
        else{
            temp2.pos_of_fa=temp1.pos_of_fa;
            writenode(temp1,pos);
            writenode(temp2,head.num_of_block+1);
            head.num_of_block++;
            flashindex(temp1.pos_of_fa,head.num_of_block,temp2.value[0]);
        }
    }
    bool judge(int pos,int fa,node& temp){
        if(pos==0)return false;
        getnode(temp,pos);
        if(temp.pos_of_fa!=fa)return false;
        return true;
    }
    void merge(int pos,node &obj1,node &obj2,node &fa,int tx){
        obj1.value[obj1.now_num]=fa.value[tx];
        obj1.now_num++;
        for(int i=0;i<obj2.now_num;i++){
            obj1.value[obj1.now_num+i]=obj2.value[i];
            obj1.edge[obj1.now_num+i]=obj2.edge[i];
            node temp;
            updatefather(obj2.edge[i],pos);
        }
        obj1.now_num+=obj2.now_num;
        obj1.edge[obj1.now_num]=obj2.edge[obj2.now_num];
        updatefather(obj2.edge[obj2.now_num],pos);
    }
    void balanceindex(int pos,data delindex){
        node temp;
        getnode(temp,pos);
        if(pos==head.pos_of_root && temp.now_num==1){
            node son;
            getnode(son,temp.edge[0]);
            son.pos_of_fa=0;
            head.pos_of_root=temp.edge[0];
            writenode(son,temp.edge[0]);
            return;
        }
        int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,delindex)-temp.value;
        for(int i=t-1;i<temp.now_num-1;i++)temp.value[i]=temp.value[i+1];
        for(int i=t;i<temp.now_num;i++)temp.edge[i]=temp.edge[i+1];
        temp.now_num--;
        if(pos==head.pos_of_root){
            writenode(temp,pos);
            return;
        }
        if(temp.now_num<size_of_block/2-1){
            node fa;
            getnode(fa,temp.pos_of_fa);
            int tx=sjtu::upper_bound(fa.value,fa.value+fa.now_num,temp.value[0])-fa.value;
            if(tx!=fa.now_num){
                node rightbro;
                getnode(rightbro,fa.edge[tx+1]);
                if(rightbro.now_num>=size_of_block/2){
                    temp.edge[size_of_block/2-1]=rightbro.edge[0];
                    updatefather(rightbro.edge[0],pos);
                    temp.value[size_of_block/2-2]=fa.value[tx];
                    fa.value[tx]=rightbro.value[0];
                    for(int i=0;i<rightbro.now_num-1;i++){
                        rightbro.value[i]=rightbro.value[i+1];
                        rightbro.edge[i]=rightbro.edge[i+1];
                    }
                    rightbro.edge[rightbro.now_num-1]=rightbro.edge[rightbro.now_num];
                    rightbro.now_num--;
                    temp.now_num++;
                    writenode(temp,pos);
                    writenode(rightbro,fa.edge[tx+1]);
                    writenode(fa,temp.pos_of_fa);
                }
                else{
                    merge(pos,temp,rightbro,fa,tx);
                    writenode(temp,pos);
                    balanceindex(temp.pos_of_fa,fa.value[tx]);
                }
            }
            else{
                node leftbro;
                if(tx==0){
                    std::cout<<"wrong "<<temp.pos_of_fa<<' '<<std::endl;
                    std::cout<<fa.now_num<<' '<<fa.edge[0]<<' '<<fa.edge[1]<<std::endl;
                }
                getnode(leftbro,fa.edge[tx-1]);
                if(leftbro.now_num>=size_of_block/2){
                    for(int i=temp.now_num;i>0;i--){
                        temp.value[i]=temp.value[i-1];
                        temp.edge[i+1]=temp.edge[i];
                    }
                    temp.edge[1]=temp.edge[0];
                    temp.edge[0]=leftbro.edge[leftbro.now_num];
                    temp.value[0]=fa.value[fa.now_num-1];
                    updatefather(temp.edge[0],pos);
                    temp.now_num++;
                    leftbro.now_num--;
                    fa.value[tx-1]=leftbro.value[leftbro.now_num];
                    writenode(temp,pos);
                    writenode(leftbro,fa.edge[tx-1]);
                    writenode(fa,temp.pos_of_fa);
                }
                else{
                    merge(fa.edge[tx-1],leftbro,temp,fa,tx-1);
                    writenode(leftbro,fa.edge[tx-1]);
                    balanceindex(temp.pos_of_fa,fa.value[tx-1]);
                }
            }
        }
        else writenode(temp,pos);
    }
    void balanceleaf(int pos){
        node temp,temp_back,temp_front;
        getnode(temp,pos);
        if(!temp.back_pos && !temp.front_pos)return;
        if(!judge(temp.back_pos,temp.pos_of_fa,temp_back)){
            getnode(temp_front,temp.front_pos);
            if(temp_front.now_num>size_of_block/2-1){
                temp.value[size_of_block/2-2]=temp_front.value[0];
                for(int i=0;i<temp_front.now_num-1;i++)temp_front.value[i]=temp_front.value[i+1];
                temp_front.now_num--;
                temp.now_num++;
                node temp_fa;
                getnode(temp_fa,temp.pos_of_fa);
                int t=sjtu::upper_bound(temp_fa.value,temp_fa.value+temp_fa.now_num,
                                temp.value[size_of_block/2-2])-temp_fa.value;
                temp_fa.value[t-1]=temp_front.value[0];
                writenode(temp,pos);
                writenode(temp_front,temp.front_pos);
                writenode(temp_fa,temp.pos_of_fa);
            }
            else{
                for(int i=size_of_block/2-2;i<size_of_block-3;i++)
                    temp.value[i]=temp_front.value[i-(size_of_block/2-2)];
                temp.front_pos=temp_front.front_pos;
                updateleft(temp.front_pos,pos);
                temp.now_num=size_of_block-3;
                writenode(temp,pos);
                balanceindex(temp.pos_of_fa,temp_front.value[0]);
            }
            return;
        }
        if(!judge(temp.front_pos,temp.pos_of_fa,temp_front)){
            if(temp_back.now_num>size_of_block/2-1){
                for(int i=temp.now_num;i>0;i--)temp.value[i]=temp.value[i-1];
                temp.value[0]=temp_back.value[temp_back.now_num-1];
                temp_back.now_num--;
                temp.now_num++;
                node temp_fa;
                getnode(temp_fa,temp.pos_of_fa);
                int t=sjtu::upper_bound(temp_fa.value,temp_fa.value+temp_fa.now_num,
                                 temp.value[0])-temp_fa.value;
                temp_fa.value[t]=temp.value[0];
                writenode(temp,pos);
                writenode(temp_back,temp.back_pos);
                writenode(temp_fa,temp.pos_of_fa);
            }
            else{
                for(int i=size_of_block/2-1;i<size_of_block-3;i++)
                    temp_back.value[i]=temp.value[i-size_of_block/2+1];
                temp_back.front_pos=temp.front_pos;
                updateleft(temp_back.front_pos,temp.back_pos);
                temp_back.now_num=size_of_block-3;
                writenode(temp_back,temp.back_pos);
                balanceindex(temp_back.pos_of_fa,temp.value[0]);
            }
            return;
        }

        if(temp_back.now_num>size_of_block/2-1){
            for(int i=temp.now_num;i>0;i--)temp.value[i]=temp.value[i-1];
            temp.value[0]=temp_back.value[temp_back.now_num-1];
            temp_back.now_num--;
            temp.now_num++;
            node temp_fa;
            getnode(temp_fa,temp.pos_of_fa);
            int t=sjtu::upper_bound(temp_fa.value,temp_fa.value+temp_fa.now_num,
                                temp.value[0])-temp_fa.value;
            temp_fa.value[t]=temp.value[0];
            writenode(temp,pos);
            writenode(temp_back,temp.back_pos);
            writenode(temp_fa,temp.pos_of_fa);
            return;
        }
        if(temp_front.now_num>size_of_block/2-1){
            temp.value[size_of_block/2-2]=temp_front.value[0];
            for(int i=0;i<temp_front.now_num-1;i++)temp_front.value[i]=temp_front.value[i+1];
            temp_front.now_num--;
            temp.now_num++;
            node temp_fa;
            getnode(temp_fa,temp.pos_of_fa);
            int t=sjtu::upper_bound(temp_fa.value,temp_fa.value+temp_fa.now_num,
                            temp.value[size_of_block/2-2])-temp_fa.value;
            temp_fa.value[t-1]=temp_front.value[0];//修改
            writenode(temp,pos);
            writenode(temp_front,temp.front_pos);
            writenode(temp_fa,temp.pos_of_fa);
            return;
        }
        for(int i=size_of_block/2-2;i<size_of_block-3;i++)
            temp.value[i]=temp_front.value[i-(size_of_block/2-2)];
        temp.front_pos=temp_front.front_pos;
        updateleft(temp.front_pos,pos);
        temp.now_num=size_of_block-3;
        writenode(temp,pos);
        balanceindex(temp.pos_of_fa,temp_front.value[0]);
    }
    void freshleft(int pos,const data &obj){
        if(pos==0)return;
        node temp;
        getnode(temp,pos);
        int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,obj)-temp.value;
        if(t!=0){
            temp.value[t-1]=obj;
            writenode(temp,pos);
        }
        else freshleft(temp.pos_of_fa,obj);
    }
public:
    database(){}
    database(std::string name){
        std::ifstream in;
        in.open(name);
        if(!in){
            std::ofstream outfile(name);
            outfile.seekp(0);
            start t1;
            outfile.write(reinterpret_cast<char*>(&t1),sizeof(start));
            outfile.seekp(sizeof(start));
            node t2;
            outfile.write(reinterpret_cast<char*>(&t2),sizeof(node));
        }
        opfile.open(name);
        getstart(head);
    }
    void clear(std::string name){
        std::ofstream file(name, std::ios::trunc);
        file.close();
        std::ifstream in;
        in.open(name);
        if(!in){
            std::ofstream outfile(name);
            outfile.seekp(0);
            start t1;
            outfile.write(reinterpret_cast<char*>(&t1),sizeof(start));
            outfile.seekp(sizeof(start));
            node t2;
            outfile.write(reinterpret_cast<char*>(&t2),sizeof(node));
        }
        opfile.open(name);
        getstart(head);
    }
    void setfile(std::string name){
        std::ifstream in;
        in.open(name);
        if(!in){
            std::ofstream outfile(name);
            outfile.seekp(0);
            start t1;
            outfile.write(reinterpret_cast<char*>(&t1),sizeof(start));
            outfile.seekp(sizeof(start));
            node t2;
            outfile.write(reinterpret_cast<char*>(&t2),sizeof(node));
        }
        opfile.open(name);
        getstart(head);
    }
    ~database(){
        writestart(head);
        opfile.close();
    }
    sjtu::vector<T> find(const keys &key){
        int num = finds(key,head.pos_of_root);
        node temp;
        getnode(temp,num);
        int l=0,r=temp.now_num-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(key<=temp.value[mid].key)r=mid;
            else l=mid+1;
        }
        int x=l;
        sjtu::vector<T> ans;
        if(temp.now_num==0)return ans;
        while(true){
            if(x==temp.now_num){
                if(temp.front_pos==0)break;
                getnode(temp,temp.front_pos);
                x=0;
            }
            //std::cout<<x<<'*'<<std::endl;
            if(temp.value[x].key==key)ans.push_back(temp.value[x].value);
            else if(key<temp.value[x].key)break;
            x++;
        }
        return ans;
    }
    void insert(const keys &index,const T &val){
        data obj(index,val);
        int pos=find_pos(obj,head.pos_of_root);
        node temp;
        getnode(temp,pos);
        int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,obj)-temp.value;
        for(int i=temp.now_num;i>t;i--)temp.value[i]=temp.value[i-1];
        temp.value[t]=obj;
        temp.now_num++;
        writenode(temp,pos);
        if(temp.now_num==size_of_block)devideleaf(pos);
    }
    void erase(keys key,T val){
        data obj(key,val);
        int pos=find_pos(obj,head.pos_of_root);
        node temp;
        getnode(temp,pos);
        int t=sjtu::upper_bound(temp.value,temp.value+temp.now_num,obj)-temp.value;
        if(!(temp.value[t-1]==obj))return;
        t--;
        if(t==0 && head.pos_of_root!=pos){
            if(temp.now_num!=1){
                node fa;
                getnode(fa,temp.pos_of_fa);
                int t1=sjtu::upper_bound(fa.value,fa.value+fa.now_num,temp.value[0])-fa.value;
                if(t1!=0){
                    fa.value[t1-1]=temp.value[1];
                    writenode(fa,temp.pos_of_fa);
                }
                else freshleft(fa.pos_of_fa,temp.value[1]);
            }
            else{
                node fa;
                getnode(fa,temp.pos_of_fa);
                node left,right;
                if(!judge(temp.back_pos,temp.pos_of_fa,left)){
                    getnode(right,temp.front_pos);
                    int t1=sjtu::upper_bound(fa.value,fa.value+fa.now_num,temp.value[0])-fa.value;
                    if(t1!=0){
                        fa.value[t1-1]=right.value[0];
                        writenode(fa,temp.pos_of_fa);
                    }
                    else freshleft(fa.pos_of_fa,right.value[0]);
                }
                else if(!judge(temp.front_pos,temp.pos_of_fa,right)){
                    int t1=sjtu::upper_bound(fa.value,fa.value+fa.now_num,temp.value[0])-fa.value;
                    if(t1!=0){
                        fa.value[t1-1]=left.value[left.now_num-1];
                        writenode(fa,temp.pos_of_fa);
                    }
                    else freshleft(fa.pos_of_fa,left.value[left.now_num-1]);
                }
                else{
                    getnode(right,temp.front_pos);
                    int t1=sjtu::upper_bound(fa.value,fa.value+fa.now_num,temp.value[0])-fa.value;
                    if(t1!=0){
                        fa.value[t1-1]=right.value[0];
                        writenode(fa,temp.pos_of_fa);
                    }
                    else freshleft(fa.pos_of_fa,right.value[0]);
                }
            }
        }
        for(int i=t;i<temp.now_num-1;i++)temp.value[i]=temp.value[i+1];
        temp.now_num--;
        writenode(temp,pos);
        if(temp.now_num<size_of_block/2-1)balanceleaf(pos);
    }
    bool empty()
    {
        node root;
        getnode(root,head.pos_of_root);
        if(root.type==leaf && root.now_num==0)return true;
        else return false;
    }
    // void prints(){
    //     node root;
    //     getnode(root,head.pos_of_root);
    //     std::cout<<std::endl<<"***********"<<std::endl;
    //     for(int i=0; i< root.now_num;i++)std::cout<<root.value[i].key<<std::endl;
    //     std::cout<< "***********"<<std::endl;
    // }
};

#endif