Java程序辅导

CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 1 
PR Quadtree 
 
This assignment involves implementing a point-region quadtree (specifically the PR quadtree as described in section 3.2 of 
Samet’s paper) as a Java generic.  This data structure will play a vital role in your solution to the next project. 
 
Design and Implementation Requirements 
 
There are some explicit requirements, stated in the header comments for prQuadtree<> and in the header comments for 
some of the specified public methods, in addition to those on the Programming Standards page of the course website.  
Your implementation must conform to those requirements.  In addition, none of the specified prQuadtree<> member 
functions should write output. 
 
You may safely add features to the given interface, but if you omit or modify members of the given interface you will almost 
certainly face compilation errors when you submit your implementation for testing.   
 
You must implement all tree traversals recursively, not iteratively.  You will certainly need to add a number of private 
recursive helper functions that are not shown above.  Since those will never be called directly by the test code, the interfaces 
are up to you. 
 
The declaration of your PR quadtree tree generic must not be in a package, or compilation will fail when you submit it. 
 
Design and Implementation Suggestions 
 
In most cases, the public functions shown in the PR quadtree interface will be little more than stubs that call recursive 
private helper functions.  This is the standard pattern for implementation, and it is natural, since the recursive traversals 
require a parameter that points to a tree node (and the client who makes calls to the public function will not possess any 
such pointer).   
 
Some operations can fail.  The client may attempt to find a value that doesn't occur in the tree, or may attempt to insert a 
value that already occurs in the tree (our version of the PR quadtree will not insert duplicate values).  When an operation fails, 
it should not do so silently, and so the public functions will return an indicator of success or failure.  If the public 
function returns a pointer (Java reference), it could simply return null on failure.  Otherwise, the public function will 
return a Boolean value. 
 
Note that it is never acceptable to perform a needless traversal of the tree; that wastes time and is unnecessary.  For example, 
insertion logic should never call the public search function, or its private helper, to determine whether the target value 
is in the tree, and then perform a second search traversal if the value is absent.  Such implementations seem to be fairly 
common, perhaps due to a misunderstanding of the purpose of the software engineering goal of avoiding code duplication. 
 
 
 
 
 
 
 
  
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 2 
PR Quadtree Interface 
 
Because this assignment will be auto-graded using a test harness we will provide, your implementation must conform to the 
public interface below, and include at least all of the public that are shown: 
 
// To support testing, we will make certain elements of the generic. 
// 
// You may safely add data members and function members as needed, but 
// you must not modify any of the public members that are shown. 
// 
public class prQuadTree< T extends Compare2D > { 
    
   // Inner classes for nodes (public so test harness has access)   
   public abstract class prQuadNode { . . . } 
 
   public class prQuadLeaf extends prQuadNode { 
      // Use an ArrayList to support a bucketed implementation later. 
      ArrayList Elements; 
      . . . 
   } 
 
   public class prQuadInternal extends prQuadNode { 
      // Use base-type pointers since children can be either leaf nodes 
      // or internal nodes. 
      prQuadNode NW, NE, SE, SW; 
      . . . 
   } 
    
   // prQuadTree elements (public so test harness has access) 
   public prQuadNode root; 
   public long xMin, xMax, yMin, yMax; 
   . . . 
 
   // Initialize quadtree to empty state, representing the specified region. 
   // Pre:   xMin < xMax and yMin < yMax 
   public prQuadTree(long xMin, long xMax, long yMin, long yMax) {. . .} 
     
   // Pre:   elem != null 
   // Post:  If elem lies within the tree's region, and elem is not already  
   //        present in the tree, elem has been inserted into the tree. 
   // Return true iff elem is inserted into the tree.  
   public boolean insert(T elem) {. . .} 
 
   // Pre:  elem != null 
   // Returns reference to an element x within the tree such that  
   // elem.equals(x)is true, provided such a matching element occurs within 
   // the tree; returns null otherwise. 
   public T find(T Elem) {. . .} 
 
