#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>



int nb_occurrences(int n, int* tab, int x) {
    int cpt=0;
    for (int i=0;i<n;i++){
        if (tab[i]==x){
            cpt++;
    }
}
  return cpt;
}

int une_occurrence(int n, int* tab, int x) {
  int d = 0;
  int f = n - 1;
  int res = -1;

  while (d <= f) {
    int m = (d + f) / 2;
    if (tab[m]==x) {
      res = m;
      break;
    } else if (tab[m] < x) {
      d=m+1;
    }
    else {
      f=m-1;
    }
  }
  
  return res;
}

int premiere_occurrence(int n, int* tab, int x) {
  // À compléter
  int d = 0;
  int f = n - 1;

  

  while (d < f) {
    int m = (d + f) / 2;
    if (tab[m]==x) {
      f=m;
    } else if (tab[m] < x) {
      d=m+1;
    }
    else {
      f=m-1;
    }
  }
  
  if (tab[f]==x){
    return f ;
    }
    else return (-1);
} 

int derniere_occurrence(int n, int* tab, int x) {
  // À compléter
  int d = 0;
  int f = n - 1;

 if (f<d) return (-1);

  while (d+1 < f) {
    int m = (d + f) / 2;
    if (tab[m]==x) {
      d=m;
    } else if (tab[m] < x) {
      d=m+1;
    }
    else {
      f=m-1;
    }
  }
  printf("%d,%d\n",d,f);
  if (tab[d+1]==x){
    return d+1 ;
    }
    else if (tab[d]==x) return (d);
    else return (-1);
} 


int nombre_occurrences(int n, int* tab, int x) {
  int first = premiere_occurrence(n,tab,x);
  int next = derniere_occurrence(n,tab,x);
  if (first !=(-1))
  return (next-first+1);
  else return 0;
}

int main(void) {

  int tab[17] = {0, 1, 1, 2, 2, 2, 4, 4, 5, 6, 6, 6, 8, 8, 8, 8, 9};
  int occ[10] = {1, 2, 3, 0, 2, 1, 3, 0, 4, 1};
  int fst[10] = {0, 1, 3, -1, 6, 8, 9, -1, 12, 16};
    printf("%d\n",derniere_occurrence(17, tab, 1));
  // Test de `nb_occurrences` [ne pas modifier]
  bool test = true;
  test = test && nb_occurrences(0, tab, 0) == 0;
  test = test && nb_occurrences(1, tab, 0) == 1;
  test = test && nb_occurrences(1, tab, 1) == 0;
  test = test && nb_occurrences(2, tab, 0) == 1;
  for (int i = 0; i < 10; i += 1) {
    test = test && nb_occurrences(17, tab, i) == occ[i];
  }
  printf("Test nb_occurrences : %s\n", test ? "validé" : "échec");

  // Test de `une_occurrence` [ne pas modifier]
  test = true;
  test = test && une_occurrence(0, tab, 0) == -1;
  test = test && une_occurrence(1, tab, 0) == 0;
  test = test && une_occurrence(1, tab, 1) == -1;
  test = test && une_occurrence(2, tab, 0) == 0;
  for (int i = 0; i < 10; i += 1) {
    int k = une_occurrence(17, tab, i);
    if (occ[i] > 0) {
      test = test && 0 <= k && k < 17 && tab[k] == i;
    } else {
      test = test && k == -1;
    }
  }
  printf("Test une_occurrence : %s\n", test ? "validé" : "échec");

  // Test de `premiere_occurrence` [ne pas modifier]
  test = true;
  test = test && premiere_occurrence(0, tab, 0) == -1;
  test = test && premiere_occurrence(1, tab, 0) == 0;
  test = test && premiere_occurrence(1, tab, 1) == -1;
  test = test && premiere_occurrence(2, tab, 0) == 0;
  for (int i = 0; i < 10; i += 1) {
    test = test && premiere_occurrence(17, tab, i) == fst[i];
  }
  printf("Test première occurrence : %s\n", test ? "validé" : "échec");

  // Test de `nombre_occurrences` [ne pas modifier]
  test = true;
  test = test && nombre_occurrences(0, tab, 0) == 0;
  test = test && nombre_occurrences(1, tab, 0) == 1;
  test = test && nombre_occurrences(1, tab, 1) == 0;
  test = test && nombre_occurrences(2, tab, 0) == 1;
  for (int i = 0; i < 10; i += 1) {
    test = test && nombre_occurrences(17, tab, i) == occ[i];
    if (!test) printf("%d",i);
  }
  printf("Test nombre_occurrences : %s\n", test ? "validé" : "échec");

}