/*------------------------------------------------*
 | File: btree.c - Binary tree routines for sort. |
 | v1.00 MLO 911226 - see the comments in sort.c  |
 *------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mlo.h"
#include "sort.h"

extern short int abortProg;
extern Boolean reverse;
extern FILE *fp;
extern Node *root;

#ifndef SIMPLE
extern char *temp1;
#endif

#ifdef BALANCED_TREE
extern Node *critical, *father;
static short int sign(int x);
#endif

void FreeTree(
  Node *pN
){

/**
 | Frees (recursively) the binary tree, at node pointed to by pN.
**/

  if (pN->left != NULL)   FreeTree(pN->left);
  if (pN->right != NULL)  FreeTree(pN->right);
  free(pN);
}

Node *InsertTree(
  char *buffer,
  Node *pN
){

/**
 | Inserts (recursively) the string "buffer" in the binary tree; see
 | the comments in sort.c about the balanced binary tree algorithm.
**/

#ifdef BALANCED_TREE

  if (pN != NULL) {

/**
 | This node is not empty; compare our string with the one
 | related to this node, and follow right or left branch -
 | or bump the node counter if the strings are identical (if
 | so, the tree is already balanced since no new nodes has been
 | created; if not, alter the balance count in this node toward
 | right or left). For the balancing algorithm, we need to know
 | the last node having a non-zero balance factor, and his father.
**/
    short int z;

    if ((z = Compare(buffer, pN->line)) == 0) {
      (pN->count)++;
      critical = NULL;
    } else {
      if (pN->balance)    critical = pN;
      if (z < 0) {
        if (pN->left != NULL   &&   pN->left->balance)    father = pN;
        pN->left = InsertTree(buffer, pN->left);
      } else {
        if (pN->right != NULL   &&   pN->right->balance)  father = pN;
        pN->right = InsertTree(buffer, pN->right);
      }
    }
  } else {

/**
 | We are at the end of the binary tree; a new node
 | must be inserted here.
**/

    if ((pN = malloc(sizeof(Node)+strlen(buffer))) == NULL) {
      puts("sort: couldn't obtain heap memory.");
      FreeTree(root);
      if (temp1 != NULL) free(temp1);
      if (fp != NULL) fclose(fp);
      exit(SYS_ABORT_CODE);
    }
    strcpy(pN->line, buffer);
    pN->balance = 0;
    pN->count   = 1;
    pN->left    = NULL;
    pN->right   = NULL;
  }
  return pN;

#else

/**
 | Unbalanced binary tree algorithm.
**/

  if (pN != NULL) {
    short int z;

#ifdef SIMPLE
    if ((z = strcmp(buffer, pN->line)) == 0) {
#else
    if ((z = Compare(buffer, pN->line)) == 0) {
#endif

      (pN->count)++;
    } else if (z < 0) {
      pN->left = InsertTree(buffer, pN->left);
    } else {
      pN->right = InsertTree(buffer, pN->right);
    }
  } else {
    if ((pN = malloc(sizeof(Node)+strlen(buffer))) == NULL) {
      puts("sort: couldn't obtain heap memory.");
      FreeTree(root);

#ifndef SIMPLE
      if (temp1 != NULL) free(temp1);
#endif

      if (fp != NULL) fclose(fp);
      exit(SYS_ABORT_CODE);
    }
    strcpy(pN->line, buffer);
    pN->count = 1;
    pN->left  = NULL;
    pN->right = NULL;
  }
  return pN;

#endif
}

void PrintTree(
  Node *pN
){

/**
 | Prints (recursively) the binary tree, at node pointed to by pN.
 | The allocated memory is also freed.
**/

  if (reverse) {
    if (pN->right != NULL) PrintTree(pN->right);
  } else {
    if (pN->left != NULL) PrintTree(pN->left);
  }

  if (!abortProg) {
    while ((pN->count)--) fputs(pN->line, stdout);
    CheckBreak(False);
  }

  if (reverse) {
    if (pN->left != NULL) PrintTree(pN->left);
  } else {
    if (pN->right != NULL) PrintTree(pN->right);
  }

  free(pN);
}

#ifdef BALANCED_TREE

void BalanceTree(
  char *key
)
{

/**
 | If the binary tree needs re-balancing (critical != NULL),
 | we rearrange the node ordering  so that the number of them
 | being in the right sub-tree and in the left sub-tree in
 | EVERY node differs at most by one. To obtain this, is
 | sufficient to start from *critical.
**/

  short int a, a0;
  Node *p = critical;
  Node *p0;

  if (critical == NULL) return;

  if ((a0 = Compare(key, p->line)) != 0) {
    a0 = sign(a0);
    p = p0 = (a0 > 0) ? p->right : p->left;
    while ((a = Compare(key, p->line)) != 0) {
      p->balance = (a = sign(a));
      p = (a > 0) ? p->right : p->left;
    }
  }

  if (a0   &&   critical->balance == a0) {
    if (p0->balance == a0) {
      p = p0;
      if (a0 > 0) {
        critical->right = p0->left;
        p0->left = critical;
      } else {
        critical->left = p0->right;
        p0->right = critical;
      }
      critical->balance = p0->balance = 0;
    } else if (p0->balance == -a0) {
      if (a0 > 0) {
        p = p0->left;
        p0->left = p->right;
        p->right = p0;
        critical->right = p->left;
        p->left = critical;
      } else {
        p = p0->right;
        p0->right = p->left;
        p->left = p0;
        critical->left = p->right;
        p->right = critical;
      }
      if (p->balance == 0) {
        critical->balance = p0->balance = 0;
      } else if (p->balance == a0) {
        critical->balance = -a0;
        p0->balance = 0;
      } else if (p->balance == -a0) {
        critical->balance = 0;
        p0->balance = a0;
      }
      p->balance = 0;
    }
    if (father == NULL) {
      root = p;
    } else if (critical == father->right) {
      father->right = p;
    } else {
      father->left = p;
    }
  } else {
    critical->balance += a0;
  }
}

static short int sign(
  int x
){

/**
 | "sign" function
**/

  if (x > 0)          return  1;
    else if (x < 0)   return -1;
    else              return  0;
}

#endif