/* Tree.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Tree.h"
static Tree MkBranch(Tree left, int value, Tree right) {
    TreeNode * result = malloc( sizeof( TreeNode ) );
    if ( result == NULL )
         fprintf(stderr, "MkBranch(%d): no memory available.\n", value);
    else { 
         result->data = value;
         result->leftPtr = left;
         result->rightPtr = right;
    }
    return result;
}
void treeInsert( Tree * t, int value )
{ 
   if ( *t == NULL ) { *t = MkBranch( NULL, value, NULL ); }
   else {
      if ( value < (*t)->data ) {
         treeInsert( &( (*t)->leftPtr ), value );
      }
      else if ( value > (*t)->data ) {
         treeInsert( &( (*t)->rightPtr ), value );
      }
      else {} /*@{}@XPC{@CP style {symbol} {value == (*t)->data} --- ignore duplicate values}*/
   }
}
void treeInsertIter( Tree * t, int value )
{
   while ( *t != NULL && value != (*t)->data ) {
      if ( value < (*t)->data ) {
         t = &( (*t)->leftPtr );
      }
      else /*@{}@XPC{@CP style {symbol} {value > (*t)->data}}*/ {
         t = &( (*t)->rightPtr );
      }
   }
   if ( *t == NULL ) { *t = MkBranch( NULL, value, NULL ); }
   else {} /*@{}@XPC{@CP style {symbol} {value == (*t)->data} --- ignore duplicate values}*/
}
void inOrder( Tree t ) {
   if ( t != NULL ) { inOrder( t->leftPtr );
		      printf( "%3d", t->data );
		      inOrder( t->rightPtr );      }
}

void preOrder( Tree t ) {
   if ( t != NULL ) { printf( "%3d", t->data );
		      preOrder( t->leftPtr );
		      preOrder( t->rightPtr );   }
}

void postOrder( Tree t ) {
   if ( t != NULL ) { postOrder( t->leftPtr );
		      postOrder( t->rightPtr );
		      printf( "%3d", t->data );    }
}
int treeSize( Tree t ) {
   if ( t == NULL ) return 0;
   else return treeSize( t->leftPtr ) + 1 + treeSize ( t->rightPtr );
}
void treeAddSizeToCounter( Tree t, int * count ) {
   if ( t == NULL ) return;
   else { (*count)++;
              treeAddSizeToCounter( t->leftPtr, count );
              treeAddSizeToCounter( t->rightPtr, count );
   }
}
int treeSize2( Tree t ) {
  int count = 0;
  treeAddSizeToCounter( t, &count );
  return count;
}
bool treeMember( Tree t, int q ) {
   if ( t == NULL ) return false;
   if ( q < t->data ) return treeMember ( t->leftPtr, q);
   if ( q > t->data ) return treeMember ( t->rightPtr, q);
   return true;                                  // because here q == t->data
}
bool treeMemberIter( Tree t, int q ) {
   while ( t != NULL && q != t->data )
      if ( q < t->data ) t = t->leftPtr;
      else               t = t->rightPtr;
   return t != NULL;                     // because then  q == t->data
}
static Tree cutOffLargestNode(Tree * t) {
  Tree result;
  if ( *t == NULL ) return NULL;       /* refine specification! */
  else if ( (*t)->rightPtr != NULL )   /* not yet found */
    return cutOffLargestNode( &( (*t)->rightPtr ) );
  else { /*@{}@XPC{@CP style {symbol} {( (*t)->rightPtr == NULL )} --- @B {found largest node}}*/
    result = *t;                       /* remembered largest node */
    *t = result->leftPtr;              /* redirected in-edge */
    result->leftPtr = NULL;            /* deleted out-edge */
    return result;
  }
}
void treeDelete( Tree * t, int value ) {
  Tree delNode;
  while ( *t != NULL && value != (*t)->data )
    if ( value < (*t)->data ) t = &( (*t)->leftPtr );
    else                              t = &( (*t)->rightPtr );
  if ( *t == NULL ) return;
  else { /*@{}@XPC{ @CP style {symbol} {value == (*t)->data}}*/
    delNode = *t;
    if          ( (*t)->leftPtr == NULL )  *t = (*t)->rightPtr;
    else if ( (*t)->rightPtr == NULL ) *t = (*t)->leftPtr;
    else { /* two succesors */
      delNode = cutOffLargestNode( &( (*t)->leftPtr ) );
      (*t)->data = delNode->data;
    }
    free( delNode );
  }
}