#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    char *value;
    struct Node *prev;
    struct Node *next;
};

// Global string pool: 10 strings of max length 100
#define MAX_STRINGS 10
#define MAX_LENGTH 100
char *stringPool[MAX_STRINGS];

void initStringPool() {
    for (int i = 0; i < MAX_STRINGS; i++) {
        stringPool[i] = (char *)malloc(MAX_LENGTH * sizeof(char));
        if (!stringPool[i]) {
            fprintf(stderr, "Memory allocation failed for stringPool[%d]\n", i);
            exit(1);
        }
        stringPool[i][0] = '\0'; // empty string initially
    }
}

// Create node using preallocated buffer
struct Node* createNode(const char *value) 
{
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    if (!node) {
        fprintf(stderr, "Memory allocation failed for node\n");
        exit(1);
    }

    // Find an empty buffer in stringPool
    int found = 0;
    for (int i = 0; i < MAX_STRINGS; i++) {
        if (stringPool[i][0] == '\0') {  // empty
            strncpy(stringPool[i], value, MAX_LENGTH - 1);
            stringPool[i][MAX_LENGTH - 1] = '\0';
            node->value = stringPool[i];
            found = 1;
            break;
        }
    }

    if (!found) {
        fprintf(stderr, "No free string buffer available\n");
        free(node);
        exit(1);
    }

    node->prev = node->next = NULL;
    return node;
}

// Insert at end (pointer-to-pointer style)
void insert(struct Node **head, const char *value) {
    struct Node **current = head;
    struct Node *prev = NULL;

    while (*current) {
        prev = *current;
        current = &((*current)->next);
    }

    struct Node *newNode = createNode(value);
    newNode->prev = prev;
    *current = newNode;
}

// Delete node with exact value
void deleteValue(struct Node **head, const char *value) {
    struct Node **current = head;

    while (*current) {
        if (strcmp((*current)->value, value) == 0) {
            struct Node *tmp = *current;

            if (tmp->next)
                tmp->next->prev = tmp->prev;

            *current = tmp->next;

            // Reset the string buffer
            tmp->value[0] = '\0';
            free(tmp);
            return;
        }
        current = &((*current)->next);
    }
}

// Delete node before a given value
void deleteBefore(struct Node **head, const char *value) {
    struct Node **current = head;
    struct Node *prev = NULL;

    while (*current) {
        if (strcmp((*current)->value, value) == 0 && prev) {
            struct Node *tmp = prev;

            if (tmp->prev) {
                tmp->prev->next = *current;
                (*current)->prev = tmp->prev;
            } else {
                *head = *current;
                (*current)->prev = NULL;
            }

            tmp->value[0] = '\0';
            free(tmp);
            return;
        }

        prev = *current;
        current = &((*current)->next);
    }
}

// Delete node after a given value
void deleteAfter(struct Node **head, const char *value) {
    struct Node **current = head;

    while (*current) {
        if (strcmp((*current)->value, value) == 0 && (*current)->next) {
            struct Node *tmp = (*current)->next;

            (*current)->next = tmp->next;

            if (tmp->next)
                tmp->next->prev = *current;

            tmp->value[0] = '\0';
            free(tmp);
            return;
        }

        current = &((*current)->next);
    }
}

// Print list
void printList(struct Node *head) {
    while (head) {
        printf("%s ", head->value);
        head = head->next;
    }
    printf("\n");
}

// Free list
void freeList(struct Node *head) {
    while (head) {
        struct Node *tmp = head;
        head = head->next;
        tmp->value[0] = '\0';
        free(tmp);
    }

    // Free the string pool
    for (int i = 0; i < MAX_STRINGS; i++) {
        free(stringPool[i]);
    }
}

// Example usage
int main() {
    struct Node *head = NULL;
    initStringPool();

    insert(&head, "apple");
    insert(&head, "banana");
    insert(&head, "cherry");
    insert(&head, "date");

    printf("List: ");
    printList(head);

    deleteValue(&head, "banana");
    printf("After deleteValue(banana): ");
    printList(head);

    deleteBefore(&head, "cherry");
    printf("After deleteBefore(cherry): ");
    printList(head);

    deleteAfter(&head, "apple");
    printf("After deleteAfter(apple): ");
    printList(head);

    freeList(head);

    return 0;
}