#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef struct memoryBlock{
    string jobName;
    int startadress;
    int length;
    bool state;
}memoryBlock;
vector<memoryBlock> mb;
void init(){
    memoryBlock m1,m2,m3,m4,m5,m6;
    m1.jobName="作业1";m2.jobName="作业2";m3.jobName="未分配";m4.jobName="作业3";m5.jobName="未分配";m6.jobName="未分配";
    m1.state=1;m2.state=1;m3.state=0;m4.state=1;m5.state=0;m6.state=0;
    m1.startadress=60;m2.startadress=32;m3.startadress=60;m4.startadress=8;m5.startadress=32;m6.startadress=8;
    m1.length=4;m2.length=16;m3.length=4;m4.length=20;m5.length=16;m6.length=20;
    mb.push_back(m1);mb.push_back(m2);mb.push_back(m3);mb.push_back(m4);mb.push_back(m5);mb.push_back(m6);
}
void firstfit(){
    string name;
    cout<<"请输入要分配的作业名称：";
    cin>>name;
    int size;
    cout<<"请输入作业主存量：";
    cin>>size;
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        int s_pos = it->startadress+size;
        int last_size = it->length-size;
        int f = 0;
        if(it->length>size){
            f=1;
        }
        if(it->state==0&&it->length>=size){
            it->state=1;
            it->length=size;
            it->jobName = name;
            if(f){
                memoryBlock m;
                m.jobName="未分配";
                m.length=last_size;
                m.state=0;
                m.startadress = s_pos;
                it++;
                mb.insert(it,m);
            }
            break;
        }
    }
}
void bestfit(){
    string name;
    cout<<"请输入要分配的作业名称：";
    cin>>name;
    int size;
    cout<<"请输入作业主存量：";
    cin>>size;
    int min_last=128;
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        if(it->state==0&&it->length>=size){
            int last_size = it->length-size;
            if(last_size<min_last){
                min_last=last_size;
            }
        }
    }
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        int s_pos = it->startadress+size;
        int last_size = it->length-size;
        if(last_size==min_last){
            it->state=1;
            it->length=size;
            it->jobName = name;
            if(last_size>0){
                memoryBlock m;
                m.jobName="未分配";
                m.length=last_size;
                m.state=0;
                m.startadress = s_pos;
                it++;
                mb.insert(it,m);
            }
            break;
        }
    }
}
void recycle(){
    cout<<"请输入要回收的作业名称：";
    string name;
    cin>>name;
    vector<memoryBlock>::iterator it_new;
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        if(it->jobName.compare(name)==0){
            it->state=0;
            it->jobName="未分配";
            it_new = it;
            break;
        }
    }
    vector<memoryBlock>::iterator it_pre=--it_new;
    it_new++;
    vector<memoryBlock>::iterator it_next=++it_new;
    it_new--;
    if(it_pre->state==1&&it_next->state==0){
        it_new->length+=it_next->length;
        mb.erase(it_next);
    }
    else if(it_pre->state==0&&it_next->state==1){
        it_pre->length+=it_new->length;
        mb.erase(it_new);
    }
    else if(it_pre->state==0&&it_next->state==0){
        it_pre->length+=it_new->length;
        it_pre->length+=it_next->length;
        mb.erase(it_new);
        mb.erase(it_next);
    }
}
void distribute(){
    cout<<"*********************空闲区表*********************"<<endl;
    cout<<"\t起止\t|\t长度\t|\t状态"<<endl;
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        if(it->state==0){
            cout<<"\t"<<it->startadress<<"k\t|\t"<<it->length<<"k\t|\t"<<it->jobName<<endl;
        }
    }
    cout<<"**************************************************"<<endl;
    cout<<"*********************已分配表*********************"<<endl;
    cout<<"\t起止\t|\t长度\t|\t名称"<<endl;
    for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
        if(it->state==1){
            cout<<"\t"<<it->startadress<<"k\t|\t"<<it->length<<"k\t|\t"<<it->jobName<<endl;
        }
    }
    cout<<"**************************************************"<<endl;
}
int main(){
    init();
    cout<<"（本次实验分配主存采用最优适应算法）"<<endl<<"请输入x或y以继续实验：";
    char option1;
    cin>>option1;
    int option2;
    int running = 1;
    while(running){
        cout<<"选择功能项（1-退出，2-分配主存，3-回收主存，4-显示主存）"<<endl<<"请输入选择的功能：";
        cin>>option2;
        switch (option2){
            case 1: running = 1;break;
			            case 2: {
			                if(option1=='x'){
			                    bestfit();
			                }
			                else if(option1=='y'){
			                    bestfit();
			                }
			                break;
			            }
			            case 3: {recycle();break;}
			            case 4: {distribute();break;}
			            default:{
			                cout<<"输入有误!请重新选择"<<endl;
			                break;
			            } 
			            
			        }
			    }
			    return 0;
}