Overview

In Madison, especially around campus and downtown, the Madison Metro bus system is an excellent way to get around! But how can you find out when a bus is coming to your stop? One way is to use Google Maps (select the “transit” option)... but that’s too easy!

The Metro system has an API for getting schedule and live bus data about different routes. An API, or Application Programming Interface, is a set of types, data formats, and methods/functions defined by some software component (like a library or a web service) so that other software can interact with it. An API is a type of abstraction – it gives us a contract about what methods we can call and the format of data we will get back, but it does not give us implementation details. You can find the Metro system’s API documentation here: https://www.cityofmadison.com/metro/business/information-for-developers … It  defines the format for the schedule data and provides a URL we can use to get live bus updates.

In this project, you will write a program that uses the schedule data from the Metro API to tell you what buses are coming to a particular stop the soonest using a BST – a Bus Stop Tree!

NOTE the pre-assignment quiz is due on a Thursday. The assignment is due on a Tuesday!

Grading Rubric

Learning Objectives

After completing this assignment, you should be able to :

●    Describe the structure and functionality of a Binary Search Tree.

●    Implement a Binary Search Tree with the relevant recursive algorithms for adding, removing, and traversing nodes.

●    Demonstrate the utility of iterators and filtering iterators.

●    Find a Madison Metro bus from a given stop at a given time :)

Additional Assignment Requirements and Notes

Keep in mind:

●    Pair programming is NOT ALLOWED for this assignment. You must complete and submit P09 individually.

●   The ONLY external libraries you may use in the files you submit are: import java.time.Local Date;

import java.time.LocalTime;

import java.util.Iterator;

import java.util.NoSuch Element Exception;

import java.util.Stack;

import java.util.List; (only in BusStopTreeTester.java)

import java.util.ArrayList; (only in BusStopTreeTester.java)

●    Use of any other packages (outside of java.lang) is NOT permitted.

●   You are allowed to define any local variables you may need to implement the methods in this  specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up.

●   You are allowed to define additional private helper methods.

●    Only the BusDriver and BusStopTreeTester classes may contain a main method.

●   All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide  .

●   Any source code provided in this specification may be included verbatim in your program without attribution.

●    Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope.

Need More Help?

Check out the resources available to CS 300 students here:

https://canvas.wisc.edu/courses/375321/pages/resources

CS 300 Assignment Requirements

You are responsible for following the requirements listed on both of these pages on all CS 300

assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while :

●   Academic Conduct Expectations and Advice, which addresses such questions as:

○    How much can you talk to your classmates?

○    How much can you look up on the internet?

○   What do I do about hardware problems?

○    and more!

●   Course Style Guide, which addresses such questions as:

○   What should my source code look like?

○    How much should I comment?

○    and more!

Getting Started

1.    Create a new project in Eclipse, called something like P09 Bus Stop Tree.

a.    Ensure this project uses Java 17. Select “JavaSE-17” under “ Use an execution environment JRE” in the New Java Project dialog box.

b.    Do not create a project-specific package; use the default package.

2.    Download bus.jar and add it to your Eclipse build path by right-clicking on it and selecting “ Build Path” -> “Add to Build Path …” (If you are curious and want to see the source code for this jar,

you can download it via the links at the end of this section).

3.    Download  two (2) provided Java source files from the assignment page on Canvas. You will not modify these files at all.

a.    BusDriver.java (DOES include a main method)

b.   BusForwardsIterator.java

4.    Download three (3) incomplete Java source files from the assignment page on Canvas. You will complete these.

a.    Bus.java

b.   BusStopTree.java

c.    BusStopTreeTester.java (DOES include a main method)

5.    Create one (1) new Java source files within that project’s src folder:

a.    BusFiltered Iterator.java – you may want to add any empty stub implementation of the constructor and the Iterator interface for now so that the rest of your project can

compile. You can fill in the stubs with the real implementation later.

6.    Download the Metro Transit Schedule Data from

http://transitdata.cityofmadison.com/GTFS/mmt_gtfs.zip

a.    NOTE: unfortunately, there doesn’t appear to be a working HTTPS version of this link (i.e., one that uses encryption). You may get a security warning from your browser.

Generally, you should heed those warnings. In this case, we are endorsing this link. 7.    Create a new folder in Eclipse under the project called mmt_gtfs.

