CSE310-Project 2 MyAppStore Application Solved

This project implements myAppStore in which applications of various categories are indexed simultaneously by a hash table and by a search tree for optimal support of various queries and updates of your store.

1         The myAppStore Application
Applications for mobile phones are available from a variety of online stores, such as iTunes for Apple’s iPhone, and Google Play for Android phones.

In this project you will write an application called myAppStore. First, you will populate myAppStore with data on applications under various categories. The data is to be stored simultaneously in both a hash table to support fast look-up of an application, and in a search tree to support certain queries.

Once you have populated myAppStore with application data, you will then process queries about the apps and/or perform updates in your store.

1.1        myAppStore Application Data Format
The myAppStore application must support n categories of applications. Allocate an array of size n of type struct categories, which includes the name of the category, and a pointer to the root of a search tree holding applications in that category. That is, there is a separate search tree for each category of applications. For example, if n = 3, and the three categories are “Games,” “Medical,” and “Social Networking,” then you are to allocate an array of size 3 of struct categories and initialize each position to the category name and a pointer to the root of a search tree for applications in that category (initially nil).

#define         CAT_NAME_LEN      25

struct categories{ char category[ CAT_NAME_LEN ]; // Name of category

struct tree *root; // Pointer to root of search tree for this category

};

// Dynamically allocate an array of size n of type struct categories struct categories *app_categories = (struct categories *) malloc( n * sizeof( struct categories ) ); The search tree to be implemented is a binary search tree (BST). Each node of the binary search tree contains a record for the application and a pointer to the left and right subtrees, respectively; see struct app info, and struct tree). The BST is to be ordered on the application name app name field.

