// Two non-empty integer arrays are stored in files
// "ina.txt" and "inb.txt". The program reads both
// arrays from files, allocating memory in the heap.
// Then the program sorts each array and calculates
// a number of different elements in it, writing
// different elements into the beginning of array
// in ascending order. Finally, the program outputs
// into the file "output.txt" those elements of 
// the first array that do not belong to the second.
#include <stdio.h>

void sort(int *a, int n);
bool inputArray(const char *fileName, int **a, int *n);
int reduce(int *a, int n);

int main() {
    int *a, *b;
    int n, m;
    if (!inputArray("ina.txt", &a, &n)) {
        return -1;
    }
    if (!inputArray("inb.txt", &b, &m)) {
        return -1;
    }
    if (n == 0 || m == 0)
        return -1;
    int n0 = reduce(a, n); // n0 is the number of different elements in a
    int m0 = reduce(b, m); // m0 is the number of different elements in b

    // Write to the file "output.txt" those elements of
    //     the array a that do not belong to b
    FILE *out = fopen("output.txt", "w");
    if (out == NULL) {
        perror("Could not open the output file");
        return -1;
    }
    // fprintf(out, "%d %d\n", n0, m0);

    // Invariant:
    //     a[i] > b[0], ..., b[k-1] &&
    //     a[i] <= b[k]
    int i = 0;
    int k = 0;
    // Ensure the implementation of invariant 
    // before the main loop
    while (k < m0 && a[i] > a[k]) {
        ++k;
    }

    while (i < n0) {
        // Invariant: a[i] > b[k-1] && a[i] <= b[k]
        if (k >= m0 || a[i] < b[k]) {
            // The element a[i] does not belong to the array b
            fprintf(out, "%d ", a[i]);
        }
        ++i;
        if (i >= n0)
            break;
        // Ensure the implementation of invariant
        while (k < m0 && a[i] > b[k]) {
            ++k;
        }
    }
    fprintf(out, "\n");
    fclose(out);

    // Release a memory
    delete[] a;
    delete[] b;
    return 0;
}

bool inputArray(const char *fileName, int **a, int *n) {
    FILE *f = fopen(fileName, "r");
    if (f == NULL)
        return false;
    // Count the number of elements in the file
    int x;
    int m = 0;
    while (fscanf(f, "%d", &x) == 1) {
        ++m;
    }
    rewind(f);
    if (m == 0) {
        // Empty file
        fclose(f);
        return false;
    }

    // Allocate a memory for array
    int *arr = new int[m];

    // Input elements
    for (int i = 0; i < m; ++i) {
        fscanf(f, "%d", arr + i);
    }
    fclose(f);

    *a = arr;
    *n = m;
    return true;
}

int reduce(int *a, int n) {
    if (n == 0)
        return 0;
    sort(a, n);
    int k = 1;  // Number of different elements
    for (int i = 1; i < n; ++i) {
        // Invariant: 
        //     i >= k &&
        //     a[0] < a[1] < ... < a[k-1]
        if (a[i] > a[k-1]) {
            if (i != k) {
                a[k] = a[i];
            }
            ++k;
        }
    }
    return k;
}

// Bubble Sort
void sort(int *a, int n) {
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (int i = 0; i < n-1; ++i) {
            if (a[i] > a[i+1]) {
                // Swap elements
                int tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                sorted = false;
            }
        }
    }
}