***IN C PROGRAMMING LANGUAGE*** For this problem you will try to emulate some ba
ID: 3911186 • Letter: #
Question
***IN C PROGRAMMING LANGUAGE***
For this problem you will try to emulate some basic functions of a Task Manager. You must support the addition and removal of tasks. Each task will be assigned a priority as a non-negative integer (1,000,000,000=highest, 0=lowest). No two distinctly named tasks will have the same priority. Additionally for a given run you can assume that each task with the same name will have the same priority.
Your Task Manager must support two types of operations. Type 1 is the creation of a new task.
Type 2 is to determine the name of a task with a particular priority.
Input Specification
The first line of input contains a single positive integer n (n ? 10,000,000), which represents the total number of queries and addition deletions combined. Each of the following n lines begins with a single integer; the i-th line’s integer describes the i-th operation type.
- When the beginning integer is 1 the operation is an add task operation. The remaining line will contain a task name followed by the task’s priority.
- Then the beginning integer is 2 the operation is the query operation. The remaining line will contain a single integer representing the desired task name’s priority.
- It is guaranteed that each location will be visited before Stackula’s stack is permanently emptied (after visiting the first location).
- The name of each task will be composed strictly of at most 19 upper and lowercase Latin letters.
Output Specification
For each attempted task addition you will output a single line containing either “ADDED”, which means the task was not already present in the task list and was successfully added, or “REDUNDANT” which means that task was already in the list and therefore not added to the Task Manager.
For each name query operation you will output a single line containing either the associated name with the task or the string “NON-EXISTANT”, which means the task was not in the Task Manager.
Explanations
Case 1
Note in the above pictorial example. We sort the “tasks” in the Binary Search Tree for this problem by their priority (not their name). Every Program added is unique except for the last one (the second “E” for the tenth input operation).
Regarding the program name by priority…
The 11-th operation asks for the name of the task with priority 3. The task with priority 3 is “C”.
The 12-th operation asks for the name of the task with priority 5. The task with priority 5 is “E”.
For the 13-th operation, which asks for the task with priority 10. Our tree should find that there is no task with priority 10. Due to this we print “NON-EXISTANT”.
For the 14-th operation we find that “D” has priority 4.
The 11-th operation asks again for the name of the task with priority 3. Again the task with priority 3 is “C”.
Case 2
There are five unique programs added,
- ProgramOne (operation 1 priority 1)
- BoiledWater (operation 2 priority 2)
- ColdFerret (operation 3 priority 3)
- MoonsShadow (operation 6 priority7)
- ThatOtherProgram (operation 7 priority 6)
For the following 6 name query operations we observe that,
- ColdFerret has priority 3.
- Nothing has priority 5.
- Nothing has priority 10.
- Nothing has priority 4.
- ColdFerrt has priority 3.
- BoiledWater has priority 2.
Case 3
Note that although later in the case ProgramTwo and ProgramThree are added, the first time their priorities are queried they don’t exist yet. For this reason the third and fourth line are
“NON-EXISTANT”. Additionally by the eighth query ProgramThree has not been added, so it also results in “NON-EXISTANT”.
Grading Information
Reading from standard input – 5 points
Writing to standard output – 5 points
Comments, white space usage, and reasonable variable names – 10 points
No output aside from the answer (e.g. no input prompts) – 10 points
Uses strings (char arrays) for the task names – 10 points
Implements Linked Binary Search Tree data structure– 10 points
Your program will be tested on 10 test cases – 5 points each
Five cases will have less than or equal 1000 simultaneous tasks at any given time No points will be awarded to programs that do not compile.
Solutions that don’t try to implement a linked binary search tree will receive a maximum of 50 points
Only cases that finish within the maximum of {5 times the judge solution, 10 seconds} will be graded.
To get Full credit you will likely need to implement a balancing Binary Search Tree. The two methods that will be (or have been) covered in class are Red-Black Trees and AVL Trees.
Input Output Example Input 15 1 F 9 1 A 1 1 I 7 1 H 8 1 D 4 1 C3 1 E 5 1 B 2 1 J 6 1 E 5 2 3 2 5 2 10 Output ADDED ADDED ADDED ADDED ADDED ADDED ADDED ADDED ADDED REDUNDANT NON-EXISTANT 2 3 13 1 ProgramOne 1 1 BoiledWater 2 1 ColdFerret 3 1 ProgramOne 1 1 ProgramOne 1 1 MoonsShadow 7 1 ThatOtherProgram 6 ColdFerret 2 3 2 5 2 10 ADDED ADDED ADDED REDUNDANT REDUNDANT ADDED ADDED NON-EXISTANT NON-EXISTANT NON-EXISTANT ColdFerret BoiledWater 2 3 12 1 ProgramOne 1 2 1 ADDED ProgramOne NON-EXISTANT NON-EXISTANT ADDED ProgramOne ProgramTwo NON-EXISTANT ADDED ProgramOne ProgramTwo ProgramThree 2 100 1 ProgramTwo 2 2 1 2 100 1 ProgramThree 100 2 1 2 100Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
char color;//color whether 'R' or 'B'
int key; //val of node
struct node *left;//ptr to left node
char id[20];
struct node *right;//ptr to right node
struct node *p;//parent pointer
}node;
node *root,*nul;//nul is sentinel node
int max_count=0,curr_count=0;
void create_sentinel(){ //A sentinel node is a black node to which all null pointers in tree point to.
node p=(node )malloc(sizeof(node));
if(p==NULL){
printf("Memory allocation failed ");
return ;
}
p->color='B';
p->left=NULL;
p->right=NULL;
nul=p;
root=nul;
root->p=nul;
}
/*Left rotation*/
void left_rotate(node *x){
node *y=x->right;
x->right=y->left;
if(y->left!=nul) y->left->p=x;
y->p=x->p;
if(x->p==nul) root=y;
else if(x==x->p->left) x->p->left=y;
else x->p->right=y;
y->left=x;
x->p=y;
}
/*Right rotation*/
void right_rotate(node *y){
node *x=y->left;
y->left=x->right;
if(x->right!=nul) x->right->p=y;
x->p=y->p;
if(y->p==nul) root=x;
else if(y==y->p->left) y->p->left=x;
else y->p->right=x;
x->right=y;
y->p=x;
}
/*corrects the color of the nodes by traversing up the tree*/
void insert_fixup(node *z){
node *y;
while(z->p->color=='R'){ //Upto parent color is red , as black color node can have its children of any color
if(z->p==z->p->p->left) { //If parent of z is left sibling
y=z->p->p->right;//y is right sibling of parent
if(y->color=='R'){//checks if color of y is R
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;
}
else if(z==z->p->right){//if z is right sibling
z=z->p;
left_rotate(z);
}
else { //if z is left sibling
z->p->color='B';
z->p->p->color='R';
right_rotate(z->p->p);
}
}
else{
y=z->p->p->left;
if(y->color=='R'){
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;
}
else if(z==z->p->left){
z=z->p;
right_rotate(z);
}
else {
z->p->color='B';
z->p->p->color='R';
left_rotate(z->p->p);
}
}
}
root->color='B';
}
/* Inserts independent of the color of nodes which will be fixed up in the insert-fixup-method*/
void insert(char *pid,int val){
node n=(node )malloc(sizeof(node));
if(n==NULL){
printf("Memory allocation failed ");
return ;
}
n->key=val;
strcpy(n->id,pid);
node *x,*y;
x=root;
y=nul;
while(x!=nul){
y=x;
if(n->key<x->key) x=x->left;
else x=x->right;
}
n->p=y;
if(y==nul) root=n;
else if(n->key<y->key) y->left=n;
else y->right=n;
n->left=nul;
n->right=nul;
n->color='R';
insert_fixup(n);
}
/* Searches for the noe*/
node search(int val,node curr){
if(curr==nul) return curr;
else if(curr->key==val) return curr;
else if(curr->key>val) return search(val,curr->left);
else return search(val,curr->right);
}
void sabfree(node *curr){
if(curr!=nul){
if(curr->left!=nul) sabfree(curr->left);
if(curr->right!=nul) sabfree(curr->right);
free(curr);
}
}
int main(){
int n;
scanf("%d",&n);
create_sentinel();
int count=0;
while(count<n){
int x;
scanf("%d",&x);
if(x==1){
char id[20];
int priority;
scanf("%s%d",id,&priority);
if(search(priority,root)!=nul) printf("REDUNDANT ");
else {
insert(id,priority);
printf("ADDED ");
}
}
else if(x==2){
int y;
scanf("%d",&y);
node *z=search(y,root);
if(z==nul) printf("NON-EXISTANT ");
else printf("%s ",z->id);
}
count++;
}
sabfree(root);
free(nul);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.