   // Pre:  xLo < xHi and yLo < yHi 
   // Returns a collection of (references to) all elements x such that x is  
   // in the tree and x lies at coordinates within the defined rectangular  
   // region, including the boundary of the region. 
   public ArrayList find(long xLo, long xHi, long yLo, long yHi) {. . .} 
 
   . . . 
} 
 
  
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 3 
You should implement tree traversals recursively, not iteratively; using iteration will only make the implementation more 
difficult.  You will certainly need to add a number of private recursive helper functions that are not shown above.  Since those 
will never be called directly by the test code, the interfaces are up to you. 
 
For this assignment, the bucket size is 1; that is, each leaf node will store exactly one data object.  That said, you must still use 
an ArrayList object to store the single data element in the leaf node; that will help you later when you convert this 
implementation to a fully bucketed approach. 
 
Note that the quadtree test harness for this assignment is shallow.  That is, aside from checking the root pointer, it does not 
attempt to examine the internal structure of your quadtree at all.  Instead, tree displays, written by the test driver, are 
compared to determine whether your tree has the correct structure.  Therefore, the restrictions on the node types are extremely 
flexible. 
 
On the other hand, data elements that are to be inserted to a prQuadTree must provide the tree with the ability to make 
directional comparisons between those objects.  We will accomplish that by stating a type bound, as shown in the declaration 
of the prQuadTree class, and including useful functions in that.  Specifically, we require those data objects implement the 
following interface: 
 
// The interface Compare2D is intended to supply facilities that are useful in 
// supporting the use of a generic 2D spatial structure with a user-defined data type. 
// As a consequence, the interface contains a number of redundant features; it is 
// unlikely that any particular PR quadtree implementation would make use of every 
// feature shown here[1]. 
// 
public interface Compare2D { 
  
   // Return the x- and y-coordinate fields of the user data object. 
   public long getX(); 
   public long getY(); 
    
   // Returns indicator of the direction to the user data object from the location  
   // (X, Y) specified by the parameters[2].  The indicators are defined in the 
   // enumeration Direction, shown later, and are used as follows: 
   // 
   //    NE:  vector from (X, Y) to user data object has a direction in the  
   //         range [0o, 90o)[3] degrees (relative to the positive horizontal axis, 
   //         OR if the user data object is at the coordinates (X, Y). 
   //    NW:  same as above, but direction is in the range [90o, 180o)  
   //    SW:  same as above, but direction is in the range [180o, 270o) 
   //    SE:  same as above, but direction is in the range [270o, 360o)   
   // 
   public Direction directionFrom(long X, long Y); 
    
   // Returns indicator of which quadrant of the rectangle specified by the 
   // parameters that user data object lies in.  The indicators are defined in  
   // the enumeration Direction, shown later, and are used as follows, relative  
   // to the center of the rectangle: 
   // 
   //    NE:  user data object lies in NE quadrant, including non-negative 
   //         x-axis, but not the positive y-axis       
   //    NW:  user data object lies in the NW quadrant, including the 
   //         positive y-axis, but not the negative x-axis 
   //    SW:  user data object lies in the SW quadrant, including the 
   //         negative x-axis, but not the negative y-axis 
   //    SE:  user data object lies in the SE quadrant, including the 
   //         negative y-axis, but not the positive x-axis 
   //    NOQUADRANT:  user data object lies outside the specified rectangle 
   // 
   public Direction inQuadrant(double xLo, double xHi, double yLo, double yHi)[4]; 
    
     
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 4 
   // Returns true iff the user data object lies within or on the boundaries 
   // of the rectangle specified by the parameters. 
   public boolean   inBox(double xLo, double xHi, double yLo, double yHi)[4]; 
} 
 
The Compare2D interface is intended to allow your implementation to either take coordinates from the data object (via 
getX() and getY()) and use those values to make directional decisions, or to use the directionFrom() method 
supplied by the data object for the same purpose.  The only restriction is that if you take the first approach you must make 
sure that your logic conforms to the diagram below, which is the basis for the description of the Compare2D interface: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
The actual test data will be created so that (ideally) no data points will ever lie on a region boundary.  However, you should 
conform to the guideline above just to be safe. 
 
