PartII_AB_AVL.cpp

/**********************************************************************************
* PART II.A+B: Binary Search Trees by Date and by Volume implemented as AVL trees *
**********************************************************************************/

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


FILE *fp; // Pointer to data file

struct dateVolume // Data record stored in binary tree node 
{  
    char Date[11];
    int Volume;
};
typedef struct dateVolume dataItem;

struct binaryTreeNode // Binary Search Tree node implemented as AVL tree node
{  
    dataItem data; 
    struct binaryTreeNode *left;
    struct binaryTreeNode *right;
    int height;
};
typedef struct binaryTreeNode btNode;

btNode *root = NULL; // Root of the tree initally empty

int (*cmpPtr)(dataItem, dataItem); // Pointer to compare functions


// Declaration of functions

void binaryTreeByDateMenu();
void binaryTreeByVolumeMenu();
void binaryTreeMenu();
void openFile(int argc, char *argv[]);
void readFileToBinTree();

btNode *createbtNode(dataItem x);
int btNodeHeight(btNode *r);
int btNodeBalance(btNode *r);
btNode *rotateL(btNode *r);
btNode *rotateR(btNode *r);

btNode *searchBinTree(btNode *r, char x[11]);
btNode *insertToBinTree(btNode *r, dataItem x);
btNode *deleteFromBinTree(btNode *r, char x[]);
void reportBinTree(btNode *r, int x);
btNode *minValuebtNode(btNode *r);
btNode *maxValuebtNode(btNode *r);

int max(int a, int b);
void inorderBinTree(btNode *r);
void printBinTree(btNode *r, int k);

int cmpDate(dataItem a, dataItem b);
int cmpVolumeDate(dataItem a, dataItem b);



int main(int argc, char *argv[])
{
    openFile(argc, argv); // Open input data file before any other action
    binaryTreeMenu();
    return 0;  
}


// Binary tree menu
void binaryTreeMenu()
{
    int selection;

    while (1)
    {
        printf("1. Read file to a Binary Search Tree by Date");
        printf("\n2. Read file to a Binary Search Tree by Volume");
          
	printf("\n\nEnter your choice (1 - 2): ");
        scanf("%d",&selection);

        switch (selection)
        {
            case 1 :
                    binaryTreeByDateMenu();
                    return;

            case 2 :        
                    binaryTreeByVolumeMenu();
                    return;

            default :        
                    printf("\nWrong option, try again ...\n\n\n");
                    break;
        }
    }
}


// Binary tree by Date menu: Read file by Date and display user menu
void binaryTreeByDateMenu()
{
    cmpPtr = &cmpDate; // The key of each data record is the field Date 
    readFileToBinTree();

    int selection;
    char x[11];
    dataItem d;
    btNode *r;

    while (1)    
    {
        printf("\n\n1. Inorder traversal of BST");
        printf("\n2. Search volume for a given date");
        printf("\n3. Modify volume for a given date");
	printf("\n4. Delete BST node of a given date");
        printf("\n5. Exit\n");

        printf("\nEnter your choice (1 - 5): ");
        scanf("%d",&selection);
          
        switch (selection)
        {
            case 1 :
                    printf("\n\nDate         Volume\tHeight\n");
                    printf("------------------------------");
                    inorderBinTree(root);

                    printf("\n\n");system("pause");
		    printf("\n\n\nTree structure:\n");
                    printf("---------------\n\n"); 
                    printBinTree(root, 1);
                    break;

            case 2 :
                    printf("\n\nGive the date (yyyy-mm-dd): ");
                    scanf("%s", x);

                    if (!root)
			printf("\nTree is empty\n\n");
		    else
		    {
			r = searchBinTree(root, x);
                        if (!r)
                            printf("\nThis date does not exist in the tree\n");
                        else
                            printf("\nVolume for the given date is: %d\n", r->data.Volume);
                    }
		    break;

            case 3 :
                    printf("\n\nGive the date (yyyy-mm-dd): ");
                    scanf("%s", x);

                    if (!root)
			printf("\nTree is empty\n\n");
		    else
		    {	
			r = searchBinTree(root, x);
                        if (!r)
                            printf("\nThis date does not exist in the tree");
                        else
                        {
			    printf("\nCurrent record: %s | %d", r->data.Date, r->data.Volume);
                            printf("\n\nGive the new volume (>= 0): ");
                            scanf("%d", &r->data.Volume);
                            printf("\nVolume modified\n");
                        }
                    }
                    break;

            case 4 :
                    printf("\n\nGive the date (yyyy-mm-dd): ");
                    scanf("%s", x);

                    if (!root)
			printf("\nTree is empty\n\n");
		    else
		    {	
			r = searchBinTree(root, x);
                        if (!r)
                            printf("\nThis date does not exist in the tree");
                        else
                        {
			    root = deleteFromBinTree(root, x);
                            r->height = btNodeHeight(r);
                            printf("\n\nDate found and deleted\n");
                        }
                    }
                    break;
			
            case 5 :        
                    return;
                        
            default :        
                    printf("\nWrong option, try again ...\n\n\n");
                    break;
        }
    }
}


