#include <stdio.h>

// Version itérative
int pgcd_iter(int a, int b)
{
    while (b) {
        int t = a;
        a = b;
        b = t % b;
    }
    return a;
}

// Alternative recursive
int pgcd_rec(int a, int b)
{
    if (b)
        return pgcd_rec(b, a%b);
    else
        return a;
}

void print_array(int l, const int t[]) // le tableau t ne sera pas modifié
{
    int i = 0;
    while (i < l) {
        printf("%3d ", t[i]); // %d suffit, mais pour pascal c'est plus joli avec
        i = i + 1;
    }
    printf("\n");
}

void fill_even(int n, int t[])
{
    int i = 0;
    while (i < n) {
        t[i] = 2*i;
        i = i + 1;
    }
}

int sum(int len, const int array[])
{
    int i = 0, sum = 0;
    while (i < len) {
        sum = sum + array[i];
        i = i + 1;
    }
    return sum;
}

int dot_product(int len, const int v1[], const int v2[])
{
    int i = 0, sum = 0;
    while (i < len) {
        sum = sum + v1[i]*v2[i];
        i = i + 1;
    }
    return sum;
}

void array_sum(int len, const int v1[], const int v2[], int res[])
{
    int i = 0;
    while (i < len) {
        res[i] = v1[i] + v2[i];
        i = i + 1;
    }
}

void pascal_line(int n, int tab[])
{
    int i = n - 1;
    tab[i] = 1;
    while (i > 1) {
        i = i - 1;
        tab[i] = tab[i - 1] + tab[i];
    }
}

void pascal(int n)
{
    int i = 0;
    int tab[n];
    while (i < n) {
        i = i + 1;
        pascal_line(i, tab);
        print_array(i, tab);
    }
}

int is_sorted(int l, const int tab[])
{
    int i = 1;
    while (i < l) {
        if (tab[i] < tab[i - 1])
            return 0;
        i = i + 1;
    }
    return 1;
}

int in_array(int k, int l, const int tab[])
{
    int i = 0;
    while (i < l) {
        if (tab[i] == k)
            return 1;
        i = i + 1;
    }
    return 0;
}

int in_sorted_array(int k, int l, const int tab[])
{
    int start = 0;
    int stop = l - 1;
    while (start <= stop) {
        int mid = (stop + start) / 2;
        if (tab[mid] > k)
            stop = mid - 1;
        else if (tab[mid] < k)
            start = mid + 1;
        else
            return 1;
    }
    return 0;
}

void test_member(int len, const int tab[], const int tab2[])
{
    // Ce test est un peu pourri (d'un point de vue test)
    int i = 0;

    while (i < len) {
        printf("%d => %d (est il pair ?)\n",
                tab[i], in_array(tab[i], len, tab2));
        printf("%d => %d (est il pair ?)\n\n",
                tab[i], in_sorted_array(tab[i], len, tab2));

        printf("%d => %d (est il dans ?)\n",
                tab[i], in_array(tab[i], len, tab));
        printf("%d => %d (est il dans ?)\n\n",
                tab[i], in_sorted_array(tab[i], len, tab));
        i = i + 1;
    }
}

int main(int argc, char* argv[])
{
    int tab[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int tab2[9];
    int tab3[9];

    print_array(9, tab);
    printf("Somme: %d\n",
            sum(9, tab));

    fill_even(9, tab2);
    print_array(9, tab2);
    printf("Somme: %d\n",
            sum(9, tab2));
    printf("Produit scalaire: %d\n",
            dot_product(9, tab, tab2));

    array_sum(9, tab, tab2, tab3);
    printf("Somme membre a membre: ");
    print_array(9, tab3);

    test_member(9, tab, tab2);

    pascal(10);

    return 0;
}

// Les bonus
int member_sorted_r_int(int k, int start, int stop, const int tab[])
{
    if (start > stop) // Les curseurs se sont croisés
        return 0;
    int mid = (stop + start) / 2;
    if (tab[mid] > k)
        return member_sorted_r_int(k, start, mid - 1, tab);
    else if (tab[mid] < k)
        return member_sorted_r_int(k, mid + 1, stop, tab);
    return 1;
}

int member_sorted_r(int k, int l, const int tab[])
{
    return member_sorted_r_int(k, 0, l - 1, tab);
}

void bubble_sort(int l, int tab[])
{
    int done;
    do {
        done = 1;
        for (int i = 0; i < l - 1; i = i + 1)
            if (tab[i] > tab[i + 1]) {
                int tmp = tab[i]; // echanger tab[i] <=> tab[i + 1]
                tab[i] = tab[i + 1];
                tab[i + 1] = tmp;

                done = 0; // on a fait une permutation, on a donc pas fini
            }
    } while (!done);
}

void eratostene(int len, int tab[])
{
    int i = 0;
    int access = 0;
    while (i < len) {
        while (!tab[i]) { // On cherche le premier non nul
            i = i + 1;
            access = access + 1;
        }

        int j = 1;
        while (j*i < len) {
            tab[j * i] = 0;
            j = j + 1;
            access = access + 1;
        }
    }
    printf("%d\t%d\n", len, access);
}