#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <iostream>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

struct Node{
    int item;
    Node* next;
};

// calculate the difference in between clock2 and clock1 (in milliseconds) 
double diffclock(clock_t clock1, clock_t clock2){
    double diffticks = clock1 - clock2;
    double diffms = (diffticks * 1000) / CLOCKS_PER_SEC;
    return diffms;
}

// array-based look up
int getEntry(int index, int* array){
    return array[index];
}

// linked-list-based look up
int getEntry(int index, Node* head){
    Node* curr = head;
    for( int i = 0; i < index && curr != NULL; i++){
        curr = curr->next;
    }
    return (curr->item);
}

#define NUM_REPETITIONS 500

int main(int argc, char* argv[]){

    clock_t begin, end;
    
    /* initialize random seed: */
    srand (time(NULL));

    // allocate memory for an array of random queries
    int* randomQueries = new int[NUM_REPETITIONS];
    
    int maxN = -1;
    do{ 
        cout << "Enter the maximum value of N: ";
        cin >> maxN;
    }while( ! cin );

    cerr << "n\tArray\tLinked List\n";

    for(int n = 10; n <= maxN; n *= 10){
        cerr << n;

        //int array[n]; // works for ~1,000,000, won't work for large n
        int* array = new int[n];

        // populate each element of the array with its index
        for( int i = 0; i < n; i++){
            array[i] = i;
        }

        // make linked list with same random numbers as array
        Node* head = new Node;
        Node* curr = head;
        int i = 0;
        curr->item = array[i]; // use the same random number as array
                           
        for( i = 1; i < n; i++){
            curr->next = new Node;
            curr = curr->next;
            curr->item = array[i];
        }
        curr->next = NULL;

        // choose new random queries
        for( int j = 0; j < NUM_REPETITIONS; j++){
            randomQueries[j] = rand() % n;
        }

        // measure how much time it takes
        begin = clock();
        for( int j = 0; j < NUM_REPETITIONS; j++){
            getEntry( randomQueries[j], array);
        }
        end = clock();
        cerr << '\t' << diffclock( end, begin);
        
        begin = clock();
        for( int j = 0; j < NUM_REPETITIONS; j++){
            getEntry( randomQueries[j], head);
        }
        end = clock();
        cerr << '\t' << diffclock( end, begin);
        cerr << '\n';
    
        delete[] array;
    }
    return 0;
}