General
Now in addition to the dictionary data structure, there’s a spatial data structure
encapsulated in the Point Region Quadtree (PRQT).
createCity – adds to dictionary/treemaps
mapCity – adds to PRQT
unmapCity – removes from PRQT
deleteCity – if city exists in PRQT, remove it AND remove city from
dictionary/treemaps
clearAll – clears both the dictionary/treemaps and the PRQT
So cities can be created and be unmapped. It may be wise to establish a means
of categorizing which cities have been mapped and have not been mapped.
PRQT
Recall, the PRQT is a 4-way search trie. That means all useful data is stored the
leaves/external nodes while internal/non-leaf nodes have 4 child pointeres each and
serve as “guides” to the leaves/data. The PRQT is a key-spaced partition which means
the manner of partitioning is decided at compile-time, not run-time.
The spatial map’s dimensions are present in the first commandNode before any
command processing. The attributes are spatialWidth and spatialHeight. They will
always be equal to one another (hence a square map, like you’re used to) and be
powers of 2 (so that partitioning can go smoothly). There are no test cases that
partition beyond the 1×1 grid, so you do not have to worry about this error case for
now.
You’ll want a class to maintain the nodes of this PRQT, but because it is a trie, the
leaves are actually going to be a little bit different than the non-leaf nodes. This is
where inheritance and abstract classes come into play. By making your PRQT node
class an abstract class, any class that extends will be considered a PRQT node. So
maybe you’ll find it smart to have some abstract methods in that class, such as insert,
contains, and delete.
You’ll want to have three different types of nodes that extend your base PRQT node
class. To make things easier, they’ll be called white, gray, and black nodes.
White – represents empty region/rectangle
Black – represents region/rectangle occupied by a city (cities treated as vertices in the
spatial map, ignore radius component of cities)
Gray – represents the partitioning
Gray nodes are the internal nodes that serve as guides to the leaves (the black and
white nodes).
Coding Suggestions
1. Make White node a Singleton (look up Singleton design, it’s easy to implement)
2. Make Black node have a city field
3. Make Gray node have fields for its center point, dimension, and references to its 4
children (perhaps a Node array of size 4 called children)
4. Make your insert/remove methods return the type of your abstract node class!
5. Use the classes Shape2DDistanceCalculator and Inclusive2DIntersectionVerifier
provided in the cmsc420 utility jar.
You can have anything else you want in your node classes.
PRQT Insertion
Note: PRQT starts off as a white node because it’s empty
White – return black node with city as field
Gray – find out what quadrant the city to be added intersects and assign to that child
what it would be if that city were inserted there
Ex: Say city “A” intersected quadrant II of a gray node. Then I would code something
like: children[1] = children[1].insert(A);
Black – Will need to partition because can’t have more than one vertex in a black
node as per PRQT rules, so create a new gray node from this black node, and
then perform gray node insert on the previously existing city as well as the new city
to be added.
PRQT Removal
White – return white
Black – if the city you’re removing is the one in this black node, return white; else,
return this black node
Gray – Find in what quadtrant the city to be removed lies and assign to that child
what it would be with removal performed there
Ex: remove city “A” when A is in quadtrant III of the current gray node: children[2]
= children[2].remove(A); Then after this, check to see if the gray node needs to be
condensed by checking the four children.
if (4 white children) return white
else if (3 white children, 1 black) return black populated with that one’s city
else return that gray node as is
Keeping Track of Dimensions
There are two ways to do this; I recommend the second.
1. Store all dimension info in each node somewhere.
2. Add some parameters to your insert/remove methods that keep track of the
dimensions. This could be passing the bottom left coordinate and dimension around
as parameters.
Example prototypes:
public abstract PRQTNode insert(City a, Point2D.Float botLeft, int dim);
public abstract PRQTNode remove(City a, Point2D.Float botLeft, int dim);
Nearest City Algorithm
Can find nearest city to a point in several ways.
1. Iterate through a list of all the cities?
You could do this, but it’s lame and takes linear time.
2. Use Java’s PriorityQueue, which has a heap backbone, meaning the extreme value
(such as, say, the next nearest node in your PRQT) can be inserted and sifted up the
heap to the front of the queue in logarithmic time.
There are also several ways to craft this priority queue, both of which work.
I. Make an object to represent quadrant distances that takes a point and a node in the
constructor and determines the minimum distance from that point to the given node.
Then make a comparator to pass to the constructor of the PriorityQueue that sorts
these quadrant distance objects on the basis of this minimum distance.
II. Put nodes themselves into the PriorityQueue and add another method to the
PRQT node class that finds minimum distance from a point to the node itself. Then
make a comparator to pass to the constructor of the PriorityQueue that sorts nodes on
the basis of this method.
Nearest City Algorithm Pseudocode
PriorityQueue pq = new PriorityQueue(new YourComparator());
pq.add(root);
cur = pq.poll();
while (cur not white) {
if (cur gray) enqueue all chilren;
if (cur black) return that city;
cur = pq.poll();
}