Lab 1: Library Waiting List
Getting Started with GitHub Classroom
Complete the week 1 Self Learning Module to configure the lab 1 IntelliJ template.
- Review the
- Introduction to
- Introduction to benchmarking
- Compare efficiency of add back, remove front, and get operations for the two list types
- Decide between two data structures for a given use case
You are a software engineer at a new online startup that wants to take libraries online. Patrons will be requesting items (e.g., books) online, have the items shipped to their home, and ship them back when done. Your company hopes that you can expand access to libraries and reduce costs and duplication from having separate libraries in every neighborhood.
You've been assigned to implement the waiting list system that allows patrons to make requests and determine which requests to fulfill next. You realize that lists are an appropriate abstract data type to use. Lists keep items in order so you can keep track of which requests were received first.
Java has two main list implementations (
You need to decide which implementation is more appropriate for your use
case. You will implement the basic waiting list system, use the provided
benchmark driver to explore the performance of various operations of the
system, and analyze the results to conclude which data structure you'll use.
Your project will have three classes (
BenchmarkDriver class has been
provided to you. You must implement the remaining three classes (see UML
diagram below). The
ItemRequest class stores a pair of user and item ids.
WaitingList class has the following methods:
WaitingList(List<ItemRequest> list)— The constructor takes an empty list instance to use for storing the item requests. This design will allow us to benchmark the waiting list system with different list implementations.
void addRequestItem(ItemRequest request)— Adds a request to the end of the list.
boolean isEmpty()— Is the waiting list empty (no requests)?
void clear()— Removes all requests from the waiting list.
ItemRequest nextFulfillableRequest(double fulfillableThreshold)— Searches the list of requests, starting at the front (index 0), to find the first request that is fulfillable. Each request item has probability that it can be fulfilled. If that probability is at least as large as the
fulfillableThresholdthe request is considered fulfillable. If a fulfillable request is found, it is removed from the list and returned. If no fulfillable request is found, the method returns
void getAllRequestsFromUser(int userId, List<ItemRequests> userRequests)— Searches the list to find all requests with the given user id and adds them to the provided
boolean cancelRequest(ItemRequest request)— Searches the list for the given request, removes it from the list if found, and returns a value indicating whether or not the request was found.
Open the IntelliJ project from version control (see SLM1) and implement the required classes.
Run the provided
BenchmarkDriverclass and record the results.
Review the source code for the provided benchmarks.
Use the provided benchmarks as templates for creating two of your own benchmarks for the
removeFromFrontBenchmark(List<String> list, int nElements)— measures the time to call
remove(0)until a list that starts with
nElementselements is empty
getMiddleBenchmark(List<String> list, int nElements)— measures the time to call
Each method should begin by clearing the list and then adding the same string to the list
Write a GUI program that generates a graph with benchmark results for each of the two benchmark methods.
Each graph must plot the result from calling the benchmark method with sizes of 20,000, 40,000, 200,000 and 400,000 for both the
ArrayList(plotted as circles) and
LinkedList(plotted as squares)
Each graph must have a title, axes labels, and labels for the data points types.
The ScatterChart class can be used for generating plots.
Below is an example of what your program should produce. Note: the y-values for this data was randomly generated.
Complete the worksheet in your repository. It is a Word file called
Just for Fun
Once all required parts of the assignment have been completed, motivated students may wish to:
- Plot additional data points
- Characterize the growth rate of the data points on the graphs
- Modify the plots so that the x-axis uses a logorithmic scale
- Refactor the benchmarking code to use a functional interface to define the operation being benchmarked
This laboratory assignment was developed by Dr. RJ Nowling.