#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;
}

type 'a arbre = Nil
  | D of 'a arbre * 'a * 'a arbre
  | T of 'a arbre * 'a * 'a arbre * 'a * 'a arbre
  | Q of 'a arbre * 'a * 'a arbre * 'a * 'a arbre * 'a * 'a arbre;;
let split4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> (D(a1, k1, a2), k2, D(a3, k3, a4) )
| _ -> failwith("split 4") ;;
let i4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> true
| _ -> false ;;
(* O(ln n) *)
let rec insert cmp v = function
| Nil -> failwith("insert")
| Q(a1, k1, a2, k2, a3, k3, a4) -> D(D(a1, k1, a2), k2, D(a3, k3, a4)) (*head*)
| D(Nil, k, Nil) -> if cmp v k = -1
  then T(Nil, v, Nil, k, Nil)
  else T(Nil, k, Nil, v, Nil)
| T(Nil, k1, Nil, k2, Nil) -> if cmp v k1 = -1
  then Q(Nil, v, Nil, k1, Nil, k2, Nil)
  else if cmp v k2 = 1
    then Q(Nil, k1, Nil, k2, Nil, v, Nil)
    else Q(Nil, k1, Nil, v, Nil, k2, Nil)
| D(a1, k1, a2) -> if cmp v k1 = -1
  then if i4 a1
    then let (a1', k1', a1'') = split4 a1
      in insert cmp v (T (a1', k1', a1'', k1, a2))
    else D (insert cmp v a1, k1, a2)
  else if i4 a2
    then let (a2', k2', a2'') = split4 a2
      in insert cmp v (T (a1, k1, a2', k2', a2''))
    else D (a1, k1, insert cmp v a2)
| T(a1, k1, a2, k2, a3) -> if cmp v k1 == -1
  then if i4 a1
    then let (a1', k1', a1'') = split4 a1 in if cmp v k1' = 1
      then Q (a1', k1', insert cmp v a1'', k1, a2, k2, a3)
      else Q (insert cmp v a1', k1', a1'', k1, a2, k2, a3)
    else T(insert cmp v a1, k1, a2, k2, a3)
  else if cmp v k2 = 1
    then if i4 a3
      then let (a3', k3', a3'') = split4 a3 in if cmp v k3' = 1
    then Q (a1, k1, a2, k2, a3', k3', insert cmp v a3'')
    else Q (a1, k1, a2, k2, insert cmp v a3', k3', a3'') 
      else T(a1, k1, a2, k2, insert cmp v a3)
    else if i4 a2
      then let (a2', k2', a2'') = split4 a2 in if cmp v k2' = 1
    then Q (a1, k1, a2', k2', insert cmp v a2'', k2, a3)
    else Q (a1, k1, insert cmp v a2', k2', a2'', k2, a3)
      else T(a1, k1, insert cmp v a2, k2, a3);;
let insert cmp v tree = if tree = Nil then D(Nil, v, Nil) else insert cmp v tree;;
let cmp_i a b = if a < b then -1 else if a = b then 0 else 1;;
let insert_i = insert cmp_i;;
(* O(ln n) *)
let rec search cmp v = function
| Nil -> None
| D (a1, k1, a2) -> let c = cmp v k1 in
  if c = 0 then Some k1 else search cmp v (if c = 1 then a2 else  a1)
| T(a1, k1, a2, k2, a3) -> let c = cmp v k1 in
  if c = 0 then Some k1 else if c = -1 then search cmp v a1
  else search cmp v (D(a2, k2, a3))
| Q(a1, k1, a2, k2, a3, k3, a4) -> let c = cmp v k2 in
  if c = 0 then Some k2 else if c = -1
    then search cmp v (D(a1, k1, a2))
    else search cmp v (D(a3, k3, a4));;
(* O(n) <=> O(2^p) *)
let arbre2li =
let rec i acc= function
| Nil -> acc
| D(a1, k1, a2) -> i (k1::(i acc a2)) a1
| T(a1, k1, a2, k2, a3) -> i (k1::(i acc (D(a2, k2, a3)) )) a1
| Q(a1, k1, a2, k2, a3, k3, a4) -> i (k1::(i acc (T(a2, k2, a3, k3, a4)))) a1
in i [];;