dsa hw0 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>


#define ADD 1
#define REMOVE 2
#define MOVE 3
#define MERGE 4

#define MAX_NUM_DECKS 100000 
// hello
typedef struct card
{
    int value;
    struct card* next;
    struct card* prev;
} Card;

typedef struct 
{
    int numCards;
    Card* btm;
    Card* top;

} Deck;

Card* newCard(int card, Card* prev, Card* next);
void printDeck(Deck decks[], int deckIdx);
void initDecks(int numDecks, Deck decks[]);

void add(Deck decks[], int targetDeck, int card);
void removeCard(Deck decks[], int targetDeck);
void move(Deck decks[], int srcDeck, int destDeck);
void merge(Deck decks[], int deck1, int deck2);

int main()
{
    int numDecks, numOperations;
    scanf("%d%d", &numDecks, &numOperations);

    Deck decks[MAX_NUM_DECKS];
    initDecks(numDecks, decks);

    for (int i = 0; i < numOperations; i++)
    {
        int opType;
        scanf("%d", &opType);

        if (opType == ADD)
        {
            int targetDeck, card;
            scanf("%d%d", &targetDeck, &card);
            add(decks, targetDeck - 1, card);
        }
        else if (opType == REMOVE)
        {
            int targetDeck;
            scanf("%d", &targetDeck);
            removeCard(decks, targetDeck - 1);
        }
        else if (opType == MOVE)
        {
            
            int srcDeck, destDeck;
            scanf("%d%d", &srcDeck, &destDeck);
            move(decks, srcDeck - 1, destDeck - 1);
            
        }
        else // opType == MERGE
        {
            int srcDeck, destDeck;
            scanf("%d%d", &srcDeck, &destDeck);
            merge(decks, srcDeck - 1, destDeck - 1);
        }
    }

    for (int i = 0; i < numDecks; i++)
    {
        printf("%d ", decks[i].numCards);
        printDeck(decks, i);
    }


}

Card* newCard(int card, Card* prev, Card* next)
{
    Card* newCard = (Card*)malloc(sizeof(Card));
    newCard->value = card;
    newCard->prev = prev;
    newCard->next = next;
    
    return newCard;
}

void printDeck(Deck decks[], int deckIdx)
{
   
    Card* ptr = decks[deckIdx].top;
    for (int i = 0; i < decks[deckIdx].numCards; i++)
    {
        /*de
        printf("\n");
        printf("%d %d %d \n", decks[0].numCards, decks[1].numCards, decks[2].numCards);
        printf("failed, deck: %d, card: %d\n", deckIdx + 1, i);
        */
        
        assert(ptr != NULL);
        printf("%d ", ptr->value);
        ptr = ptr->prev;
    }
    printf("\n");
}

void initDecks(int numDecks, Deck decks[])
{
    for (int i = 0; i < numDecks; i++)
        decks[i].numCards = 0;
}

void add(Deck decks[], int targetDeck, int card)
{
    decks[targetDeck].numCards++;
    if (decks[targetDeck].numCards == 1)
    {

        decks[targetDeck].top = newCard(card, NULL, NULL);
        decks[targetDeck].btm = decks[targetDeck].top;
        return;
    }

    // the deck is not empty
    decks[targetDeck].top->next = newCard(card, decks[targetDeck].top, NULL);
    decks[targetDeck].top = decks[targetDeck].top->next;
}

 

void removeCard(Deck decks[], int targetDeck)
{
    if (decks[targetDeck].numCards == 0)
        return;
    
    decks[targetDeck].top = decks[targetDeck].top->prev;
    if (decks[targetDeck].top != NULL)
        decks[targetDeck].top->next = NULL;

    decks[targetDeck].numCards--;
    // assert(decks[targetDeck].numCards >= 0); 
    
    return;
}

void move(Deck decks[], int srcDeck, int destDeck)
{
    if (decks[srcDeck].numCards == 0)
        return;

    if (decks[destDeck].numCards == 0)
    {
        decks[destDeck] = decks[srcDeck];
        decks[srcDeck].numCards = 0;
        return;
    }
    decks[destDeck].numCards += decks[srcDeck].numCards;
    decks[srcDeck].numCards = 0;

    // both destDeck and srcDeck aren not empty
    decks[destDeck].top->next = decks[srcDeck].btm;
    decks[srcDeck].btm->prev = decks[destDeck].top;

    decks[destDeck].top = decks[srcDeck].top;


    return;
}

void merge(Deck decks[], int deck1, int deck2)
{
    if (decks[deck1].numCards == 0)
        return;
    if (decks[deck2].numCards == 0)
    {
        decks[deck2] = decks[deck1];
        decks[deck1].numCards = 0;
        return;
    }

    Deck merged;
    Card* ptr1 = decks[deck1].top;
    Card* ptr2 = decks[deck2].top;

    merged.top = ptr1;
    merged.btm = ptr1;
    ptr1 = ptr1->prev;

    while (ptr1 != NULL && ptr2 != NULL)
    {
        Card* tempPrev1 = ptr1->prev;
        Card* tempPrev2 = ptr2->prev;

        merged.btm->prev = ptr2;
        ptr2->next = merged.btm;
        merged.btm = merged.btm->prev;

        merged.btm->prev = ptr1;
        ptr1->next = merged.btm;
        merged.btm = merged.btm->prev;

        ptr1 = tempPrev1;
        ptr2 = tempPrev2;
    }

    if (ptr1 == NULL && ptr2 != NULL)
    {
        merged.btm->prev = ptr2;
        ptr2->next = merged.btm;
        merged.btm = decks[deck2].btm;
    }
    else if (ptr1 != NULL && ptr2 == NULL)
    {
        merged.btm->prev = ptr1;
        ptr1->next = merged.btm;
        merged.btm = decks[deck1].btm;
    }


    merged.numCards = decks[deck1].numCards + decks[deck2].numCards;
    decks[deck1].numCards = 0;
    decks[deck2] = merged;

    return;
}