程序代写代做代考 Java algorithm data structure General

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();

}