Skip to Main Content

Data Structures

Computer Science Department

RU Hungry – 98 course points

In this assignment, you will implement a program to manage the menu, stock, transactions, and guests of a fictional restaurant. You will work with hash tables, separate chaining, referencing objects, and the object-oriented programming (OOP) paradigm.

This assignment IS LONGER than ANY previous assignment.

Start your assignment early! You will need time to understand this assignment and the many questions it may present.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

The assignment has two components:

  1. Coding (95 points) submitted through Autolab.
  2. Reflection (3 points) submitted through a form.
    • Submit the reflection AFTER you have completed the coding component.
    • Be sure to sign in with your RU credentials! (netid@scarletmail.rutgers.edu)
    • You cannot resubmit reflections but you can edit your responses before the deadline by clicking the Google Form link, signing in with their netid, and selecting “Edit your response”

Introduction

RUHungry is a fictitious restaurant. You will be running RUHungry for a day by seating guests, taking orders, donation requests and restocking the pantry as necessary.

As you may or may not know, the Rutgers Pantry is an integral part of Rutgers student life especially for those students who face food insecurity. But not only does the pantry have food but because the pantry is a partnership with the Off Campus Living and Community the pantry also provides contacts for campus housing information and commuter information. Since March 2020, there have been around 3,000 student visits to the pantry. Remember food insecurity doesn’t mean starving, it refers to the state of an inadequate food supply or unreliable food source.

And because of this huge impact on the Rutgers NB student population, donations are always welcome and encouraged. However there are many other ways to help the pantry like volunteering as an ambassador through social media promotion or just spreading awareness to hundreds of students… like this assignment is doing!

Your assignment is to run RUHungry for the day (*disclaimer* this assignment is NOT affiliated with RUHungry in any capacity however RUHungry is located at the Yard for anyone who does want a fat sandwich or a milkshake) by seating guests, taking orders, donation requests and restocking the pantry. As all good businesses should do, you will be keeping track of which parties are sat and when, as well as printing an end of day receipt for every single transaction regardless of its success.

Overview

A visual of the provided files and methods are included below. There are quite a lot of classes and objects which we will provide. DO NOT EDIT any other files except the RUHungry file (which you will submit). Those combined with written instructions will help you complete the assignment.

Enjoy the data structures pick up lines sprinkled throughout the assignment but please don’t use any of them in real life (since their success rate is astronomically low). Good luck!

The assignment uses:

  • a 1D array to hold information about the restaurant number of seats per table.
  • a 1D array to hold the people currently sitting at a certain table.
  • a hashtable to hold the stock.
  • two 1D parallel arrays. One holds the menu categories’ name and the other that holds the dishes in a linked list. 
  • a linked list to hold the transactions that happened during the day.

menu: represents the menu at the restaurant. Each index (you will populate based on CategoryVar) of the menu is a linked list of MenuNodes. The “data” part of the MenuNodes are the dishes (see visual).

stock: represents the stockroom at the restaurant. This is THE hashtable and you will use the ingredientID%tableSize hash function to organize the dishes into their appropriate indices. (as this is the hashtable assignment, it will also be your job to write the methods that manipulate the hashtable, add/delete/search). This assignment uses chaining to handle collisions, so each index of the stock is a linked list of StockNodes. The key is the ingredientID and the value is the “data” part of the StockNode which is the ingredient (see visual).

transactions: transactions are implemented through another linked list of TransactionNodes. This is similar to an end of day receipt that keeps track of all successful and unsuccessful transactions. As you perform any order, donation request or restock you must add a new TransactionNode to the end of the linked list. The “data” part of the TransactionNodes are TransactionData (see visual).

seating guests: this is the most challenging single method. You will be fed a waiting queue, where you will dequeue the first party and seating them at the first table that will accommodate their size. The tables array keeps track of who is currently sitting since you may eventually need to “kick” parties out in order of when they arrive when there are no more empty tables with enough seats for the incoming guests.

