tree.c

//
//  trees.c
//  final-trial
//
//  Created by Ahmed Omar on 5/27/14.
//  Copyright (c) 2014 Ahmed Omar. All rights reserved.
//

#include <stdio.h>
#include "trees.h"
#include <string.h>

//ana 3adlt hena
//if 2 have the same id, the id will be inserted in the right node
node_id* insert_id(node_id* tree, int id, char* name) {
    // this node will be inserted
    node_id* temp = NULL;

    //if tree is empty
    if (!tree) {

        temp = (node_id*)malloc(sizeof(node_id));
        temp->left = temp->right = NULL;
        temp->id = id;
        strcpy(temp->name, name);
        //insert
        //tree = temp;
        return temp;
    }

    //insert node in left subtree
    if (id < tree->id) {
        tree->left = insert_id(tree->left, id, name);
        //insert node in right subtree
    } else {
        tree->right = insert_id(tree->right, id, name);
    }

    return tree;
}

//ana 3adlt hena
//the same amendment as insert_id
node_id* insert_name(node_id* tree, int id, char* name) {
    // this node will be inserted
    node_id* temp = NULL;

    //if tree is empty
    if (!tree) {

        temp = (node_id*)malloc(sizeof(node_id));
        temp->left = temp->right = NULL;
        temp->id = id;
        strcpy(temp->name, name);
        //insert
        //tree = temp;
        return temp;
    }

    //insert node in left subtree
    if (strcmp(tree->name,name)>0) {
        tree->left = insert_name(tree->left, id, name);
        //insert node in right subtree
    } else {
        tree->right = insert_name(tree->right, id, name);
    }

    return tree;
}


void insert(node_id** tree_id, node_id** tree_name, int id, char* name) {
    //insert to tree_id
    (*tree_id)  = insert_id(*tree_id, id, name);
    //insert to tree_name
    (*tree_name) = insert_name(*tree_name, id, name);
}

//ana 3adel hena x3
//msh hatefre2 en kan name aw id
void print_preorder(node_id* tree) {
    if (tree) {
        printf("%d\t%s\n", tree->id, tree->name);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}


void print_inorder(node_id* tree) {
    if (tree) {
        print_inorder(tree->left);
        printf("%d\t%s\n", tree->id, tree->name);
        print_inorder(tree->right);
    }
}

void print_postorder(node_id* tree) {
    if (tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\t%s\n", tree->id, tree->name);
    }
}







//searh in tree_id
//ana 3adelt hena
//ÇáãÝÑæÖ ÏáæÞÊí íÞÏÑ íØÈÚ ÇÊäíä áíåã äÝÓ ÇáÈíÇäÇÊ
node_id* search_id(node_id** tree, int id) {
    if (!(*tree)) {
        return NULL;
    }

    if (id == (*tree)->id) {
        return *tree;
    } else if (id < (*tree)->id) {
        search_id(&((*tree)->left), id);
    } else if (id > (*tree)->id) {
        search_id(&((*tree)->right), id);
    }

    return NULL;
}

//searh in tree_name
node_id* search_name(node_id** tree, char* name) {
    if (!(*tree)) {
        return NULL;
    }

    if (strcmp(name, (*tree)->name) == 0) {
        return *tree;
    } else if (strcmp(name, (*tree)->name) < 0) {
        search_name(&((*tree)->left), name);
    } else if (strcmp(name, (*tree)->name) > 0) {
        search_name(&((*tree)->right), name);
    }
    return NULL;
}

//ana 3adlt hena
//msh hatefr2 name aw id
node_id * min_value_node_id(node_id* node) {
    node_id* current = node;
    while (current->left != NULL)
        current = current->left;

    return current;
}

//delete node by id
//3adelt hena
//ÎáíÊå áæ ãÓÍ åäÇ íãÓÍ Ýí ÇáÊÑí ÇáÊÇäíÉ ÚÔÇä ÇáÊÚÏíá íÈÞì ÚÇáÇÊäíä
node_id* delete_id(node_id* tree, int id) {
    if (tree == NULL) {
        return tree;
    }
    if (id < tree->id)
        //delete node from left subtree
        tree->left = delete_id(tree->left, id);
    else if (id > tree->id)
        //delete node from right subtree
        tree->right = delete_id(tree->right, id);

    else {

        if (tree->left == NULL) {
            node_id* temp = tree->right;
            free(tree);
            return temp;
        }
        else if (tree->right == NULL) {
            node_id* temp = tree->left;
            free(tree);
            return temp;
        }

        node_id* temp = min_value_node_id(tree->right);

        tree->id = temp->id;
        strcpy(tree->name, temp->name);
        tree->right = delete_id(tree->right, temp->id);
    }
    return tree;
}

node_id* delete_name(node_id* tree, char* name) {
    if (tree == NULL) {
        return tree;
    }


    if (strcmp(name, tree->name) > 0)
        tree->left = delete_name(tree->left, name);
    else if (strcmp(name, tree->name) < 0) {
        tree->right = delete_name(tree->right, name);
    }
    else {
        if (tree->left == NULL) {
            node_id* temp = tree->right;
            free(tree);
            return temp;
        }
        else if (tree->right == NULL) {
            node_id* temp = tree->left;
            free(tree);
            return temp;
        }
        node_id* temp = min_value_node_id(tree->right);
        strcpy(tree->name, temp->name);
        tree->id = temp->id;

        tree->right = delete_name(tree->right, temp->name);
    }

    return tree;
}



void reed_file_to_tree(node_id** tree_id, node_id** tree_name, char* file_name) {
    FILE* fp = fopen("/Users/BoshraNour/Desktop/final-trial/final-trial/project.txt", "r");

    if (fp == NULL) {
        printf("Error open file\n");
        return;
    }

    char buf[1024], *p;

    //get line from file
    while (fgets(buf, sizeof(buf), fp) != NULL) {
        if ((p = strchr(buf, '\n')) == NULL) {
            fprintf(stderr, "input line too long.\n");
            return;
        }
        *p = '\0';
        // our line should be bigger than 1
        if (strlen(buf) > 1) {
            //split line
            char* pch = strtok(buf, ",");
            char name[40];
            //copy name
            strncpy(name, pch, 40);
            pch = strtok(NULL, ",");
            //copy id
            int id = atoi(pch);
            //insert
            (*tree_id)  = insert_id(*tree_id, id, name);
            (*tree_name) = insert_name(*tree_name, id, name);
        }



    }

    fclose(fp);


}

void write_tree_to_file(node_id* tree_id, FILE* fp) {
    if (fp == NULL) {
        printf("Error file\n");
        return;
    }
    char line[60];
    char numb[20];
    if (tree_id) {
        // convert int to char
        sprintf(numb, "%d", tree_id->id);
        //add strings
        strcpy(line, tree_id->name);
        strcpy(line+strlen(tree_id->name), ",");
        strcpy(line+strlen(line), numb);
        //add sym
        strcat(line,"\n");
        //write to file
        fputs(line, fp);
        write_tree_to_file(tree_id->left, fp);
        write_tree_to_file(tree_id->right, fp);
    }
    //fclose(fp);
}