struct tree{ // A binary search tree struct app_info record; // Information about the application struct tree *left; // Pointer to the left subtree struct tree *right; // Pointer to the right subtree };

For each application, its category, app name, version, size, units, and price are provided in that order in the data set.

#define         APP_NAME_LEN 50

#define           VERSION_LEN 10

#define          UNIT_SIZE          3

struct app_info{ char category[ CAT_NAME_LEN ]; // Name of category char app_name[ APP_NAME_LEN ]; // Name of the application char version[ VERSION_LEN ]; // Version number float size; // Size of the application char units[ UNIT_SIZE ]; // GB or MB float price; // Price in $ of the application };

First, you are to populate myAppStore with m applications. For each application, allocate a node of type struct tree. The node contains a structure of type struct app info; initialize the structure. Now, search the array of categories, to find the position matching the category of the application. Insert the node as a leaf into the search tree for that application category.

In addition, you must insert into a hash table using the app name as the key. Only the app name and a pointer to the node just inserted into the search tree storing the full application record are to be stored in the hash table (not any of the other fields of the application). The hash table is to be implemented using separate chaining, with a table size k that is the first prime number greater than 2 ×m. (You may find the boolean function in the file prime.cc provided to you useful; it returns true if the integer parameter is a prime number and false otherwise.) That is, a hash table of size k containing entries of type struct hash table  entry * is to be allocated and maintained.

struct hash_table_entry{ char app_name[ APP_NAME_LEN ]; // Name of the application struct tree *app_node; // Pointer to node in tree containing the application information struct hash_table_entry *next; // Pointer to next entry in the chain

};

// Declare hash table; dynamically allocate it as an array of size k of pointers struct hash_table_entry **hash_table;

The hash function is computed as the sum of the ASCII value of each character in the application name, modulo the hash table size. For example, if a game is named Sky and the hash table size is 11, then the hash function value is: (83 + 107 + 121) mod 11 = 311 mod 11 = 3, because the ASCII value for S is 83, for k is 107, and for y is 121. That is, the app name and a pointer to the node inserted into the search tree, is inserted at the head of the chain at position 3 of the hash table.

1.2        myAppStore Queries and Updates
Once myAppStore is populated with m applications, you are ready to process q queries and updates. When all queries and updates are processed, if requested your myAppStore application is to collect characteristics of the data structures constructed, and then terminate gracefully. Graceful termination means your program must deallocate all dynamically allocated data structures that you created before it terminates.

In the following, < bracket variables, while the other strings are literals. There are 5 queries that myAppStore must be able to process:

1.   find app <app name, searches the hash table for the application with name <app name. If found, it prints Found Application: <app name and then follows the pointer to the node in the search tree to print the record associated with the application (i.e., the contents of the struct app info, with each field tab indented and labelled on a separate line); otherwise it prints Application <app  name not found. substituting the parameter app name given in the command.

2.   find category <category name, searches the array of categories to find the given <category name. If found, and the BST is not empty prints Category: <category name, then performs an inorder traversal of the search tree for that category, printing the tab indented name of the application (field app name in the record), i.e., this results in a list of applications of the given category in sorted order by app name. If the <category name is found but the tree is empty, then print Category <category name no apps found. If the <category name does not exist, prints Category <category  name not found., always substituting the parameter category name given in the command.

3.   find price free, steps through the array of categories in the order provided and, for each category, performs an in-order traversal of the search tree, printing the names of the applications in each category whose price is free on a separate line. Organize your output by category, i.e., with the title Free Applications in Category: <category  name. If no free applications are found print No free applications found.

4.   range <category  name price <low <high, for the given <category name, performs an in-order traversal of the search tree, printing the tab indented name of the each application whose price is greater than or equal to (float) <low and less than or equal to (float) <high on a separate line with the header

Applications in Price Range (<low,<high) in Category: <category name. If no applications are found whose price is in the given range print No applications found in <category  name for the given price range (<low,<high). substituting the parameters given in the command.

5.   range <category  name app <low <high, for the given <category name, performs an in-order traversal of the search tree, printing the tab indented names of the applications whose application name (app name) is alphabetically greater than or equal to (string) <low and less than or equal to (string) <high with the header Applications in Range (<low,<high) in Category: <category  name. If no applications are found whose name is in the given range print No applications found in <category  name for the given range (<low,<high). substituting the parameters given in the command.

There is only one update that myAppStore must be able to process:

1. delete <category name <app name, first searches the hash table for the application with name <app name. Then it first deletes the entry from the search tree of the given <category name, and then also deletes the entry from the hash table. Finally, it prints Application <app  name from Category <category  name successfully deleted. If the application is not found it prints Application

<app name not found in category <category name; unable to delete. substituting the parameters given in the command.

1.3        Sample Input
The following is sample input myAppStore must process. You may assume that the input is in the correct format. (The comments are not part of the input.)

3                                            // n=3, the number of app categories

Games                                      // n=3 lines containing the names of each of the n categories

Medical

Social Networking

4                                            // m=4, number of apps to add to myAppStore; here all in Games

Games                                  // Each field in app_info is provided in order; first the name of the category

Minecraft: Pocket Edition                              // Name of the application

0.12.1                                 // Version number of the application

24.1                                   // Size of the application

MB                                           // Units corresponding to the size, i.e., MB or GB

6.99                                   // Price of the application

Games                                 // Start of record for the second app

FIFA 16 Ultimate Team

2.0

1.25

GB

0.00

Games                                  // Start of record for the third app

Candy Crush Soda Saga

1.50.8

61.3

MB

0.00

Games                                  // Start of record for the fourth app

Game of Life Classic Edition

1.2.21

15.3

MB

0.99

8                                                                      // q=8, number of queries and/or updates to process

find app Candy Crush Soda Saga // List information about the application find category Medical   // List all applications in the Medical category find price free      // List all free applications

range Games app A F         // List alphabetically all Games whose name is in the range A-F range Games price 0.00 5.00 // List all names of Games whose price is in the range $0.00-$5.00 delete Games Minecraft        // Delete the game Minecraft from the Games category find category Games          // List all applications in the Games category find app Minecraft // Application should not be found because it was deleted no report // do not produce hash table and tree statistics

1.4        Sample Output
The following is sample output produced by myAppStore. (The comments are not part of the input.)

Found Application: Candy Crush Soda Saga                        // Output of: find app Candy Crush Soda Saga

Category: Games

Application Name: Candy Crush Soda Saga

Version: 1.50.8

Size: 61.3

Units: MB

Price: $0.00

Category Medical no apps found.                             // Output of: find category Medical

Free Applications in Category: Games                              // Output of: find price free

Candy Crush Soda Saga

FIFA 16 Ultimate Team

Applications in Range (A,F) in Category: Games           // Output of: range Games app A F Candy Crush Soda Saga

Applications in Price Range ($0.00,$5.00) in Category: Games // Output of: range Games price 0.00 5.00 Candy Crush Soda Saga

FIFA 16 Ultimate Team

Game of Life Classic Edition

Application Minecraft from Category Games successfully deleted. // Output of: delete Games Minecraft

Application Minecraft not found.                             // Output of: find app Minecraft

2         Program Requirements for Project #2
1.   Write a C/C++ program that implements all of the queries and updates described in §1.2 on data in the format described in §1.1. You must build all dynamic data structures, i.e., the hash table and the BSTs, by yourself from scratch. All memory management must be handled using only malloc and free, or new and delete.

2.   If the last command is report, then collect characteristics of the data structures you’ve built as described in §3 for your report. If the last command is no report then no statistics are collected.

3.   Provide a makefile that compiles your program into an executable named myAppStore. This executable must run on general.asu.edu, compiled by a C/C++ compiler that is installed on that machine, reading input from stdin (of course, you may redirect stdin from a file in the prescribed format).

Sample input files that adhere to the format described in §1.1 will be provided on Canvas; use them to test the correctness of your program.

3         Characteristics of the Data Structures
For the binary search tree associated with each category: Print the category name, a count of the total number of nodes in the tree, the height of the tree, the height of the root node’s left subtree, and the height of the root node’s right subtree.

For the hash table: Print a table that lists for each chain length `, 0 ≤ ` ≤ `max, the number of chains of length `, up to the maximum chain length `max that your hash table contains. In addition, compute and print the load factor α for the hash table, giving n and m.

Implement the find app <app  name command by directly searching the BST instead of the hash table. The easiest way to do this may be to use the hash table to extract the <category name and then search the appropriate BST. Compare the time to find an ¡app name¿ using the hash table, and by searching the BST for its category.