// Arup Guha
// 9/2/2021
// Code for Fall 2021 COP 3502 Quiz #1

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

// Used for versions C, F
typedef struct fraction {
    int x;
    int y;
} fraction;

void print(int* a, int n);
int* rndArr(int n, int jump);
int* slist_union(int list1[], int n, int list2[], int m, int*news);
int* slmp_linear(int list1[], int n, int list2[], int m, int* news);
int search(int list[], int n, int value);
int* rangelist(int list[], int n, int low, int high, int* news);
int* nomorethanlist(int list[], int n, int max, int* newlen);
int* atleastlist(int list[], int n, int min, int* newlen);
fraction** makeRandList(int n, int max);

int** makeCustomMultTable(int* list1, int len1, int* list2, int len2);
void print2D(int** a, int r, int c);
void printFrac(fraction* f);


// Runs some tests.
int main(void) {

    srand(time(0));

    // Version B - union test.
    int* a = rndArr(10, 5);
    int* b = rndArr(8, 5);
    print(a, 10); print(b, 8);
    int news;
    int* c = slist_union(a, 10, b, 8 , &news);
    print(c, news);

    // Version A, regular SLMP
    int* d = slmp_linear(a, 10, b, 9, &news);
    print(d, news);

    // Version C - Binary Search Test
    for (int i=10; i<=15; i++)
    printf("%d %d\n", search(a, 10, i));

    // Version D - Range List Test
    int* e = rangelist(a, 10, 12, 23, &news);
    print(e, news);
    free(e);

    // Version E - No More Test
    e = nomorethanlist(a, 10, 15, &news);
    print(e, news);
    free(e);

    // Version F - At Least Test.
    e = atleastlist(a,10, 14, &news);
    print(e, news);

    // Multiplication Table Versions A, D (just switch to adding for versions B, E)
    int** mult = makeCustomMultTable(a, 10, b, 8);
    print2D(mult, 10, 8);

    // Free the table.
    for (int i=0; i<10; i++) free(mult[i]);
    free(mult);

    // Done with these tests, so I free it all.
    free(a); free(b); free(c); free(d); free(e);

    // Fraction List Versions C, F
    fraction** fList = makeRandList(10, 30);
    for (int i=0; i<10; i++)
        printFrac(fList[i]);
    printf("\n");

    // Free the fraction memory.
    for (int i=0; i<10; i++)
        free(fList[i]);
    free(fList);

    return 0;
}

// Prints out a 2D array a of dimensions r by c.
void print2D(int** a, int r, int c) {
    for (int i=0; i<r; i++)
        print(a[i], c);
}

// Prints out a[0..n-1].
void print(int* a, int n) {
    for (int i=0; i<n; i++) printf("%d ", a[i]);
    printf("\n");
}

// Creates a random sorted array and returns it.
int* rndArr(int n, int jump) {
    int* a = malloc(n*sizeof(int));
    a[0] = rand()%jump;
    for (int i=1; i<n; i++)
        a[i] = a[i-1] + rand()%jump + 1;
    return a;
}

// Pre-condition: list1 is length n and sorted.
//                list2 is length m and sorted.
// Post-condition: All elements belonging to both lists are
//                 returned in a dynamically allocated array.
int* slist_union(int list1[], int n, int list2[], int m, int*news) {

    // This is enough room at first.
    int* res = calloc(n+m, sizeof(int)) ;

    // i is index to list1, j to list2, k to res.
    int i = 0, j = 0, k = 0;

    // Keep going as long as there are numbers left.
    while (i < n || j < m) {

        // Avoid AOOB and get next # from list 1.
        if (j==m || (i<n && list1[i] < list2[j])) {
            res[k] = list1[i] ;
            i++; k++;
        }

        // Here we definitely grab from list2.
        else if (i==n || list2[j] < list1[i]) {
            res[k] = list2[j] ;
            j++; k++;
        }

        // Otherwise from both lists.
        else {
            res[k] = list1[i] ;
            i++; j++; k++;
        }
    }

    // Reallocate, update size of list and return.
    res = realloc(res, k*sizeof(int)) ;
    *news = k;
    return res;
}

