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

typedef struct n {
    int index;
    int payload;
    struct n* next;
    struct n* prev;
} node;

typedef struct {
    node* head;
    node* tail;
} list;

#define MAX_PAYLOAD 100000000

/**
   Builds a list of the specified size.
 */
list* build_list(int size){
    list* l = malloc(sizeof(list));
    assert(l != NULL);
    node* first = malloc(sizeof(node));
    assert(first != NULL);
    
    l->head = first;
    l->tail = first;
    first->next = NULL;
    first->prev = NULL;
    first->payload = rand() % MAX_PAYLOAD;
    first->index = 0;
    int current_sum = 0;
    for(int i = 1; i < size; i++){
	node* new_node = malloc(sizeof(node));
	assert(new_node != NULL);
	new_node->next = l->head;
	l->head->prev = new_node;
	l->head = new_node;
	new_node->prev = NULL;

	int amt = rand() % 100;
	current_sum += amt;
	new_node->index = current_sum;
	new_node->payload = rand() % MAX_PAYLOAD;
    }
    return l;
}

void print_list_forwards(list* l){
    node* current = l->head;
    while(current != NULL){
	fprintf(stdout, "%d->%d ", current->index, current->payload);
	current = current->next;
    }
    fprintf(stdout, "\n");
}

void print_list_backwards(list* l){
    node* current = l->tail;
    while(current != NULL){
	fprintf(stdout, "%d->%d ", current->index, current->payload);
	current = current->prev;
    }
    fprintf(stdout, "\n");
}

node* scan_list(list* l, int x){
    node* current = l->head;
    while(current != NULL){
	if(current->payload > x)
	    return current;
	current = current->next;
    }
    return NULL;
}

int main(int argc, char** argv){
    int length = atoi(argv[1]);
    list* l = build_list(length);
    int value = atoi(argv[2]);
    node* p = scan_list(l, value);
//    print_list_forwards(l);
    if(p != NULL){
	fprintf(stdout, "index: %d\n", p->index);
    }
    else {
	fprintf(stdout, "Not Found\n");
    }
    return 0;
}