*there are a lot of people in the Computer Science department but I like to think I’m an exception; if I throw myself at you, will you catch me?*

Implementation

Overview of files provided

  • Dish.java – is the data portion of the MenuNode
  • MenuNode.java – is the “node” in the linked list at each index in the Menu “hashtable”
  • Ingredient.java – is the data portion of the StockNode
  • StockNode.java – is the “node” in the linkedlist at each index in the Stock hashtable
  • *are you a hash table? cuz you’re the key that gives value to my life*
  • TransactionData.java – is the data portion of the TransactionNode
  • TransactionNode.java – is the “node” in the Transaction LinkedList
  • Party.java – contains a party’s information which is imputed into a queue
  • *people aren’t objects, but if I wrap myself around you, it gives me a method to my madness*
  • Queue.java – queue class from algs4.cs.princeton.edu. For implementation documentation please refer to the documentation.
  • RUHungry.java – holds all of the methods you will be writing and that will be tested. Edit ONLY the empty methods with your code, but DO NOT edit the given methods or the method signatures of any method. **This is the file you will submit!**
  • Menu.java – used to test the menu() method – given to you as an example.
    • WRITE OTHER FILES to test each method.
    • printRestaurant() inside RUHungry.java prints menu, stock, transactions, and tables of the restaurant.
  • StdIn.java/StdOut.java – used by you to handle input and output. DO NOT EDIT!
    • The methods StdIn.readInt() and StdIn.readString() actually leave the newline character unread, so if you use StdIn.readLine() after one of these methods, it will read this character rather than the next line. If you want to read the next line with StdIn.readLine(), you will need to call StdIn.readLine() once to read the newline character and then again to read the next line. StdIn.readInt() and StdIn.readString() ignore spaces and newlines by default.
  • Multiple Text Files (“____.in”) – Feel free to edit them or even make new ones to help test your code.
    • Menu.in —> to test menu methods
    • Stock.in —> to test stockroom methods
    • order.in/donate.in/restock.in —> to individually test the three types of transactions
    • Transaction.in —> to test all types of transactions
    • tables.in/seatguests.in —> to test seat guests method

RUHungry.java

*are you the main method? cuz I want you in all my classes*

In this assignment, you will write your own code to call and test methods. We provide Menu.java, which calls menu() and prints out the restaurant using printRestaurant(), as a reference. You can use printRestaurant() to print out the entire state of the restaurant.

  • printRestaurant() is a method given to you that prints the menu, stock, transactions, and tables of the restaurant.
  • Do NOT add any import statements.
  • Do NOT change any method signatures.
  • Use the .equalsIgnoreCase() method when writing methods.
  • You are encouraged to write helper methods as you see fit. Just make sure they are private!
  • HowTo debug video.

*I know you’re a private person; but we’re in the same class so we can still access each other; we can even be discrete about it cuz we’re hidden*

The class contains:

  • menuVar – is a hashtable (without the hash function) where each index is sorted by category and contains a linked list of MenuNodes
  • categoryVar – is a String array where each index corresponds to a same category in MenuVar (parallel array)
  • *are you an index in an array? cuz I want your number*
  • stockVar – is a hashtable (with a hash function) where each index contains a linked list of StockNodes
  • * you know I’m all about efficiency, but I would sacrifice having a good hash function if it meant colliding with you*
  • front – refers to the first TransactionNode in the Transaction linked list.
  • *are you a node? what do you say we link together? I have a list of reason why we should*
  • leftQueueVar – queue for people who’ve left the restaurant.
  • tables – 1D integer array representing the number of seats at each table.

Methods to be implemented by you:

1. menu(String inputFile)

This method simulates creating a Menu for the RUHungry restaurant. There is only ONE input file to test this method (menu.in). The input file format is as follows:
  1. the first number corresponds to the number of categories (aka length of menuVar and categoryVar).
  2. the next line states the name of the category (populate categoryVar as you read each category name).
  3. the next number represents how many dishes are in that category.
  4. the next line states the name of the dish.
  5. the first number in the next line represents how many ingredient IDs there are.
  6. the next few numbers (all in the 100s) are each the ingredient ID.
