/*
Brian St.Amour
COP 3502
Program 5
4/1/11
*/

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


typedef struct buddyList{
        int buddy;
        struct buddyList *next;
} buddies;


typedef struct tree_node{
       int ID;
       char firstName[21];
       char lastName[21];
       int age;
       buddies *myBuddies;
       struct tree_node *left;
       struct tree_node *right;
} BSTnode;


BSTnode* create_node(int val, char first[], char last[], int age);
BSTnode* insert(BSTnode *root, BSTnode *element);
BSTnode* findID(BSTnode *ptr, int val);
BSTnode* findNAME(BSTnode *ptr, char first[], char last[]);
BSTnode* parent(BSTnode *root, BSTnode *node);
BSTnode* maxVal(BSTnode *root);
buddies* insertBuddyNode(buddies *ptr, int value);
buddies* deleteBuddyNode(buddies *ptr, int value);
void addBuddies(BSTnode *ptr, char last[], char first[], char last2[], char first2[]);
void unbuddy(BSTnode *ptr, char last[], char first[], char last2[], char first2[]);
void printNodeID(BSTnode *ptr, int ID, int num);
void printNodeName(BSTnode *ptr, char first[], char last[], int num);
void printBuddies(buddies *ptr);
void inorder(BSTnode *ptr, FILE*);
int compare(int ID, buddies *ptr);
int isLeaf(BSTnode *node);
int hasOnlyLeftChild(BSTnode *node);
int hasOnlyRightChild(BSTnode *node);
int count(buddies *ptr);

FILE *ifp, *ofp;
BSTnode* root = NULL;


/**********************************************************************
 * main                                                               *
 *                                                                    *
 *                                                                    *
 *                                                                    *
 **********************************************************************/

