// invoke this as ./a.out 1000000 100
// ./a.out <array-size> <num-iterations>

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>

//#define N	1000000
typedef int (*searchFun)(int *, int, int);	// function pointer type

int printMemoryUsage() {	// credit: https://www.hackerearth.com/practice/notes/vivekprakash/technical-diving-into-memory-used-by-a-program-in-online-judges/
    int fd, data, stack;
    char buf[4096], status_child[] = "/proc/self/status";
    char *vm;

    if ((fd = open(status_child, O_RDONLY)) < 0)
        return -1;

    read(fd, buf, 4095);
    buf[4095] = '\0';
    close(fd);

    vm = strstr(buf, "VmData:");
    if (vm) {
        sscanf(vm, "%*s %d", &data);
    }
    vm = strstr(buf, "VmStk:");
    if (vm) {
        sscanf(vm, "%*s %d", &stack);
    }
    printf("Memory used so far: %d KB\n", data + stack);
    return data + stack;
}
int *initArray(int n) {
	// create a random sorted array
	int curr = 0;
	int *arr = (int *)malloc(n * sizeof(int));
	for (int ii = 0; ii < n; ++ii) {
		curr = curr + rand() % 10;
		arr[ii] = curr;
	}
	return arr;
}
void printArray(int *arr, int n) {
	for (int ii = 0; ii < n; ++ii)
		printf("%d ", arr[ii]);
	puts("");
}
int linearSearch(int *arr, int n, int key) {
	if (n == 0) return 0;
	if (*arr == key) return 1;
	return linearSearch(arr + 1, n - 1, key);	 // recursive
}
int binarySearch(int *arr, int n, int key) {
	int start = 0, end = n - 1;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (key == arr[mid]) return 1;
		else if (key < arr[mid])
			end = mid - 1;
		else
			start = mid + 1;
	}
	return 0;
}
void profileSearch(int numiter, int *arr, int n, searchFun fun, char *display) {
	clock_t starttime, endtime;

	starttime = clock();
	for (int ii = 0; ii < numiter; ++ii) {
		int key = rand() % (10 * n);
		(*fun)(arr, n, key);	// ignoring the return value
	}
	endtime = clock();
	printf("Time taken by %s = %lf seconds\n", display, ((double) (endtime - starttime)) / CLOCKS_PER_SEC);
}
int main(int a, char *b[]) {
	if (a < 3) {
		printf("Usage: %s <array-size> <number-of-iterations>\n", *b);
		exit(1);
	}
	printMemoryUsage();

	int N = atoi(b[1]);
	int *arr = initArray(N);
	//printArray(arr, N);

	int numiter = atoi(b[2]);
	profileSearch(numiter, arr, N, linearSearch, "Linear Search");
	profileSearch(numiter, arr, N, binarySearch, "Binary Search");

	printMemoryUsage();
	// Additional time functions: time(), difftime(), localtime(), strftime().
	return 0;
}