/* Based on Data Structures and Algorithm Analysis in C (Second Edition)
 * by Mark Allen Weiss.
 *
 * Modified by Minlan Yu.
 */
#include <stdlib.h>
#include <stdio.h>

#include "tree.h"
#include "util.h"

#ifdef ENABLE_DMALLOC
#include <dmalloc.h>
#endif //ENABLE_DMALLOC

struct TreeNode * pmin;

SearchTree TreeMakeEmpty( SearchTree T ) {
  if( T != NULL ) {
    TreeMakeEmpty( T->Left );
    TreeMakeEmpty( T->Right );
    free( T );
    pmin = NULL;
  }
  return NULL;
}

Position TreeFind( int value, SearchTree T ) {
  if( T == NULL ) return NULL;
  if( value < T->Element.l1num ) {
    return TreeFind( value, T->Left );
  } else {
    if( value > T->Element.l1num ) {
      return TreeFind(value, T->Right );
    } else {
      return T;
    }
  }
}

Position TreeFindMin( SearchTree T ) {
  if (pmin != NULL) return pmin;
  if( T == NULL ) {
    return NULL;
  } else {
    if( T->Left == NULL ) {
      return T;
    } else {
      return TreeFindMin( T->Left );
    }
  }
}

Position TreeFindMax( SearchTree T ) {
  if( T != NULL ) {
    while( T->Right != NULL ) {
      T = T->Right;
    }
  }
  return T;
}

SearchTree TreeInsert( TreeElementType X, SearchTree T ) {
  if (pmin!= NULL && X.l1num < pmin->Element.l1num) pmin = NULL;
  if( T == NULL ) {
    /* Create and return a one-node tree */
    T = malloc( sizeof( struct TreeNode ) );
    if( T == NULL ) {
      perror( "Out of space!!!" );
    } else {
      T->Element = X;
      T->Left = T->Right = NULL;
    }
  } else {
    if( X.l1num < T->Element.l1num ) {
      T->Left = TreeInsert( X, T->Left );
    } else {
      if( X.l1num > T->Element.l1num ) {
        T->Right = TreeInsert( X, T->Right );
      }
      /* Else X is in the tree already; we'll do nothing */
    }
  }
  return T;  /* Do not forget this line!! */
}

SearchTree TreeDelete( TreeElementType X, SearchTree T ) {
  Position TmpCell;
            
  if (pmin != NULL && X.l1num == pmin->Element.l1num) pmin = NULL;

  if( T == NULL ) {
    perror( "Element not found" );
  } else {
    if( X.l1num < T->Element.l1num ) {
      /* Go left */
      T->Left = TreeDelete( X, T->Left );
    } else {
      if( X.l1num > T->Element.l1num ) {
        /* Go right */
        T->Right = TreeDelete( X, T->Right );
      } else {
        /* Found element to be deleted */
        if( T->Left && T->Right ) {
          /* Two children */
          /* Replace with smallest in right subtree */
          TmpCell = TreeFindMin( T->Right );
          T->Element = TmpCell->Element;
          T->Right = TreeDelete( T->Element, T->Right );
        } else {
          /* One or zero children */
          TmpCell = T;
          if( T->Left == NULL ) {
            /* Also handles 0 children */
            T = T->Right;
          } else {
            if( T->Right == NULL ) {
              T = T->Left;
            }
          }
          free( TmpCell );
        }
      }
    }
  }

  return T;
}

TreeElementType Retrieve( Position P ) {
  return P->Element;
}