int main(void)
{

    int i, j, k, ID, age, num;
    char command[10], fName[21], lName[21], fName2[21], lName2[21];
    BSTnode* temp_node;
    BSTnode* temp_node1;
    BSTnode* parent_node;
    BSTnode* maxNode;

      ifp = fopen("buddyBook.in", "r");
      ofp = fopen("buddyBook.out", "w");
      if (ifp == NULL) {
            printf("Error reading file.\n");
            system("pause");
        return 1;
      }

      if (ofp == NULL) {
        printf("File does not exist.\n");
        system("pause");
        return 1;
      }

    fscanf(ifp, "%d", &k);

    for(i = 0; i < k; i++)
    {
       fscanf(ifp , "%s", command);

       if(strcmp(command, "ADD") == 0)
       {
            fscanf(ifp, "%d%s%s%d", &ID, fName, lName, &age);
            if(age < 13)
            {
                fprintf(ofp, "%s %s rejected - You must be 13 or over to create a profile.", fName, lName);
            }

            else
            {
                 temp_node = (BSTnode*) create_node(ID, fName, lName, age);
                 root = insert(root, temp_node);
                 fprintf(ofp, "Added %s %s, age %d", temp_node->firstName, temp_node->lastName, temp_node->age);
            }
       }


       else if (strcmp(command, "FINDNAME") == 0)
       {
            fscanf(ifp, "%s%s", fName, lName);
            temp_node = findNAME(root, fName, lName);
            printNodeName(temp_node, fName, lName, count(temp_node->myBuddies));
       }


       else if(strcmp(command, "FINDID") == 0)
       {
            fscanf(ifp, "%d", &ID);
            temp_node = findID(root, ID);
            printNodeID(temp_node, ID, count(temp_node->myBuddies));
       }


       else if(strcmp(command, "BUDDY") == 0)
       {
            fscanf(ifp, "%s%s%s%s", fName, lName, fName2, lName2);
            temp_node = (BSTnode*)findNAME(root, fName, lName);
            temp_node1 = (BSTnode*)findNAME(root, fName, lName);

            if(compare(temp_node->ID, temp_node1->myBuddies) == 1)
            {
                 fprintf(ofp, "Cannot Perform BUDDY Command:\n\t %s %s %s %s are already buddies.", fName, lName, fName2, lName2);
            }

            else if(findNAME(root, fName, lName) == NULL && findNAME(root, fName2, lName2) == NULL)
            {
                 fprintf(ofp, "Cannot Perform BUDDY Command:\n\t %s %s - This profile does not exist.\n\t %s %s - This profile does not exist.", fName, lName, fName2, lName2);
            }

            else if(findNAME(root, fName, lName) == NULL)
            {
                 fprintf(ofp, "Cannot Perform BUDDY Command:\n\t %s %s - This profile does not exist.", fName, lName);
            }
            else if(findNAME(root, fName2, lName2) == NULL)
            {
                 fprintf(ofp, "Cannot Perform BUDDY Command:\n\t %s %s - This profile does not exist.", fName2, lName2);
            }

            else
            {
                addBuddies(root, lName, fName, lName2, fName2);
                fprintf(ofp, "%s %s and %s %s are now Buddies.\n", fName, lName, fName2, lName2);
            }
       }


       else if(strcmp(command, "UNBUDDY") == 0)
       {
            fscanf(ifp, "%s%s%s%s", fName, lName, fName2, lName2);
            temp_node = (BSTnode*)findNAME(root, fName, lName);
            temp_node1 = (BSTnode*)findNAME(root, fName, lName);

            if(compare(temp_node->ID, temp_node1->myBuddies) != 1)
            {
                 fprintf(ofp, "Cannot Perform UNBUDDY Command:\n\t %s %s and %s %s are not Buddies.", fName, lName, fName2, lName2);
            }

            else if(findNAME(root, fName, lName) == NULL && findNAME(root, fName, lName) == NULL)
            {
                 fprintf(ofp, "Cannot Perform UNBUDDY Command:\n\t %s %s - This profile does not exist.\n\t %s %s - This profile does not exist.", fName, lName, fName2, lName2);
            }

            else if(findNAME(root, fName, lName) == NULL)
            {
                 fprintf(ofp, "Cannot Perform UNBUDDY command:\n\t %s %s - This profile does not exist.", fName, lName);
            }

            else if(findNAME(root, fName2, lName2) == NULL)
            {
                 fprintf(ofp, "Cannot Perform UNBUDDY command:\n\t %s %s - This profile does not exist.", fName2, lName2);
            }

            else
            {
                 unbuddy(root, lName, fName, lName2, fName2);
                 fprintf(ofp, "%s %s and %s %s are no longer Buddies.\n", fName, lName, fName2, lName2);
            }

       }


       else if(strcmp(command,"DELETE") == 0)
       {
            fscanf(ofp, "%s%s", fName, lName);
            temp_node = findNAME(root, fName, lName);
            if(temp_node == NULL) fprintf(ofp, "Cannot delete %s %s.\n", fName, lName);
            else
            {
                if(isLeaf(temp_node))
                {
                     parent_node = (BSTnode*)malloc(sizeof(BSTnode));
                     parent_node = (BSTnode*)parent(root, temp_node);
                     if(temp_node->ID > parent_node->ID)
                     {
                          free(parent_node->right);
                          parent_node->right = NULL;
                     }

                     else
                     {
                          free(parent_node->left);
                          parent_node->left = NULL;
                     }

                }
                else if(hasOnlyLeftChild(temp_node))
                {
                     parent_node = (BSTnode*)malloc(sizeof(BSTnode));
                     parent_node = (BSTnode*)parent(root, temp_node);

                     if(temp_node->ID > parent_node->ID)
                     {
                         parent_node->right = parent_node->right->left;
                         free(temp_node);
                     }

                     else
                     {
                         parent_node->left = parent_node->left->right;
                         free(temp_node);
                     }
                }

                else if(hasOnlyRightChild(temp_node))
                {
                     parent_node = (BSTnode*)malloc(sizeof(BSTnode));
                     parent_node = (BSTnode*)parent(root, temp_node);

                     if(temp_node->ID > parent_node->ID)
                     {

                         parent_node->right = parent_node->right->right;
                         free(temp_node);
                     }

                     else
                     {
                          parent_node->left = parent_node->left->right;
                          free(temp_node);
                     }
                }

                else if(hasOnlyRightChild(temp_node) && hasOnlyLeftChild(temp_node))
                {
                     parent_node = (BSTnode*)malloc(sizeof(BSTnode));
                     maxNode = (BSTnode*)malloc(sizeof(BSTnode));
                     parent_node = (BSTnode*)parent(root, temp_node);
                     maxNode = (BSTnode*)maxVal(temp_node);

                     if(temp_node->ID < parent_node->ID);
                     {
                          maxNode->right = maxNode->left;
                          maxNode->left = temp_node->left;
                          parent_node->left = parent_node->left->right;
                          free(temp_node);
                     }

                }
            }

       }


       else if(strcmp(command,"PRINTBUDDIES") == 0)
       {
            fscanf(ifp, "%s%s", fName, lName);
            temp_node = findNAME(root, fName, lName);
            num = count(temp_node->myBuddies);

            if(num == 0) fprintf(ofp, "%s %s has no Buddies;\n", fName, lName);
            if(num != 1)
            {
                   fprintf(ofp, "%s %s has %d Buddies:\n", fName, lName, num);
                   printBuddies(temp_node->myBuddies);
            }
            else
            {
                   fprintf(ofp, "%s %s has 1 Buddy:\n", fName, lName);
                   printBuddies(temp_node->myBuddies);
            }


       }


       else if(strcmp(command, "PRINTTREE") == 0)
       {
            if(root != NULL){
                    fprintf(ofp, "Members of Buddy Book:\n");
            inorder(root, ofp);
            }
       }



    }

return 1;
}