One more note, we specifically require that the equals() and directionFrom() methods are consistent, in the sense 
that equals() returns true only in cases where directionFrom() returns NE.  We are specific about this because the 
Java language specification does, in fact, allow an inconsistency between equals() and compareTo(). 
 
The Compare2D interface depends upon the following enumerated type: 
 
public enum Direction {NW, SW, SE, NE, NOQUADRANT}; 
 
The use of an enumerated type allows us to use descriptive labels at critical points in the implementation.  If you have not 
made use of this Java feature before, this is a good place to learn about it.  Some quick points: 
 
 We include the value NOQUADRANT as a catch-all value when no direction is actually appropriate.  It may very well 
be the case that, in actual use, this value is rarely used. 
 You refer to the values by including the name of the type, like:  Direction.NE 
 The values are compared using equals(), not ==. 
 
 
  
Positive y-axis belongs 
to the NW quadrant 
Positive x-axis belongs 
to the NE quadrant 
Negative y-axis belongs 
to the SE quadrant 
Negative x-axis belongs 
to the SW quadrant 
Center point belongs to 
the NE quadrant 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 5 
For testing your implementation, you must implement the following data type: 
 
public class Point implements Compare2D { 
 
 private long xcoord; 
 private long ycoord; 
  
 public Point() { 
  xcoord = 0; 
  ycoord = 0; 
 } 
 
 public Point(long x, long y) { 
  xcoord = x; 
  ycoord = y; 
 } 
 
 public long getX() { 
  return xcoord; 
 } 
 
 public long getY() { 
  return ycoord; 
 } 
  
 public Direction directionFrom(long X, long Y) { . . . } 
  
 public Direction inQuadrant(double xLo, double xHi,  
                               double yLo, double yHi) { . . . } 
  
 public boolean   inBox(double xLo, double xHi,  
                          double yLo, double yHi) { . . . } 
  
 public String toString() { 
     
    return new String("(" + xcoord + ", " + ycoord + ")"); 
   } 
  
 public boolean equals(Object o) { . . . } 
 
   // Additional methods as needed... 
   . . . 
} 
 
Since we will use your implementation of the Point class to test your quadtree, we will actually treat the Point type as a 
separate submission, and provide a separate test harness for your implementation of Point.  Your score from testing your 
Point class will be counted as 20% of your overall project score. 
 
Note that whether your quadtree makes calls to all, or only some, of the Compare2D methods, the test harness for Point 
will test all of those methods, so you must provide a complete implementation of Point. 
 
 
  
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 6 
Test Harnesses and Grading 
 
There are two separate test harnesses, one for the Point type and one for the prQuadTree generic.   
 
Testing Point 
 
For the Point type, the harness is packaged as PointHarness.zip, and contains the following files: 
 
testPoint.java driver and testing code 
Point.java shell for your Point implementation 
Compare2D.java interface for Point 
Direction.java enum type used in Compare2D 
 
The only file you need to modify is Point.java, but you can edit the test driver if you want to control which tests are run.  
Once you've implemented Point, compile and execute the test code by running the commands: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
This will write its test results to the terminal window, so you might want to redirect that to a file.  The testing checks some 
edge cases, and some basic cases, but I do not consider it to be fully comprehensive.  If your implementation of Point does 
not pass these tests, there is a good chance your tree will not pass testing using your Point type. 
 
  
Z:\J2\Point>dir 
01/31/2022  01:26 PM             2,272 Compare2D.java 
01/31/2022  01:27 PM                80 Direction.java 
01/31/2022  08:04 PM             2,134 Point.java 
02/01/2022  10:13 PM            10,894 testPoint.java 
 
Z:\J2\Point>javac *.java 
 
Z:\J2.QuadTree\Point>dir *.class 
02/02/2022  12:17 PM               307 Compare2D.class 
02/02/2022  12:17 PM               908 Direction.class 
02/02/2022  12:17 PM             2,205 Point.class 
02/02/2022  12:17 PM             6,445 testPoint.class 
 