// Pre-condition: list1 is length n, sorted, with unique values.
//                list2 is length m, sorted, with unique values.
// Post-condition: All elements belonging to both lists are
//                 returned in a dynamically allocated array.
int* slmp_linear(int list1[], int n, int list2[], int m, int* news) {

    // This is more than enough space.
    int* res = calloc(n, sizeof(int)) ;

    // i is index to list1, j to list2, k to res.
    int i = 0, j = 0, k = 0;

    // Can stop as soon as we get to the end of either list.
    while (i < n && j < m) {

        // Safe to advance list1 pointer.
        if (list1[i] < list2[j]) i++;

        // Safe to advance list2 pointer.
        else if (list2[j] < list1[i]) j++;

        // Got a match.
        else {

            // Add to our result and update all pointers(indexes).
            res[k] = list1[i] ;
            k++;
            i++;
            j++;
        }
    }

    // Reallocate, store length and return.
    res = realloc(res, k*sizeof(int)) ;
    *news = k ;
    return res;
}

// Returns the number of loop iterations necessary to find value in the sorted array list. Returns -1 if not found.
int search(int list[], int n, int value) {

    // Set to whole array and 1 search (at beginning)
    int low = 0, high = n-1, res = 1;

    // Usual binary search loop.
    while ( low<=high ) {

        // Go halfway.
        int mid = (low+high)/2 ;

        // Too low, update high and add 1 to loop iterations.
        if (value < list[mid]) {
            res++ ;
            high = mid-1 ;
        }

        // Too big, update low and add 1 to loop iterations.
        else if (value > list[mid]) {
            res++;
            low=mid+1 ;
        }

        // Got it, so we can return res. (I already added 1 at the beginning...)
        else
            return res ;
    }

    // Never found it.
    return -1;
}

// Returns all the values in list in between low and high in a new array and stores the size of that array in *news.
int* rangelist(int list[], int n, int low, int high, int* news) {

    // Go tot he first value low or greater.
    int i=0;
    while (i<n && list[i] < low) i++;

    // Now go to the first value greater than high.
    int j = i;
    while (j<n && list[j] <= high) j++;

    // We have exactly j-i values in range.
    int* res = malloc((j-i)*sizeof(int));

    // Copy the values over.
    for (int z=0; z<j-i; z++)
        res[z] = list[i+z];

    // Store the size and return.
    *news = j-i;
    return res;
}

// Returns all of the values in list no greater than max and stores the list in the variable *newlen
int* nomorethanlist(int list[], int n, int max, int* newlen) {

    // Keep going until max is exceeded.
    int i=0;
    while ( i<n && list[i]<=max ) i++ ;

    // This is how big to make the array.
    int* res = malloc(i*sizeof(int));

    // Just copy the left i values over.
    for (int z=0; z<i; z++)
        res[z] = list[z];

    // Update the length and return the pointer to the new array.
    *newlen = i ;
    return res;
}

// Returns a pointer to a new array storing all values in list greater than or equal to min and stores the length of
// the list in *newlen.
int* atleastlist(int list[], int n, int min, int* newlen) {

    // Find the first value at least as big as min.
    int i=0;
    while ( i<n && list[i]<min ) i++ ;

    // This is how many numbers are min or greater.
    int* res = malloc((n-i)*sizeof(int)) ;

    // Start copying from index i in list.
    for (int z=i; z<n; z++)
        res[z-i] = list[z];

    // Store the length and return.
    *newlen = n-i;
    return res;
}


// Create the aforementioned multiplication table and return a pointer to the newly allocated 2D array.
int** makeCustomMultTable(int* list1, int len1, int* list2, int len2) {

    // Allocate space for the array of pointers.
    int** res = malloc(len1*sizeof(int*));

    // Now, allocate space for the arrays each pointer is pointing to.
    for (int i=0; i<len1; i++)
        res[i] = malloc(len2*sizeof(int));

    // Just fill up the table, multiplying the two appropriate values each time.
    for (int i=0; i<len1; i++)
        for (int j=0; j<len2; j++)
            res[i][j] = list1[i]*list2[j];

    // Ta da!
    return res;
}

// Returns a pointer to an array of pointers to random fractions with a denominator in between 1 and max and a numerator in between
// 0 and the denominator.
fraction** makeRandList(int n, int max) {

    // Allocate space for the array of pointers.
    fraction** res = malloc(n*sizeof(fraction*));

    // Go through each array slot.
    for (int i=0; i<n; i++) {

        // Allocate space for this fraction,
        res[i] = malloc(sizeof(fraction));

        // Here is how you get a number from 1 to max.
        res[i]->y = 1 + rand()%max;

        // This will be a number from 0 to res[i]->y, as desired.
        res[i]->x = rand()%(res[i]->y+1);
    }

    // Ta da!
    return res;
}

void printFrac(fraction* f) {
    printf("%d/%d ", f->x, f->y);
}