BSTnode* create_node(int val, char first[], char last[], int age)
{
       BSTnode* temp;
       temp = (BSTnode*)malloc(sizeof(BSTnode));

       temp->ID = val;
       strcpy(temp->firstName, first);
       strcpy(temp->lastName, last);
       temp->left = NULL;
       temp->age = age;
       temp->right = NULL;

return temp;
}



BSTnode* insert(BSTnode *root, BSTnode *element)
{
       if (root == NULL)
          return element;
       else
       {
           if (element->ID > root->ID)
                root->right = insert(root->right, element);
           else
                root->left = insert(root->left, element);
           return root;
       }
}



BSTnode* findID(struct tree_node *ptr, int val)
{
    if (ptr != NULL)
    {
         if (ptr->ID == val) return ptr;
         if (val < ptr->ID) return findID(ptr->left, val);
         else return findID(ptr->right, val);
    }
    else

    return NULL;
}



BSTnode* findNAME(BSTnode *ptr, char first[], char last[])
{
    if (ptr != NULL)
    {
         if (strcmp(ptr->lastName, last))
         {
              if(strcmp(ptr->firstName, first)) return ptr;
              else return NULL;
         }

         if(strcmp(ptr->lastName, last) > 0) return findNAME(ptr->left, first, last);
         else return findNAME(ptr->right, first, last);
    }
    else
    return NULL;
}



void addBuddies(BSTnode *ptr, char last[], char first[], char last2[], char first2[])
{
     BSTnode *temp, *temp1;
     if (ptr != NULL)
     {
          temp = findNAME(ptr, first, last);
          temp1 = findNAME(ptr, first2, last2);
          insertBuddyNode(temp->myBuddies, temp1->ID);
          insertBuddyNode(temp1->myBuddies, temp->ID);
     }

}



void unbuddy(BSTnode *ptr, char last[], char first[], char last2[], char first2[])
{
     BSTnode *temp, *temp1;
     if(ptr != NULL)
     {
            temp = findNAME(ptr, first, last);
            temp1 = findNAME(ptr, first2, last2);
            deleteBuddyNode(temp->myBuddies, temp1->ID);
            deleteBuddyNode(temp1->myBuddies, temp->ID);
     }
}



