Assignment #6 Solution

1 Class Design (20 points)




Design a class hierarchy (classes and/or interfaces) to support a program dealing with geographic

objects. Support the following classes (at least):

- Countries

- States/Provinces

- Cities

- Boundary Segments

- Rivers

Support the following operations, where applicable, plus any others that seem useful (arguments

have been omitted, but you will have to include them):

- area()

- capital()

- getCities()

- getCountry()

- distance() { between cities

- boundaryLength() { total length of boundary

- neighbors() { objects sharing boundaries

- borderOf() { the countries/states this separates




Write out the class definitions, instance variables and method definitions. Some of the instance

variables should probably be various kinds of Collections.




You do not need to implement the methods, but you should include comments inside each method that describe the approach you would

take (alternately, you can actually implement them (that might be simpler for some methods).




Use interfaces and superclasses where appropriate.




Supply javadoc comments for all classes, interfaces,

and methods.

The system you write should compile, even if it doesn't actually work (because the

methods are just stubs with comments).




Identify all of the classes as belonging to the package "geography", and put the .java files in a directory called geography,

so that javadoc functions properly.




Note that this means that the compiler must be run from outside the geography directory,

and you should type `javac geography/*.java`, say, to compile your code.

This is annoying, and one of the reasons I dislike Java's package system.

(You would do the same thing to run a program in a package, but in this particular case you are not writing a program, so the issue won't come

up.)




Note: This problem is deliberately openended. Don't panic! Be creative!

Extra credit: Be especially creative!




2 Permutations (30 points)

Implement a class that works like an iterator and generates all possible permutations of a list.




It cannot actually be an Iterator, because the official Java Iterator interface looks like the following:

a

```java

public interface Iterator<E {

public boolean hasNext();

public E next();

public void remove();

}

```




The `next()` method of a Java iterator returns an element of a collection, but our permutation generator must return a whole list.

Nevertheless, we will adopt the mechanics of iterators.




Create a Permutations object that implements the following three methods (at least):

```java

public class Permutations<E {

public Permutations(List<E list);

public boolean hasNext();

public List<E next();

}

```




Notice the difference? We should be able to call the constructor with an arbitrary list. Then,

as long as `hasNext()` returns `true`, we should be able to call `next()` and get a new permutation of

our list.




The easiest way to generate permutations is (not surprisingly) recursively.




The algorithm for creating a Permutations object is as follows:

- (Base case) If I am a **P**ermutations object of list length 0, do nothing, except to note that I

should always return false when `hasNext()` is called.

- (Recursive case) Remove and remember the first element (**c**) from the list.

- Create and remember a new Permutations object (**P**) with the leftover list.

- Obtain and remember the first permutation (**L**) from this new object, or an empty list if it

has none (because it is size 0).

- Initialize an index counter (**i**) to 0.




Each time the next() method is called on a Permutations object, it should do the following:

- Return a copy of **L** with **c** inserted at position **i**. Increment **i**.

- Once i becomes too large, set **L** to `P.next()` and reset **i** to 0.

- If **P** has no next permutation, then this object is finished as well. `hasNext()` should return

`false` from here on out.

Here's how it works for the list [0, 1, 2]:

- For each permutation of [1, 2],

- Insert 0 into each position in the list.




Thus successive calls to next() return [0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1] and [2, 1, 0].




After this last list is returned, `hasNext()` should return `false`.




Hint: The list you return should be a newly-created one, either a LinkedList or an ArrayList

(your choice), with elements copied over.




Don't try to use the same list that you were given in the constructor, because you'd be disassembling it and reassembling it at multiple levels of recursion,

and it's almost impossible to keep it straight and do it right.




Extra Credit: You should really think about doing this one, because it's a great way to test

your Permutations object. Use your Permutations object to implement the exponential NP sort

that we talked about in class. Generate all of the permutations of a list in turn, checking each one

to see if it's sorted. Stop when you find the sorted list. How long a list can you sort using this

algorithm, before the time it takes becomes intolerable?