#include "xor_ll.h"
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>


node* XOR(node *a, node *b) {
    return (node *) ((uintptr_t) a ^ (uintptr_t) b);
}

void insert(node **head, int data) {
    node *new_node = (node *) malloc(sizeof(node));

    new_node->data = data;
    new_node->prev_xor_nxt = *head;
    if (*head != NULL) {
        (*head)->prev_xor_nxt = XOR(new_node, (*head)->prev_xor_nxt);
    }
    *head = new_node;
    return;
}

void pop(node **head, int to_delete) {
    node *curr = *head;
    node *prev = NULL;
    node *nxt = XOR(prev , curr->prev_xor_nxt);
    while (curr != NULL) {
        if ((curr)->data == to_delete) {
            if (prev != NULL) {
                prev->prev_xor_nxt = XOR(curr, prev->prev_xor_nxt);
                prev->prev_xor_nxt = XOR(nxt, prev->prev_xor_nxt);
            }
            if (nxt != NULL) {
                nxt->prev_xor_nxt = XOR(curr, nxt->prev_xor_nxt);
                nxt->prev_xor_nxt = XOR(prev, nxt->prev_xor_nxt);
            }
            if (curr == *head) {
                *head = nxt;
            }
            free(curr);
            return;
        }
        prev = curr;
        curr = nxt;
        nxt = XOR(prev, curr->prev_xor_nxt);
    }
    return;
}

void insert_after(node **head, node *target, int data) {
    node *new_node = (node *) malloc(sizeof(node));
    new_node->prev_xor_nxt = NULL;
    new_node->data = data;

    node *curr = *head;
    node *prev = NULL;
    node *nxt = XOR(prev, curr->prev_xor_nxt);
    while (curr != NULL) {
        if (curr == target) {
            if (nxt != NULL) {
                nxt->prev_xor_nxt = XOR(curr, nxt->prev_xor_nxt);
                nxt->prev_xor_nxt = XOR(new_node, nxt->prev_xor_nxt);
            }
            curr->prev_xor_nxt = XOR(curr->prev_xor_nxt, nxt);
            curr->prev_xor_nxt = XOR(curr->prev_xor_nxt, new_node);
            
            new_node->prev_xor_nxt = XOR(new_node->prev_xor_nxt, curr);
            new_node->prev_xor_nxt = XOR(new_node->prev_xor_nxt, nxt);
            return;
        }
        prev = curr;
        curr = nxt;
        nxt = XOR(prev, curr->prev_xor_nxt);
    }
    return;
}

void print_list(node *head) {
    node *curr = head;
    node *prev = NULL;
    node *nxt;

    while (curr != NULL) {
        printf("%d ", curr->data);
        nxt = XOR(prev, curr->prev_xor_nxt);
        prev = curr;
        curr = nxt;
    }
    printf("\n");
}


double bench_insert_after() {
    node *head = NULL;
    node *targets[10000];
    int j = 0;
    int x;
    srandom(0);
    for (int i = 0; i < 100000; i++) {
        x = random();
        insert(&head, x);
        if (x % 10 == 0 && j < 10000) {
            targets[j] = head;
            j++;
        }
    }
    clock_t begin = clock();
    for  (int i = 0; i < j; i++) {
        insert_after(&head, targets[i], random());
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}


double bench_pop(){
    node *head = NULL;
    node *targets[10000];
    int j = 0;
    int x;
    srandom(0);
    for (int i = 0; i < 100000; i++) {
        x = random();
        insert(&head, x);
        if (x % 10 == 0 && j < 10000) {
            targets[j] = head;
            j++;
        }
    }
    clock_t begin = clock();
    for  (int i = 0; i < j; i++) {
        pop(&head, targets[i]->data);
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}

double bench_insert(){
    node *head = NULL;
    srandom(0);
    clock_t begin = clock();
    for (int i = 0; i < 100000; i++) {
        insert(&head, random());
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}

int main() {
    printf("%g\n", bench_insert());
    printf("%g\n", bench_pop());
    printf("%g\n", bench_insert_after());
    return 0;
}