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

struct dlist_t{
  int data;
  struct dlist_t* prev;
  struct dlist_t* next;
};
typedef struct dlist_t dl;

//Cherche si la clé k est présente dans
//  la liste l
//Renvoi la cellule de la liste contenant k si k est présent
//       NULL sinon
dl* dl_pres(int k, dl* l);

//Ajoute la clé k à la liste 
//  pointée par l
//Si l==NULL, alors une nouvelle liste
//  cyclique est crée
//Renvoi vrai si l'ajout a été effectué
//       faux sinon
bool dl_ajout(int k, dl** l);

//Retire la cellule contenant la clé k
//  dans la liste pointée par l
//Si la première cellule est modifiée, ce
//  changement est répercuté sur l
//Renvoi vrai si la cellule a été retirée
//       faux sinon
bool dl_retire(int k, dl** l);

dl* dl_pres(int k, dl* l){
  if(l==NULL){
    return NULL;
  }
  dl* tmp = l;
  while(tmp != NULL){
    if(tmp->data == k){
      return tmp;
    }
    tmp = tmp->next;
  }
  return NULL;
}

bool dl_ajout(int k, dl** l){
  dl* tmp = (dl*) malloc(sizeof(dl));
  if(tmp == NULL){
    return false;
  }
  tmp->data = k;
  tmp->next = *l;
  tmp->prev = NULL;
  if(*l != NULL){
    (*l)->prev = tmp;
  }
  *l = tmp;
  return true;
}

bool dl_retire(int k, dl** l){
  dl* tmp = dl_pres(k,*l);
  if(tmp == NULL){
    return false;
  }
  if(tmp->prev != NULL){
    tmp->prev->next = tmp->next;
  }else{
    *l = tmp->next;
  }
  if(tmp->next != NULL){
    tmp->next->prev = tmp->prev;
  }
  free(tmp);
  return true;
}

int main(int argc, char** argv){

  dl* l = NULL;
  assert(dl_ajout(1,&l));
  assert(dl_pres(1,l));
  assert(!dl_pres(2,l));
  assert(dl_retire(1,&l));
  assert(l == NULL);
  
  for(int i =0; i<10; i++){
    assert(dl_ajout(i,&l));
  }

  for(int i =0; i<10; i++){
    assert(dl_pres(i,l));
  }

  for(int i=0; i<10; i++){
    assert(dl_retire(i,&l));
    for(int j=0; j<=i; j++){
      assert(!dl_pres(j,l));
    }
    for(int j=i+1; j<10; j++){
      assert(dl_pres(j,l));
    }
  }

  assert(l == NULL);

  return EXIT_SUCCESS;
  argc = argc;
  argv = argv;
}