CS2351

#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
    int val;
    int damage;
    int health;
    int level;
    struct node *prev;
    struct node *next;
}Node;

// 整個 linked list ，目前的某一個點
Node *current;
int list_size = 0;

void evolve(Node *newnode);
void delete_node(Node *node);



void attack(Node *newnode)
{
    if (newnode->prev != newnode->next)
        newnode->prev->health-=newnode->damage;
    newnode->next->health-=newnode->damage;
}

void insert_instance(int idx, int damage,int health,string stance){
    Node *newnode = new Node;
    newnode -> val = idx;
    newnode -> damage = damage;
    newnode -> health = health;
    newnode -> level = 1;
    if(current==NULL)//只有Newnode一個點
    {
        current = newnode;
        newnode->next=current;
        current->prev=newnode;
    }
    else if(current->prev!=NULL || current->next!=NULL)//?DLL的插入
    {
        newnode->next=current;
        current->prev->next=newnode;
        newnode->prev=current->prev;
        current->prev=newnode;
    }
    list_size++;

    if(stance=="Attack")
    {
        attack(newnode);
        if(newnode->prev->health<=0)
        {
            delete_node(newnode->prev);
        }
        if(newnode->next->health<=0)
        {
            delete_node(newnode->next);
        }
    }
    if(stance == "Evolve"){
        evolve(newnode);
    }
}


void evolve(Node *newnode){
    if(list_size >= 3 && newnode->val==newnode->prev->val && newnode->val==newnode->next->val
    && newnode->prev->level < 3 && newnode->next->level < 3)
    {
        //找最大值
        int max_damage=newnode->damage;
        int max_health=newnode->health;
        int max_level=newnode->level;
        max_damage = max(max_damage, newnode->prev->damage);
        max_damage = max(max_damage, newnode->next->damage);
        max_health = max(max_health, newnode->prev->health);
        max_health = max(max_health, newnode->next->health);
        max_level = max(max_level, newnode->prev->level);
        max_level = max(max_level, newnode->next->level);
        max_level += 1;

        // delete 2 node
        delete_node(current->prev);
        delete_node(current->prev);

        // 確保current指到剩下的那個點
        // 賦值
        current->damage = max_damage;
        current->health = max_health;
        current->level = max_level;
    }
}

// delete current node
void delete_node(Node *node) // node ready to be delete
{
    if(current==NULL)
    {
        return;
    }
    else if(list_size == 1){
        current=NULL;
        list_size = 0;
    }
    else if(node == current)
    {
        Node *temp=current;
        current->prev->next=current->next;
        current->next->prev=current->prev;
        current=current->next;
        free(temp);
        list_size--;
    }else{
        node->prev->next=node->next;
        node->next->prev=node->prev;
        free(node);
        list_size--;
    }
}

vector<int> v;
vector<int> dup_nums;
void check(int num) //?
{
    // 揪出重複的數字
    Node *temp=current;
    v.clear();
    dup_nums.clear();
    for(int i=0;i<num;i++)
    {
        int val=temp->val;
        v.push_back(val);
        temp = temp->next;
    }

    // 找出重複數字
    sort(v.begin(), v.end());
    for(int i=1;i<v.size();i++){
        if(v[i] == v[i-1]){
            if(dup_nums.empty() || dup_nums.back() != v[i]){
                dup_nums.push_back(v[i]);
            }
        }
    }

    // 刪除重複數字
    temp=current;
    for(int i=0;i<num;i++)
    {
        //判斷temp->val是否出現在dup_nums裡面
        auto low_bound = lower_bound(dup_nums.begin(), dup_nums.end(), temp->val);
        if(low_bound == dup_nums.end() || *low_bound != temp->val){
            // 不重複
        }else{
            //重複，刪除current
            if (temp == current){
                delete_node(temp);
                temp = current;
            }else{
                delete_node(temp);
            }
        }
        temp = temp->next;
    }
}

void Shuffle(char dir, int num)
{
    Node *temp=current;
    if(dir=='c')//順時針方向
    {
        for(int i=0;i<num;i++)
        {
            temp=temp->next;
        }
        //交換值就好
        swap(current->val,temp->val);//swap是否會將指標交換?
        swap(current->health,temp->health);//swap是否會將指標交換?
        swap(current->damage,temp->damage);//swap是否會將指標交換?
        swap(current->level,temp->level);//swap是否會將指標交換?
        current = temp;
    }
    if(dir=='a')
    {
        for(int i=0;i<num;i++)
        {
            temp=temp->prev;
        }
        //交換節點(只動next, prev)
        Node *current_next = current->next;
        Node *current_prev = current->prev;
        Node *temp_next = temp->next;
        Node *temp_prev = temp->prev;
        //更新current,temp的指針
        swap(current->next,temp->next);
        swap(current->prev,temp->prev);
        // 更新current,temp前後節點的指針
        current_next->prev = temp;
        current_prev->next = temp;
        temp_next->prev = current;
        temp_prev->next = current;
    }
}

void reverse_segment(Node *start, int seg_size){
    if (seg_size == 1) return;
    Node *prev = start->prev;
    Node *next = start->next;
    Node *last = start;
    for(int i = 0; i < seg_size-1; i++){
        Node *temp = next->next;
        last->prev = next;
        next->next = last;
        last = last->next;
        next = temp;
    }
    prev->next = last;
    last->prev = prev;
    start->next = next;
    next->prev = start;
    if (current == start){
        current = last;
    }
}

void reverse_ll(int num)
{
    if (num >= list_size){
        //reverse all
    }else{
        Node *tmp = current;
        for(int i = 0; i < list_size / num; i++){
            reverse_segment(tmp, num);
            for(int j = 0; j < num; j++){
                tmp = tmp->next;
            }
        }
        if (list_size % num > 0){
            reverse_segment(tmp, list_size % num);
        }
    }
}

void print_list(){
    cout << "list: \n";
    for (int i = 0; i < list_size; i++){
        cout<<"ID: "<<current->val<<"HP: "<<current->health<<"LVL: "<<current->level<<"\n";
        current = current -> next;
    }
}

int main()
{
    int n,x,y,z;
    string cmd, option;
    char dir;
    cin >> n;
    while(n--){
        cin >> cmd;
        if(cmd == "Insert"){
            cin >> x >> y >> z >> option;
            insert_instance(x, y, z, option);
        }else if(cmd == "Delete"){
            delete_node(current);
        }else if(cmd == "Shuffle"){
            cin >> dir >> x;
            Shuffle(dir, x);
        }else if(cmd == "Check"){
            cin >> x;
            check(x);
        }else if(cmd == "Reverse"){
            cin >> x;
            reverse_ll(x);
        }
        print_list();
    }
    cout << "ans\n";
    for (int i = 0; i < list_size; i++){
        cout<<"ID: "<<current->val<<"HP: "<<current->health<<"LVL: "<<current->level<<"\n";
        current = current -> next;
    }
    return 0;
}