Z:\J2\Point>java testPoint 
 
Checking default Point constructor. 
   Good, both coordinates were set to 0. 
Checking parameterized Point constructor with values 37 and -109 
   Good, both coordinates were set correctly. 
   Passed test of Point initialization. 
. . . 
1 >> Score: 330 / 330 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 7 
Testing prQuadTree 
 
For the prQuadTree type, the harness is packaged as QuadTreeHarness.zip, and contains the following files: 
 
gradeJ2.py Python script to automate running grading code 
prQuadGenerator.jar exe jar to generate reference results and seed 
LogComparator.jar exe jar to compare reference and test logs 
testQuadTree.java driver for testing; see header comments 
prQuadTree.java* shell for implementing PR quadtree generic 
Point.java* shell for implementing data type for testing 
Compare2D.java interface for generic type bound 
Direction.java enum type used in Compare2D 
Lewis.class compiled Java test code 
 
* files that you must complete in order to run the testing code 
 
After unpacking the test harness, you must implement the Point and prQuadtree classes in order to perform testing.  
Specifically, you must implement the parts of the Point type related to the elements of the Compare2D interface that your 
PR quadtree implementation actually makes use of.  You can restrict which methods in the PR quadtree are tested by 
commenting out sections of the main test driver file, testDriver.java. 
 
The supplied test code is thorough, but some edge cases may not occur on every execution of the test code, since it 
randomizes the generated test data.  You should be sure to run the test code a number of times, using the randomization 
feature.  For that purpose, you may share test code (but absolutely no tree code!!) via the class Forum. 
 
Be sure you test all of the interface elements thoroughly, both in isolation and in interleaved fashion.  Do not include any 
testing code in your submission, including calls to JUnit elements. 
 
 
Using the Generator Tool 
 
The first tool, prQuadGenerator.jar, can be used to create test data and reference results.  The tool is designed to be 
executed from a command-line environment.  Here is a sample session, using a Windows 10 terminal window, that shows the 
tool at work.  The same approach works on a Linux system[5].  After unpacking the zip file to a directory, open a terminal 
window in that directory and execute it: 
 
 
 
 
 
 
 
 
 
 
This will create a set of reference log files, based upon random test data, and save the corresponding random seed value in a 
file, seed.txt, so it can be used to generate exactly the same data when testing your implementation. 
 
 
Running Your Solution on the Generated Test Data 
 
The driver, testQuadTree.java, will read the seed value from seed.txt, and create the same test values as the 
generator tool.  So, just execute the (compiled) test driver with seed.txt in the same directory, and the test driver will 
(ideally) create a log file for each phase of testing: 
 
  
Z:\J2\prQuadTree> prQuadGenerator.jar 
 
Z:\J2\Point> dir 
02/05/2022  08:17 PM                14 seed.txt 
02/05/2022  08:17 PM               351 refTestTreeInitialization.txt 
02/05/2022  08:17 PM            36,113 refTestInsertion.txt 
02/05/2022  08:17 PM             4,298 refTestRegionSearch.txt. . . 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 8 
 
 
 
 
 
 
 
 
 
 
 
The test driver will execute the constructor, the insertion logic, and the region search logic; the simple search logic is not 
examined, since it is relatively trivial, compared to the region search. 
 
If the log for a test is missing, or empty, an exception occurred, and you need to fix that.  When in doubt, load test logs into a 
text editor and see if there are any clues there (like exception messages or logged error messages from the test driver).  Fix 
and repeat. 
 
 
Using the Comparison Tool 
 
The next step is to use the supplied comparison tool to determine your score for each test; that can be done as shown below.  
Executing the comparison tool with no parameters displays instructions: 
 
 
 
 
 
 
 
 
Invoking the comparison tool on the two tree initialization test files[6]: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Repeat the process to evaluate your results for each test that was completed.  Some tests will produce a lot of output, so if you 
don't get a full score, I suggest redirecting the output to a file so you can examine it in a text editor. 
 
 
  