Use the StdIn library to read from the input file:
  • StdIn.setFile(filename) opens a file to be read
  • StdIn.readInt() reads the next integer value from the opened file (whether the value is in the current line or in the next line)
  • StdIn.readString() reads the next String value from the opened file.
  • *I’m pretty StdIn(to you) but I can’t read you well; I wanna double check that you like me too and aren’t just stringing me along*
  • StdIn.readLine() reads the rest of the line as a String
Your job is to populate categoryVar and menuVar which is a “hashtable” (not exactly since we won’t have a hash function).
  • These are parallel arrays. For example, if index 0 (zero) at categoryVar contains “Appetizers” then menuVar, at index 0, contains a linked list of MenuNodes that are appetizers.
  • At each array index of menuVar (each index represents a category) contains a reference to the front node of a linked list of MenuNodes.
  • As you read through the input file, populate the categoryVar array, populate menuVar depending on which index (aka which category).
  • To populate menuVar 
    1. make a Dish object with filled parameters (do not worry about “price” and “profit” right now).
    2. create a MenuNode that refers to the Dish object just created.
    3. insert the MenuNode at the front of menuVar (NOTE: since this is a linked list, there will be multiple MenuNodes in one index).
  • *are you a return type? cuz I can’t function without you* (Objects don’t have functions though, they have methods)
Submit RUHungry.java with this method completed under Early Submission to receive extra credit. This is the expected output for menu.in: Note: keep in mind that menu won’t have price and profit updated until we run the stock method so $0.0 is NORMAL.

2. addStockNode(StockNode newNode)

*can I insert myself into your life? cuz you always help me sort out my problems and bring stability to mine*

This method adds the parameter StockNode to the stockVar hashtable. The hashtable <key,value> pair is the ingredient ID (key) and the Ingredient stored in the MenuNode is they value.

  • Your task is to retrieve the ingredientID of the StockNode parameter and use the hash function to get the index at which the StockNode will be inserted.
    • Use “ingredientID % stockVarSize” as your hash function.
  • Then, insert into the front of the linked list at that specific index in stockVar.
  • Keep in mind that at that specific index, there may OR may not already be a linked list, so insert accordingly.

Note: no resizing will occur in the hash table.

3. createStockHashTable(String inputFile)

This method creates the stockVar hashtable, essentially the pantry of the restaurant with all the ingredients, the prices for all the ingredients, and how much there is of each ingredient.

Read the input file that contains the size of stockVar and a several ingredients.

There is only ONE input file to test this method (stock.in). The format is as follows:

  1. the first number corresponds to the size of StockVar. Make sure to update stockVarSize with this value.
  2. the first integer of the next line represents the ingredientID.
  3. Use StdIn.readChar() to get rid of the space between the id and the name.
  4. the string that follows is the ingredient name (NOTE -> there are spaces between certain strings).
  5. the double on the next line corresponds to the ingredient’s cost.
  6. the next integer is the stock amount for that ingredient.

Use the StdIn library to read from the input file:

  • StdIn.setFile(filename) opens a file to be read
  • StdIn.readInt() reads the next integer value from the opened file (whether the value is in the current line or in the next line).
  • StdIn.readDouble() reads the next double value from the opened file (whether the value is in the current line or the next line).
  • StdIn.readChar() reads the next char value from the opened file (you’ll need to use this so items are read as “Water” and not “ Water”).
  • StdIn.readLine() reads the rest of the line as a String

While reading the stock.in file, you will do the following for each ingredient in the file:

  1. create an Ingredient object.
  2. create a StockNode that refers to the Ingredient object just created.
  3. call addNode() to insert the StockNode into stockVar.

Once you create the hashtable, then print out the stockroom as well as the updated menu with the updated price and profit.

