Background
For this project you will build a simple Geographic Information System for storing point data. The focus is organizing city records into a database for fast search. For each city you will store the name and its location (X and Y coordinates). Searches can be by either name or location. Thus, your project will actually implement two trees: you will implement a Binary Search Tree to support searches by name, and you will implement a variation on the PR Quadtree to support searches by position.
Consider what happens if you store the city records using a linked list. The cost of key operations (Insert, remove, search' using this representation would be Θ(n) where n is the numbs of cities. For a few records this is acceptable, but for a large number of records this becomes too slow. Some other representation is needed that makes these operations much faster. In this project, you will implement a variation on one such representation, known as a PR Quadtree. A binary search tree gives O(log n) performance for insert, remove, and search operations Of you Ignore the possibility that it h unbalanced). This would allow you to insert and remove cities, and locate them by name. However, the BST does not help when doing a search by coordinate. In particular, the primary search operation that we are concerned with in this project is a form of range query called "regionsearch." In a regionsearch, we want to find all cities that are within a certain distance of a query point.
You could combine the (x. y) coordinates into a single key and store cities using this key in a second BST. That would allow search by coordinate, but does nothing to help regionsearch. The problem is that the BST only works well for one-dimensional keys, while a coordinate Is a two-dimensional key. To solve these problems, you will implement a variant of the PR Quadtree. The PR Quadtree Is one of many hierarchical data structures commonly used to store data such as city coordinates. It allows for efficient insertion, removal, and regionsearch queries. You should pay particular attention to the discussion regarding parameter passing in recursive functions.
Extra two points implement a Quadtree in which the leaf nodes will store up to three points.
Invocation and I/O Files:
Your program must be named PRprog and should be invoked as: PRprog , where is a command line argument for the name of the command file. Your program should write to standard output (System.out). The program should terminate when it reads the end of file mark from the Input file. The Input for this project will consist of a series of commands (some with associated parameters, separated by spaces), one command foe each tine. Commands are free format In that an arbitrary number of additional spaces may be interspersed between parameters. The Mimi file may also contain blank lines, which your program should ignore. Each Input command should result in meaningful feedback in terms of an output message. In addition, some Indication of success or error should be reported. Some of the command specifications below indicate particular additional Information that Is to be output Commands and their syntax are as follows. Note that a name is defined to be a string containing only upper and lower case letters and the underscore character,
insert x y name:
A city at coordinate (x y) with name is entered into the database. That means you will stow the city record once In the BST, and once In the PR Quadtree. Spatially, the database should be viewed as a square whose origin
Is in the upper left (NorthWest) corner at position (0, 0). The world is 234 by 214 units wide, and so x and y are integers in the range 0 to 214 -1. The x - coordinate increases to the right, the y-coordinate increases going down. Note that it is an error to insert two cities with identical coordinates, but not an error to insert two cities with identical names.
remove xy:
The city with coordinate (x y) is removed from the database (If it exists). That means it must be removed from both the PR Quadtree and the BST. Be sure to prim the name and coordinates of the city that Is removed.
remove name:
Acity with name is removed from the database (If any exists). That means it must be removed from both the PR Quadtree and the BST. Be sure to prim the name and coordinates of the city that is removed.
find name:
Print the name and coordinates from all city records with name. You would search the BST for this Information.
search xy radius:
All cities within radius distance from location (x y) are listed. A city that is exactly radius distance from the query point should be listed x and y are (signed) Integers with absolute value less than 214 radius is a non-negative integer.
debug:
Print a listing of the PR Quadtree nodes in preorder. PR Quadtree children will appear in the order NW, NE, SW, SE. The node listing should appear as a single string (without internal newline characters or spaces) as follows:
• For an internal node, print "I".
• For an empty leaf node, print "E".
• For a leaf node containing on or more data points, for each data point print X, Y, NAME where X is the x-coordinate, Y is the y-coordinate, and NAME is the city name. After at of the city records for that node have been printed, print a 'bar" or "pipe symbol (the | character).
The tree corresponding to the following Figure would be printed as: |40,45||15,70B||70,10C|E69,50D|EIEEEEE55,80E|80,90F|.
Requirements
Environment: Make sure your program is able to work on T-lab machine. (Note the version of compiler: g++ (GCC)
4.4.7 20120313 (Red Hat4.4.7-3))
Program:
Your code should he well commented and explain what you are doing. Make sure your runs correctly, efficiently.