Z:\J2\prQuadTree> java -jar LogComparator.jar 1 refTestTreeInitialization.txt 
TestTreeInitialization.txt 
Maximum score 50 
            checkTreeInitialization results: 
              Creating a new prQuadtree with world boundaries: 
                xMin:  0 
                xMax:  32768 
                yMin:  0 
                yMax:  32768 
              prQuadtree root was OK. 
              prQuadtree xMin was OK. 
              prQuadtree xMax was OK. 
              prQuadtree yMin was OK. 
              prQuadtree yMax was OK. 
 
 
 1 >> Score: 50.00 /  50 
Z:\J2\prQuadTree> java testQuadTree 
 Completed test of quadtree initialization. 
 Completed test of quadtree insertion. 
 Completed test of quadtree region search. 
 
Z:\J2\prQuadTree> dir *.txt 
. . . 
02/05/2022  08:33 PM               285 TestTreeInitialization.txt 
02/05/2022  08:33 PM            26,387 TestInsertion.txt 
02/05/2022  08:33 PM             3,374 TestRegionSearch.txt 
Z:\J2\prQuadTree> java -jar LogComparator.jar 
Invoke:  java LogComparator    
   The reference results file should be created with the posted generator tool. 
   The student results file should be created by your solution, using the. 
       the input file corresponding to the reference results file. 
   The order of the file names on the command line does matter. 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 9 
If You Are Using Eclipse (or some other IDE) 
 
Compile your source code as usual (once you figure out how to use the supplied Lewis.class file with your IDE[7]).  Put 
the two supplied Java jar files in the same directory as the .class files from your compilation.  Then, just follow the 
previous instructions to use the generator and comparison tools. 
 
 
Using the Python Script 
 
Of course, you need to check ALL of the results, and that will be tedious since there are several separate test files.  So, I've 
also supplied a Python script that will automate running the tests and performing the comparisons, if you work from the 
command line.  This does assume that you have correctly installed Python on your machine. 
 
The script is designed for use from the command line.  Here's an example[8], running in a directory that holds all of the 
supplied files, except that I've substituted my completed Point.java and prQuadTree.java: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
The script will: 
 
 attempt to compile the code (requires having installed Java 11 JDK) 
 run prQuadGenerator.jar to create the reference data and seed file 
 run testDriver to produce your output 
 run LogComparator.jar on each pair of reference output your output files 
 
Watch for error messages from the script; fix and repeat.  If all goes well, the script will produce a comparison file for each of 
the test output files: 
 
 
 
 
 
 
 
Examine each of these to see how you did; fix and repeat as necessary. 
 
  
Z:\J2\prQuadTree> dir 
02/04/2022  08:36 PM             4,399 testQuadTree.java 
02/03/2022  09:11 PM             3,176 gradeJ2.py 
02/02/2022  08:16 PM            12,575 Lewis.class 
02/02/2022  01:10 PM             5,140 LogComparator.jar 
02/03/2022  09:45 PM            17,661 prQuadGenerator.jar 
01/31/2022  01:26 PM             2,272 Compare2D.java 
01/31/2022  01:27 PM                80 Direction.java 
01/31/2022  08:04 PM             2,134 Point.java 
01/31/2022  01:33 PM            19,191 prQuadTree.java 
 
Z:\J2\prQuadTree> gradeJ2.py 
 Completed test of quadtree initialization. 
 Completed test of quadtree insertion. 
 Completed test of quadtree region search. 
Now, check the comparison files to see your scores 
Z:\J3\working > dir comp*.txt 
 
02/05/2022  09:14 PM               464 compTestTreeInitialization.txt 
02/05/2022  09:14 PM            45,888 compTestInsertion.txt 
02/05/2022  09:14 PM             5,278 compTestRegionSearch.txt 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 10 
More on the Comparison Tool 
 
If you notice different data values in the reference and student log files, then you've misused the tools.  Whether or not you 
are using the Python script to run things, then there are several possibilities, but in the end it comes down to the fact that the 
reference logs and the student logs were generated using different seed values. 
 
