In many areas of life, we provide goods and services to people ordered by when they line up for access (e.g., grocery store checkouts, TSA security lines). While this might promote one notion of fairness by avoiding “cutting in line” (as we will explore soon with the queue data structure), it can also result in inequalities in some applications, especially when people might make multiple purchases at once.
Imagine that you want to order tickets to your favorite popular musical artist who will be performing soon at a nearby, large concert venue. Tickets sales will begin promptly early in the morning. You (and many others) might want to buy multiple tickets, so you “get in line” by logging into the ticket sellers website. Due to popularity, many people log in simultaneously right when ticket sales open up, and you find yourself #10,578 in the line. That’s close enough to the front that you will hopefully get tickets, so long as those who logged in milliseconds before you do not buy too many tickets each. However, you will likely be stuck purchasing tickets that are for seats far from the stage where it is difficult to see your favorite artist. It would be natural to ask whether it is really fair that others who logged in simultaneously but won the electronic speed lottery should get all the good seats?
An alternative approach that might be more fair would be to keep the same line ordering, but:
In this lab, we will use the doubly-linked list and its iterator to simulate this ticket allocation process to see whether it might be more fair than the traditional approach. Here, we consider the approach to be “fair” if the sum of everyone’s ticket numbers (starting with 1) are the same (so that one person doesn’t have a total ticket allocation that is much more favorable than anyone else, like purchasing all the front row tickets).
As an example, if we consider a scenario with 5 people trying to purchase 20 tickets, we should see the following ticket allocation, where each person has the same sum of ticket numbers (42):
Person 1:
Ticket 1
Ticket 10
Ticket 11
Ticket 20
Sum of tickets: 42
Person 2:
Ticket 2
Ticket 9
Ticket 12
Ticket 19
Sum of tickets: 42
Person 3:
Ticket 3
Ticket 8
Ticket 13
Ticket 18
Sum of tickets: 42
Person 4:
Ticket 4
Ticket 7
Ticket 14
Ticket 17
Sum of tickets: 42
Person 5:
Ticket 5
Ticket 6
Ticket 15
Ticket 16
Sum of tickets: 42
You should implement your program in a class called FairTickets (in a .java file of the same name). The program should:
MyLinkedList<String> that contains the “names” of the people trying to purchase tickets (simply named “Person 1”, “Person 2”, up to “Person n” where n is the number of people in the command line argument.)MyLinkedList<MyLinkedList<Integer>> that contains a list of ticket numbers for each person (where the first inner list is the list of tickets for the first person, etc.). You will need to use a loop to add each of the inner lists.The main flow of your program should go in a public static void main(String[] args) method, but you should use good object-oriented design to split the parts of your program into instance variables and private methods.
To earn full credit for this program, you should:
MyLinkedList data structure to save both the names of people and their assigned ticket numbersListIterator to iterate through the names and ticket lists (i.e., not use any numeric indices with the get method) so the program can be as swift as possible (e.g., maybe we have 100,000 tickets to allocate for concerts at a large football stadium).However, if you were not able to complete the earlier parts of the lab, you can still earn partial credit by using Java’s built-in LinkedList collection and/or numeric indices with the get method.
Hint
To avoid using numeric indices to retrieve data from our data structure, we can instead use the next and previous methods from our ListIterator. And we can loop forward or backwards over our data structures using a while loop and the hastNext and hasPrevious methods like at the end of Part 3 of the Warmup.
We can also iterate through both the names and ticket collections together by creating an iterator for both linked lists, then calling next or previous on both in successive lines of code like:
// create the iterators
ListIterator<String> namesIterator = names.listIterator();
ListIterator<MyLinkedList<Integer>> ticketsIterator = allTickets.listIterator();
// get the first items from both collections
String name = namesIterator.next();
MyLinkedList<Integer> namesTickets = ticketsIterator.next();
where names is the collection created in Step 2 above and allTickets is the collection created in Step 3 above.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.