// Binary tree by Volume menu: Read file by Volume and display user menu
void binaryTreeByVolumeMenu()
{
    cmpPtr = &cmpVolumeDate; // The key of each data record is the pair (Volume, Date)
    readFileToBinTree();

    int selection, v;

    while (1)
    {
        printf("\n\n1. Find date(s) with MIN volume");
        printf("\n2. Find date(s) with MAX volume\n");
          
	printf("\nEnter your choice (1 - 2): ");
        scanf("%d",&selection);

        switch (selection)
        {
            case 1 :
                    /* // This code is used for verification: Display tree nodes info in inorder and the tree structure  
		    printf("\n\nDate         Volume\tColor\tBNodes\tTNodes\n");
                    printf("----------------------------------------------");
                    inorderBinTree(root);
                        
		    printf("\n\n\nTree structure:\n");
                    printf("---------------\n\n"); 
                    printBinTree(root, 1); */
                        
                    if (!root)
                        printf("\n\nTree is empty\n\n");
                    else
                    {
                        v = minValuebtNode(root)->data.Volume;
			printf("\nDates with MIN volume: ");
                        reportBinTree(root, v);
                        printf("\nMIN volume: %d\n", v);
                    }
                    return;

            case 2 :        
                    if (!root)
                        printf("\n\nTree is empty\n\n");
                    else
                    {
                        v = maxValuebtNode(root)->data.Volume;
			printf("\nDates with MAX volume: ");
                        reportBinTree(root, v);
                        printf("\nMAX volume: %d\n", v);
                    }
                    return;

            default :        
                    printf("\nWrong option, try again ...\n");
                    break;
        }
    }
}


// Open the input data file
void openFile(int argc, char *argv[])
{
    
    char *fileName;
    if (argc >= 2)  // Data filename passed as a command line argument
        fileName = strdup(argv[1]);
    else
    {
        printf("Give the stock data filename: "); // Data filename asked by user
        scanf("%ms", &fileName);
        printf("\n\n");
    } 

    // Check if the file exists
    if (access(fileName, F_OK) == -1)
    {
        printf("\nERROR: File '%s' not found\n", fileName);
        free(fileName);
        exit(1);
    }

    fp = fopen(fileName, "r");
    if (!fp) // fp == NULL
    {
        printf("\nERROR: can't open file\n");
        free(fileName);
        exit(1);
    }
}

// Read the file and store data records to a binary tree implemented as an AVL tree 
void readFileToBinTree()
{
    char line[80];  
    dataItem dt;
    float a, b, c, d;
    int e;

    fgets(line, 80, fp); // Get the first line

                                  while (fgets(line, 80, fp))
    {
        sscanf(line, "%10s,%f,%f,%f,%f,%d,%d", dt.Date, &a, &b, &c, &d, &dt.Volume, &e);  // a, b, c, d and e are dummy variables
        root = insertToBinTree(root, dt);
        root->height = btNodeHeight(root); // Update height of root node
    }

    fclose(fp);
}


// Allocate memory to a new tree node n and set left and right pointers to NULL and height to 0
btNode *createbtNode(dataItem x) 
{
    btNode *n = (btNode *) malloc(sizeof(btNode));
    if (!n)
    {
        printf("\nERROR: Memory failure\n\n");
        exit(1);
    }
    n->data = x;
	n->left = n->right = NULL;
    n->height = 0;

    return n;
}


// Inorder traversal of the tree rooted at r
void inorderBinTree(btNode *r)
{
    if (r)
    {
      	inorderBinTree(r->left);
        printf("\n%s   %d\t%d\t%d", r->data.Date, r->data.Volume, r->height, btNodeBalance(r));
        inorderBinTree(r->right);
    }
}