Normally, I use output redirection, because the comparison tool writes its output to the terminal, and I want to save those 
results for easy examination if the score is less than optimal.  For example: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
That's not very good… notice that some lines show point deductions.  The key now is to find the first lines in the results that 
show deductions: 
 
 
 
 
 
 
 
 
 
 
 
OK, the error is obvious; the implementation inserted a duplicate value, but the specification says that should NOT happen.  
So, we'd need to fix the implementation (in Point.java or prQuadtree.java), recompile, repeat the test, and then 
compare the results again. 
 
 
What to turn in and how 
 
This assignment will be auto-graded under CentOS (which should not matter at all) using Java version 11, and the posted 
testing/grading code.  
 
You should document your implementation in accordance with the guidelines on the course website.  It is possible that your 
implementation will be evaluated, by one of the TAs, for documentation and design, as well as for correctness of results.  
 
For the Point Class 
 
Submit your Point.java file (not a zip or jar) containing your PR quadtree generic to the Curator System under the 
collection point J2Point.  Submit nothing else.  Grading will use the supplied testing code.  Your solution should not write 
anything to standard output. 
 
For the prQuadTree Class 
 
Submit a zip file containing your Point.java and prQuadTree.java files to the Curator System under the collection 
point J2Tree.  Submit nothing else.  Your solution should not write anything to standard output. 
 
  
. . . 
  -2.00    --------------- 963 
  -2.00    --------------------- 968 
           ------------------ 994 
 
 
Student file has 1 more lines than reference file. 
 
 
 1 >> Score: 42.50 / 301.00 
. . . 
              Try inserting a value, -248, that's already in the tree. 
              insert() returned false. 
              Let's see what the tree looks like now: 
  -2.50    ------ -248 
  -5.00    --- -248 
  -5.00    -238 
. . . 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 11 
Your submissions will be evaluated by running the supplied testing script.  I will make no accommodations for submissions 
that do not work with that code.   
 
Warning:  I will not accept files in any other format (e.g., tar files, 7-zip'd files, gzip'd files, jar files, rar files, …).  Such 
submissions will NOT work with the supplied script, and will be discarded when I run the grading code. 
 
You will be allowed to submit your solution for each part multiple times, in order to make corrections.  Your score will be 
determined by testing your last submission.  The Curator will not be used to grade your submissions in real time, but you will 
have already done the grading using the posted code. 
 
Instructions, and the appropriate link, for submitting to the Curator are given in the Student Guide at the Curator website:  
 
http://www.cs.vt.edu/curator/. 
 
Pledge 
 
Each of your program submissions must be pledged to conform to the Honor Code requirements for this course.  Specifically, 
you must include the following pledge statement at the beginning of the file that contains main(): 
 
//    On my honor: 
//    
//    - I have not discussed the Java language code in my program with 
//      anyone other than my instructor or the teaching assistants 
//      assigned to this course. 
//    
//    - I have not used Java language code obtained from another student, 
//      or any other unauthorized source, including the Internet, either 
//      modified or unmodified.  
//    
//    - If any Java language code or documentation used in my program 
//      was obtained from another source, such as a text book or course 
//      notes, that has been clearly noted with a proper citation in 
//      the comments of my program. 
//    
//    - I have not designed this program in such a way as to defeat or 
//      interfere with the normal operation of the grading code. 
// 
//     
//     
 
I reserve the option of assigning a score of zero to any submission that is undocumented or 
does not contain this statement. 
 
 
Change Log 
 
Version Date Change(s) 
7.00 Feb 6 Base document 
 
 
  
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 12 
Notes 
 
[1] For what it's worth, my implementation only uses two of the supplied methods, and one of those is only called once. 
 
[2] Be careful here… the direction is from the user-supplied location, specified by x and y, to the location of the data object 
on which the method is called.  So, if Q is a user data object and we make the call Q.directionFrom(17, 42), the 
returned value will tell us what direction Q is from the point (17,42).  It would be very bad to get this backwards. 
 
[3] Do not use the trig functions in the Java Library to compute angles here!  Just use coordinate comparisons.  The logic 
corresponds precisely to the diagram given on page 4. 
 
