#include <stdio.h>
#include <stdlib.h>
#define new(t) malloc(sizeof(t))
#define assert(b) if (!(b)){ printf("erreur ligne %d\n", __LINE__); exit(1); }
struct arbre234 {
  int num;
  struct arbre234 * node[4];
  void * key[3];
};
void split4(struct arbre234 *ar, struct arbre234 **b, struct arbre234 **c, void **k){
  assert(ar->num == 4);
  *k = ar->key[1];
  *b = new(struct arbre234);
  *c = new(struct arbre234);
  b[0]->num = 2;
  c[0]->num = 2;
  b[0]->node[0] = ar->node[0];
  b[0]->node[1] = ar->node[1];
  c[0]->node[0] = ar->node[2];
  c[0]->node[1] = ar->node[3];
  b[0]->key[0] = ar->key[0];
  c[0]->key[0] = ar->key[2];
}
void addKey(struct arbre234 *a, int n, void * val){
  int i;
  assert(a!= NULL && (a->num == 2 || a->num == 3));
  a->node[a->num] = NULL;
  for (i = a->num - 1 ; i>n; i--){
    a->key[i] = a->key[i-1];
  }
  a->key[n] = val;
  a->num ++ ;
}
void insert__(struct arbre234 *p, int n, struct arbre234 *a, int cmp(void*, void*), void * val){
  if (a == NULL){
    addKey(p, n, val);
    return;
  }
  assert(a->num == 2 || a->num == 3 || a->num == 4);
  if (a->num == 4){
    struct arbre234 *b, *c;
    void *k;
    int i;
    split4(a, &b, &c, &k);
    for (i=p->num ; i>n; i--)
      p->node[i] = p->node[i-1];
    for (i=p->num - 1 ; i>n; i--)
      p->key[i] = p->key[i-1];
    p->key[n] = k;
    p->node[n] = b;
    p->node[n+1] = c;
    p->num ++;
    free(a);
    if (cmp(val, k) == -1){
      insert__(p, 0, b, cmp, val);
    }else{
      insert__(p, 1, c, cmp, val);
    }
  }else{
    if (cmp(val, a->key[0]) == -1){
      insert__(a, 0, a->node[0], cmp, val);
    }else if (a->num == 2){
      insert__(a, 1, a->node[1], cmp, val);
    }else{
      if (cmp(val, a->key[1]) == -1){
    insert__(a, 1, a->node[1], cmp, val);
      }else{
    insert__(a, 2, a->node[2], cmp, val);
      }
    }
  }
}
void insert_(struct arbre234 *a, int cmp(void*, void*), void * val){
  assert(a != NULL); assert(a->num == 2 || a->num == 3);
  if ( cmp(val, a->key[0]) == -1 ){
    insert__(a, 0, a->node[0], cmp, val);
  }else{
    if (a->num == 2){
      insert__(a, 1, a->node[1], cmp, val);
    }else{
      if (cmp(val, a->key[1]) == -1 ){
    insert__(a, 1, a->node[1], cmp, val);
      }else{
    printf("%d > %d\n", *((int*)val), *((int*)a->key[1]) );
    insert__(a, 2, a->node[2], cmp, val);
      }
    }
  }
}
struct arbre234 * insert(struct arbre234 *a, int cmp(void*, void*), void * val){
  assert(a == NULL || a->num == 2 || a->num == 3 || a->num == 4);
  if (a == NULL || a->num == 0){
    struct arbre234 *ar = new(struct arbre234);
    ar->num = 2;
    ar->node[0] = NULL;
    ar->node[1] = NULL;
    ar->key[0] = val;
    return ar;
  }else if (a->num == 4){
    struct arbre234 *r = new(struct arbre234);
    r->num = 2;
    split4(a, &r->node[0], &r->node[1], &r->key[0]);
    insert_(r, cmp, val);
    free(a);
    return r;
  }else{
    insert_(a, cmp, val);
    return a;
  }
}
int cmpi(int a, int b){
  if (a == b) return 0;
  if (a < b) return -1;
  return 1;
}
int cmpip(void *a, void *b){
  return cmpi(*((int*)a), *((int*)b));
}
void spaces(int n){
  int i;
  for (i=0;i<n;i++) printf("   ");
}
void print_arbre(struct arbre234 *a, int t){
  int i;
  if (a == NULL) return;
  print_arbre(a->node[0], t+1);
  for (i=0;i<a->num-1;i++){
    spaces(t); printf("%d\n", * ((int*) a->key[i]));
    print_arbre(a->node[i+1], t+1);
  }
}
void free_tree(struct arbre234 *a){
  int i;
  if (a == NULL) return;
  for (i=0;i<a->num;i++)
    free_tree(a->node[i]);
  free(a);
}
int main(){
  struct arbre234 * ar = NULL;
  int tab[20] = {0,19,5,3,2,7,1,4,6,15,14,18,17,12,13};
  int i;
  for (i=0;i<20;i++){
    printf("insertion de %d\n", tab[i]);
    ar = insert(ar, cmpip, & tab[i] );
    print_arbre(ar, 0);
  }
  free_tree(ar);
  return 1;
}