/* 
 * File:   complexity.c
 * Author: Marco Sbaraglia, Stefano Benedettini, Andrea Roli
 *
 * Revised on March 2012
 */
 
#include <assert.h>
#include <stdlib.h>

#include "boolean.h"
#include "array.h"
#include "complexity.h"

/* duplicate finding algorithms */

int test_scan(int a[], int len, int* iter) {
    int i, j;
    *iter = 0;
    for (i = 0; i < len - 1; ++i)
        for (j = i + 1; j < len; ++j) {
            ++(*iter);
            if (a[i] == a[j])
                return FALSE;
        }
    return TRUE;
}

int test_store(int a[], int len, int* iter) {
    int i;
    *iter = 0;
    int* b = calloc(MAX_ELEMENT, sizeof (int));
    for (i = 0; i < len; ++i) {
        ++(*iter);
        if (b[a[i]]) {
            return FALSE;
        } else
            b[a[i]] = TRUE;
    }
    free(b);
    return TRUE;
}



/* generation functions */

int* ordered(int len) {
    int i;
    int* res = malloc(len * sizeof (int));
    for (i = 0; i < len; ++i) {
        res[i] = i;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    return res;
}

int* extremes(int len) {
    int i;
    int* res = malloc(len * sizeof (int));
    for (i = 0; i < len - 1; ++i) {
        res[i] = i;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    res[len - 1] = 0;
    return res;
}

int* firstPair(int len) {
    int i;
    int* res = malloc(len * sizeof (int));
    res[0] = 0;
    for (i = 1; i < len; ++i) {
        res[i] = i - 1;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    return res;
}

int* lastPair(int len) {
    int i;
    int* res = malloc(len * sizeof (int));
    for (i = 0; i < len - 1; ++i) {
        res[i] = i;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    res[len - 1] = len - 2;
    return res;
}

int* sequentialBlocks(int len) {
    int i;
    int limit = rand() % len;
    limit = limit > 2 ? limit : 2;
    assert(limit > 1 && limit <= len);
    int* res = malloc(len * sizeof (int));
    for (i = 0; i < len; ++i) {
        res[i] = i % limit;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    return res;
}

int* randomized(int len) {
    int i;
    int* res = malloc(len * sizeof (int));
    for (i = 0; i < len; ++i) {
        res[i] = rand() % len;
        assert(res[i] <= len && res[i] <= MAX_ELEMENT);
    }
    return res;
}

/* test runner */

int* runExperiments(int* (*generator)(int), int (*algo)(int*, int, int*), int len, int nExperiments) {
    int run;
    int* array;
    int* results = calloc(nExperiments, sizeof (int));
    for (run = 0; run < nExperiments; ++run) {
        array = generator(len);
        /* printArray(array, len); */
        algo(array, len, &results[run]);
        free(array);
    }
    return results;
}