// Search for a given date x in the tree rooted at r
btNode *searchBinTree(btNode *r, char x[11]) 
{
    if (!r)
        return NULL; // NULL tree
    else if (strcmp(x, r->data.Date) < 0) // If x is smaller than r's Date, then it lies in r's left subtree
	     return (searchBinTree(r->left, x));
         else if (strcmp(x, r->data.Date) > 0) // If x is greater than r's Date, then it lies in r's right subtree
                  return (searchBinTree(r->right, x));
              else // If x is the same as r's Date, then search successful
           	  return r;
}


// Rotate right subtree rooted at T1
btNode *rotateR(btNode *T1)
{
    btNode *T2 = T1->left;
    btNode *T3 = T2->right;
 
    // Perform rotation
    T2->right = T1;
    T1->left = T3;
 
    // Update heights
    T1->height = btNodeHeight(T1);
    T2->height = btNodeHeight(T2);

    // Return new root
    return T2;
}
 

// Rotate left subtree rooted at T1
btNode *rotateL(btNode *T1)
{
    btNode *T2 = T1->right;
    btNode *T3 = T2->left;
 
    // Perform rotation
    T2->left = T1;
    T1->right = T3;
 
    // Update heights
    T1->height = btNodeHeight(T1);
    T2->height = btNodeHeight(T2);
    
    // Return new root
    return T2;
}


// Get balance of node n
int btNodeBalance(btNode *n)
{
    if (!n)
        return 0;
    return btNodeHeight(n->left) - btNodeHeight(n->right);
}
 

// Recursive function to insert a data record x in the subtree rooted at r. It returns the new root of the subtree 
btNode *insertToBinTree(btNode *r, dataItem x)
{
    // 1. Perform the standard insertion to binary tree
    if (!r) 
        return createbtNode(x);
 
    if ((*cmpPtr)(x, r->data) < 0) // The key of each data record is the Date field (Exercise II.A) or the pair (Volume, Date) (Exercise II.B) 
        r->left = insertToBinTree(r->left, x); // Insert x to r's left subtree
   	else if (strcmp(x.Date, r->data.Date) > 0)
        	  r->right = insertToBinTree(r->right, x); // Insert x to r's right subtree
             else
         	  return r; // Duplicates are not allowed in an AVL tree. Actually, as the Date value of each data record is unique, we have no duplicates 
				 
    // 2. Update height of ancestor node r
    r->height = btNodeHeight(r);
 
    // 3. Get balance of ancestor node r to check whether the node became unbalanced  
    int balance = btNodeBalance(r);
 
    // If the node becomes unbalanced, then there are 4 Cases
 
    // Left Left Case - Right rotation
    if (balance > 1 && (*cmpPtr)(x, r->left->data) < 0)
        return rotateR(r);
  
    // Right Left Case - Double rotation: Rotate right and then Rotate left
    if (balance < -1 && (*cmpPtr)(x, r->right->data) < 0)    
    {
        r->right = rotateR(r->right);
        return rotateL(r);
    }
 
    // Left Right Case - Double rotation: Rotate left and then Rotate right
    if (balance > 1 && (*cmpPtr)(x, r->left->data) > 0) 
    {
        r->left = rotateL(r->left);
        return rotateR(r);
    }

    // Right Right Case - Left rotation
    if (balance < -1 && (*cmpPtr)(x, r->right->data) > 0) 
        return rotateL(r);
		
    // Return the (unchanged) node pointer if node stays balanced  
    return r;
}


// Given a non-empty binary tree rooted at r, return the node with minimum value stored in the tree
btNode *minValuebtNode(btNode *r)
{
    btNode *p = r;
  
    // Loop down to find the leftmost node 
    while (p->left)
        p = p->left;
  
    return p;
}
  

/* // Given a non-empty binary tree rooted at r, return the node with minimum value stored in the tree
btNode *minValuebtNode(btNode *r)
{
    if (r->left)
   	return minValuebtNode(r->left);
    else 
	return r;
} */


// Given a non-empty binary tree rooted at r, return the node with maximun value stored in the tree
btNode *maxValuebtNode(btNode *r)
{
    btNode *p = r;
  
    // Loop down to find the rightmost node  
    while (p->right)
        p = p->right;
  
    return p;
}
  

/* // Given a non-empty binary tree rooted at r, return the node with maximum value stored in the tree
btNode *maxValuebtNode(btNode *r)
{
    if (r->right)
   	return maxValuebtNode(r->right);
    else 
	return r;
} */


