CSCI-UA 102 Data Structure Project 5

Project 5: Mountain Hike

---

You may discuss any of the assignments with your classmates and tutors (or anyone else) but all work for all assignments must be entirely your own. Any sharing or copying of assignments will be considered cheating (this includes posting partial or complete solutions on Ed, GitHub, Discord, Groupme, … or any other forum). If you get significant help from anyone, you should acknowledge it in your submission (and your grade will be proportional to the part that you completed on your own). You are responsible for every line in your program: you need to know what it does and why. You should not use any data structures and features of Java that have not been covered in class (or the prerequisite class). If you have doubts about whether or not you are allowed to use certain structures, just ask your instructor.

---





Introduction and objectives

The goal of this project is to implement a program that uses a binary search tree to model a mountain hiking expedition: A hiker starts at the top of the mountain. They need to find their way down the mountain with limited resources to survive and overcome obstacles. Your program will produce a list of all the possible paths that the hiker should take to survive.

The mountain is represented by a binary search tree. Nodes in this tree represent rest stops. The hiker restocks their supplies at those rest stops. But they may also encounter obstacles at the rest stops. Some of the supplies that they carry with them may help them pass through the obstacles. The paths from the root down represent possible trails. Each path from the root of the tree to a leaf represents a path down the mountain. The hiker needs to evaluate each of those paths and decide if it is feasible or not.

Start early! This project may not seem like much coding, but debugging and testing always take time, especially for recursive algorithms and the implementation of new data structures.

 USER INTERFACE

Your program has to be console-based (no graphical interface). The user should not be prompted for any information (all required information for the program to run is provided in the input file given as a command line argument). The output of the program should be printed to the standard output stream. Any error messages should be printed to the standard error stream.

 PROGRAM USAGE

The program is started from the command line (or run within an IDE). It expects one command line argument: the name of the input file.


The input file will be a test file. Each line in the input describes a single point on the mountain (node in a BST). The format of each line is as follows:

LABEL SUPPLIES OBSTACLES

In the above, LABEL is a string with the name of the rest stop. The alphanumeric comparison of the labels determines the shape of the tree. SUPPLIES is a (possibly empty) list of supplies that the hiker will get at this rest stop. Valid supplies are food, raft, axe. OBSTACLES is a (possibly empty) list of obstacles that the hiker will encounter at this rest stop. Valid obstacles are fallen tree and river.

See below for an example.

If the program is executed with a non-existent or invalid command line argument, it should print an error message and terminate.

If the file contains any additional (and invalid) strings in the description of a rest-stop, they should be ignored.

The program should not be interactive. All input should be provided as the command line arguments. The user should not be prompted for any additional information.

 RESULTS/OUTPUT

The program has to calculate all possible paths down the mountain that lead down to the lowest level (i.e., to the leaves in the lowest level of the mountain-tree) that the hiker can take and survive.

The program output should consist of several lines equal to the number of safe paths. Each safe path should consist of a space-separated list of the rest-stop labels in the order in which they are followed from the top of the mountain to the bottom. The paths should be printed in order from left to right in the tree that represents the mountain (this is also an alphanumeric ordering of the paths).

 EXAMPLE



The above figure depicts visually a tree that results from the following input file

J food raft food
E fallen tree
G food axe river
I food fallen tree
H
F
B food
A
D axe food
C
P
L food food river
R axe food raft
Q
K
N axe
M
O

food is a single ration that lasts hiker the time needed to traverse a single segment of the trail (a single edge in the tree)

axe is needed when the trail is obstructed by a fallen tree. The hiker cannot pass a fallen tree obstacle unless they have an axe. Once they use the axe, it becomes dull and cannot be used again.

raft is needed when the trail continues through a river. The hiker cannot pass a river obstacle unless they have a raft. Each raft is designed for a single river crossing - once used, it cannot be used again.

Note that the hiker can use an axe or a raft at the very same rest stop at which it was collected or at any rest stop later along the journey.

There are many possible paths down the mountain depicted above, but only two lead to safety.

