//Classwork/CS3114/GIS/.classpath |
---|
0,0 → 1,6 |
<?xml version="1.0" encoding="UTF-8"?> |
<classpath> |
<classpathentry kind="src" path=""/> |
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/> |
<classpathentry kind="output" path=""/> |
</classpath> |
//Classwork/CS3114/GIS/.project |
---|
0,0 → 1,17 |
<?xml version="1.0" encoding="UTF-8"?> |
<projectDescription> |
<name>CS3114P2</name> |
<comment></comment> |
<projects> |
</projects> |
<buildSpec> |
<buildCommand> |
<name>org.eclipse.jdt.core.javabuilder</name> |
<arguments> |
</arguments> |
</buildCommand> |
</buildSpec> |
<natures> |
<nature>org.eclipse.jdt.core.javanature</nature> |
</natures> |
</projectDescription> |
//Classwork/CS3114/GIS/.settings/org.eclipse.jdt.core.prefs |
---|
0,0 → 1,12 |
#Mon Oct 03 14:51:02 EDT 2011 |
eclipse.preferences.version=1 |
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled |
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6 |
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve |
org.eclipse.jdt.core.compiler.compliance=1.6 |
org.eclipse.jdt.core.compiler.debug.lineNumber=generate |
org.eclipse.jdt.core.compiler.debug.localVariable=generate |
org.eclipse.jdt.core.compiler.debug.sourceFile=generate |
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error |
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error |
org.eclipse.jdt.core.compiler.source=1.6 |
//Classwork/CS3114/GIS/BSTree.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/BSTree.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/BSTree.java |
---|
0,0 → 1,161 |
import java.util.ArrayList; |
// Generic BST implementation |
public class BSTree<K extends Comparable<? super K>, E> implements Dictionary<K, E> { |
private BSTreeNode<K,E> root; // Root of the BST |
// Constructor |
public BSTree() { |
this.root = null; |
} |
// Inserts a node into the BST |
public void insert(K key, E element) { |
// Set the BST root as the returned node |
this.root = insertRecursive(root, key, element); |
} |
// Removes a node from the BST given the key |
public void remove(K key) { |
// Adds invalid coordinates if none are specified |
this.remove(key, -1, -1); |
} |
public void remove(K key, int x, int y) { |
// Check if node exists |
E temp = findRecursive(root, key); |
if (temp != null) { |
// Remove the node |
this.root = removeRecursive(root, key, x, y); |
} |
} |
// Returns a node from the BST given the key |
public E find(K key) { |
return findRecursive(root, key); |
} |
// Returns a list of all nodes with the given key |
public ArrayList<E> findAll(K key) { |
ArrayList<E> elementList = new ArrayList<E>(); |
findAllRecursive(root, key, elementList); |
return elementList; |
} |
// Removes all nodes from the BST |
public void clear() { |
this.root = null; |
} |
// Recursively inserts a node into the BST |
private BSTreeNode<K,E> insertRecursive(BSTreeNode<K,E> root, K key, E element) { |
if (root == null) |
// If there are no nodes in the BST, create and return a new node |
return new BSTreeNode<K,E>(key, element); |
if (root.getKey().compareTo(key) > 0) |
// If passed key is smaller, insert into left child |
root.setLeft(insertRecursive(root.getLeft(), key, element)); |
else |
// If passed key is greater, insert into right child |
root.setRight(insertRecursive(root.getRight(), key, element)); |
return root; |
} |
// Recursively searches minimal nodes for matches to the given key |
private E findRecursive(BSTreeNode<K,E> root, K key) { |
if (root == null) |
return null; |
if (root.getKey().compareTo(key) > 0) |
// If passed key is smaller, search the left child |
return findRecursive(root.getLeft(), key); |
else if (root.getKey().compareTo(key) == 0) |
// If key is found, return with the found element |
return root.getElement(); |
else |
// If key is not found, search the right child |
return findRecursive(root.getRight(), key); |
} |
// Recursively searches all nodes for matches to the given key |
private void findAllRecursive(BSTreeNode<K,E> root, K key, ArrayList<E> elementList) { |
if (root == null) |
return; |
// If key matches, save to list |
if (root.getKey().compareTo(key) == 0) |
elementList.add(root.getElement()); |
// Recursively call search on all possible nodes |
if (root.getKey().compareTo(key) > 0) |
findAllRecursive(root.getLeft(), key, elementList); |
else |
findAllRecursive(root.getRight(), key, elementList); |
} |
// Recursively removes a node from the BST given a key |
private BSTreeNode<K,E> removeRecursive(BSTreeNode<K,E> root, K key, int x, int y) { |
if (root == null) |
return null; |
// Find the node to remove |
if (root.getKey().compareTo(key) > 0) |
root.setLeft(removeRecursive(root.getLeft(), key, x, y)); |
else if (root.getKey().compareTo(key) < 0) |
root.setRight(removeRecursive(root.getRight(), key, x, y)); |
// Node's key matches |
else { |
// If we want to narrow it down by coordinates as well |
if (x >= 0 && y >= 0) { |
// If coordinates do not match, keep searching from the right child |
if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) { |
root.setRight(removeRecursive(root.getRight(), key, x, y)); |
} else { |
// If one of the leaves is null, just return the other leaf |
if (root.getLeft() == null) |
return root.getRight(); |
else if (root.getRight() == null) |
return root.getLeft(); |
else { |
// Otherwise create a new node with the smallest value on the right leaf |
BSTreeNode<K,E> temp = getMin(root.getRight()); |
root.setElement(temp.getElement()); |
root.setKey(temp.getKey()); |
root.setRight(deleteMin(root.getRight())); |
} |
} |
// Otherwise just remove the node |
} else { |
// If one of the leaves is null, just return the other leaf |
if (root.getLeft() == null) |
return root.getRight(); |
else if (root.getRight() == null) |
return root.getLeft(); |
else { |
// Otherwise create a new node with the smallest value on the right leaf |
BSTreeNode<K,E> temp = getMin(root.getRight()); |
root.setElement(temp.getElement()); |
root.setKey(temp.getKey()); |
root.setRight(deleteMin(root.getRight())); |
} |
} |
} |
return root; |
} |
// Recursively returns the minimum key node |
private BSTreeNode<K,E> getMin(BSTreeNode<K,E> root) { |
if (root.getLeft() == null) |
return root; |
else |
return getMin(root.getLeft()); |
} |
// Recursively deletes the minimum key node |
private BSTreeNode<K,E> deleteMin(BSTreeNode<K,E> root) { |
if (root.getLeft() == null) |
return root.getRight(); |
else { |
root.setLeft(deleteMin(root.getLeft())); |
return root; |
} |
} |
} |
//Classwork/CS3114/GIS/BSTreeNode.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/BSTreeNode.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/BSTreeNode.java |
---|
0,0 → 1,60 |
// Single generic node for the BSTree |
public class BSTreeNode<K,E> { |
private K key; // Key |
private E element; // Value |
private BSTreeNode<K,E> left; // Left child |
private BSTreeNode<K,E> right; // Right child |
// Empty constructor |
public BSTreeNode() { |
setLeft(setRight(null)); |
} |
// Constructor given key value pair |
public BSTreeNode(K k, E e) { |
setLeft(setRight(null)); |
setKey(k); |
setElement(e); |
} |
// Constructor given key value pair and children |
public BSTreeNode(K k, E e, BSTreeNode<K,E> left, BSTreeNode<K,E> right) { |
setKey(k); |
setElement(e); |
this.setLeft(left); |
this.setRight(right); |
} |
// Query if node has leaves |
public boolean isLeaf() { |
return left == null && right == null; |
} |
// Encapsulation methods |
public K getKey() { |
return key; |
} |
public void setKey(K key) { |
this.key = key; |
} |
public E getElement() { |
return element; |
} |
public void setElement(E element) { |
this.element = element; |
} |
public BSTreeNode<K,E> getLeft() { |
return left; |
} |
public void setLeft(BSTreeNode<K,E> left) { |
this.left = left; |
} |
public BSTreeNode<K,E> getRight() { |
return right; |
} |
public BSTreeNode<K,E> setRight(BSTreeNode<K,E> right) { |
this.right = right; |
return right; |
} |
} |
//Classwork/CS3114/GIS/CityRecord.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/CityRecord.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/CityRecord.java |
---|
0,0 → 1,25 |
// Specific implementation of CityRecord that stores coordinates and a city name |
public class CityRecord implements Record { |
private String name; // City name |
private int x; // X-coordinate |
private int y; // Y-coordinate |
// Constructor initializing a new CityRecord |
public CityRecord(String name, int x, int y) { |
this.x = x; |
this.y = y; |
this.name = name; |
} |
// Encapsulation methods |
public String getName() { |
return name; |
} |
public int getX() { |
return x; |
} |
public int getY() { |
return y; |
} |
} |
//Classwork/CS3114/GIS/CmdParser.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/CmdParser.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/CmdParser.java |
---|
0,0 → 1,200 |
import java.util.ArrayList; |
import java.util.LinkedList; |
// Class to parse a specific set of commands |
public class CmdParser { |
BSTree<String, CityRecord> GISTree; // Binary Search Tree |
PRQuadTree CTree; // PR QuadTree |
public CmdParser() { |
// Initialize BSTree and PRQuadTree |
GISTree = new BSTree<String, CityRecord>(); |
CTree = new PRQuadTree(); |
} |
// Calls specific functions depending on input |
public void Parse(String input) { |
// Split the passed line into tokens |
String delim = "[ ]+"; |
String[] tokens = input.split(delim); |
// Echo the command to the output |
for (String token : tokens) { |
System.out.printf(token + " "); |
} |
System.out.printf("\n"); |
// Parse tokens to determine what action to take |
if (tokens[0].compareToIgnoreCase("insert") == 0) { |
Cmd_Insert(tokens); |
} else if (tokens[0].compareToIgnoreCase("remove") == 0) { |
Cmd_Remove(tokens); |
} else if (tokens[0].compareToIgnoreCase("find") == 0) { |
Cmd_Find(tokens); |
} else if (tokens[0].compareToIgnoreCase("search") == 0) { |
Cmd_Search(tokens); |
} else if (tokens[0].compareToIgnoreCase("debug") == 0) { |
Cmd_Debug(); |
} else if (tokens[0].compareToIgnoreCase("makenull") == 0) { |
Cmd_Makenull(); |
} else { |
System.out.printf(">> \"%s\" command is not supported\n", tokens[0]); |
} |
System.out.printf("\n"); |
} |
// Parse insert command |
private void Cmd_Insert(String[] tokens) { |
// Check to make sure there is a correct number of arguments for the command |
if (tokens.length != 4) { |
System.out.printf(">> Arguments must be in format \"insert x y name\"\n"); |
} else { |
try { |
// Parse and check each argument token |
int x = Integer.parseInt(tokens[1]); |
int y = Integer.parseInt(tokens[2]); |
String name = tokens[3]; |
if (x < 0 || x > 16383 || y < 0 || y > 16383) { |
System.out.printf(">> Insert failed: Coordinate values out of range\n"); |
} else { |
// If all arguments are ok, create a new record with the specified values |
CityRecord newRecord = new CityRecord(name, x, y); |
// Check if record with same coordinates already exists |
LinkedList<Record> list = new LinkedList<Record>(); |
CTree.search(x, y, 0, list); |
if (list.size() != 0) { |
System.out.printf(">> Insert failed: City at (%d,%d) already exists\n", x, y); |
} else { |
// Insert record into both trees |
System.out.printf(">> Inserting city %s (%d,%d)\n", name, x, y); |
GISTree.insert(name, newRecord); |
CTree.insert(newRecord); |
} |
} |
} catch (NumberFormatException e) { |
System.out.printf(">> Insert failed: Unable to parse given coordinates\n"); |
} |
} |
} |
// Parse remove command |
private void Cmd_Remove(String[] tokens) { |
// Check to make sure there is a correct number of arguments for the command |
if (tokens.length < 2 || tokens.length > 3) { |
System.out.printf(">> Arguments must be in format \"remove x y\" or \" remove name\"\n"); |
} else { |
// A single argument means search by name |
if (tokens.length == 2) { |
String name = tokens[1]; |
// First check if city exists |
CityRecord record = GISTree.find(name); |
if (record != null) { |
// Remove city if found |
System.out.printf(">> Removing city %s (%d,%d)\n", |
record.getName(), record.getX(), record.getY()); |
GISTree.remove(name, record.getX(), record.getY()); |
CTree.remove(record.getX(), record.getY()); |
} else { |
System.out.printf(">> Remove failed: City %s not found\n", name); |
} |
// Otherwise search by coordinates |
} else { |
try { |
// Parse and check each argument token |
int x = Integer.parseInt(tokens[1]); |
int y = Integer.parseInt(tokens[2]); |
if (x < 0 || x > 16383 || y < 0 || y > 16383) { |
System.out.printf(">> Remove failed: Coordinate values out of range\n"); |
} else { |
// Check if city with coordinates exists |
LinkedList<Record> list = new LinkedList<Record>(); |
CTree.search(x, y, 0, list); |
if (list.size() == 0) { |
System.out.printf(">> Remove failed: City with coordinates (%d,%d) not found\n", x, y); |
} else { |
// Remove using coordinates |
System.out.printf(">> Removing city %s (%d,%d)\n", |
((CityRecord)list.get(0)).getName(), list.get(0).getX(), list.get(0).getY()); |
CTree.remove(x, y); |
GISTree.remove(((CityRecord)list.get(0)).getName(), x, y); |
} |
} |
} catch (NumberFormatException e) { |
System.out.printf(">> Remove failed: Unable to parse given coordinates\n"); |
} |
} |
} |
} |
// Parse find command |
private void Cmd_Find(String[] tokens) { |
// Check to make sure there is a correct number of arguments for the command |
if (tokens.length != 2) { |
System.out.printf(">> Arguments must be in format \"find name\"\n"); |
} else { |
String name = tokens[1]; |
// Get all records with the matching name |
ArrayList<CityRecord> records = GISTree.findAll(name); |
if (records.size() != 0) { |
// For each city found, print the city details |
for (CityRecord record : records) { |
System.out.printf(">> City found: %s (%d,%d)\n", |
record.getName(), record.getX(), record.getY()); |
} |
} else { |
System.out.printf(">> Find failed: City %s not found\n", name); |
} |
} |
} |
// Parse search command |
private void Cmd_Search(String[] tokens) { |
// Check to make sure there is a correct number of arguments for the command |
if (tokens.length != 4) { |
System.out.printf(">> Arguments must be in format \"search x y radius\"\n"); |
} else { |
try { |
// Parse and check each argument token |
int x = Integer.parseInt(tokens[1]); |
int y = Integer.parseInt(tokens[2]); |
int r = Integer.parseInt(tokens[3]); |
if (r < 0 || r > 16383) { |
System.out.printf(">> Search failed: Radius value out of range\n"); |
} else if (x < -16383 || x > 16383 || y < -16383 || y > 16383) { |
System.out.printf(">> Search failed: Coordinate values out of range\n"); |
} else { |
// Get a list of all cities found within specified radius of point |
LinkedList<Record> results = new LinkedList<Record>(); |
int nodesLookedAt = CTree.search(x, y, r, results); |
System.out.printf(">> %d nodes visited:\n", nodesLookedAt); |
if (results.size() == 0) { |
System.out.printf(">> No records found with specified coordinates\n"); |
} else { |
// Print the found cities |
for (Record record : results) { |
System.out.printf(">> %s (%d,%d)\n", ((CityRecord)record).getName(), record.getX(), record.getY()); |
} |
} |
} |
} catch (NumberFormatException e) { |
System.out.printf(">> Search failed: Unable to parse given coordinates\n"); |
} |
} |
} |
// Parse debug command |
private void Cmd_Debug() { |
System.out.printf(">> "); |
CTree.debug(CTree.getRoot()); |
System.out.printf("\n"); |
} |
// Parse makenull command |
private void Cmd_Makenull() { |
GISTree.clear(); |
CTree.clear(); |
System.out.printf(">> Makenull successful\n"); |
} |
} |
//Classwork/CS3114/GIS/Dictionary.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/Dictionary.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/Dictionary.java |
---|
0,0 → 1,10 |
import java.util.ArrayList; |
// Generic dictionary interface |
public interface Dictionary<Key, Element> { |
public void insert(Key k, Element e); |
public void clear(); |
public void remove(Key k); |
public Element find(Key k); |
public ArrayList<Element> findAll(Key k); |
} |
//Classwork/CS3114/GIS/P2.pdf |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/P2.pdf |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRProg.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRProg.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRProg.java |
---|
0,0 → 1,86 |
/* |
* CS 3114 Project 2 |
* Author: Kevin Lee |
* Compiler: Eclipse 3.7.0 |
* Operating System: Windows 7 x64 |
* Date Completed: 10/7/2011 |
* |
* The following program is an implementation of two different |
* trees that allows for efficient storing of records with |
* coordinates. A binary search tree is used to allow for |
* efficient search by name, while a point region quad tree is |
* used to allow for efficient search by coordinates. The |
* program parses an input file for commands, and outputs the |
* results to standard out. |
* |
* On my honor: |
* |
* - I have not used source code obtained from another student, |
* or any other unauthorized source, either modified or |
* unmodified. |
* |
* - All source code and documentation used in my program is |
* either my original work, or was derived by me from the |
* source code published in the textbook for this course. |
* |
* - I have not discussed coding details about this project with |
* anyone other than my partner (in the case of a joint |
* submission), instructor, ACM/UPE tutors or the TAs assigned |
* to this course. I understand that I may discuss the concepts |
* of this program with other students, and that another student |
* may help me debug my program so long as neither of us writes |
* anything during the discussion or modifies any computer file |
* during the discussion. I have violated neither the spirit nor |
* letter of this restriction. |
*/ |
import java.io.BufferedReader; |
import java.io.File; |
import java.io.FileNotFoundException; |
import java.io.FileReader; |
import java.io.IOException; |
public class PRProg { |
public static void main(String[] args) { |
String input_commandFile; // Location of file to parse |
// 3 arguments must be supplied to the program |
if (args.length != 1) { |
System.out.println("1 Arguments must be supplied!"); |
return; |
} |
// Parses passed arguments into member variables |
input_commandFile = args[0]; |
// Check to make sure the command file exists |
File cmdFile = new File(input_commandFile); |
if (!cmdFile.exists()) { |
System.out.printf("Command file not found"); |
return; |
} |
CmdParser GISParser = new CmdParser(); |
// Parse each command with the memory client |
try { |
BufferedReader reader = new BufferedReader(new FileReader(cmdFile)); |
String cin; |
while ((cin = reader.readLine()) != null) { |
cin = cin.trim(); |
if (cin.length() != 0) { |
// Send string to command parser |
GISParser.Parse(cin); |
} |
} |
} catch (FileNotFoundException e) { |
System.out.printf("Command file not found"); |
return; |
} catch (IOException e) { |
System.out.printf("Unable to read input file"); |
return; |
} |
} |
} |
//Classwork/CS3114/GIS/PRQuadTree.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRQuadTree.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRQuadTree.java |
---|
0,0 → 1,257 |
import java.util.LinkedList; |
import java.lang.Math; |
// Somewhat generic implementation of a PR QuadTree |
public class PRQuadTree { |
private PRQuadTreeNode root; // Root of the PR QuadTree |
private PRQuadTreeNodeFlyweight flyweight; // Flyweight representing empty nodes |
private int maxSize = 16384; // Maximum size of the grid |
// Constructor |
public PRQuadTree() { |
// Initialize a singleton flyweight object |
flyweight = new PRQuadTreeNodeFlyweight(); |
root = flyweight; |
} |
// Inserts given record into the tree |
public void insert(Record record) { |
// Recursively call function to insert a record |
this.root = insertRecursive(root, record, maxSize); |
} |
// Removes a record from the tree given a set of coordinates |
public void remove(int x, int y) { |
// Recursively call function to remove a record |
this.root = removeRecursive(root, x, y, maxSize); |
} |
// Searches for all records within radius and returns the results in the passed list |
public int search(int x, int y, int r, LinkedList<Record> results) { |
// Searches for all cities in radius of given point |
// Number of nodes looked at is returned while list of cities is stored in 'list' |
return searchRecursive(root, x, y, r, results, maxSize); |
} |
// Removes all records from the tree |
public void clear() { |
// Set root to the flyweight to remove all nodes |
root = flyweight; |
} |
// Prints out all records from the tree |
public void debug(PRQuadTreeNode root) { |
// If root is the flyweight ... |
if (root == flyweight) { |
System.out.printf("E"); |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { |
System.out.printf("%d,%d,%s", record.getX(), record.getY(), ((CityRecord) record).getName()); |
record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
} while (record != null); |
System.out.printf("|"); |
// If root is an internal node ... |
} else { |
System.out.printf("I"); |
debug(((PRQuadTreeNodeInternal) root).getNW()); |
debug(((PRQuadTreeNodeInternal) root).getNE()); |
debug(((PRQuadTreeNodeInternal) root).getSW()); |
debug(((PRQuadTreeNodeInternal) root).getSE()); |
} |
} |
// Returns the root of the tree |
public PRQuadTreeNode getRoot() { |
return root; |
} |
// Recursively insert a record into a root node |
private PRQuadTreeNode insertRecursive(PRQuadTreeNode root, Record record, int size) { |
// If root is the flyweight, create and return a leaf node with the record |
if (root == flyweight) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
newLeaf.insert(record); |
return newLeaf; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Try to insert the record into the leaf, return leaf if successful |
if (((PRQuadTreeNodeLeaf) root).insert(record)) { |
return root; |
// Otherwise all nodes in the leaf are filled |
} else { |
// Create new internal node and populate it with flyweights |
PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight); |
// Get the first record to insert into the internal node |
Record rec = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { |
// Insert every record from the full leaf into the internal node |
newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, rec, size); |
} while ((rec = ((PRQuadTreeNodeLeaf) root).getNext(rec)) != null); |
// Now insert the initial record into the internal node |
newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, record, size); |
// Return the newly created internal node |
return newNode; |
} |
// If root is an internal node ... |
} else { |
// Insert the record into the correct quadrant |
if (record.getX() < size/2 && record.getY() < size/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) root).setNW(insertRecursive(((PRQuadTreeNodeInternal) root).getNW(), record, size/2)); |
} else if (record.getX() >= size/2 && record.getY() < size/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) root).setNE(insertRecursive(((PRQuadTreeNodeInternal) root).getNE(), record, size/2)); |
} else if (record.getX() < size/2 && record.getY() >= size/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) root).setSW(insertRecursive(((PRQuadTreeNodeInternal) root).getSW(), record, size/2)); |
} else { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) root).setSE(insertRecursive(((PRQuadTreeNodeInternal) root).getSE(), record, size/2)); |
} |
// Return the internal node after inserting a record into it |
return root; |
} |
} |
// Recursively remove a record from a root node given the coordinates |
private PRQuadTreeNode removeRecursive(PRQuadTreeNode root, int x, int y, int size) { |
// If root is the flyweight, return the root |
if (root == flyweight) { |
return root; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Try to remove element from the leaf |
((PRQuadTreeNodeLeaf) root).remove(x, y); |
// If the leaf is empty, return the flyweight |
if (root.isEmpty()) |
return flyweight; |
else |
return root; |
// If root is an internal node ... |
} else { |
// Remove the record from the correct quadrant |
if (x < size/2 && y < size/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) root).setNW(removeRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, size/2)); |
} else if (x >= size/2 && y < size/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) root).setNE(removeRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, size/2)); |
} else if (x < size/2 && y >= size/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) root).setSW(removeRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, size/2)); |
} else { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) root).setSE(removeRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, size/2)); |
} |
// Return a flyweight if the internal node is empty after removal |
if (root.isEmpty()) { |
return flyweight; |
// Otherwise if the internal node contains all leaves or flyweights ... |
} else if (((PRQuadTreeNodeInternal) root).containsAllLeavesOrFlyweight()) { |
// If the number of records in subleaves is under 3, create and return a new leaf holding all records |
if (((PRQuadTreeNodeInternal) root).countOfAllLeafNodes() <= 3) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNW()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNW()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNE()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNE()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSW()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSW()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSE()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSE()); |
} |
// Return the new leaf that holds all records from the internal node |
return newLeaf; |
// If there are more than 3 records in subleaves, return the internal node |
} else { |
return root; |
} |
// Otherwise return the internal node if it contains internal nodes |
} else { |
return root; |
} |
} |
} |
// Recursively searches for records within radius of given coordinates |
private int searchRecursive(PRQuadTreeNode root, int x, int y, int radius, LinkedList<Record> results, int size) { |
// If root is the flyweight ... |
if (root == flyweight) { |
return 1; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Loop through each record in the leaf node |
Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { // Note: the first record can never be null (else it'll be a flyweight) |
// Check each record to see if it lies within the specified radius of the point |
if ((x - record.getX()) * (x - record.getX()) + |
(y - record.getY()) * (y - record.getY()) <= radius * radius) { |
// If it is, add it to the list |
results.add(record); |
} |
record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
} while (record != null); |
// Return the number of nodes looked at (1, this node) |
return 1; |
// If root is an internal node ... |
} else { |
int ret = 0; |
// Check each quadrant to see if any intersect with the circle/radius |
// NW quadrant |
if (intersects(x, y, radius, size/2, size/2, size/4, size/4)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, radius, results, size/2); |
} |
// NE quadrant |
if (intersects(x, y, radius, size/2, size/2, size/4 + size/2, size/4)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, radius, results, size/2); |
} |
// SW quadrant |
if (intersects(x, y, radius, size/2, size/2, size/4, size/4 + size/2)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, radius, results, size/2); |
} |
// SE quadrant |
if (intersects(x, y, radius, size/2, size/2, size/4 + size/2, size/4 + size/2)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, radius, results, size/2); |
} |
ret++; |
return ret; |
} |
} |
// Calculates if any points in a circle intersects with a rectangle |
private boolean intersects(int cX, int cY, int cR, int rW, int rH, int rX, int rY) { |
// Reference: http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection/402010#402010 |
// Distance from center of circle to center of rectangle |
int xCircleDistance = Math.abs(cX - rX); |
int yCircleDistance = Math.abs(cY - rY); |
// If Distance > width of rectangle + radius, circle cannot overlap rectangle |
if (xCircleDistance > (rW/2 + cR)) { |
return false; |
} |
if (yCircleDistance > (rH/2 + cR)) { |
return false; |
} |
// If distance <= width of rectangle, circle must overlap rectangle |
if (xCircleDistance <= (rW/2)) { |
return true; |
} |
if (yCircleDistance <= (rH/2)) { |
return true; |
} |
// Check for overlap on corners |
int cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) + |
(yCircleDistance - rH/2) * (yCircleDistance - rH/2); |
return (cornerDist <= cR * cR); |
} |
} |
//Classwork/CS3114/GIS/PRQuadTreeNode.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRQuadTreeNode.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRQuadTreeNode.java |
---|
0,0 → 1,5 |
// Interface for a generic PRQuadTree node |
public interface PRQuadTreeNode { |
public boolean isEmpty(); |
} |
//Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.java |
---|
0,0 → 1,7 |
public class PRQuadTreeNodeFlyweight implements PRQuadTreeNode { |
public boolean isEmpty() { |
return true; |
} |
} |
//Classwork/CS3114/GIS/PRQuadTreeNodeInternal.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRQuadTreeNodeInternal.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRQuadTreeNodeInternal.java |
---|
0,0 → 1,79 |
// Internal node for the PRQuadTree |
public class PRQuadTreeNodeInternal implements PRQuadTreeNode { |
private PRQuadTreeNode NW; // Node in each quadrant |
private PRQuadTreeNode NE; |
private PRQuadTreeNode SW; |
private PRQuadTreeNode SE; |
private PRQuadTreeNodeFlyweight flyweight; // Flyweight |
// Constructor to initialize the node with flyweights |
public PRQuadTreeNodeInternal(PRQuadTreeNodeFlyweight flyweight) { |
// Initialize all subnodes with the flyweight |
NW = NE = SW = SE = flyweight; |
this.flyweight = flyweight; |
} |
// Queries if all subnodes are flyweights |
public boolean isEmpty() { |
return (NW == flyweight)&&(NE == flyweight)&& |
(SW == flyweight)&&(SE == flyweight); |
} |
// Test if node contains other internal nodes |
public boolean containsAllLeavesOrFlyweight() { |
// Queries if all subnodes are either leaves or flyweights |
return (NW instanceof PRQuadTreeNodeLeaf || NW instanceof PRQuadTreeNodeFlyweight)&& |
(NE instanceof PRQuadTreeNodeLeaf || NE instanceof PRQuadTreeNodeFlyweight)&& |
(SW instanceof PRQuadTreeNodeLeaf || SW instanceof PRQuadTreeNodeFlyweight)&& |
(SE instanceof PRQuadTreeNodeLeaf || SE instanceof PRQuadTreeNodeFlyweight); |
} |
// Returns the number of all records in all subleaves |
public int countOfAllLeafNodes() { |
int ret = 0; |
if (NW instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) NW).getCount(); |
if (NE instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) NE).getCount(); |
if (SW instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) SW).getCount(); |
if (SE instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) SE).getCount(); |
return ret; |
} |
// Returns the number of records in a node if it is a leaf node |
public int countOfLeafNode(PRQuadTreeNode node) { |
if (node instanceof PRQuadTreeNodeLeaf) |
return ((PRQuadTreeNodeLeaf) node).getCount(); |
else |
return 0; |
} |
// Encapsulation functions |
public PRQuadTreeNode getNW() { |
return NW; |
} |
public void setNW(PRQuadTreeNode nW) { |
NW = nW; |
} |
public PRQuadTreeNode getNE() { |
return NE; |
} |
public void setNE(PRQuadTreeNode nE) { |
NE = nE; |
} |
public PRQuadTreeNode getSW() { |
return SW; |
} |
public void setSW(PRQuadTreeNode sW) { |
SW = sW; |
} |
public PRQuadTreeNode getSE() { |
return SE; |
} |
public void setSE(PRQuadTreeNode sE) { |
SE = sE; |
} |
} |
//Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.java |
---|
0,0 → 1,119 |
// Leaf node for the PRQuadTree |
public class PRQuadTreeNodeLeaf implements PRQuadTreeNode { |
private Record[] records; // Array holding the records in the leaf |
private int numOfRecords; // Number of records in the leaf |
// Initialize a new leaf node that holds 'size' records |
public PRQuadTreeNodeLeaf(int size) { |
records = new Record[size]; |
numOfRecords = size; |
} |
// Inserts each record from input leaf into current leaf |
public void insert(PRQuadTreeNodeLeaf leaf) { |
Record record = leaf.getFirst(); |
do { |
this.insert(record); |
record = leaf.getNext(record); |
} |
while (record != null); |
} |
// Inserts a record into the current leaf |
public boolean insert(Record in) { |
if (in == null) |
return true; |
boolean ret = false; |
// If all records are filled, return false |
for (Record record : records) { |
if (record == null) { |
ret = true; |
break; |
} |
} |
if (ret != false) { |
// Otherwise insert record into the first avalaible slot |
for (int i = 0; i < numOfRecords; i++) { |
if (records[i] == null) { |
records[i] = in; |
break; |
} |
} |
} |
return ret; |
} |
// Removes a record from the leaf given a set of coordinates |
public Record remove(int x, int y) { |
Record ret = null; |
// Check if any of the records have matching coordinates |
ret = find(x, y); |
if (ret != null) { |
// If record is found, return record and shift other records forward |
for (int i = 0; i < numOfRecords; i++) { |
if (records[i] == ret) { |
// Shift records forward |
for (int j = i; j < numOfRecords; j++) { |
if (j+1 < numOfRecords) |
records[j] = records[j+1]; |
else |
records[j] = null; |
} |
break; |
} |
} |
} |
return ret; |
} |
// Returns a record with the specified coordinates if it exists |
public Record find(int x, int y) { |
Record ret = null; |
// Check if any records have matching coordinates |
for (Record record : records) { |
if (record != null && record.getX() == x && record.getY() == y) { |
// Return the record if found |
ret = record; |
break; |
} |
} |
return ret; |
} |
// Returns the first record in the leaf node |
public Record getFirst() { |
return records[0]; |
} |
// Returns the next record given a record |
public Record getNext(Record record) { |
Record ret = null; |
for (int i = 0; i < numOfRecords; i++) { |
if (records[i] == record) { |
if (i+1 < numOfRecords) |
ret = records[i+1]; |
break; |
} |
} |
return ret; |
} |
// Returns the number of records in the leaf node |
public int getCount() { |
int ret = 0; |
for (int i = 0; i < numOfRecords; i++) { |
if (records[i] != null) |
ret++; |
else |
break; |
} |
return ret; |
} |
// If first record is empty, the entire leaf is empty |
public boolean isEmpty() { |
return (records[0] == null); |
} |
} |
//Classwork/CS3114/GIS/Record.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/Record.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/Record.java |
---|
0,0 → 1,6 |
// Interface for a generic record for the BSTree or PRQuadTree |
public interface Record { |
public int getX(); |
public int getY(); |
} |
//Classwork/CS3114/GIS/Schedule.xls |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/GIS/Schedule.xls |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/GIS/p2SyntaxTest.txt |
---|
0,0 → 1,54 |
makenull |
insert -1 1597 Blacksburg |
insert 16384 4 Blacksburg |
insert 16383 16834 Blacksburg |
insert 8581 -8581 Blacksburg |
insert 5001 5012 Blacksburg |
insert 5001 5012 Christiansburg |
insert 5001 6213 Blacksburg |
insert 5001 8414 Christiansburg |
insert 0 0 Floyd |
insert 16383 16383 Virginia_Beach |
debug |
find Blacksbrug |
find Blacksburg |
remove -160 15958 |
remove 0 -15958 |
remove 581 3851 |
remove 5001 5012 |
remove 5001 5012 |
remove Blacksbrug |
remove Christiansburg |
insert 5002 1019 Radford |
search 0 16893 1 |
search 100 159 -1 |
search -100 159 500 |
search 0 68 1000000 |
search 5000 5000 100 |
makenull |
debug |
//Classwork/CS3114/GIS/p2SyntaxTestOutput.txt |
---|
0,0 → 1,94 |
makenull |
>> Makenull operation successful |
insert -1 1597 Blacksburg |
>> Insert rejected, bad X coordinate |
insert 16384 4 Blacksburg |
>> Insert rejected, bad X coordinate |
insert 16383 16834 Blacksburg |
>> Insert rejected, bad Y coordinate |
insert 8581 -8581 Blacksburg |
>> Insert rejected, bad Y coordinate |
insert 5001 5012 Blacksburg |
>> Insert operation successful |
insert 5001 5012 Christiansburg |
>> Insert rejected, coordinates duplicate an existing city record |
insert 5001 6213 Blacksburg |
>> Insert operation successful |
insert 5001 8414 Christiansburg |
>> Insert operation successful |
insert 0 0 Floyd |
>> Insert operation successful |
insert 16383 16383 Virginia_Beach |
>> Insert operation successful |
debug |
>> I5001,5012,Blacksburg5001,6213,Blacksburg0,0,Floyd|E5001,8414,Christiansburg|16383,16383,virginia_Beach| |
find Blacksbrug |
>> City record(s) found: |
>> No records |
find Blacksburg |
>> City Records found: |
>> 5001, 5012, Blacksburg |
>> 5001, 6213, Blacksburg |
remove -160 15958 |
>> Remove operation failed: Bad X coordinate |
[The Y coordinate is also bad, but one error is sufficient to report] |
remove 0 -15958 |
>> Remove operation failed: Bad Y coordinate |
remove 581 3851 |
>> No such City Record found |
remove 5001 5012 |
>> Removed 5001, 5012, Blacksburg |
remove 5001 5012 |
>> No such City Record found |
remove Blacksbrug |
>> No such City Record found |
remove Christiansburg |
>> Removed 5001, 8414, Christiansburg |
insert 5002 1019 Radford |
>> Insert operation successful |
search 0 16893 1 |
>> Search operation failed: Bad Y value |
search 100 159 -1 |
>> Search operation failed: Bad radius value |
search -100 159 500 |
>> City record(s) found: |
>> 0, 0, Floyd |
>> 2 nodes visited |
search 0 68 1000000 |
>> Search operation failed: Bad radius value |
search 5000 5000 100 |
>> City record(s) found: |
>> No such record |
>> 2 nodes visited |
makenull |
>> Makenull operation successful |
debug |
>> E |