8.    Extract the zip file such that its contents end up in the new mmt_gtfs folder.

a.    On Windows, right click on the zip file then choose Extract. Select the mmt_gtfs folder in your Eclipse workspace.

b.    On macOS, double click on the zip file. Then, drag-and-drop the files onto your mmt_gtfs folder in Eclipse.

9.    You should now see something like this (NOTE: you will likely need to refresh the project to see the addition: Right Click on the project in the Package Explore; then select Refresh.):

If you are curious about the source code for

bus.jar, you can download it via these links :

●   BusDataLoader.java

●   BusRoute.java

●   BusStop.java

●   Node.java

1. Overview

In this project you will implement an application that reads bus schedule data provided by the Madison Metro API and constructs a Binary Search Tree to sort buses by when they arrive at a particular stop

(presumably so you can get on the bus). We are providing the code that reads the schedule data files and parses it. You will provide the code that constructs the tree. The Metro system provides the buses.

You can find the Javadocs for this project here.

Provided Classes

We are providing the following classes (some of which are in bus.jar). You do not need to implement anything in them.

●    BusDriver (ha!) – this is the driver class with a main method. It loads the bus schedule data,   prompts the user for input about a desired stop, and then builds and uses a BST to give you a sorted list of relevant buses.

●    BusRoute – this class contains the raw schedule data for one bus route.

●    BusDataLoader – this class contains functionality for parsing the raw schedule data into usable objects.

●    BusStop – this class represents a single bus stop in the Metro system. Each stop has a unique ID number. All the stops in the system are created by the BusDataLoader, and you should use

BusStop.getStop() to get a particular stop by ID.

●    Node<T> –  a generic Binary Search Tree node.

●    BusForward Iterator – an Iterator<Bus> that returns all Buses that arrive at a stop after a given time.

Classes You Will Implement

You will completely or partially implement the following classes:

●    Bus – represents a single bus on a particular run of a particular route. Specifically, you will implement the Comparable<Bus> interface for this class.

●    BusStopTree – a BST (ha!) of Node<Bus>.

●    BusFiltered Iterator – an Iterator<Bus> that returns all Buses from another iterator that go to a particular destination stop.

●    BusStopTreeTester (ha!) – a tester class for your BST implementation.

Organization of the Bus Stop Tree

The core data structure in this project is the BusStopTree, which is a Binary Search Tree – a BST (ha! see what we did there?!) of Bus objects. The BST will order buses by when they arrive at a particular stop of interest (the userStop). In other words, the minimum value in the BST will be the Bus that arrives at userStop earliest today, and the maximum value in the BST will be the Bus that arrives at userStop latest today.

We are providing you with a generic BST Node<T> class. Your BusStopTree must be built out of

Node<Bus> (note Bus, not T), and you will implement the relevant algorithms in the BusStopTree class. You will also need to implement Comparable<Bus> for Bus, which is the comparison method you will     need to use in the BusStopTree.

2. Implement Comparable<Bus> for Bus + Tests

Our BST is going to be a tree full of Buses, so we need to have a way to compare Bus objects. To do this, you will implement the Comparable<Bus> interface for the Bus class. See the javadocs for more information.

Implement these three test methods for Bus.compareTo() in the BusStopTreeTester.

1.   test BusCompareToDifferentArrivalTime

2.   test BusCompareToSameArrivalTimeDifferent Route

3.   test BusCompareToSameArrivalTimeSameRouteDifferent Direction

A note on testing:

●    DO NOT use BusDataLoader.java in your tests. (As general programming practice, we avoid file (or network) I/O in tests.)

●   We have provided a few methods to ease the creation of test objects :

○    BusRoute.dummyRoute() is a convenience method to simplify route creation in your tests. It should not be used outside of BusStopTreeTester.java.

○    BusStop.createDummyStops() is called at the beginning of the main method of the  BusStopTreeTester.java. This creates BusStops with stopIds ranging from 1-100. You should use these stopIds in your tests. This method should only be called once.

3. Implement the BusStopTree + Tests

We recommend implementing the methods in the order list below. Testing and debugging the latter methods will be significantly easier if you know the structure of your BST is correct, and implementing the earlier methods will help you to get the structure correct. After implementing each of these methods, implement the relevant tester methods in BusStopTreeTester, and test your implementation thoroughly! If you wait to the very end to test, you will have lots of weird and confusing bugs.

