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

#include "rkdtree.h"
#include "rkdnode.h"
#include "common.h"

#include "insert.h"

/**
 * Given a node, insert it as root of the (sub)tree
 */
static rkdnode_t *rkdtree_insert_at_root(rkdnode_t *TN, rkdnode_t *N)
{
  printf("Entering rkdtree_insert_at_root()\n");
  /* Empty Tree */
  if ( TN == NULL )
    {
      printf(">> Insert it as leaf\n");
      TN = N;
    }
  else
    {
      TN->elem_count += 1;
      
      /* 1/1+n -> become root (+1?) */
      if ( random() % (TN->elem_count+1) == 0 )
	{
	  rkdnode_t *N_l, *N_r;
	  rkdtree_split(TN, N->key, N->disc, &N_l, &N_r);
	  rkdnode_set_children(N, N_l, N_r);
	  TN = N;
	}
      else
	{
	  int *y = TN->key;
	  int j = TN->disc;
	  int *x = N->key;
	  int i = N->disc;

	  if ( x[j] < y[j] )
	    {
	      printf("x goes left at y\n");
	      rkdnode_set_l_child(TN, rkdtree_insert_at_root(TN->L, N));
	    }
	  else
	    {
	      printf("x goest right at y\n");
	      rkdnode_set_r_child(TN, rkdtree_insert_at_root(TN->R, N));
	    }
	}

    }

  return TN;
}


/**
 * Given a key and data, insert it into tree T
 */
void rkdtree_insert(rkdtree_t *T,
		    int *key,
		    void *x)
{
  printf("Entering rkdtree_insert()\n");
  rkdnode_t *node = rkdnode_new(T->dim, key, x);

  T->root = rkdtree_insert_at_root(T->root, node);
}


rkdnode_t *rkdtree_remove_rec(rkdnode_t *TN,
			      int *key)
{
  if ( TN == NULL )
    return NULL;

  int *x = key;
  int *y = TN->key;
  unsigned int j = TN->disc;

  if ( x[j] < y[j] )
    rkdnode_set_l_child(TN, rkdtree_remove_rec(TN->L, x));
  else if ( y[j] < x[j] )
    rkdnode_set_r_child(TN, rkdtree_remove_rec(TN->R, x));
  else
    {
      rkdnode_t *TN_old = TN;
      TN = rkdtree_join(TN->L, TN->R, j);
      rkdnode_free(TN_old);
    }

  return TN;
}

/**
 * Given a key, delete corresponding node
 */
void rkdtree_remove(rkdtree_t *T,
		    int *key)
{
  printf("Entering rkdtree_remove()\n");
  
  T->root = rkdtree_remove_rec(T->root, key);
}