part2
General Changes/Getting Started
-each command now has an optional id attribute you need to keep track of and
append to output
-update your package name to cmsc420.meeshquest.part2
-update your XSD file to the part2in.xsd in the ProjectBook
RNG Generation
To generate random integers to establish TreapNode priority, instantiate a Java
Random object (see Java API). Only ever instantiate one Random object
because you want it to be seeded the same for each next random number
generated.
Treap
The treap is a data structure with two properties:
1. BST property on keys
2. max heap property on RNG priority
It will eventually replace your dictionary treemaps, so it must support generics
(but keep your current ones until you have a working treap so that you don’t lose
extra points on a broken treap!).
Your treap MUST be in the package cmsc420.sortedmap!
class prototype:
public class Treap
SortedMap
Have an inner class within your Treap to represent nodes.
node inner class prototype:
private class TreapNode extends AbstractMap.SimpleEntry
SortedMap.Entry
READ JAVA API FOR THESE CLASSES TO SEE WHAT YOU GET FOR FREE
(i.e., what you already get from inheriting these classes)
TreapNode Fields
-generic key
-generic value
-int priority (will be decided by RNG)
-references to other TreapNodes (parent, left, right)
Treap Fields
-TreapNode root
-int size
-int modCount (short for modification count, counts all operations performed on
this treap)
-Comparator
Treap Constructor (You must have BOTH of these constructors)
public Treap(Comparator
appropriately
public Treap(), make comparator field null
If no comparator is provided, you have to compare elements of type K via their
natural ordering (compareTo).
Methods to throw UnsupportedOperationException for (in part 2)
-headMap()
-tailMap()
-keySet()
-values()
-remove()
BIG RECOMMENDATION FOR CODING TREAP
Google “grepcode treemap” to see Java’s actual code for TreeMap. You are
encouraged to borrow from this to make coding the Treap easier; just make sure
you document it in the README!
Treap EntrySet/SubMap (make as inner classes of Treap)
-entrysets and submaps are backing structures, which means that any method
calls performed on these backing structures should actually affect the Treap
itself; i.e., calling insert on the entryset should insert into the Treap itself
-see grepcode implementation(s) of submap and entryset
*have your entryset extend AbstractSet
EntrySet Iterator
-again check grepcode implementation, no remove in part 2
-this is where modCount field in Treap comes into play. Any add/remove/clear
call to the treap should increment the modCount field.
-Upon instantiation, the iterator checks the current (expected) modCount of the
Treap.
-At any point, if you’re calling an iterator method and the Treap’s current
modCount is not equal to this expected modCount, you must throw a
ConcurrentModificationException.
Read the Java SortedMap API to know exactly what to return.
Treap Insert
1. Perform BST insert on basis of key (look up BST insert if you don’t know it,
any node added to BST starts as leaf)
2. Rotate that node upward while it’s priority is less than its parent’s
Treap Delete
1. Perform BST find until the node to be deleted is found
2. While that node is not a leaf, rotate it downward with greater priority child
3. Assign that node to null (deleting it)
Treap Rotations
Generally,
Insert: rotate node being inserted up while its priority is lower than its parent’s
Delete: rotate node being deleted down with its greater priority child until it’s a
leaf, and then remove
Rotations preserve the BST property on the keys while also shifting the tree to
maintain max heap property on the priority.
In class, I’ll go over the rotations with illustrations… if you miss them, just look
up the assignments you need to make for treap rotations online. You’ll find
them.
Roads
-Now spatial map has roads that serve almost like adjacencies between cities
-Make a road class and have it extend Line2D.Float, which has fields for start
and end cities
AdjacencyList (determine edge existence in logarithmic time)
-You should make an adjacency list class
-Have a TreeMap
roads are mapped
PM3 Quadtree (replaces PRQT for part 2)
Differences:
-rectangle bounds now closed on all sides
-black node now may have as many roads in it as it wants, but still at max one
city
-cities and roads appear in every node they intersect
-A road is valid and can be mapped so long as any part of the road touches the
spatial map
PM3 Black Node
Now your black node needs to maintain several geometries.
Options: have a City field and a List of Roads field
OR have your City and Road classes implement Geometry2D, and have your
black node have a field for a List of Geometry2D (I recommend this one)
PM Insert
White – return black with that geometry added
Gray – basically the same as PRQT, find where geometry intersects and add it
there
Black – Adding road? just add that road to the black node and return
Adding city? Add that city and return this black node if there was no city
previously; otherwuse, return a gray node with all the geometries added
appropriately to reflect the partitioning
If you want to be slick and/or prepare yourself well for part 3, read the section in
the spec about a validator object. Basically, this just checks a black node to
verify whether it needs to partition or not.
PM Delete
Don’t need to do this for part 2. However, check out the pseudocode in the
project spec or contact me if you need help.
MapRoad
This is how NonIsolated cities are inserted. If endpoints intersect the spatial map
and are not mapped, map the road enpoints (NonIsolated cities) first, followed
by mapping the road itself.
Isolated vs NonIsolated Cities
-Cities mapped via mapCity are isolated cities now! Have a field that certifies a
city is isolated or not.
-Isolated cities CANNOT have any roads starting, ending, or otherwise
intersecting them
-cities mapped by mapRoad are not isolated cities
Tweaks for Nearest/Range Commands
-Black nodes have several geometries now, so finding geometrys’ distances to a
point becomes weirder
-Still use the priorityqueue but now make distance to black nodes reflect the
minimum distance from the point of interest to the black node’s rectangle
-Finally, iterate through all geometries in all equidistant black nodes before
deciding what nearest road or city is
Shortest Path
-ONLY INCLUDE ADJACENCIES WHOSE ENDPOINTS ARE BOTH PRESENT IN
THE SPATIAL MAP
– Use doubles for distance
-Use Dijkstra’s algorithm and document in README from where you got it
-In the case of a distance tie, ALWAYS locally opt for the path that is
asciibetically smaller
-Undirected graph- put adjacency from A to B and B to A