Note: Call menu() before calling this method.

This is the expected output for stock.in (the stockroom part below):

4. findStockNode(int ingredientID)

This method finds and returns the StockNode (from stockVar) containing the ingredient with the parameter ingredientID.

  • Find the ingredient based upon the ingredientID. Use the hash function ingredientID % stockVarSize to find the hashtable index where the ingredient is located.
    • This is an efficient search as it looks only at the linked list which the key hashes to.
  • Return the StockNode if ingredientID is found, null otherwise.

5. updateStock(String ingredientName, int ingredientID, int stockAmountToAdd)

This method updates the stock amount of an ingredient in stockVar.

The method searches for an ingredient using either it’s name or it’s ID.

  • if the ingredientName parameter is null, use the ingredientID to search.
  • if the ingredientID is -1, use the ingredientName to search.

Once the ingredient is found, update the stock amount by adding the parameter stockAmountToAdd to the current stock amount.

Hint: you can use findStockNode() to search for the ingredient in stockVar.

Note: printRestaurant() prints out all states of the restaurant.

6. updatePriceAndProfit()

This method iterates over the entire menuVar to update the price and profit of each dish, using the stockVar hashtable to lookup for the ingredients’ cost.

  • compute dish cost: add up the cost variable for each ingredient (found in stockVar).
  • compute dish price: multiply the dish cost by 1.2.
  • update the price of the dish with it’s price.
  • update the profit of the dish with the difference between price and cost.

Hint: you can use findStockNode() to search stockVar for an ingredient.

Note: Call menu() and createStockHashTable() before calling this method.

*are you a single ‘for’ loop? cuz i only have i’s for you*

This is the expected output for stock.in (the menu part below):

*are you a decimal? cuz the thought of you always floats in my head and the two of us would make double*

7. addTransactionNode(TransactionData data)

The daily transactions that occur in RUHungry are customer’s orders, donations to food pantries, or restocking of ingredients.
  • The daily transactions are kept in a linked list of TransactionNodes.
  • The front of the transaction linked list is the instance variable transactionVar.
This method inserts a new transaction to the end of transactionVar. We insert at the end of the list to keep the order in which the transactions occurred. Terrible running time, isn’t it?
  1. create a TransactionNode that refers to the parameter TransactionData.
  2. insert the TransactionNode at the end of the transaction linked list.

checkDishAvailability(String dishName, int numberOfDishes)

This method checks if there’s enough ingredients in stock to prepare one or more dishes. Returns true if the stockroom has sufficient stock to prepare the dish, false otherwise.

This method IS NOT required but it’s highly recommended as a helper method to the order() method.

  1. Firstly, use findDish() to find the MenuNode containing the Dish with dishName.
  2. Then traverse the ingredient array within the Dish object to determine whether you have enough stock of each ingredient for the kitchen to prepare the dish.
  3. If there isn’t enough, return false, and if there is enough, return true.

Note: a Dish requires several ingredients (stockID array) but it doesn’t specify quantity. Assume that the dish uses 1 (one) of each ingredient. For example, if we are checking if there is enough stock to prepare 3 dishes and the dish requires lemon, the method returns true if there are at least 3 lemons in stock.

*are you the break command? cuz everything else stops when I see you*

8. order(String dishName, int quantity)

This method simulates a customer ordering a dish. Use the checkDishAvailability() method to check whether the dish can be ordered.

  • If the dish can be prepared
    1. create a TransactionData object of type “order” where the item is the dishName, the amount is the quantity being ordered, and profit is the dish profit multiplied by quantity.
    2. then add the transaction as a successful transaction (call addTransactionNode())
    3. Call updateStock() for each dish’s Ingredient to update stock accordingly. 
  • If the dish cannot be prepared
    1. create a TransactionData object of type “order” where the item is the dishName, the amount is the quantity being ordered, and profit is 0 (zero).
    2. then add the transaction as an UNsuccessful transaction and,
    3. simulate the customer trying to order other dishes in the same category linked list:
      • if the dish that comes right after the dishName can be prepared, great. If not, try the next one and so on.
      • you might have to traverse through the entire category searching for a dish that can be prepared. If you reach the end of the list, start from the beginning until you have visited EVERY dish in the category.
      • It is possible that no dish in the entire category can be prepared.
      • Note: the next dish the customer chooses is always the one that comes right after the one that could not be prepared.