1.    get First BusHelper and get Last BusHelper

2.    isValidBST (see the hints below) and following test methods :

a.   testIsValidBSTEmpty

b.   testIsValidBSTInvalid

c.    testIsValidBSTValid

3.    heightHelper

4.    addBusHelper and the following test methods:

a.   testAddBusEmpty

b.   testAddBus

c.    testAddBusDuplicate

5.    containsHelper and the following test methods :

a.   testContains

6.   get First NodeAfter and the following test methods :

a.    testGet First NodeAfterRoot

b.   testGet First NodeAfterLeftSubtree

c.    testGet First NodeAfterRightSubtree

Note that you may NOT write ANY loops (of any kind) in the BusStopTree class. You MUST implement the above methods recursively, as indicated in the javadocs. In most cases, we’ve provided an implementation of the public method that calls a private helper method. The helper method for a method named foo would be a private method called fooHelper. You are required to implement all of   the helpers specified in the javadocs. You may also define your own private helper methods in addition to the ones we are requiring you to write.

Some hints :

●    Draw LOTS of pictures!

●   Write tests as you go along. If you save testing for last you will be sad.

●    For most of the BusStopTree tests, it is easiest if you use nearly identical Bus-es that only differ by one aspect (eg, arrival time at userStop or routeName). That will help you keep track of the  relative ordering.

●    Remember: in every node, the left and right subtree should also be a valid binary tree. That is, if  you were to just yank out any left or right node anywhere in the tree (with its descendants), they could stand alone as a valid binary tree.

●    isValidBST should check that all nodes in the BST obey the ordering properties of BSTs. Consider what should be true of the left and right children of any BST node? What should be true of ALL

left and right descendants of a node (i.e., all nodes in the left/right subtree)? Think about the

algorithm described in the lecture. How can you implement it? Will your implementation flag the invalid tree depicted below?

●   get First NodeAfter should only consider the time of a Bus, not its name, etc. That means you

should compare the arrivalTime of Buses directly (LocalTime is also Comparable, though, so you can use LocalTime.compareTo()), rather than use Bus.compareTo(). In contrast, contains should  compare Buses using their compareTo().

●    If you are writing really long methods, you are probably overthinking it. The longest method in    our reference implementation is removeBusHelper, and it is ~40 lines long (including 16 lines of comments and whitespace), and it is about twice as long as anything else in BusStopTree.

●   Feel free to change the toString methods of anything in the program to help your debugging.

4. Implement the Iterator + Tests

Implement BusFilteredIterator. It takes another iterator and filters out the elements that don’t stop at a  particular BusStop. Make sure you do not change any of the iterator’s fields when you call hasNext() – all changes should be happening in next().

Implement the following test methods for the Iterators:

1.   testGet Next BusesToEmpty

2.   testGet Next BusesToSome

3.   testGet Next BusesToAll

Future work

Congratulations! At this point you should be able to run the main method in the BusDriver class and get useful results  翼

However, there is a lot of functionality we have not implemented that you could add to the app for your own enjoyment and use. Here are some ideas if you are looking for a neat project (or trying to impress a potential employer):

●    Implement BusStopTree.removeBus(). You should know how to do this. We may ask you to do it in the future!

●   The Metro API publishes live trip updates (e.g., how late a bus is running). Update the program to make use of this data.

●   The Metro API also publishes schedule data about holidays and detours. Currently, our BusDataLoader mostly ignores this data. Update the program to take it into account.

●    Handle arrivals after midnight. These are kind of a pain because the raw schedule data has them with timestamps like 25:30, and most time parsing libraries require the hours to be 0 to 23 …

●    Handle arrival and departure times separately. The schedule data actually has separate arrival and departure times for each bus at each stop because buses actually take some time to load  and unload passengers. For simplicity, our program always treats buses as taking 0 time to do  this. Fix this inaccuracy.

●   Add trip planning. Can you find the fastest path to get from one location to another via buses? One way to do this would be to compute for each bus route the best place to get on and off the bus given an origin and destination. Then, sort the routes by the total amount of walk + ride time and present the user with useful information, such as how far they would need to walk, which stop to walk too, and estimated arrival times.

●    Implement a backwards iterator – an iterator that tells you what Buses you have missed at a given stop.

Assignment Submission

Hooray, you’ve finished this CS 300 programming assignment!