www

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

dichotomique.c (1219B)

      1 #include <module.h>
      2 #include <types.h>
      3 #include <recherche/dichotomique/dichotomique.h>
      4 #include <interfaceUtilisateur/console/console.h>
      5 
      6 MODULE(RechercheDichotomique);
      7 
      8 void* testGet(void* t, uint32 index) {
      9 	return ((int*)t) + index;
     10 }
     11 
     12 int testCmp(void* a, void* b) {
     13 	int aa = *((int*)a);
     14 	int bb = *((int*)b);
     15 	return (aa == bb) ? 0 : ((aa < bb) ? -1 : 1);
     16 }
     17 
     18 void initRechercheDichotomique(void** etat) {
     19 	*etat = NULL;
     20 }
     21 
     22 void deinitRechercheDichotomique(void** etat) {
     23 	*etat = NULL;
     24 }
     25 
     26 int rechercheDichotomiquePremier(void* e, void* t, int taille, AccesseurIndex get, ComparaisonStricte comparer) {
     27 	int i = 0;
     28 	int j = taille - 1;
     29 	int m;
     30 	
     31 	if (comparer(get(t, i), e) == 0)
     32 		return i;
     33 	
     34 	while (i + 1 < j) {
     35 		m = (i + j) / 2;
     36 		if (comparer(get(t, m), e) < 0)
     37 			i = m;
     38 		else
     39 			j = m;
     40 	}
     41 	
     42 	return (comparer(get(t, j), e) == 0) ? j : -1;
     43 }
     44 
     45 int rechercheDichotomiqueDernier(void* e, void* t, int taille, AccesseurIndex get, ComparaisonStricte comparer) {
     46 	int i = 0;
     47 	int j = taille - 1;
     48 	int m;
     49 	
     50 	if (comparer(get(t, j), e) == 0)
     51 		return j;
     52 	
     53 	while (i + 1 < j) {
     54 		m = (i + j) / 2;
     55 		if (comparer(get(t, m), e) > 0)
     56 			j = m;
     57 		else
     58 			i = m;
     59 	}
     60 	
     61 	return (comparer(get(t, i), e) == 0) ? i : -1;
     62 }