Revisions History:
- Created Feb 15 2017
- ArrayLists speciified for simple TwoDimDictionary

Assignment Goals:

1. Give you experience designing and implementing data structures in Java.
2. More practice with code craft requirements. See the code craft requirements document BEFORE you start this assignment.
3. Give you experience experimentally evaluating data structure performance.
4. Give you practice with creating JDocs documentation and JUnit testing

In class we are spending a lot of time considering dictionary data structures that take a single key and support insert and search operations. What happens if you have more than one key?

Consider the problem of storing n 2 dimensional points where for each point p, p.x is an integer in the range 1...2^k, and p.y is an integer in the range 1...2^k. We want to support the following operations:

• void insert(Point p) - insert point p into the data structure.
• int count(Rectangle b) - Return the number of points in the data structure that are inside the rectangular query bounds b
• query(ArrayList s, Rectangle b) - Add to ArrayList s references to all points in the data structure that are inside the rectangular query bounds b
• int size() - return the number of points stored in the data structure.
• display() - Prints to System.out a representation of the data structure

We could simply create a list all n points and search the whole list for each query or count operations. This would give us an O(1) insert and O(n) query and count operations. But we can do better!

A quadtree is a recursive data structure for storing 2D points that is based on recursively subdividing a region into 4 equal sized quadrants. Each sub-quadrant is further divided until each point sits in its own quadrant.

A quadtree contains tree types of nodes: an internal node with four children, a node representing a quadrant containing a single point, and a node representing an empty quadrant.

One might represent a quadtree in Java as follows:

The query operation can be implemented as follows:

The insert operation can be implemented as follows:

For this assignment you are to do the following:

a) Create a java interface called TwoDimDictionary that specifies insert, query, count, size, and display operations.

b) Implement a simple TwoDimDictionary based on a Java ArrayList class. You should create helper classes for representing points and query rectangles.

c) Implement a TwoDimDictionary based quadtrees as described above. Use the  helper classes for points and query rectangles created for part b).

The rectangle class will likely have to support the following methods:

• //test if the recieving rectangle contains the point p2
  public boolean contains(Point p2) {..}
  
  
• //Test of the recieving rectangle intersects the rectangle r
  // Note: a rectangle b is not intersected by a rectangle r iff
  // it is completely above, below, to the right of, OR to the left of r
  public boolean interects(Rectangle r) {...}
  
  
• //Test if the recieving rectangle is covered by the rectangle r
  public boolean coveredBy(Rectangle r) {...}
  
  
• //Return an int between 0 and 3 representing which quadrant the point p2 falls in. (see diagram in assignment)
  public int quadrant(Point p2) {...}
  
  
• //Helper methods
  public int left(){return p.x;}
  public int right(){return p.x + x;}
  public int top(){return p.y;}
  public int bottom(){return p.y + y;}
  

d) Create a testing and evaluation class which generates random points and query rectangles and evaluates your two implementations of TwoDimDictionary.

e) Create a complete set of JUnit tests for all classes. Also document all classes using JDoc comments.

e) Perform a careful experimental evaluation of your TwoDimDictionary implementations graphing the results. Analysis the performance of the methods and make recommendations as to when one is preferable over the other.

In total you will need to create the following classes:

Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing! You are to use only code that you have developed yourself for this assignment. Be sure to hand in your documentation.

Bonus Question:

Graphvis (http://www.graphviz.org/) is a great open source tool for visualizing graphs. If you create a description of a graph in .dot language and save it in a text file. Graphvis can take that text file and produce nice visualizations of trees and general graphs. Add a toDotString() method to your QuadTree class and a saveDotFile() methot that together generate nice visualizations of your data structure. See the graphviz web site for examples.