/* domacak.c */

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

#define MAX_LENGHT 100

void merge(char a[], char b[], int levy, int pravy, int poslPravy) {
    int poslLevy = pravy-1;
    int i = levy;
    int prvniLevy = levy;

    while (levy<=poslLevy && pravy<=poslPravy)
        b[i++] = (a[levy]<a[pravy])? a[pravy++] :a [levy++];

    while (levy<=poslLevy) b[i++] = a[levy++];
    while (pravy<=poslPravy) b[i++] = a[pravy++];
}

int min(int x, int y) {
    if (x<y) return x;
    else     return y;
}

void mergeSort(char a[], int n) {
    char *pom = (char*)malloc(n*sizeof(char)),
                *odkud = a, *kam = pom;
    int delkaUseku = 1;
    int posl = n-1, i;
    while (delkaUseku<n) {
        int levy = 0;
        while (levy<=posl) {
            int pravy = levy+delkaUseku;
            merge(odkud, kam, levy, min(pravy, n), min(pravy+delkaUseku-1, posl));
            levy = levy+2*delkaUseku;
        }
        delkaUseku = 2*delkaUseku;
        char *p = odkud;
        odkud = kam;
        kam = p;
    }
    if (odkud!=a)
        for (i=0; i<n; i++) a[i] = pom[i];
}
void prunik(char A[], int na,char B[], int nb,char C[], int cn) {
    int ia = 0,ib=0,ic=0;
    while (ia < na || ib < nb) {
        if (A[ia]>B[ib]) ia++;
        else if (A[ia]<B[ib]) ib++;
        else if (A[ia]==B[ib]) {
            C[ic++] = A[ia++];
            ib++;
        }
    }
}

void sjednoceni(char A[], int na,char B[], int nb,char C[], int cn) {
    int ia = 0,ib=0,ic=0;
    char predchozi = 0;
    while (ia < na && ib < nb) {
        if (A[ia]==B[ib]) ia++;
        else {
            if (A[ia]>B[ib]) C[ic++] = A[ia++];
            else C[ic++] = B[ib++];
        }
    }
    while (ia<na) C[ic++] = A[ia++];
    while (ib<nb) C[ic++] = B[ib++];

}



int main(void) {
    char retezec1[MAX_LENGHT], retezec2[MAX_LENGHT], vysledek[2*MAX_LENGHT];
    int prvni, druhy,i;
    char jmenoSouboru1[MAX_LENGHT], jmenoSouboru2[MAX_LENGHT];
    printf("Zadejte jmeno souboru mnoziny X: \n");
    scanf("%s", jmenoSouboru1);
    printf("Zadejte jmeno souboru mnoziny Y: \n");
    scanf("%s", jmenoSouboru2);
    FILE *soubor1;
    soubor1 = fopen(jmenoSouboru1, "r");
    fscanf(soubor1, "%s", retezec1);
    FILE *soubor2;
    soubor2 = fopen(jmenoSouboru2, "r");
    fscanf(soubor2, "%s", retezec2);
    prvni = strlen(retezec1);
    druhy = strlen(retezec2);
    mergeSort(retezec1, prvni);
    mergeSort(retezec2, druhy);
    printf("Mnozina X: %s  \n", retezec1);
    printf("Mnozina Y: %s  \n", retezec2);
    for (i = 0;i < (2*MAX_LENGHT);i++) vysledek[i] = 0;
    prunik(retezec1, prvni,retezec2, druhy,vysledek,prvni+druhy);
    printf("prunik: %s  \n", vysledek);
    for (i = 0;i < (2*MAX_LENGHT);i++) vysledek[i] = 0;
    sjednoceni(retezec1, prvni,retezec2, druhy,vysledek,prvni+druhy);
    printf("sjednoceni: %s  \n", vysledek);
    system("PAUSE");
    return 0;
}