Data dictionaries and notes about Cities

We have alluded to the fact that you are going to have to maintain a dictionary (a collection) of all the cities we create using the createCity command. Generally speaking, you are going to want to be able to access cities by their names in logarithmic time. You can use a TreeMap for this, where the keys are the cities' names and the values are the city objects themselves. This will allow you to get the cities' $(x,y)$ coordinates based on their names very quickly. You also need to be able to find cities based on their $(x,y)$ coordinates, since aside from two cities bearing the same name being illegal, two cities cannot occupy the same $(x,y)$ coordinate. You'll need a way to sort points in 2D space in such a way that they can be stored in a TreeMap. Remember reading about comparators?

You can write a comparator that will sort $(x,y)$ coordinates in a useful way: sort on the $y$ coordinate first; if two cities have the same $y$ coordinate, compare their $x$ coordinates to determine their final ordering. A sample ordering:

(0,0)
(1,0)
(100,0)
(0,1)
(1,5)
(100, 100)
(0,1000)
(5,1000)
(50,1000)

Keep in mind: cities will always have integer coordinates. In fact, we will only use integer values as inputs to your projects. However, you may find it useful to convert them to floats or doubles in later project parts.

For every city created, you'll need to add it to two indexes: the first maps strings to cities (name to city object) and the second would coordinates to city objects. However, if you write your City class such that the city's name is one of its fields, then using maps doesn't seem to make any sense because the keys contain all the info you need (but keep reading). You could instead use sets. The first set, which sorts by name, uses a CityNameComparator which compares two cities just based on the default string comparison between their two names, and the second which uses a CityCoordinateComparator which compares two cities based on the $(x,y)$ ordering discussed above. However, there is one minor problem with using sets: once you put something into a set, you can't easily get it out again based on some other data type. In other words, suppose I pass you a string $s$, which I claim is the name of a city in your set. If you modified your comparator to allow strings to be passed to the compare() method, the best you could do is tell me that the city with that name either exists or doesn't exist--you can't get the actual city object back out of your set in better than linear time. So at least for the names, you definitely want to use a Map despite the fact that a Set could sort them for you. The coordinate dictionary will probably only be used to check containment, so in that case a set is probably sufficient.

Here I go again alluding to this mysterious City object. Yeah, the major data type we'll deal with throughout this project is a colored, named point in 2D space which we will be calling a City. Yes, you will have to write some class to store this information. A subjugate data type which you will probably also need to implement is a line segment in 2D space, which we're calling an Road. You'll have to do geometric computations involving roads and cities (specifically distance). Boo. Fortunately, Java has already done that for you. If you look at the java.awt.geom package, you'll see two useful classes: Point2D and Line2D. Both of these are abstract classes, but each contains two inner classes that are concrete implementations of their enclosing classes: Point2D.Float, Point2D.Double, Line2D.Float, and Line2D.Double. As you've guessed, the .Float and .Double refer to the precision in which their coordinates are stored. There's no Point2D.Integer, but you can just use the Float version. We'll never pass you a point whose coordinates have more than 23 significant digits (thus subjecting you to a precision error due to the limitations of Float).

The best way to implement a City is to have your class extend Point2D.Float, and add data members (strings) for name and color. Note that Point2D defines two public fields, x and y, which store the coordinate data. Note: do not redefine an x and y in your City class if you extend Point2D.Float. Most Java compilers will allow you to create fields with the same names as fields in the parent class, but good editors like Eclipse will warn you about it. The problem with redefining your own fields is that the Point2D class has already implemented all the geometric computations you need to worry about, but those methods use the x and y as defined in the Line2D.Float class. If you redefine x and y in City and fail to set the x and y in the parent class (by saying super.x = and super.y =) your geometric computations will never work because all your points will be treated like (0.0f,0.0f). The same goes for Line2D and its x1, y1, x2, y2 fields.

You should avoid the urge to make your Citys implement the Comparable interface since I've already described two obvious ways to sort them and there are probably more. It's better to force your users to provide a Comparator than run the risk of them expecting one ordering and discovering another. Comparators are quick and easy to write and prevent any possible confusion on how they'll turn out when sorted.