// par20_ex2_t10_12.c SJ

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int *prefix_sum(const int *A, int N);
int *prefix_sum0(const int *A, int N);
void prefix_sum_inplace(int *A, int N);
void prefix_sum_inplace0(int *A, int N);
double dtime();

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

    int N = 1000;
    int i;
    int *A = NULL, *B = NULL;
    double starttime, endtime, inittime;

    if (argc > 1)    // first command line parameter
        N = atoi(argv[1]);

    // allocate, fill, and print input array
    starttime = dtime();    // take starting time
    A = (int *) malloc(N * sizeof(int));
    for (i = 0; i < N; i++)
        A[i] = 1;
    endtime = dtime();  // take ending time
    inittime = endtime-starttime;   // time used

    if (N < 30) {
        printf("Original array:");
        for (i = 0; i < N; i++)
            printf(" %d", A[i]);
        printf("\n");
    } else {    // for large inputs, print time instead of content
        printf("Init array of %d elements in %.6lf s, %6.2lf Melem/s\n", N, inittime, (N/inittime)/1000000);
    }

    // call task function
    B = prefix_sum(A, N);

    if (N < 30) {
        // print result
        printf("Prefix array  :");
        for (i = 0; i < N; i++)
            printf(" %d", B[i]);
        printf("\n");
    }
    free(B);


    // call task function
    B = prefix_sum0(A, N);

    if (N < 30) {
        // print result
        printf("0-prefix array:");
        for (i = 0; i < N; i++)
            printf(" %d", B[i]);
        printf("\n");
    }
    free(B);

    // test in-place versions
    // copy of A
    B = (int *) malloc(N * sizeof(int));
    for (i = 0; i < N; i++)
        B[i] = A[i];

    // in-place prefix sum of A
    prefix_sum_inplace(A, N);
    if (N < 30) {
        printf("Prefix array  :");
        for (i = 0; i < N; i++)
            printf(" %d", A[i]);
        printf("\n");
    }
    free(A);

    // in-place 0-prefix sum of B
    prefix_sum_inplace0(B, N);
    if (N < 30) {
        printf("0-prefix array:");
        for (i = 0; i < N; i++)
            printf(" %d", B[i]);
        printf("\n");
    }
    free(B);

    return 0;
}    // main()


/**
 * returns a prefix sum of A
 **/
int *prefix_sum(const int *A, int N) {
    // TODO
}

/**
 * returns a 0-prefix sum of A
 **/
int *prefix_sum0(const int *A, int N) {
    // TODO
}

/**
 * computes in-place prefix sum of A
 **/
void prefix_sum_inplace(int *A, int N) {
    // TODO
}


/**
 * computes in-place 0-prefix sum of A
 **/
void prefix_sum_inplace0(int *A, int N) {
    // TODO
}


/**
 * return current time in seconds (floating point number)
 * this works if you hava Posix-compliant libraries
 * Windows version coming later
 */
double dtime()
{
    struct timeval tv;
    struct timezone tz;
    gettimeofday(&tv, &tz);
    return tv.tv_sec + (double)tv.tv_usec/1000000;
}