Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct allowedMACS {
int linkedMAC;
struct allowedMACS *next;
} links;
typedef struct tree_node {
int MAC;
char firstName[21];
char lastName[21];
int broadcastRange;
int x;
int y;
struct allowedMACS *deviceLinks;
int numLinks;
struct tree_node *left;
struct tree_node *right;
} BSTnode;
/// Initializations
struct tree_node *CreateTreeNode();
// Functions for search
struct tree_node *FindName(struct tree_node *hunter_ptr, char FirstName[21],
char LastName[21]);
struct tree_node *FindMAC(struct tree_node *hunter_ptr, int MAC);
// operations within the tree
struct tree_node *InsertTreeNode(struct tree_node *root,
struct tree_node *element);
struct tree_node *DeleteTreeNode(struct tree_node* root, int value);
//Status of the tree
int isLeaf(struct tree_node *node);
int hasOnlyLeftChild(struct tree_node *node);
int hasOnlyRightChild(struct tree_node *node);
struct tree_node *parent(struct tree_node *root, struct tree_node *node);
struct tree_node *maxVal(struct tree_node *root);
struct tree_node *minVal(struct tree_node *root);
// structs for user lists
struct allowedMACS *Join(struct tree_node *person, int MAC);
struct allowedMACS *Link(struct tree_node *person, int MAC);
struct allowedMACS *Unlink(struct tree_node *person, int MAC);
struct allowedMACS *Quit(struct allowedMACS *front, int num);
int LLsearch(struct allowedMACS * Allusers, int MAC );
// Print function
void PrintKISMEMBERS(FILE *ofp,struct tree_node *Allusers, struct tree_node *person);
// may need more up there but for now we made it to main
int main(){
// ifp output variables
FILE *ifp, *ofp;
// tree of all users
struct tree_node *Allusers=NULL;
// The number of commands in the file
int commandsnum;
//Command to execute ..sounds powerful
char command[20];
// general loop variable
int i;
char trFirstName[21], trLastName[21], dFirstName[21], dLastName[21];
struct tree_node *tNode, *tuser;
int randomSeed, planeSizeX, planeSizeY;
srand(randomSeed);
//ifp/Output files and specification
ifp= fopen("KnightHoc.in", "r");
ofp= fopen("KnightHoc.out", "w");
if(ifp == NULL || ofp == NULL)
{
fprintf(ofp, "File not Found, Press ENTER to exit\n");
getchar();
return 0;
}
// the binary search tree node process
Allusers = NULL;
fscanf(ifp, "%d %d %d", &randomSeed, &planeSizeX, &planeSizeY);
fscanf(ifp, "%d", &commandsnum);
// ifp command conditions for join
for(i = 0; i < commandsnum; i++){
fscanf(ifp, "%s", command);
if(strcmp("Join", command)==0){
struct tree_node *NewNode = CreateTreeNode();
fscanf(ifp, "%d%s%s%d", &NewNode->MAC, NewNode->firstName,
NewNode->lastName, &NewNode->broadcastRange, &NewNode->x, &NewNode->y);
if(tNode=FindName(Allusers, NewNode->firstName,
NewNode->lastName)!=NULL)
{
fprintf(ofp, "%s %s is already a user"
" Book.\n", NewNode->firstName,
NewNode->lastName);
}
else{
fprintf(ofp, "Added %s %s, MAC %d\n",
NewNode->firstName,
NewNode->lastName, NewNode->MAC);
Allusers = InsertTreeNode(Allusers, NewNode);
}
}
else if(strcmp("FINDMAC", command)==0)
{
fscanf(ifp,"%s","%s","%d","%d","%d",&tNode->firstName,&tNode->lastName,&tNode->MAC,&tNode->x,&tNode->y);
tNode = FindMAC(Allusers, tNode->MAC);
if(tNode == NULL)
fprintf(ofp, "MAC %d not found.\n", tNode->MAC);
else
fprintf(ofp, "%d %s %s (%d,%d)", tNode->MAC,tNode->firstName,tNode->lastName,tNode->x,tNode->y);
}
else if(strcmp("LINK", command)==0)
{
// store first name set in tNode
fscanf(ifp, "%s%s", tNode->firstName, tNode->lastName);
tNode = FindName(Allusers, tNode->firstName, tNode->lastName);
// store second name set in tuser
fscanf(ifp, "%s%s", dFirstName, dLastName);
tuser = FindName(Allusers, dFirstName, dLastName);
if(tNode == NULL || tNode->deviceLinks == NULL)
{
fprintf(ofp, "Cannot Perform Link Command:\n");
if(tNode == NULL)
fprintf(ofp, " %s %s - Error.\n",
tNode->firstName, tNode->lastName);
if(tNode->deviceLinks == NULL){
fprintf(ofp, " %s %s - Error.\n",
dFirstName, dLastName);
}
}
else if(LLsearch(tNode->deviceLinks, tNode->deviceLinks->linkedMAC) ||
LLsearch(tuser->deviceLinks, tNode->MAC))
{
fprintf(ofp, "Cannot Perform Link Command:\n"
" %s %s and %s %s are linked already .\n",
tNode->firstName, tNode->lastName, dFirstName, dLastName);
}
else
{
// store the users
tNode->deviceLinks = Link(tNode, tNode->MAC);
tuser->deviceLinks = Link(tuser, tuser->MAC);
fprintf(ofp, "%s %s and %s %s are linked.\n", tNode->firstName,
tNode->lastName, dFirstName, dLastName);
}
}
else if(strcmp("UNLINK", command)==0)
{
fscanf(ifp, "%s%s%d", tNode->firstName, tNode->lastName,tNode->MAC);
tNode = FindName(Allusers, tNode->firstName, tNode->lastName);
fscanf(ifp, "%s%s%d", dFirstName, dLastName);
tuser = FindName(Allusers, dFirstName, dLastName);
if(tNode == NULL || tuser == NULL)
{
fprintf(ofp, "Can't do UNLINK Command:\n");
if(tNode == NULL)
fprintf(ofp, " %s %s %d - not a valid user.\n",
tNode->firstName, tNode->lastName);
if(tuser == NULL){
fprintf(ofp, " %s %s %d - Not a valid user.\n",
dFirstName, dLastName);
}
}
else if(tNode->deviceLinks == NULL)
{
fprintf(ofp, "Cannot Perform UNLINK Command:\n"
" %s %s and %s %s are not currently linked.\n",
tNode->firstName, tNode->lastName, dFirstName, dLastName);
}
else
{
tuser->deviceLinks = Unlink(tuser, tNode->MAC);
tNode->deviceLinks->next = Unlink(tNode, tuser->MAC);
fprintf(ofp, "%s %s and %s %s are now unlinked from the the share site.\n",
tNode->firstName, tNode->lastName, dFirstName,
dLastName);
}
}
else if(strcmp("PRINTKISMEMBERS", command)==0)
{
if(Allusers != NULL){
fprintf(ofp, "KnightsHOC internet share users:\n");
PrintKISMEMBERS(ofp, Allusers,0);
}
else{
fprintf(ofp, "Can't do PRINTKIS Command aint no one hrrr:\n");
}
}
else if(strcmp("QUIT", command)==0)
{
fscanf(ifp, "%s%s%d", tNode->firstName, tNode->lastName,tNode->MAC);
tuser= FindName(Allusers, tNode->firstName, tNode->lastName);
if(tuser == NULL)
{
fprintf(ofp, "Cannot Perform DELETE Command user does not exist:\n");
}
else
{
while(tuser->deviceLinks->next !=NULL){
//removes user before deleting user
FindMAC(Allusers, tuser->numLinks--);
tuser->deviceLinks->next = Quit(tuser->deviceLinks->next,tuser->deviceLinks->next->linkedMAC);
}
fprintf(ofp, "has quit %s %s.\n", tuser->firstName,
tuser->lastName);
Allusers = DeleteTreeNode(Allusers, tuser->MAC);
}
}
else if(strcmp("SHOWCONNECTIONS", command)==0){
int bigmac;
fscanf(ifp, "%d", &bigmac);
tNode = FindMAC(Allusers, bigmac);
fprintf(ofp, "Connections for MAC %d, %s %s, located at position (%d,%d):\n",
tNode->MAC, tNode->firstName, tNode->lastName, tNode->x, tNode->y);
fprintf(ofp, "\tThere are a total of %d link(s).\n", tNode->numLinks);
fprintf(ofp, "\tThere are %d active link(s) within the broadcast range of %d", tNode->numLinks, tNode->broadcastRange);
// cycle through active links, print each one
// else no links?
fprintf(ofp, "MAC %d has no links.", tNode->MAC);
}
else if(strcmp("MOVEDEVICES", command)==0){
int currentNode;
tNode = FindMAC(Allusers,currentNode);
fprintf(ofp,"assigning coordinates for MAC at postion (%d,%d):\n",
tNode->MAC,tNode->firstName,tNode->lastName,tNode->x,tNode->y);
// currentNode is used to store each user one at a time
for(i=0;i>0;i++){
fscanf(ifp,"%d%d",&planeSizeX,&planeSizeY);
// for each member the loop goes through, do this:
}
}
}
}
// End main
// making function for tree node
struct tree_node* CreateTreeNode(){
struct tree_node * temp;
temp = (struct tree_node*)malloc(sizeof(struct tree_node));
temp->left = NULL;
temp->right = NULL;
}
// fucntion for findMAC find a person and prints their name mac and coordinates
//Error message will print if null or the user is not found
struct tree_node* FindMAC(struct tree_node *hunter_ptr, int MAC)
{
// checking if any nodes are in the tree
if (hunter_ptr != NULL) {
// if value found at root
if(hunter_ptr->MAC == MAC)
return hunter_ptr;
// Search left.
if (hunter_ptr->MAC > MAC)
return (struct tree_node *)FindMAC(hunter_ptr->left, MAC);
// search right.
else
return (struct tree_node *)FindMAC(hunter_ptr->right, MAC);
}
else
return NULL; // No node found.
}
// links users to the internet share. will print error if not in the network or already identified
//hunter_ptr is a valid tree node. the mac of the user is also added to the network
struct allowedMACS *Link(struct tree_node *person,int MAC){
struct allowedMACS *temp;
struct allowedMACS *iter;
struct allowedMACS *savelink;
struct allowedMACS * front = person->deviceLinks;
person->numLinks++;
// Create the new node.
temp = (struct allowedMACS*)malloc(sizeof(struct allowedMACS));
temp->linkedMAC = MAC;
temp->next = NULL;
// insert into an empty list
if (front == NULL){
return temp;
}
if (MAC < front->linkedMAC) {
temp->next = front;
return temp;
}
// Start iter at the front of the linked list.
iter = front;
// Use front to iterate to the right spot to insert temp.
while (iter->next != NULL && iter->next->linkedMAC < MAC)
iter = iter->next;
// Save the node to patch
savelink = iter->next;
// Insert temp.
iter->next = temp;
temp->next = savelink;
return front;
}
// Removes user off of network. If no user was there print error. return pointer to front of list
struct allowedMACS *Unlink(struct tree_node * person, int MAC){
struct allowedMACS *front = person->deviceLinks;
struct allowedMACS *temp, *del;
temp = front;
// Only need to delete if the list is not null.
if (temp != NULL) {
person->numLinks--;
// delete then free and return
if (temp->linkedMAC == MAC) {
del = temp -> next;
free(temp);
return del;
}
// if still not found loop through list til found then delete
while (temp->next != NULL) {
if (temp ->next->linkedMAC == MAC) {
del = temp -> next;
temp->next = temp ->next->next;
free(del);
return front;
}
temp = temp -> next;
}
}
return NULL;
}
// Deletes laptop from the KIS Internet share and deletes the users address. a pointer will loop through
// the list and find the adress and delete it
struct allowedMACS * Quit(struct allowedMACS *front, int num)
{
struct allowedMACS *temp, *del;
temp = front;
// Again only need to delete if list is not null
if (temp != NULL) {
// get to node that needs to be deleted
if (temp->linkedMAC == num)
{
del = temp->next;
free(temp);
return del;
}
// loop til the node is found...then delete it!
while (temp->next != NULL)
{
if (temp->next->linkedMAC == num)
{
del = temp -> next;
temp->next = temp->next->next;
free(del);
return front;
}
temp = temp-> next;
}
}
return front;
}
//Prints out all of the users and their devices that take part of knightshoc internet share
void PrintKISnumbers(FILE * ofp, BSTnode *Allusers){
BSTnode *helper_ptr = Allusers;
if(helper_ptr != NULL){
if(helper_ptr->right != NULL)
{
PrintKISMEMBERS(ofp, helper_ptr->left,helper_ptr->right);
}
fprintf(ofp, " ");
PrintPerson(ofp, helper_ptr);
if(helper_ptr->left != NULL){
PrintKISMEMBERS(ofp, helper_ptr->right,helper_ptr->right);
}
}
}
struct tree_node * InsertTreeNode(struct tree_node *root,struct tree_node *element){
if (root == NULL)
return element;
else {
// element should be inserted to the right.
if (element->MAC > root->MAC) {
// There is a right subtree to insert the node.
if (root->right != NULL)
root->right = InsertTreeNode(root->right, element);
// Place the node directly to the right of root.
else
root->right = element;
}
// element should be inserted to the left.
else {
// There is a left subtree to insert the node.
if (root->left != NULL)
root->left = InsertTreeNode(root->left, element);
// Place the node directly to the left of root.
else
root->left = element;
}
// Return the root pointer of the updated tree.
return root;
}
}
struct tree_node* DeleteTreeNode(struct tree_node* root, int value)
{
struct tree_node *delnode, *new_del_node, *save_node;
struct tree_node *par;
int save_val;
delnode = FindMAC(root, value); // Get a pointer to the node to delete.
par = parent(root, delnode); // Get the parent of this node.
// Take care of the case where the node to delete is a leaf node.
if (isLeaf(delnode))
{
// Deleting the only node in the tree.
if (par == NULL)
{
free(root); // free the memory for the node.
return NULL;
}
// Deletes the node if it's a left child.
if (value < par->MAC)
{
free(par->left); // Free the memory for the node.
par->left = NULL;
}
// Deletes the node if it's a right child.
else
{
free(par->right); // Free the memory for the node.
par->right = NULL;
}
return root; // Return the root of the new tree.
}
// Take care of the case where the node to be deleted only has a left child
if (hasOnlyLeftChild(delnode)) {
// Deleting the root node of the tree.
if (par == NULL) {
save_node = delnode->left;
free(delnode); // Free the node to delete.
return save_node; // Return the new root node of the resulting tree.
}
// Deletes the node if it's a left child.
if (value < par->MAC) {
save_node = par->left; // Save the node to delete.
par->left = par->left->left; // Readjust the parent pointer.
free(save_node); // Free the memory for the deleted node.
}
// Deletes the node if it's a right child.
else {
save_node = par->right; // Save the node to delete.
par->right = par->right->left; // Readjust the parent pointer.
free(save_node); // Free the memory for the deleted node.
}
return root; // Return the root of the tree after the deletion.
}
// Takes care of the case where the deleted node only has a right child.
if (hasOnlyRightChild(delnode)) {
// Node to delete is the root node.
if (par == NULL) {
save_node = delnode->right;
free(delnode);
return save_node;
}
// Delete's the node if it is a left child.
if (value < par->MAC) {
save_node = par->left;
par->left = par->left->right;
free(save_node);
}
// Delete's the node if it is a right child.
else {
save_node = par->right;
par->right = par->right->right;
free(save_node);
}
return root;
}
// Find the new physical node to delete.
new_del_node = minVal(delnode->right);
save_val = new_del_node->MAC;
DeleteTreeNode(root, save_val); // Now, delete the proper value.
// Restore the MAC to the original node to be deleted.
delnode->MAC = save_val;
return root;
}
struct tree_node* parent(struct tree_node *root, struct tree_node *node) {
// Take care of NULL cases.
if (root == NULL || root == node)
return NULL;
// The root is the direct parent of node.
if (root->left == node || root->right == node)
return root;
// Look for node's parent in the left side of the tree.
if (node->MAC < root->MAC)
return parent(root->left, node);
// Look for node's parent in the right side of the tree.
else if (node->MAC > root->MAC)
return parent(root->right, node);
return NULL; // Catch any other extraneous cases.
}
int isLeaf(struct tree_node *node)
{
return (node->left == NULL && node->right == NULL);
}
int hasOnlyLeftChild(struct tree_node *node)
{
return (node->left!= NULL && node->right == NULL);
}
int hasOnlyRightChild(struct tree_node *node)
{
return (node->left== NULL && node->right != NULL);
}
struct tree_node* minVal(struct tree_node *root)
{
// Root stores the minimal value.
if (root->left == NULL)
return root;
// The left subtree of the root stores the minimal value.
else
return minVal(root->left);
}
struct tree_node* maxVal(struct tree_node *root)
{
// root stores the maximal value.
if (root->right == NULL)
return root;
// the right subtree of the root stores the maximal value.
else
return maxVal(root->right);
}
int LLFind(struct allowedMACS * AllBuddies, int user)
{
struct allowedMACS * helperBuddy = AllBuddies;
while(helperBuddy != NULL)
{
if(helperBuddy->linkedMAC == user)
return 1;
helperBuddy = helperBuddy->next;
}
return 0;
}