buddies* insertBuddyNode(buddies *ptr, int value)
{
       buddies *help_ptr = ptr;
       buddies *pNew = (buddies*)malloc(sizeof(buddies));
       pNew->buddy = value;
       pNew->next = NULL;

       if (ptr == NULL || ptr->buddy > value)
       {
               pNew->next = ptr;
               ptr = pNew;
               return ptr;
       }

       while(help_ptr->next != NULL && help_ptr->next->buddy < value)
       {
            help_ptr = help_ptr->next;
            pNew->next = help_ptr->next;
            help_ptr->next = pNew;
            return ptr;
       }

}



buddies* deleteBuddyNode(buddies *ptr, int value)
{
         buddies *help_ptr = ptr;
         buddies *node2delete;

         if (help_ptr != NULL)
         {
              if(help_ptr->buddy == value)
              {
                   ptr = help_ptr->next;
                   free(help_ptr);
                   return ptr;
              }

             while (help_ptr->next != NULL)
             {
                   if(help_ptr->next->buddy == value)
                   {
                        node2delete = help_ptr->next;
                        help_ptr->next = help_ptr->next->next;
                        free(node2delete);
                        return ptr;
                   }
                   help_ptr = help_ptr->next;
             }
         }
         return ptr;
}



void printNodeID(BSTnode *ptr, int ID, int num)
{
     if(ptr != NULL)
     {
          if(num != 1)
          fprintf(ofp, "Found: %s %s, age %d, %d Buddies\n", ptr->firstName, ptr->lastName, ptr->age, num);

          else
          fprintf(ofp, "Found: %s %s, age %d, 1 Buddy\n", ptr->firstName, ptr->lastName, ptr->age);
     }

     else fprintf(ofp, "ID %d not found.\n", ID);
}



void printNodeName(BSTnode *ptr, char first[], char last[], int num)
{
     if(ptr != NULL)
     {
          if(num != 1)
          fprintf(ofp, "Found: %s %s, age %d, %d Buddies\n", ptr->firstName, ptr->lastName, ptr->age, num);

          else
          fprintf(ofp, "Found: %s %s, age %d, 1 Buddy\n", ptr->firstName, ptr->lastName, ptr->age);
     }

     else fprintf(ofp, "%s %s not found.\n", first, last);
}



void printBuddies(buddies *ptr)
{
     buddies *help_ptr;
     BSTnode* temp;
     temp = (BSTnode*)malloc(sizeof(BSTnode));
     help_ptr = ptr;

     while(help_ptr != NULL)
     {
          temp = findID(root, help_ptr->buddy);
          fprintf(ofp, "\t%s %s", temp->firstName, temp->lastName);
          help_ptr = help_ptr->next;
     }
}



void inorder(BSTnode *ptr, FILE *ofp)
{

  if (ptr != NULL) {
    inorder(ptr->left, ofp);
    fprintf(ofp, "\t%s %s, age %d, %d Buddies\n", ptr->firstName, ptr->lastName, ptr->age, count(ptr->myBuddies));
    inorder(ptr->right, ofp);
  }
}



int compare(int ID, buddies *ptr)
{
    buddies *help_ptr;
    help_ptr = ptr;

    while(help_ptr != NULL)
    {
         if (help_ptr->buddy == ID) return 1;
         help_ptr = help_ptr->next;
    }
return 0;
}



BSTnode* parent(BSTnode *root, BSTnode *node)
{
       if (root == NULL || root == node) return NULL;
       if (root->left == node || root->right == node) return root;
       if (node->ID < root->ID) return parent (root->left, node);
       else if (node->ID > root->ID) return parent(root->right, node);

       return NULL;
}



int isLeaf(BSTnode *node)
{
    return (node->left == NULL && node->right == NULL);
}



int hasOnlyLeftChild(BSTnode *node)
{
    return (node->left != NULL && node->right == NULL);
}



int hasOnlyRightChild(BSTnode *node)
{
    return (node->left == NULL && node->right != NULL);
}



BSTnode* maxVal(BSTnode *root)
{
    if (root->right == NULL) return root;
    else return maxVal(root->right);
}


int count(buddies *ptr)
{
     int i;

     for(i = 0; ptr != NULL; i++)
     {
          ptr = ptr->next;
     }
 return i;
}