HW 4 - Note there are 2 parts (3 methods)


NOTE: This HW has 200 Bonus points available (an additional method)

SETUP

Note that in this assignment, you will have to use the eclipse IDE. To start:


Part 1 - using Trees to parse HTML

HTML is a very simple language. It is not a programming language (it has no logic or instructions). It is a markup language, using tags (like <p>) to define the structure and content of a Web page. The structure of an HTML document (as well as XML), is hierarchical. Tags are placed inside of other tags, to denote relationships between different page components. Becauase of this, Web Tools (like Browsers) store Web page documents like HTML & XML files in trees. In this part, we are going to build Web pages (HTML) by manipulating trees. For this part, I have provided the HTMLFrame class.

The HTMLFrame class has a main method that opens up a GUI and uses a JTree to display the contents of a tree that stores an HTML document we may want to build. Note that we will never load or save our HTML document, just view it using the preview button. The GUI has buttons to allow us to add node, remove nodes, and change the contents of nodes.

The Java API has a number of classes for storing and manipulating trees, but 3 interest us for this part of the assignment: DefaultTreeModel, which is a tree-managing class, DefaultMutableTreeNode, which is a tree node class, and TreePath, which stores an array of objects representing a path to a node.

YOUR TWO METHODS, ALL FOR THE HTMLFrame CLASS

NOTE: Note that when a tree has been updated, to ensure the changes are immediately displayed we have to call the JTree's scrollPathToVisible method, which takes a tree path argument. A tree path can be constructed using the path of nodes provided by the node you want to make visible. For example, to make the titleTextNode visible, we might write:

tree.scrollPathToVisible(new TreePath(titleTextNode.getPath()));

NOTE: Your nodes should be storing text. Either tag text (like <body>), or content text, which humans will acutally read in a Web browser. Your nodes do not have to store HTML closing tags, but your generateHTMLText method needs to include them when generating the Web page text.

Should you implement your tree initialization properly, when the program starts it should look like:



Should you click on the "Preview" button, it should open a dialog that looks like:



Part 2 - FlightPlanner

The FlightPlanner program might be used by an airline that flies to a number of American cities. It uses AirportGraph, a graph-managing class, to create paths between various cities it flies to. Left-click on a city to select the start city for a trip. Right-click on a city to select the destination of the trip. Examine the following 3 files:

YOUR METHOD, IN THE AirportGraph CLASS:

Note that I have provided the calculateDistance method inside the Airport class. This method will return the number of miles between the two Airport arguments, a1 & a2.

A Greedy Path Algorithm: When trying to find a path from point A to poitn B, at each step along the way, a Greedy algorithm would make decisions with the most immediate benefit. So, for example, if I am looking for a path starting at node A, I will start by getting all neighbors of A, and if none of them are B, I will try to make a path to B going through the neighbor closest to A. You should then continually do this until you have a complete path connecting the two airports.


200 Bonus Points

You may earn additional points in this assignment by finding the shortest path from the source to the destination, not just any old path. In order to do this, you'll have keep track of the minimal path found to each node you encounter, and update this path as you find faster routes. This is not so easy, so make sure you design your solution out first before starting your coding. For this part, you must define the following method:


Handin Instructions


Grading

All assignment will be graded purely based on program performance. Submissions that do not compile will receive 0 points. Submissions that never produce correct results will receive 0 points. The TAs will test your submissions using various input, and grades will be awarded depending on how often your code produces the correct results.



SUNYSB CSWeb page created and maintained
by Richard McKenna