• J E B A, J E B D C, J E G F, J E G I H - the hiker reaches rest-stop E and cannot continue without an axe.
• J P L K - the hiker reaches rest-stop K and falls off the cliff (since the leaf K is not at the lowest level of the tree).
• J P L N M, J P L N O - the hiker uses the raft at rest-stop L and with new food supplies, continues to the bottom of the mountain at either M or O.
• J P R Q - the hiker reaches rest-stop Q and falls off the cliff.

In this case, the program should produce two lines of output:

J P L N M
J P L N 0

Note that the rest stops' labels can be longer strings, not just single letters as above.

 DATA STORAGE AND ORGANIZATION

The design of classes is up to you, but you do need to implement certain classes to represent certain entities in the program. You need to make decisions about how to design these classes to produce an efficient and well-put-together program. Make sure that all methods that you include in a particular class belong to that class. Java is an object-oriented programming language and your programs should follow object-oriented principles.

MountainClimb class

This is the class that is the program. This means it has the main method. This class is responsible for parsing and validating the command line arguments, reading and parsing the input file, producing any error messages, handling any exceptions thrown by other classes, and producing output.

BST<E> class

This is a generic BST<E> class. The specification is similar to the one for TreeSet class provided by Java libraries, but your implementation will be very different.

The specification for this class is provided at its javadoc page. You can use the source code we wrote in class, but keep in mind that the class you are implementing requires additional functionality and you may need to rewrite some of the methods created in class.

Node class

The program should provide and use a nested class (to learn more about nested and inner classes see: https://docs.oracle.com/javase/tutorial/java/javaOO/nested.html) that provides nodes for your tree. The details of the implementation of that class are up to you, but this class should be private (or protected, if another class in your code inherits from it and needs to be able to create variables of type Node):

private class Node

HINT: to improve the performance of your BST algorithms, it may be useful to keep additional data fields in the nodes, i.e., more than just data, left and right. Those design decisions are up to you. But you should explain in comments for this class, why you have additional data fields if you chose to do so.

Iterator

The BST<E> class implements Iterable<E> interface. This means that its iterator() method needs to return an instance of a class that implements the Iterator<E> interface. The iterator() method should return an iterator instance that accesses the values in the tree according to the inorder traversal of the binary search tree. The two additional methods preorderIterator() and postOrederIterator() need to return iterators that access the values in the tree according to the preorder and postorder traversals, respectively.

The implementation details are up to you and you are free to implement more than one internal private iterator class. The next() and hasNext() methods of the iterator classes should perform in O(1). The constructor of the iterator classes can be O(N). You are not allowed to use the implementation of iterators of any built-in classes when writing your implementation of the iterators.

The remove method in the Iterator<E> interface is optional and you do not need to provide the actual remove functionality. (This means that the method has to exist, but instead of performing its function, it throws an instance of UnsopportedOperationException.)




NOTE: normally, all data fields in the class should be private. However since the BST class serves as a base class for the BSTMountain class below, its data fields can be made protected instead to allow the subclass to access these data fields.

BSTMountain class

This should be the class that inherits from your own BST<RestStop>. Your class should represent the mountain itself (therefore, it should not be generic and its nodes should store data items of type RestStop). It is up to you to decide how to implement this class, which methods to provide etc. Hint: this class should implement methods that allow a hiker to explore the mountain. The reason for that is that the exploration algorithm is specific to the mountain itself, not to the hiker (any Hiker object will follow the same steps when traveling down the same mountain). The exploration of the mountain is the process of figuring out which paths lead safely from the top of the mountain to its bottom (lowest level) with sufficient supplies for the hiker to survive.

RestStop class

This class should represent a single rest stop. It should be capable of storing the label of the rest stop along with a list of the supplies that a hiker can collect at this rest stop and a list of obstacles that a hiker may encounter at this rest stop. It may be useful (or necessary) to implement the Comparable interface.

Hiker class

This class should represent a hiker traveling down the mountain. An object of this class should be capable of keeping track of all the supplies that the hiker has in their possession. This information should be updated as the hiker travels along a trail and consumes supplies (by either eating along the way or using the tools to clear the path or cross the river).

You may, but you are not required to, implement other classes.