// Recursive function to delete a node with given date from subtree rooted at r. It returns the root of the modified subtree 
btNode *deleteFromBinTree(btNode *r, char x[])
{
    // 1. Perform the standard deletion from binary tree
  
    if (!r)
        return r; // NULL tree
  
    // If x is smaller than r's Date, then it lies in r's left subtree
    if (strcmp(x, r->data.Date) < 0)
        r->left = deleteFromBinTree(r->left, x);
  
        // If x is greater than r's Date, then it lies in r's right subtree
        else if (strcmp(x, r->data.Date) > 0)
        	 r->right = deleteFromBinTree(r->right, x);
  
             // If x is the same as r's Date, then this is the node to be deleted
    	     else
    	     {
        	  // Node with only one son or a leaf
        	  if(!r->left || !r->right)
        	  {
                       btNode *t = r->left ? r->left : r->right;
  
                       // Leaf case
            	       if (!t)
            	       {
                           t = r;
                           r = NULL;
                       }
                       else // One son case
                           *r = *t; // Copy the contents of the non-empty son
            	       free(t);
            	  }
                  else
        	  {
                      // Node with two sons: Get the inorder successor (node with minimum value in the right subtree)
            	      btNode *t = minValuebtNode(r->right);
  
            	      // Copy the inorder successor's data to this node
            	      r->data = t->data;
  
            	      // Delete the inorder successor
            	      r->right = deleteFromBinTree(r->right, t->data.Date);
                  }
             }
  
    // If the tree had only one node, return NULL
    if (!r)
      	return r;
  
    // 2. Update height of current node r  
    r->height = btNodeHeight(r);
  
    // 3. Get balance of node r in order to check whether the node became unbalanced 
    int balance = btNodeBalance(r);
  
    // If the node becomes unbalanced, then there are 4 Cases
  
    // Left Left Case - Right rotation
    if (balance > 1 && btNodeBalance(r->left) >= 0)
        return rotateR(r);
  
    // Left Right Case - Double rotation: Rotate left and then Rotate right 
    if (balance > 1 && btNodeBalance(r->left) < 0)
    {
        r->left =  rotateL(r->left);
        return rotateR(r);
    }

    // Right Left Case - Double rotation: Rotate right and then Rotate left
    if (balance < -1 && btNodeBalance(r->right) > 0)
    {
        r->right = rotateR(r->right);
        return rotateL(r);
    }

    // Right Right Case - Left rotation
    if (balance < -1 && btNodeBalance(r->right) <= 0)
        return rotateL(r);
		
    // Return the (unchanged) node pointer if node stays balanced  
	return r;
}
  

// Print tree structure 
void printBinTree(btNode *r, int k)
{
    if (r)
    {
	printBinTree(r->right, k+1);
	for (int i = 0; i < k; i++)
            printf("    ");
	printf("%d (%d)\n", r->data.Volume, btNodeBalance(r));
	printBinTree(r->left, k+1);
    }
}


// Utility function
int max(int a, int b)
{
    return a >= b ? a : b;
}


// Compute the height of the tree rooted at r from height info stored in the roots of left and right subtrees
int btNodeHeight(btNode *r) 
{
    if (!r)
        return -1;
    if (r->left == r->right) // A leaf
	return 0;
    if (r->left && !r->right) // r has only left son
        return 1 + r->left->height; 
    if (!r->left && r->right) // r has only right son
        return 1 + r->right->height;
    return 1 + max(r->left->height, r->right->height); // r has two sons
} 


// Utility function to compare Date fields
int cmpDate(dataItem a, dataItem b)
{
    return strcmp(a.Date, b.Date);
} 


// Utility function to compare pairs (Volume, Date)
int cmpVolumeDate(dataItem a, dataItem b)
{
    if (a.Volume > b.Volume)
	return 1;
    if (a.Volume < b.Volume)	
	return -1;
    if (strcmp(a.Date, b.Date) > 0)
	return 1;
    if (strcmp(a.Date, b.Date) < 0)
	return -1;
    return 0;	 
} 


// Report the date(s) with Volume value == x
void reportBinTree(btNode *r, int x) 
{
    if (r)
    {
	if (r->data.Volume == x) // x can be stored in many tree nodes
        {
            printf("%s ", r->data.Date);
            reportBinTree(r->left, x);
            reportBinTree(r->right, x);
        }
        else if (x < r->data.Volume)
                 reportBinTree(r->left, x);
             else
                 reportBinTree(r->right, x);
    }  
}