data程序代做、java编程代写调试、java程序代写

日期：2021-03-11 11:13

The guide describes what you need to do for the minimum, core, completion,

and challenge

The data:

stops.txt stores the stops . In the file, the first line is the title. From

the second line, each line represents a stop, including its ID, name, latitude

and longitude. The entries are separated by tab.

trips.txt stores the trips of the transport network. Each trip is a sequence

of stops. In the file, the first line is the title. From the second line,

each line represents a trip. The first entry is the trip ID. Then, the sequence

of stops in this trip is represented by the second to the last entry of the

line. The entries are separated by tab as well. In each trip, there is a

directed edge from each stop in the sequence to its successive stop.

The program should read the data from the data files into an appropriate set

of data structures, and then draw the graph. The program should also have

the proper functionalities when the user presses the buttons, clicks on the

map to select a stop, and type something into the search box. The details

of the functionalities are given in the next section.

GUI is provided in the model code called GUI.java. This contains an area for

drawing the graph, a loading button, some navigation buttons, a search box,

and a text output area. It is an abstract class; the behaviour of how to draw

the drawing area, load the data, and what happens when you press the

navigation buttons, click the screen, or enter something in the search box

are left unimplemented. You will need to extend the GUI class and implement

these using your data structures. For an example of how to do this,

SquaresExample.java repurposes the GUI class to make an unrelated little game.

The program will need a collection of Stop objects, a collection of Trip

objects, and a collection of Connection objects. You will need to access stops

both by their IDs and by their names. The first can be accomplished with a

Hash Map. The second should use a Trie structure, since it needs to be able

to access all the roads whose names start with a specified prefix. The Stops

and Connections form a graph, with the Stops as the nodes, and the Connections

as the edges. The graph is directed (each trip is directed), is a multi-graph

(there can be more than one connection between two stops belonging to

different trips), but has no ‘looped’ connections that start and end at

the same stop. You need to choose an appropriate data structure for this graph

recommend using Stop objects and Connection objects, where the Stop objects

include a list of all the incoming and outgoing Connections. The Stop objects

also need to store their location, both for drawing them and for finding the

stop the user clicks on. The Connection objects need to store the Stops at

each end, and the Trip they belong to. You should decide whether to use the

IDs in the data structure or to simply connect Stop and Connection objects

directly to each other.

Solving the problem in stages

Minimum – Parsing, data structures, and drawing.

? Construct classes to represent Stops, Trips, and Connections between two

stops. The class should have methods to read the data from the files and

construct the objects. Hint: Use the Location class to represent positions

of the Stops. The class includes methods for converting from

latitude/longitude to x/y coordinates in kilometers.

? Make methods to read the data files, parse them, and create data structures.

When using the GUI class, these methods should run when the onLoad method

is called. This method is passed a File object for each of the stop and trip

files. Hint: When reading the Trips, you need to add each of the Connections

in the trip to the appropriate Stop objects. Hint: Loading the data is best

done with a BufferedReader.

? Draw the graph by filling in the redraw method left abstract in the GUI

class. This method should call a draw method on the Connection and Stop, which

should use the passed Graphics object. It will make the zooming easier if

these methods also take an origin and scale factor as parameters, so they

can calculate where on the graphics object they should be drawn.

Core – Using the graph structure and other functionality.

? Allow the user to navigate the map, i.e. implement panning and zooming

with the buttons. Whenever these buttons are pressed, the onMove method (left

abstract in GUI) is called, and is passed an enum representing which button

was pushed; this is where should write the movement logic.

? Make the program respond to the mouse so that the user can select a stop

with the mouse, and the program will then highlight it, and print out the

name of the stop and the id of all the trips going through the stop. This

can be done by implementing the onClick method left abstract by the GUI class,

which is called whenever the mouse is clicked. This method is passed a

MouseEvent object, which contains, among other things, the coordinates of

click within the graphics area. The simplest method will do a linear search

through the collection of stops to find the closest one to the mouse position.

(Use the methods in Location to convert between pixel based positions on the

screen and the locations in the Stops.)

? Implement the behaviour of the search box in the top right, which should

allow a user to select a Stop by entering its name. This can be done with

the onSearch method, which is called whenever the user presses ‘enter’ in

the search box. When they complete their entry, the program should highlight

the stop with name (exactly) matching their input, and highlight all the trips

going through that stop. Hint: Remember that there may be multiple Trip

objects going through the stop, and each Trip object may have multiple

Connections in it. Hint: The search box, and its contents, can be accessed

with the getSearchBox method in GUI.

? The text output area at the bottom of the window should be used to show

information about stops and trips, and can be accessed via the

getTextOutputArea method in GUI.

Completion – Making a trie and improving search.

? To make the program more usable, we want the search function to highlight

all the stops whose name is prefixed by the search input, and not just an

exact match. A linear search is not an efficient way of doing this, and using

some hashing scheme wouldn’t work either, as we need to do prefix-matching

(unless the hashing scheme was very cleverly designed). A better way is to

construct a trie data structure to store all the Stop objects, indexed by

their name. This data structure will need methods to add a new stop, and to

retrieve all stops matching a given prefix.

? Improve the search using a trie. Highlight all stops that start with the

prefix typed into the search box. For example, there are 4 stop names starting

with “VRD”. If the user’s search query exactly matches a stop name, it

should only highlight and show exact matches. Print out the name of the

matched stops in the text output area. Also, highlight all the trips going

through the match stops. Hint: The UPDATE_ON_EVERY_CHARACTER variable in the

GUI class can be set to true to make the onSearch method be called each time

the user types a character in the search box, and not just when they press

enter.

Challenge – Quad-trees and UI improvements.

? A linear search through the stops to find the closest one is also inefficient,

but searching for inexact matches for 2D positions doesn’t work with hashing

or binary search. (This problem is a standard problem in computer graphics.)

The right structure to use for searching for the closest 2D point is called

a quad-tree .Implement a quad-tree index of all the nodes and use it to search

for the closest node to the mouse location.

? The user interface in the GUI class is functional, but could be improved

further; find a way to significantly improve it. Two ideas are: – Implement

navigation with the mouse and scroll wheel. – Add a drop-down suggestions

box to the search box, which the user can select completions from.