*if (you were a while loop and I were a boolean), we could run together forever because I’ll always stay true to you*

Note: Call menu(), createStockHashTable(), and updatePriceAndProfit() before calling this method.

Input File for Order: In your own test code, read from the order input file and call order on each order. The input file is formatted as follows:
  • 1 line containing the number of orders, say n
  • n lines containing order quantity and dish name, separated by a space
  • To read one order do:
                     int amount = StdIn.readInt();
                     StdIn.readChar();
                     String item = StdIn.readLine();

This is the expected output for order1.in (just testing order method):

9. profit()

This method returns the total profit for the day so far. It will be called in the donation and restock methods to check for sufficient profit.
The profit is computed by traversing the transaction linked list (transactionVar) adding up all the profits for the day. Then, return the total profit.

10. donation(String ingredientName, int quantity)

This method simulates the donation of ingredients to Rutgers Pantry. Donations can only happen if the profit for the day is greater than $50 (50 dollars).

Therefore, this method runs checks on whether the total profit for the day is greater than $50 and if there’s enough stock in the stockroom for the donation request to be successful. If there is, the stock is updated accordingly.

The transaction is recorded wether the donation is successful or not:

  1. create a TransactionData object of type “donation” where the item is the ingredientName, the amount is the quantity being ordered, and profit is 0 (zero).
  2. then add the transaction as a successful (if donation is happens) or failed (if donation cannot occur) transaction (call addTransactionNode()).
  3. Call updateStock() to update the stock accordingly.

NOTE: to test the donation method.

  1. call the order() method on all orders of a order file;
  2. then run the donate on all donations of its correspondent file.
    • order1.in corresponds to donate1.in
    • order2.in corresponds to donate2.in
    • order3.in corresponds to donate3.in
Input File for Donation: In your own test code, read from the donation input file and call donation on each donation. The input file is formatted as follows:
  • 1 line containing the number of donations, say n
  • n lines containing donation quantity and ingredient name, separated by a space
  • To read one donation do:
                   int amount = StdIn.readInt();
                   StdIn.readChar();
                   String item = StdIn.readLine();

Note: Call menu(), createStockHashTable(), updatePriceAndProfit() and order() before calling this method. 

This is the expected output using order1.in and donation1.in:

11. restock(String ingredientName, int quantity)

This method simulates restock orders.

This method runs checks on whether there’s enough total profit in the day to pay for the restock request.

  • The cost of restocking is the ingredient’s cost multiplied by the quantity the restaurant needs to buy.

The restock happens as long as there’s enough profit. Call updateStock() to update the stockroom accordingly.

The transaction is recorded wether the restock is successful or not:

  1. create a TransactionData object of type “restock” where the item is the ingredientName, the amount is the quantity being ordered, and profit is:
    • 0 (zero) if there isn’t enough profit to restock.
    • cost of restocking (negative) if the restocking is successful. 
  2. then add the transaction as a successful (if restocking is happens) or failed (if restocking cannot occur) transaction (call addTransactionNode()) and updates the stock accordingly.

NOTE: to test the restock method.

  1. call the order() method on all orders of a order file;
  2. then run the restock on all restocks of its correspondent file.
    • order1.in corresponds to restock1.in
    • order2.in corresponds to restock2.in
    • order3.in corresponds to restock3.in

Note: Call menu(), createStockHashTable(), updatePriceAndProfit() and order() before calling this method.