[4] Logically we treat the coordinates in this assignment as integer values (total seconds).  That said, I strongly recommend 
computing region boundaries, as you split regions, as double values.  This will provide a more precise representation of 
the partitioning logic. 
 
[5] On Linux, invoke as:  java –jar prQuadGenerator.jar. 
 
[6] The LogComparator tool requires an integer label for the label generated for the score; it doesn't really matter what 
integer value you use, but you must supply one. 
 
[7] Here are some instructions for using Eclipse with this.  YMMV… this worked for me with a somewhat earlier version of 
Eclipse and s slightly different code organization. 
 
In order to use the supplied implementation framework with Eclipse: 
 
 create a new Java project in Eclipse; do not create any files within the project; I called mine prQuadTree 
 unpack the supplied zip file into the top-level directory for the Eclipse project (not into the src directory!) 
 
Create a subdirectory named supplied in the main project directory, and copy Lewis.class into that.  This should 
have created a directory structure like this: 
 
.\prQuadTree 
|   gradeJ2.py 
|   LogComparator.jar 
|   prQuadGenerator.jar 
| 
+---src 
    |   testQuadTree.java 
    |   Point.java 
    |   Compare2D.java 
    |   Direction.java 
    |   prQuadTree.java 
+---supplied 
    |   Lewis.class 
 
Back in Eclipse, with the project open, press the F5 key to refresh the project view.  The Package Explorer panel should 
now show the subdirectories and files you just added. 
 
Now, right-click on the Project and go to Properties.  Then go to Java Build Path and choose the Libraries pane.  Select 
Add Class Folder… and select the ./supplied folder.   
 
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 13 
 
 
This makes the Eclipse builder aware of the supplied .class file.  Now, you should be able to compile and execute 
your code as usual.  Note that if you execute the program from within Eclipse, input files like seed.txt must be placed 
in the top-level project folder (where prQuadGenerator.jar is). 
 
Edit the files Point.java and prQuadTree.java to complete them.  Executing the project will run the testing code 
and produce test logs for the tests, as described earlier.  Follow the previous instructions to use the comparison tool to 
check your results manually. 
 
[8] On rlogin:  python3.6 gradeJ2.py 
 
 
Design and implementation requirements 
 
There are some explicit requirements, in addition to those on the Programming Standards page of the course website: 
 
 You must implement the Point type and the PR quadtree to conform to the specification. 
 The insertion logic must not allow duplicate (according to equals()) records to be inserted.  Think about what 
could happen if you did not prevent this. 
 The insertion logic must not allow the insertion of records that lie outside the world boundaries. 
 Under no circumstances should any of the PR quadtree member functions write output, except for a display() 
method and its helper, if you choose to implement that (the test harness will never call such a method). 
 When carrying out a region search, you must determine whether the search region overlaps with the region 
corresponding to a subtree node before descending into that subtree.  The Java libraries include a Rectangle class 
which could be (too) useful.  You may not make use of the Rectangle class from the Java library, but it is 
acceptable to make use of those methods during development of a solution to this assignment. 
 When carrying out a region search, the order in which you add elements to the vector does not matter, since the 
testing code will sort the elements before considering them. 
 Naturally, your implementation of region search should be efficient; therefore, it must not look at subtrees that could 
not possibly contain elements that fall in to the specified region.  This will be checked by the course TAs. 
 
  
CS 3114 Data Structures and Algorithms   Project 2: PR Quadtree Generic 
 
Version 7.00 This is a purely individual assignment! 14 
Some Advice 
 
There are many ways to implement a non-working PR quadtree, and it's not possible to cover all of them here… 
 
A common issue is a runaway recursive descent, that ends with a StackOverflowError, which is thrown when a Java 
process experiences a too-deep recursion.  With a PR quadtree, this often is the result of one of the following logic errors: 
 
 Computing the center point of a square incorrectly. 
 Computing the boundaries of a quadrant incorrectly when splitting a square. 
 Passing the region boundaries in the wrong order when performing a descent into the tree. 
 Attempting to insert a point that lies outside the world boundaries.