#include <stdio.h>

#include "common.h"

void rkdtree_split(rkdnode_t *TN,
		   int *x,
		   int i,
		   rkdnode_t **L,
		   rkdnode_t **R)
{
  printf("Entering rkdtree_split()\n");

  *L = *R = NULL;

  /* Empty tree */
  if ( TN == NULL )
    return;
  else
    {
      int *y = TN->key;
      unsigned int j = TN->disc;

      /* Same discriminant */
      if ( i == j )
	{
	  if ( y[i] < x[i] )
	    {
	      printf("i = j and y(i) < x(i)\n");
	      *L = TN;
	      rkdnode_t *tmp;
	      rkdtree_split(TN->R, x, i, &tmp, R);
	      rkdnode_set_r_child(*L, tmp);
	    }
	  else
	    {
	      printf("i = j and y(i) > x(i)\n");
	      *R = TN;
	      rkdnode_t *tmp;
	      rkdtree_split(TN->L, x, i, L, &tmp);
	      rkdnode_set_l_child(*R, tmp);
	    }
	}
      /* Different discriminants */
      else
	{
	  rkdnode_t *L_l, *L_r, *R_l, *R_r;

	  rkdtree_split(TN->L, x, i, &L_l, &L_r);
	  rkdtree_split(TN->R, x, i, &R_l, &R_r);

	  if ( y[i] < x[i] )
	    {
	      printf("i != j and y(i) < x(i)\n");
	      *L = TN;
	      rkdnode_set_children(*L, L_l, R_l);
	      *R = rkdtree_join(L_r, R_r, j);
	    }
	  else
	    {
	      printf("i != j and y(i) > x(i)\n");
	      *R = TN;

	      rkdnode_set_children(*R, L_r, R_r);
	      *L = rkdtree_join(L_l, R_l, j);
	    }
	}

    }  
}

rkdnode_t *rkdtree_join(rkdnode_t *A, rkdnode_t *B, unsigned int i)
{
  printf("Entering rkdtree_join()\n");
  if ( A == NULL )
    {
      if ( B == NULL )
	return NULL;
      else
	return B;
    }
  else if ( B == NULL )
    return A;
  
  rkdnode_t *T = NULL;

  /* A becomes root (probability of n/(n+m)) */
  if ( (random() % (A->elem_count + B->elem_count)) < A->elem_count )
    {
      T = A;
      unsigned int j_a = A->disc;

      if ( i == j_a )
	rkdnode_set_r_child(A, rkdtree_join(A->R, B, i));
      else
	{
	  rkdnode_t *B_l, *B_r;
	  rkdtree_split(B, A->key, j_a, &B_l, &B_r);
	  rkdnode_set_children(A,
			       rkdtree_join(A->L, B_l, i),
			       rkdtree_join(A->R, B_r, i));
	}
    }
  /* B becomes root */
  else
    {
      T = B;
      unsigned int j_b = B->disc;
      
      if ( i == j_b )
	rkdnode_set_l_child(B, rkdtree_join(A, B->L, i));
      else
	{
	  rkdnode_t *A_l, *A_r;
	  rkdtree_split(A, B->key, j_b, &A_l, &A_r);
	  rkdnode_set_children(B,
			       rkdtree_join(A_l, B->L, i),
			       rkdtree_join(A_r, B->R, i));
	}
    }

  return T;
}