Input File for Restock: In your own test code, read from the restock input file and call restock on each restock. The input file is formatted as follows:
  • 1 line containing the number of orders, say n
  • n lines containing order quantity and ingredient name, separated by a space
    • To read one restock do:
                     int amount = StdIn.readInt();
                     StdIn.readChar();
                     String item = StdIn.readLine();
     
    This is the expected output using order1.in and restock1.in:

RUNNING THE ENTIRE TRANSACTION METHOD

Input File for Transactions: In your own test code, read from the transaction input file. The input file is formatted as follows:

  • 1 line containing the number of transactions, say n
  • n lines containing the transaction type, quantity, and item/ingredient separated by a space.
  • To read one line do:

                String type = StdIn.readString();
                StdIn.readChar();
                int amount = StdIn.readInt();
                StdIn.readChar();
                String item = StdIn.readLine();

This is the expected output for transaction1.in:

Challenge – seatAllGuests(Queue waitingQueue) [0 points]

This method DOES NOT count towards this assignment’s grade.

This method removes people from the waitingQueue and sits them at the tables array in the order parties are dequeued. You are guaranteed to be able to sit everyone from the waitingQueue eventually.

This simulates the host. Our host isn’t optimal, it doesn’t ensure that most seats are taken.

While there are people waiting to be sat:

  • Starting from index 0 (zero), seat the next party in the first available table that fits their party.
  • If there is no available table for the next party, kick a party out from the tables array:
    1. starting at index 0 (zero), find the first table big enough to hold the next party in line.
    2. remove the current party, add them to the leftQueueVar.
    3. seat the next party in line.

tableSeats contains the number of seats per table.

tables contains the Party object currently at the table.

  • These two instance variables have been initialized in createTables() for you.

After everyone has been seated (waitingQueue is empty), remove all the parties from tables and add them to the leftQueueVar along with the other parties that already have left.

The figure below shows that tables 0 (zero) and 1 (one) are occupied.

  • tables[0] contains one party of Party.
  • tables[1] contains the other party of Party.

*are you a linked list? cuz nothing could stack up to you and you’re pretty queue(te)*

This is the expected output for seatguests1.in:

Implementation Notes

  • YOU MAY ONLY update the methods with the “WRITE YOUR CODE HERE” comment. 
  • COMMENT OUT all print statements you have written from RUHungry.java before submission
  • DO NOT add any instance variables to the RUHungry class.
  • DO NOT change any of the method signatures.
  • DO NOT add any public methods to the RUHungry class.
  • DO NOT add/rename the project or package statements.
  • DO NOT change the class RUHungry name.
  • YOU MAY add private methods to the RUHungry class.
  • DO NOT use System.exit()

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download RUHungry.zip from Autolab Attachments.
  2. Unzip the file by double clicking.
  3. Open VSCode
    • Import the folder to a workspace through File > Open

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to RUHungry directory/folder
      • to compile: javac -d bin src/restaurant/*.java
      • to execute: java -cp bin restaurant.Menu menu.in menu.out
      • OR java -cp bin resturant.Menu class-you-created-to-test

Before submission

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit RUHungry.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Post your questions on Piazza (Canvas -> Piazza)
  • Find instructors office hours here  
  • Find TAs office hours here  
  • Find tutors office hours on Canvas -> Tutoring -> RU CATS
  • In addition to office hours we have the CAVE (Collaborative Academic Versatile Environment), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

Problem by Mary Buist and Kushi Sharma

These pick up lines were written by me (Mary) during Spring 2023 Data Structures. I started making them during lectures and while working on coding assignments. Everytime we learned about a new data structure or property, I would try to make a connection. Creating these pickup lines helped me remember certain data structures and concepts and of course always made people laugh. Although on a personal note, I didn’t do well on exams, I learned a lot through the assignments and creating pick up lines along the way helped keep things interesting. But here’s the proof that your grade doesn’t define you as a person; you can still be super successful without straight A’s. And seriously, you guys are doing a great job. You’re almost done with the semester, just a couple more weeks. You got this!!!