An online movie service needs help keeping track of their stock. You should help
ID: 3863851 • Letter: A
Question
An online movie service needs help keeping track of their stock. You should help them by developing a program that stores the movies in a Binary Search Tree (BST) ordered by movie title. For each of the movies in the store’s inventory, the following information is kept:
- IMDB ranking
- Title
- Year released
- Quantity in stock
Your program will have a menu similar to previous assignments from which the user could select options. In this assignment, your menu needs to include options for finding a movie, renting a movie, printing the inventory, deleting a movie, and quitting the program. Your program needs to incorporate the following functionality. These are not menu options, see Appendix A for the specific menu options.
Insert all the movies in the tree.
When the user starts the program they will pass it the name of the text file
that contains all movie information. Each line in the file shows the IMDB
ranking, title, year released, and quantity in stock. Your program needs to
handle that command line argument, open the file, and read all movie data in
the file. From this data, build the BST ordered by movie title. All other
information about the movie should also be included in the node for that
movie in the tree. Note: the data should be added to the tree in the order it
is read in. The name of the file that contains the movie data is
Assignment8Movies.txt.
Contents of Assignment8Movies.txt:
Find a movie.
When the user selects this option from the menu, they should be prompted
for the name of the movie. Your program should then search the tree and
display all information for that movie. If the movie is not found in the tree,
your program should display, “Movie not found.”
Rent a movie.
When the user selects this option from the menu, they should be prompted
for the name of the movie. If the movie is found in the tree, your program
should update the Quantity in stock property of the movie and display the
new information about the movie. If the movie is not found, your program
should display, “Movie not found.” When the quantity reaches 0, the movie
should be deleted from the tree.
Print the entire inventory.
When the user selects this option from the menu, your program should
display all movie titles and the quantity available in sorted order by title. See
the lecture notes and recitation exercises on in-order tree traversal for more
information.
Delete a movie.
When the user selects this option, they should be prompted for the title of the movie to delete. Your code should then search the tree for that movie, delete it if it’s found, re-assign to the parent and child pointers to bypass the deleted node, and free the memory assigned to the node. If the movie is not found in the search process, print “Movie not found” and do not attempt to delete. A movie node should also be deleted when its quantity goes to 0.
Count movies in the tree.
When the user selects this option, your program should traverse the tree in any order and count the total movie nodes in the tree and print the count.
Quit the program.
When the user selects this option, your program should delete the nodes in the tree and exit the program. When the user selects quit, the destructor for the MovieTree class should be called and in the destructor, all of the nodes in the tree should be deleted. You need to use a postorder tree traversal for the delete or you will get segmentation fault errors.
Use the cout statements in Appendix A to set the order of the menu options.
Implementation details
Your BST should be implemented in a class. You are provided with a MovieTree.h file on Moodle that includes the class prototype for this assignment. You need to implement the class functionality in a corresponding MovieTree.cpp file and Assignment8.cpp file. To submit your work, zip all files together and submit them to COG. If you do not get your assignment working on COG, you will have the option of a grading interview.
Appendix A – cout statements that COG expects
Display menu
cout << "======Main Menu======" << endl;
cout << "1. Find a movie" << endl;
cout << "2. Rent a movie" << endl;
cout << "3. Print the inventory" << endl;
cout << "4. Delete a movie" << endl;
cout << "5. Count the movies" << endl;
cout << "6. Quit" << endl;
Find a movie
cout << "Enter title:" << endl;
Display found movie information
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
If movie not found
cout << "Movie not found." << endl;
Rent a movie
//If movie is in stock
cout << "Movie has been rented." << endl;
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
//If movie not found in tree
cout << "Movie not found." << endl;
Print the inventory
//For all movies in tree
cout<<"Movie: "<title<<" "<quantity< Count movies in the tree
cout<<"Tree contains: "<
Header File:
#ifndef MOVIETREE_H
#define MOVIETREE_H
#include
struct MovieNode{
int ranking;
std::string title;
int year;
int quantity;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;
MovieNode(){};
MovieNode(int in_ranking, std::string in_title, int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
parent = NULL;
leftChild = NULL;
rightChild = NULL;
}
};
class MovieTree
{
public:
MovieTree();
~MovieTree();
void printMovieInventory();
int countMovieNodes();
void deleteMovieNode(std::string title);
void addMovieNode(int ranking, std::string title, int releaseYear, int quantity);
void findMovie(std::string title);
void rentMovie(std::string title);
protected:
private:
void DeleteAll(MovieNode * node); //use this for the post-order traversal deletion of the tree
void printMovieInventory(MovieNode * node);
void countMovieNodes(MovieNode *node, int *c);
MovieNode* search(std::string title);
MovieNode* searchRecursive(MovieNode *node, std::string value);
MovieNode* treeMinimum(MovieNode *node);
MovieNode *root;
};
#endif // MOVIETREE_H
Explanation / Answer
Here is the code for the question. Comments are inline. Please go through deletion algorithm from text book to understand how it works. Please rate the answer if it helped. Thanks
Assignment8.cpp
#include "MovieTree.h"
#include <fstream>
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
ifstream file("movies.txt");
/* if fopen( ) was not successful there was an error, so exit with error */
if(!file.is_open() )
{
cout<<"Error opening input file";
exit(1);
}
int choice=4;
MovieTree *tree=new MovieTree(); //our movie tree
char buffer[100];
int ranking,quantity,year;
string title;
//initially load all movies from file
while(!file.eof()) //while its not end of file
{
file.getline(buffer,100,','); //read the ranking from file ,using comma delimiter
ranking=atoi(buffer);
file.getline(buffer,100,',');//get the title from file
title=string(buffer);
file.getline(buffer,100,',');
year=atoi(buffer);
file.getline(buffer,100,' ');
quantity=atoi(buffer);
tree->addMovieNode(ranking,title,year,quantity);
}
file.close();
//now repeatedly get user's choice and perform action accordingly
do
{
cout<<"======Main Menu======" << endl;
cout << "1. Find a movie" << endl;
cout << "2. Rent a movie" << endl;
cout << "3. Print the inventory" << endl;
cout << "4. Delete a movie" << endl;
cout << "5. Count the movies" << endl;
cout << "6. Quit" << endl;
cout << "Enter your choice : "<<endl;
cin>>choice;
switch(choice) //based on command number call diffent functions
{
case 1:
//find a title
cout<<"Enter the movie title : "<<endl;getchar();
getline(cin,title);
tree->findMovie(title);
break;
case 2:
//rent a title
cout<<"Enter the movie title : "<<endl;getchar();
getline(cin,title);
tree->rentMovie(title);
break;
case 3:
//print inventory
tree->printMovieInventory();
break;
case 4:
//delete movie
cout<<"Enter the movie title : "<<endl;getchar();
getline(cin,title);
tree->deleteMovieNode(title);
break;
case 5:
//count movies
cout<<"Tree has "<<tree->countMovieNodes()<<" movies"<<endl;
break;
case 6:
delete tree;
break;
default:
;
}
}while(choice!=6);
return 0;
}
MovieTree.cpp
#include "MovieTree.h"
#include <iostream>
using namespace std;
//default constructor
MovieTree::MovieTree()
{
root=NULL;
}
//destructor
MovieTree::~MovieTree()
{
DeleteAll(root); //use post order deletion
}
//does in-order traversal from specified node and display info
void MovieTree::printMovieInventory(MovieNode * node)
{
if(node==NULL)
return;
//travel left then the node itself and then the right node
printMovieInventory(node->leftChild);
cout<<"Movie: "<<node->title<<" "<<node->quantity<<endl;
printMovieInventory(node->rightChild);
}
//displays all movies in tree
void MovieTree::printMovieInventory()
{
printMovieInventory(root);
int count=0;
countMovieNodes(root,&count);
cout<<"Tree contains: "<<count<<" movies"<<endl;
}
int MovieTree::countMovieNodes()
{
int count=0;
countMovieNodes(root,&count);
return count;
}
void MovieTree::countMovieNodes(MovieNode *node, int *c)
{
if(node==NULL)
return;
//travel left then the node itself and then the right node , updating count each time
countMovieNodes(node->leftChild,c);
*c=*c+1;
countMovieNodes(node->rightChild,c);
}
MovieNode* MovieTree::search(string title)
{
return searchRecursive(root,title);
}
MovieNode* MovieTree::searchRecursive(MovieNode *node, string value)
{
if(node==NULL)
return NULL;
MovieNode *current=node;
while(current!=NULL)
{
if(current->title==value)
return current;
else if (value<current->title) // go to left subtree if the search value is less than current title
{
current=current->leftChild;
}
else //go to right when search value is greater than current title
{
current=current->rightChild;
}
}
return NULL; //no matching title found in the tree
}
void MovieTree::findMovie(string title)
{
MovieNode *foundMovie=search(title);
if(foundMovie!=NULL)
{
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
}
else
{
cout << "Movie not found." << endl;
}
}
void MovieTree::rentMovie(std::string title)
{
MovieNode *foundMovie=search(title);
if(foundMovie!=NULL)
{
cout << "Movie has been rented." << endl;
foundMovie->quantity=foundMovie->quantity-1; //update the quantity
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
if(foundMovie->quantity==0) //if quantity reached 0, delete the movie from tree
deleteMovieNode(foundMovie->title);
}
else
{
cout << "Movie not found." << endl;
}
}
void MovieTree::addMovieNode(int ranking, string title, int releaseYear, int quantity)
{
MovieNode *movie=new MovieNode(ranking,title,releaseYear,quantity);
if(root==NULL)//there are no nodes yet in tree
{
root=movie;
}
else
{
MovieNode *current=root;
while(true)
{
if(movie->title<=current->title) //the new value is less than parent's value, go to left subtree
{
if(current->leftChild==NULL) //no more left subtree, so this is the correct place for new node
{
current->leftChild=movie;
movie->parent=current; //set the parent for new node
return; //finished adding so return
}
else
{
current=current->leftChild;
}
}
else
{
if(current->rightChild==NULL) //no more right subtree, so this is the correct place for new node
{
current->rightChild=movie;
movie->parent=current;//set the parent for new node
return; //finished adding so return
}
else
current=current->rightChild;
}
}
}
}
MovieNode* MovieTree::treeMinimum(MovieNode *node)
{
MovieNode *current=node;
//the minimum in the tree is left most leaf node in the tree which does not have any other left child
while(current!=NULL)
{
if(current->leftChild==NULL)
break;
else
current=current->leftChild;
}
return current;
}
//used only in destructor
void MovieTree::DeleteAll(MovieNode * node) //use this for the post-order traversal deletion of the tree
{
if(node==NULL)
return;
DeleteAll(node->leftChild);
DeleteAll(node->rightChild);
delete node;
}
//Uses standard deletion algorithm to delete in BST
void MovieTree::deleteMovieNode(std::string title)
{
MovieNode *movie=search(title);
if(movie==NULL)
return;
else
{
if(movie->leftChild==NULL && movie->rightChild==NULL) //no children , so delete easily and set the corresponding link in parent to NULL
{
if(movie->parent==NULL) //check if we are deleting root
root=NULL;
else
{
if(movie->parent->leftChild==movie) // if node to be deleted was parent's left child ,set left link to NULL
{
movie->parent->leftChild=NULL;
}
else
{
movie->parent->rightChild=NULL;
}
}
delete movie;
}
else
{
//if the node to be deleted has just right child, then attach this child to correspoding link in parent
if(movie->leftChild==NULL && movie->rightChild!=NULL)
{
//cout<<" node with right "<<n->data;
if(movie->parent==NULL)//delet root
{
root=movie->rightChild;
root->parent=NULL;
}
else
{
if(movie->parent->leftChild==movie)
{
movie->parent->leftChild=movie->rightChild; //n is left child of parent and n had only right child
}
else
{
movie->parent->rightChild=movie->rightChild;//n is right child of parent and n had only right child
}
movie->rightChild->parent=movie->parent; //set the rightchild new parent
}
delete movie;
}
//if the node to be deleted has just left child, then attach this child to correspoding link in parent
else if (movie->leftChild!=NULL && movie->rightChild==NULL)
{
//cout<<" node witth left"<<n->data;
if(movie->parent==NULL)//delet root
{
root=movie->leftChild;
root->parent=NULL;
}
else
{
if(movie->parent->leftChild==movie)
{
movie->parent->leftChild=movie->leftChild; //n is left child of parent and n had only left child
}
else
{
movie->parent->rightChild=movie->leftChild;//n is right child of parent and n had only left child
}
movie->leftChild->parent=movie->parent; //set the new parent
}
delete movie;
}
else // node to be deleted n has both children
{
//find the minimum in right subtree of movie and set this title in place of movie->title
//and remove that minimum node in right subtree . Note the minimum node will always
//be one without a left child
MovieNode *min=treeMinimum(movie->rightChild);
if(min!=NULL)
{
movie->title=min->title;
min->title=min->title+"|"; //changing the title to be deleted
return deleteMovieNode(min->title); //recursively remove this min node from tree
}
}
}
}
}
Sample output
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
3
Movie: 12 Angry Men 56
Movie: American History X 1
Movie: Apocalypse Now 5
Movie: Back to the Future 5
Movie: Casablanca 5
Movie: City Lights 10
Movie: City of God 9
Movie: Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb 5
Movie: Fight Club 6
Movie: Forrest Gump 1
Movie: Gladiator 5
Movie: Goodfellas 5
Movie: Inception 10
Movie: Interstellar 8
Movie: It's a Wonderful Life 21
Movie: Leon: The Professional 31
Movie: Life Is Beautiful 3
Movie: Memento 9
Movie: Modern Times 9
Movie: Once Upon a Time in the West 12
Movie: One Flew Over the Cuckoo's Nest 10
Movie: Psycho 6
Movie: Pulp Fiction 34
Movie: Raiders of the Lost Ark 6
Movie: Rear Window 7
Movie: Saving Private Ryan 3
Movie: Schindler's List 10
Movie: Se7en 11
Movie: Seven Samurai 7
Movie: Shawshank Redemption 45
Movie: Spirited Away 10
Movie: Star Wars: Episode IV - A New Hope 6
Movie: Star Wars: Episode V - The Empire Strikes Back 12
Movie: Sunset Blvd. 5
Movie: Terminator 2: Judgment Day 10
Movie: The Dark Knight 90
Movie: The Departed 7
Movie: The Godfather 34
Movie: The Godfather: Part II 12
Movie: The Good the Bad and the Ugly 2
Movie: The Green Mile 8
Movie: The Lord of the Rings: The Fellowship of the Ring 20
Movie: The Lord of the Rings: The Return of the King 4
Movie: The Lord of the Rings: The Two Towers 5
Movie: The Matrix 5
Movie: The Pianist 7
Movie: The Silence of the Lambs 19
Movie: The Untouchables 3
Movie: The Usual Suspects 2
Movie: Whiplash 8
Tree contains: 50 movies
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
1
Enter the movie title :
Forrest Gump
Movie Info:
===========
Ranking:13
Title:Forrest Gump
Year:1994
Quantity:1
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
2
Enter the movie title :
Forrest Gump
Movie has been rented.
Movie Info:
===========
Ranking:13
Title:Forrest Gump
Year:1994
Quantity:0
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
5
Tree has 49 movies
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
4
Enter the movie title :
The Pianist
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
5
Tree has 48 movies
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
3
Movie: 12 Angry Men 56
Movie: American History X 1
Movie: Apocalypse Now 5
Movie: Back to the Future 5
Movie: Casablanca 5
Movie: City Lights 10
Movie: City of God 9
Movie: Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb 5
Movie: Fight Club 6
Movie: Gladiator 5
Movie: Goodfellas 5
Movie: Inception 10
Movie: Interstellar 8
Movie: It's a Wonderful Life 21
Movie: Leon: The Professional 31
Movie: Life Is Beautiful 3
Movie: Memento 9
Movie: Modern Times 9
Movie: Once Upon a Time in the West 12
Movie: One Flew Over the Cuckoo's Nest 10
Movie: Psycho 6
Movie: Pulp Fiction 34
Movie: Raiders of the Lost Ark 6
Movie: Rear Window 7
Movie: Saving Private Ryan 3
Movie: Schindler's List 10
Movie: Se7en 11
Movie: Seven Samurai 7
Movie: Shawshank Redemption 45
Movie: Spirited Away 10
Movie: Star Wars: Episode IV - A New Hope 6
Movie: Star Wars: Episode V - The Empire Strikes Back 12
Movie: Sunset Blvd. 5
Movie: Terminator 2: Judgment Day 10
Movie: The Dark Knight 90
Movie: The Departed 7
Movie: The Godfather 34
Movie: The Godfather: Part II 12
Movie: The Good the Bad and the Ugly 2
Movie: The Green Mile 8
Movie: The Lord of the Rings: The Fellowship of the Ring 20
Movie: The Lord of the Rings: The Return of the King 4
Movie: The Lord of the Rings: The Two Towers 5
Movie: The Matrix 5
Movie: The Silence of the Lambs 19
Movie: The Untouchables 3
Movie: The Usual Suspects 2
Movie: Whiplash 8
Tree contains: 48 movies
======Main Menu======
1. Find a movie
2. Rent a movie
3. Print the inventory
4. Delete a movie
5. Count the movies
6. Quit
Enter your choice :
6