//Classwork/CS3114/Project 4/.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/Project 4/.project |
---|
0,0 → 1,17 |
<?xml version="1.0" encoding="UTF-8"?> |
<projectDescription> |
<name>CS3114P4</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/Project 4/.settings/org.eclipse.jdt.core.prefs |
---|
0,0 → 1,12 |
#Fri Dec 02 19:58:28 EST 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/Project 4/BSTree.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/BSTree.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/BSTree.java |
---|
0,0 → 1,172 |
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 |
NodeSerializer serializer; |
// Constructor |
public BSTree(MemManager mem) { |
serializer = new NodeSerializer(mem); |
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) { |
CityRecord record = serializer.handleToCityRecord((Handle)root.getElement()); |
// If coordinates do not match, keep searching from the right child |
// if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) { |
if (record.getX() != x || record.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) { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
return root.getRight(); |
} else if (root.getRight() == null) { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
return root.getLeft(); |
} else { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
// 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) { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
return root.getRight(); |
} else if (root.getRight() == null) { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
return root.getLeft(); |
} else { |
serializer.removeCityRecordHandle((Handle)root.getElement()); |
// 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/Project 4/BSTreeNode.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/BSTreeNode.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/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/Project 4/Bindisk.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/Bindisk.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/Bindisk.java |
---|
0,0 → 1,105 |
/* |
* CS 3114 Project 4 |
* Author: Kevin Lee |
* Compiler: Eclipse 3.7.0 |
* Operating System: Windows 7 x64 |
* Date Completed: 12/4/2011 |
* |
* The following program is an combination of the previous three |
* projects. This program implements the GIS b-tree and |
* quad-tree, but instead of keeping the PRQuad-Tree in memory, |
* the PRQuad-Tree interfaces with a memory manager to store and |
* retrieve internal and leaf nodes, as well as city names. The |
* memory manager interfaces to a file ("p4bin.dat") using a |
* buffer pool. The buffer pool is implemented using a least |
* recently used block list. |
* |
* Note that while the PRQuad-Tree is optimized for speed, the |
* conversion of CityRecords to handles for the b-tree severely |
* slows down the program (see test _seq-16384-IR). If the b-tree |
* is kept completely in memory, the program runs >30x faster. |
* |
* 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 Bindisk { |
public static void main(String[] args) { |
// 3 arguments must be supplied to the program |
if (args.length != 3) { |
System.out.println("3 Arguments must be supplied!"); |
return; |
} |
// Parses passed arguments into member variables |
String dataFile = args[0]; |
int buffSize = Integer.parseInt(args[1]); |
int blockSize = Integer.parseInt(args[2]); |
if (buffSize < 1 || buffSize > 20) { |
System.out.println("Number of buffers must be between 1 and 20"); |
return; |
} |
LRUBuffer buffer = new LRUBuffer("p4bin.dat", "p4bin-stat.dat", buffSize, blockSize); |
MemManager memManager = new MemManager(buffer, blockSize); |
// Check to make sure the command file exists |
File cmdFile = new File(dataFile); |
if (!cmdFile.exists()) { |
System.out.printf("Command file not found"); |
return; |
} |
CmdParser GISParser = new CmdParser(memManager); |
long time1 = System.currentTimeMillis(); |
// 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; |
} |
buffer.flushBuffer(); |
long time2 = System.currentTimeMillis(); |
buffer.writeStats(time2-time1); |
} |
} |
//Classwork/CS3114/Project 4/BufferBlock.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/BufferBlock.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/BufferBlock.java |
---|
0,0 → 1,72 |
public class BufferBlock { |
private long startAddress; |
private byte[] bytes; |
private int size; |
private BufferBlock prev; |
private BufferBlock next; |
private boolean dirtyBit; |
public BufferBlock(int sz) { |
setStartAddress(-1); |
bytes = new byte[sz]; |
this.size = sz; |
prev = null; |
next = null; |
setDirtyBit(false); |
} |
/** Copies size bytes starting from address to out + offset |
* |
* @param out Destination array to copy bytes to |
* @param offset Offset of position to write to in the destination array |
* @param address Starting address in block to copy bytes from |
* @param length Number of bytes to copy from the block |
*/ |
public void getBytes(byte[] out, int offset, int address, int length) { |
for (int i = 0; i < length; i++) { |
out[i + offset] = bytes[address + i]; |
} |
} |
/** Puts size bytes starting to address from in |
* |
* @param in Source array to copy bytes from |
* @param offset Offset position in the source array to copy from |
* @param address Starting address in the block to copy bytes to |
* @param length Number of bytes to copy into the block |
*/ |
public void setBytes(byte[] in, int offset, int address, int length) { |
for (int i = 0; i < length; i++) { |
bytes[address + i] = in[i + offset]; |
} |
} |
public BufferBlock getPrev() { |
return prev; |
} |
public void setPrev(BufferBlock prev) { |
this.prev = prev; |
} |
public BufferBlock getNext() { |
return next; |
} |
public void setNext(BufferBlock next) { |
this.next = next; |
} |
public int getSize() { |
return size; |
} |
public boolean isDirtyBit() { |
return dirtyBit; |
} |
public void setDirtyBit(boolean dirtyBit) { |
this.dirtyBit = dirtyBit; |
} |
public long getStartAddress() { |
return startAddress; |
} |
public void setStartAddress(long startAddress) { |
this.startAddress = startAddress; |
} |
} |
//Classwork/CS3114/Project 4/CityRecord.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/CityRecord.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/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/Project 4/CmdParser.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/CmdParser.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/CmdParser.java |
---|
0,0 → 1,202 |
import java.util.ArrayList; |
import java.util.LinkedList; |
// Class to parse a specific set of commands |
public class CmdParser { |
BSTree<String, Handle> GISTree; // Binary Search Tree |
PRQuadTree CTree; // PR QuadTree |
NodeSerializer serializer; |
public CmdParser(MemManager mem) { |
// Initialize BSTree and PRQuadTree |
GISTree = new BSTree<String, Handle>(mem); |
CTree = new PRQuadTree(mem); |
serializer = new NodeSerializer(mem); |
} |
// 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); |
CTree.insert(newRecord); |
Handle cityHandle = serializer.cityRecordToHandle(newRecord); |
GISTree.insert(name, cityHandle); |
} |
} |
} 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 |
Handle handle = GISTree.find(name); |
if (handle != null) { |
CityRecord record = serializer.handleToCityRecord(handle); |
// 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<Handle> records = GISTree.findAll(name); |
if (records.size() != 0) { |
// For each city found, print the city details |
for (Handle handle : records) { |
CityRecord record = serializer.handleToCityRecord(handle); |
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() { |
CTree.printDebug(); |
} |
// Parse makenull command |
private void Cmd_Makenull() { |
GISTree.clear(); |
CTree.clear(); |
System.out.printf(">> Makenull successful\n"); |
} |
} |
//Classwork/CS3114/Project 4/Dictionary.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/Dictionary.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/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/Project 4/DoubleLinkedList.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/DoubleLinkedList.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/DoubleLinkedList.java |
---|
0,0 → 1,138 |
// Class for managing the linked list of free blocks |
public class DoubleLinkedList { |
private LinkedListBlock head; // Start of linked list |
public void insert(LinkedListBlock entry) { |
boolean adjacencyFound = false; // Adjacency flag |
// Create the first entry if there are none existing |
if (head == null) { |
head = entry; |
head.setNextBlock(null); |
head.setPrevBlock(null); |
return; |
} |
LinkedListBlock current = head; |
// Check to see if adjacent entries exist |
while (current != null) { |
if (current.getStartAddress() == entry.getEndAddress() + 1) { |
// Entry is adjacent to start of current |
LinkedListBlock newEntry = new LinkedListBlock(entry.getStartAddress(), |
current.getEndAddress(), entry.getSize() + current.getSize()); |
remove(current.getStartAddress()); |
insert(newEntry); |
adjacencyFound = true; |
break; |
} |
if (current.getEndAddress() == entry.getStartAddress() - 1) { |
// Entry is adjacent to end of current |
LinkedListBlock newEntry = new LinkedListBlock(current.getStartAddress(), |
entry.getEndAddress(), current.getSize() + entry.getSize()); |
remove(current.getStartAddress()); |
insert(newEntry); |
adjacencyFound = true; |
break; |
} |
current = current.getNextBlock(); |
} |
// Otherwise insert entry into sorted list (by size) |
current = head; |
if (!adjacencyFound && (entry.getSize() > current.getSize())) { |
// Insert into beginning of list if size is largest |
entry.setNextBlock(current); |
current.setPrevBlock(entry); |
head = entry; |
return; |
} else if (!adjacencyFound) { |
// Otherwise find location to insert into |
LinkedListBlock prev = head; |
while (prev.getNextBlock() != null) { |
current = prev.getNextBlock(); |
if (entry.getSize() == current.getSize()) { |
// Sort by address location in accending order |
if (entry.getStartAddress() < current.getStartAddress()) { |
// Insert before current |
entry.setNextBlock(current); |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
current.setPrevBlock(entry); |
return; |
} else { |
// Insert after current |
prev = current; |
if (prev.getNextBlock() != null) { |
current = prev.getNextBlock(); |
entry.setNextBlock(current); |
current.setPrevBlock(entry); |
} |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
return; |
} |
} else if (entry.getSize() > current.getSize()) { |
// Insert block between prev and current |
entry.setNextBlock(current); |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
current.setPrevBlock(entry); |
return; |
} else { |
// Otherwise continue searching |
prev = current; |
} |
} |
// Insert into end of list |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
} |
} |
// Deletes an entry from the list, returns true if address is found |
public boolean remove(long address) { |
// First check if list is empty |
if (head == null) { |
return false; |
} else { |
// Otherwise loop through and fine entry |
LinkedListBlock entry = head; |
do { |
if (entry.getStartAddress() == address) { |
if (entry.getPrevBlock() == null && entry.getNextBlock() == null) { |
// Deletes entry (only entry in list) |
head = null; |
} else if (entry.getPrevBlock() == null && entry.getNextBlock() != null) { |
// Deletes entry (first in list) |
head = entry.getNextBlock(); |
head.setPrevBlock(null); |
} else if (entry.getPrevBlock() != null && entry.getNextBlock() == null) { |
// Deletes entry (last in list) |
entry.getPrevBlock().setNextBlock(null); |
} else { |
// Deletes entry (in between two entries) |
LinkedListBlock prev = entry.getPrevBlock(); |
prev.setNextBlock(entry.getNextBlock()); |
entry.getNextBlock().setPrevBlock(prev); |
} |
return true; |
} |
entry = entry.getNextBlock(); |
} while (entry != null); |
} |
return false; |
} |
// Returns an entry from the list with the passed address |
public LinkedListBlock getFirstEntry() { |
// First check if list is empty |
if (head == null) { |
return null; |
} else { |
// Otherwise return head entry |
return head; |
} |
} |
} |
//Classwork/CS3114/Project 4/Handle.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/Handle.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/Handle.java |
---|
0,0 → 1,17 |
// Handle passed to and from MemManager |
public class Handle { |
private long address; // Location of block in memory pool |
public Handle(long addr) { |
this.address = addr; |
} |
public long getAddress() { |
return address; |
} |
public void setAddress(int address) { |
this.address = address; |
} |
} |
//Classwork/CS3114/Project 4/LRUBuffer.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/LRUBuffer.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/LRUBuffer.java |
---|
0,0 → 1,306 |
import java.io.BufferedWriter; |
import java.io.FileNotFoundException; |
import java.io.FileWriter; |
import java.io.IOException; |
import java.io.RandomAccessFile; |
public class LRUBuffer { |
private int blockSize = 0; |
private int cacheHit = 0; |
private int cacheMiss = 0; |
private int diskReads = 0; |
private int diskWrites = 0; |
private String dataFile; |
private String statFile; |
private BufferBlock bufferHead; |
private RandomAccessFile file; |
public LRUBuffer(String datafile, String statfile, int size, int blocksize) { |
this.dataFile = datafile; |
this.statFile = statfile; |
this.blockSize = blocksize; |
// Allocates a new doubly linked list of BufferBlocks |
// The buffer will have at least one block |
bufferHead = new BufferBlock(blockSize); |
BufferBlock cur = bufferHead; |
for (int i = 0; i < size-1; i++) { |
BufferBlock newBlock = new BufferBlock(blockSize); |
cur.setNext(newBlock); |
newBlock.setPrev(cur); |
cur = newBlock; |
} |
// Open access to the datafile |
try { |
file = new RandomAccessFile(dataFile, "rw"); |
file.setLength(0); |
} catch (FileNotFoundException e) { |
e.printStackTrace(); |
} catch (IOException e) { |
e.printStackTrace(); |
} |
} |
/** Recursive function to copy length number of bytes from file at startAddress |
* to offset position in out |
* |
* @param out Destination array to copy bytes to |
* @param offset Offset of position to write to in the destination array |
* @param startAddress Starting address on disk to copy bytes from |
* @param length Number of bytes to copy to the destination array |
* @return |
*/ |
public boolean getBytes(byte[] out, int offset, long startAddress, int length) { |
BufferBlock cur = bufferHead; |
// If the requested length doesnt extends to the next block |
if (startAddress % blockSize + length < blockSize) { |
// Check if address is already in a buffer block |
while (cur != null && cur.getStartAddress() != -1) { |
if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) { |
// Address is in block |
cacheHit++; |
// Bring current block to front of list |
bringToFront(cur); |
// Get data |
cur.getBytes(out, offset, (int)startAddress % blockSize, length); |
return true; |
} |
cur = cur.getNext(); |
} |
// Address is not in buffer, read new block from disk |
cacheMiss++; |
cur = readFromDisk(startAddress); |
insertToFront(cur); |
// Get data from block |
cur.getBytes(out, offset, (int)startAddress % blockSize, length); |
return true; |
// If the requested length extends to the next block |
} else { |
int bytesToRead = 0; |
// Check if address is already in a buffer block |
while (cur != null && cur.getStartAddress() != -1) { |
if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) { |
// Address is in block |
cacheHit++; |
// Bring current block to front of list |
bringToFront(cur); |
// Read in from address to end of block |
bytesToRead = blockSize - (int)startAddress % blockSize; |
cur.getBytes(out, offset, (int)startAddress % blockSize, bytesToRead); |
offset += bytesToRead; |
// Get data from the next consecutive block |
getBytes(out, offset, startAddress + bytesToRead, length - bytesToRead); |
return true; |
} |
cur = cur.getNext(); |
} |
// Address is not in buffer, read new block from disk |
cacheMiss++; |
cur = readFromDisk(startAddress); |
insertToFront(cur); |
// Read in from address to end of block |
bytesToRead = blockSize - (int)startAddress % blockSize; |
cur.getBytes(out, offset, (int)startAddress % blockSize, bytesToRead); |
offset += bytesToRead; |
// Get data from the next consecutive block |
getBytes(out, offset, startAddress + bytesToRead, length - bytesToRead); |
return true; |
} |
} |
/** Recursive function to copy length number of bytes from in to file at startAddress |
* |
* @param in Input array to copy bytes from |
* @param startAddress Starting address on disk to copy bytes to |
* @param length Number of bytes to copy from in to disk |
* @return |
*/ |
public boolean putBytes(byte[] in, int offset, long startAddress, int length) { |
BufferBlock cur = bufferHead; |
// If the requested length doesnt extends to the next block |
if (startAddress % blockSize + length <= blockSize) { |
// Check if address is already in a buffer block |
while (cur != null && cur.getStartAddress() != -1) { |
if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) { |
// Address is in block |
cacheHit++; |
// Bring current block to front of list |
bringToFront(cur); |
// Put data into block |
cur.setBytes(in, offset, (int)startAddress % blockSize, length); |
cur.setDirtyBit(true); |
return true; |
} |
cur = cur.getNext(); |
} |
// Address is not in buffer, read new block from disk |
cacheMiss++; |
cur = readFromDisk(startAddress); |
insertToFront(cur); |
// Put data into block |
cur.setBytes(in, offset, (int)startAddress % blockSize, length); |
cur.setDirtyBit(true); |
return true; |
// If the requested length extends to the next block |
} else { |
int bytesToWrite = 0; |
// Check if address is already in a buffer block |
while (cur != null && cur.getStartAddress() != -1) { |
if (startAddress >= cur.getStartAddress() && startAddress < cur.getStartAddress() + blockSize) { |
// Address is in block |
cacheHit++; |
// Bring current block to front of list |
bringToFront(cur); |
// Put in data until end of block |
bytesToWrite = blockSize - (int)startAddress % blockSize; |
cur.setBytes(in, offset, (int)startAddress % blockSize, bytesToWrite); |
cur.setDirtyBit(true); |
startAddress += bytesToWrite; |
// Put remaining data into the next consecutive block |
putBytes(in, offset + bytesToWrite, startAddress, length - bytesToWrite); |
return true; |
} |
cur = cur.getNext(); |
} |
// Address is not in buffer, read new block from disk |
cacheMiss++; |
cur = readFromDisk(startAddress); |
insertToFront(cur); |
// Put in data until end of block |
bytesToWrite = blockSize - (int)startAddress % blockSize; |
cur.setBytes(in, offset, (int)startAddress % blockSize, bytesToWrite); |
cur.setDirtyBit(true); |
startAddress += bytesToWrite; |
// Put remaining data into the next consecutive block |
putBytes(in, offset + bytesToWrite, startAddress, length - bytesToWrite); |
return true; |
} |
} |
/** Brings a block currently in the list to the front of the list */ |
private void bringToFront(BufferBlock block) { |
// If block is already in front, return |
if (block == bufferHead) |
return; |
if (block.getPrev() != null) |
block.getPrev().setNext(block.getNext()); |
if (block.getNext() != null) |
block.getNext().setPrev(block.getPrev()); |
block.setPrev(null); |
bufferHead.setPrev(block); |
block.setNext(bufferHead); |
bufferHead = block; |
} |
/** Inserts a new block into the front of the list */ |
private void insertToFront(BufferBlock block) { |
// Set head as current block |
block.setPrev(null); |
bufferHead.setPrev(block); |
block.setNext(bufferHead); |
bufferHead = block; |
// Write last block in list to disk if dirty bit is set |
// Last block is also removed |
BufferBlock cur = bufferHead; |
while (cur.getNext() != null) { |
cur = cur.getNext(); |
} |
cur.getPrev().setNext(null); |
if (cur.isDirtyBit()) { |
writeToDisk(cur); |
} |
} |
/** Reads a new block from disk given an address */ |
private BufferBlock readFromDisk(long address) { |
diskReads++; |
byte[] data = new byte[blockSize]; |
long offset = address / blockSize; |
offset = offset * blockSize; |
try { |
file.seek(offset); |
file.read(data); |
} catch (IOException e) { |
e.printStackTrace(); |
} |
// Pass read block into a new block |
BufferBlock newBlock = new BufferBlock(blockSize); |
newBlock.setBytes(data, 0, 0, blockSize); |
newBlock.setStartAddress(offset); |
return newBlock; |
} |
/** Writes the specified block to disk */ |
private void writeToDisk(BufferBlock block) { |
diskWrites++; |
byte[] data = new byte[blockSize]; |
block.getBytes(data, 0, 0, blockSize); |
try { |
file.seek(block.getStartAddress()); |
file.write(data); |
} catch (IOException e) { |
e.printStackTrace(); |
} |
} |
/** Flush the buffer by writing all blocks in buffer to disk */ |
public void flushBuffer() { |
BufferBlock cur = bufferHead; |
while (cur != null) { |
if (cur.isDirtyBit()) { |
writeToDisk(cur); |
} |
cur = cur.getNext(); |
} |
try { |
file.close(); |
} catch (IOException e) { |
e.printStackTrace(); |
} |
} |
/** Write stats to stat file */ |
public void writeStats(long time) { |
try { |
BufferedWriter out = new BufferedWriter(new FileWriter(statFile, true)); |
StringBuilder str = new StringBuilder(); |
str.append("Datafile: " + dataFile + " | "); |
str.append("Cache Hits: " + cacheHit + " | "); |
str.append("Cache Misses: " + cacheMiss + " | "); |
str.append("Disk Reads: " + diskReads + " | "); |
str.append("Disk Writes: " + diskWrites + " | "); |
str.append("Time to Sort: " + time + "\n"); |
out.write(str.toString()); |
out.close(); |
} catch (IOException e) { |
e.printStackTrace(); |
} |
} |
public void printBlockIDs() { |
BufferBlock cur = bufferHead; |
System.out.print("Buffer Pool Blocks: "); |
while (cur != null && cur.getStartAddress() != -1) { |
// System.out.print(cur.getStartAddress() + " ; "); |
System.out.print(cur.getStartAddress() / blockSize + " ; "); |
cur = cur.getNext(); |
} |
System.out.print("\n"); |
} |
} |
//Classwork/CS3114/Project 4/LinkedListBlock.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/LinkedListBlock.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/LinkedListBlock.java |
---|
0,0 → 1,46 |
// Individual entries in the linked list |
public class LinkedListBlock { |
private long startAddress; // Start address of free block |
private long endAddress; // End address of free block |
private long size; // Total size of free block |
private LinkedListBlock nextBlock; // Pointer to next block in list |
private LinkedListBlock prevBlock; // Pointer to previous block in list |
// Constructor |
public LinkedListBlock(long start, long end, long size){ |
this.startAddress = start; |
this.endAddress = end; |
this.size = size; |
setNextBlock(null); |
setPrevBlock(null); |
} |
public long getStartAddress() { |
return startAddress; |
} |
public long getEndAddress() { |
return endAddress; |
} |
public long getSize() { |
return size; |
} |
public LinkedListBlock getNextBlock() { |
return nextBlock; |
} |
public void setNextBlock(LinkedListBlock nextBlock) { |
this.nextBlock = nextBlock; |
} |
public LinkedListBlock getPrevBlock() { |
return prevBlock; |
} |
public void setPrevBlock(LinkedListBlock prevBlock) { |
this.prevBlock = prevBlock; |
} |
} |
//Classwork/CS3114/Project 4/MemManager.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/MemManager.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/MemManager.java |
---|
0,0 → 1,137 |
import java.nio.ByteBuffer; |
// Memory manager that operates on the buffer pool |
public class MemManager { |
private LRUBuffer buffer; // Buffer pool interfacing to disk |
private int blockSize = 0; // Size of each block |
private long fileLength = 0; // Current length of the file |
private DoubleLinkedList emptyBlockList; // List of free blocks |
// Constructor |
public MemManager(LRUBuffer buffer, int blockSize) { |
// Initialize buffer pool and list of free blocks |
this.buffer = buffer; |
emptyBlockList = new DoubleLinkedList(); |
this.blockSize = blockSize; |
} |
// Insert a record and return its position handle. |
public Handle insert(byte[] data, int length) { |
// There are no free blocks |
if (emptyBlockList.getFirstEntry() == null) { |
// Create a new free block of size blockSize |
LinkedListBlock newEntry = new LinkedListBlock(0, blockSize - 1, blockSize); |
emptyBlockList.insert(newEntry); |
fileLength = blockSize; |
} |
// Size to insert is greater than size of largest free block |
if ((length + 1) > emptyBlockList.getFirstEntry().getSize()) { |
// Calculate how many new free blocks needs to be created to hold the byte array |
int blocks = length / blockSize; |
if (length % blockSize != 0) { |
blocks++; |
} |
for (int i = 0; i < blocks; i++) { |
// Create a new free block and insert it into the list of empty block |
LinkedListBlock newEntry = new LinkedListBlock(fileLength, fileLength + blockSize - 1, blockSize); |
emptyBlockList.insert(newEntry); |
fileLength += blockSize; |
} |
} |
// Find the first free block that can hold the byte array |
LinkedListBlock start = emptyBlockList.getFirstEntry(); |
while (start != null) { |
// Current block is last block in list, insert into current block |
if (start.getNextBlock() == null) { |
Handle newHandle = insertDataIntoMemPool(start, data, length); |
return newHandle; |
// Best fit block found, insert into current block |
} else if ((length + 1) > start.getNextBlock().getSize()) { |
Handle newHandle = insertDataIntoMemPool(start, data, length); |
return newHandle; |
} |
// Otherwise keep searching for best fit block |
start = start.getNextBlock(); |
} |
return null; |
} |
// Free a block at address. Merge adjacent blocks if appropriate. |
public void remove(Handle handle) { |
short size = getDataBlockSize(handle); |
// Needs to create a new empty block at the specified address |
LinkedListBlock newEntry = new LinkedListBlock(handle.getAddress(), handle.getAddress() + size, size + 1); |
emptyBlockList.insert(newEntry); |
} |
// Return the record with handle posHandle, up to size bytes. |
public void get(byte[] data, Handle handle) { |
// Get bytes from buffer |
buffer.getBytes(data, 0, handle.getAddress() + 1, getDataBlockSize(handle)); |
} |
// Returns the value of the first byte for the data entry (size) |
public short getDataBlockSize(Handle handle) { |
byte[] shortArr = new byte[2]; |
// Get the first byte at the address |
buffer.getBytes(shortArr, 1, handle.getAddress(), 1); |
ByteBuffer shortBuffer = ByteBuffer.wrap(shortArr); |
short size = shortBuffer.getShort(); |
return size; |
} |
// Copies the passed byte array into the buffer |
private Handle insertDataIntoMemPool(LinkedListBlock entry, byte[] data, int length) { |
// Insert the size of the array into the first byte |
byte[] size = new byte[1]; |
ByteBuffer buff = ByteBuffer.wrap(size); |
buff.put((byte)length); |
buffer.putBytes(size, 0, entry.getStartAddress(), 1); |
// Insert the array |
buffer.putBytes(data, 0, entry.getStartAddress() + 1, length); |
// Create a new free block with remaining free space |
if (entry.getSize() - (length + 1) != 0) { |
long startAddress = entry.getStartAddress() + length + 1; |
long newSize = entry.getSize() - (length + 1); |
long endAddress = startAddress + newSize - 1; |
LinkedListBlock newEntry = new LinkedListBlock(startAddress, endAddress, newSize); |
emptyBlockList.remove(entry.getStartAddress()); |
emptyBlockList.insert(newEntry); |
} else { |
emptyBlockList.remove(entry.getStartAddress()); |
LinkedListBlock newEntry = new LinkedListBlock(fileLength, fileLength + blockSize - 1, blockSize); |
emptyBlockList.insert(newEntry); |
fileLength += blockSize; |
} |
Handle newHandle = new Handle(entry.getStartAddress()); |
return newHandle; |
} |
// Dump a printout of the freeblock list |
public void dump() { |
LinkedListBlock head = emptyBlockList.getFirstEntry(); |
while (head != null) { |
System.out.printf("Empty block at address %d to %d\n", head.getStartAddress(), head.getStartAddress() + head.getSize() - 1); |
head = head.getNextBlock(); |
} |
} |
public void printBuffer() { |
buffer.printBlockIDs(); |
} |
public void clear() { |
LinkedListBlock head = emptyBlockList.getFirstEntry(); |
while (head != null) { |
emptyBlockList.remove(head.getStartAddress()); |
head = head.getNextBlock(); |
} |
LinkedListBlock newEntry = new LinkedListBlock(0, fileLength-1, fileLength); |
emptyBlockList.insert(newEntry); |
} |
} |
//Classwork/CS3114/Project 4/NodeSerializer.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/NodeSerializer.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/NodeSerializer.java |
---|
0,0 → 1,216 |
import java.nio.ByteBuffer; |
// Assisting class for converting classes to a byte array and vice versa |
public class NodeSerializer { |
private MemManager memoryManager; |
// Constructor |
public NodeSerializer(MemManager mem) { |
memoryManager = mem; |
} |
// Removes the handle and subhandles for leaf nodes (city name) |
public void removeHandle(Handle handle) { |
PRQuadTreeNode node = handleToNode(handle); |
if (node instanceof PRQuadTreeNodeFlyweight) { |
return; |
} else if (node instanceof PRQuadTreeNodeLeaf) { |
byte[] array = new byte[memoryManager.getDataBlockSize(handle)]; |
memoryManager.get(array, handle); |
ByteBuffer buffer = ByteBuffer.wrap(array); |
int records = (int)buffer.get(); |
records = (int)buffer.get(); |
for (int i = 0; i < records; i++) { |
// Remove the CityRecord and the name of the city |
int addr = buffer.getInt(); |
Handle cityhandle = new Handle(addr); |
removeCityRecordHandle(cityhandle); |
} |
} |
memoryManager.remove(handle); |
} |
public void removeCityRecordHandle(Handle handle) { |
// Remove the handle to the city name |
byte[] data = new byte[memoryManager.getDataBlockSize(handle)]; |
memoryManager.get(data, handle); |
ByteBuffer cityrecord = ByteBuffer.wrap(data); |
Handle name = new Handle(cityrecord.getInt(8)); |
memoryManager.remove(name); |
memoryManager.remove(handle); |
} |
// Resets the empty block list in the memory manager to the size of the file |
public void clearMemory() { |
memoryManager.clear(); |
} |
// Print debug info from the memory manager |
public void printDebug() { |
memoryManager.printBuffer(); |
memoryManager.dump(); |
} |
// Allocates the node onto disk and returns a handle to the node |
public Handle nodeToHandle(PRQuadTreeNode node) { |
if (node instanceof PRQuadTreeNodeInternal) { |
byte[] array = nodeInternalToByteArray((PRQuadTreeNodeInternal)node); |
Handle ret = memoryManager.insert(array, array.length); |
return ret; |
} else if (node instanceof PRQuadTreeNodeLeaf) { |
byte[] array = nodeLeafToByteArray((PRQuadTreeNodeLeaf)node); |
Handle ret = memoryManager.insert(array, array.length); |
return ret; |
} else { |
Handle ret = new Handle(-1); |
return ret; |
} |
} |
// Reads a handle off the disk and returns the corresponding |
public PRQuadTreeNode handleToNode(Handle handle) { |
if (handle.getAddress() == -1) { |
PRQuadTreeNodeFlyweight ret = new PRQuadTreeNodeFlyweight(); |
return ret; |
} else { |
byte[] array = new byte[memoryManager.getDataBlockSize(handle)]; |
memoryManager.get(array, handle); |
return byteArrayToNode(array); |
} |
} |
private byte[] stringToByteArray(String str) { |
// Use ByteBuffer to serialize to bytes |
byte[] byteArray = new byte[str.length() + 1]; |
byte[] bstr = str.getBytes(); |
ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
// Set first byte as the length |
buffer.put((byte)bstr.length); |
// Set remaining bytes as the string |
buffer.put(bstr); |
return byteArray; |
} |
private byte[] nodeInternalToByteArray(PRQuadTreeNodeInternal node) { |
byte[] byteArray = new byte[17]; |
ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
buffer.put((byte)1); |
buffer.putInt((int)node.getNW().getAddress()); |
buffer.putInt((int)node.getNE().getAddress()); |
buffer.putInt((int)node.getSW().getAddress()); |
buffer.putInt((int)node.getSE().getAddress()); |
return byteArray; |
} |
private byte[] nodeLeafToByteArray(PRQuadTreeNodeLeaf node) { |
byte[] byteArray = new byte[14]; |
ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
// Set first byte to indicate leaf node |
buffer.put((byte)0); |
// Set second byte to hold number of records |
buffer.put((byte)node.getCount()); |
CityRecord record = (CityRecord) node.getFirst(); |
buffer.putInt((int)cityRecordToHandle(record).getAddress()); |
record = (CityRecord) node.getNext(record); |
while (record != null) { |
buffer.putInt((int)cityRecordToHandle(record).getAddress()); |
record = (CityRecord) node.getNext(record); |
} |
return byteArray; |
} |
private String byteArrayToString(byte[] byteArray) { |
ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
byte[] bstr = new byte[(int)buffer.get()]; |
buffer.get(bstr); |
String str = new String(bstr); |
return str; |
} |
private PRQuadTreeNode byteArrayToNode(byte[] data) { |
ByteBuffer buffer = ByteBuffer.wrap(data); |
// Internal node |
byte b = buffer.get(); |
if (b == (byte)1) { |
PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(new Handle(-1), this); |
Handle NW = new Handle(buffer.getInt()); |
Handle NE = new Handle(buffer.getInt()); |
Handle SW = new Handle(buffer.getInt()); |
Handle SE = new Handle(buffer.getInt()); |
newNode.setNW(NW); |
newNode.setNE(NE); |
newNode.setSW(SW); |
newNode.setSE(SE); |
return newNode; |
// Leaf node |
} else if (b == (byte)0) { |
PRQuadTreeNodeLeaf newNode = new PRQuadTreeNodeLeaf(3); |
int records = (int)buffer.get(); |
for (int i = 0; i < records; i++) { |
int address = buffer.getInt(); |
Handle handle = new Handle(address); |
CityRecord record = handleToCityRecord(handle); |
newNode.insert(record); |
} |
return newNode; |
} else { |
return null; |
} |
} |
public Handle cityRecordToHandle(CityRecord record) { |
byte[] data = new byte[12]; |
ByteBuffer buffer = ByteBuffer.wrap(data); |
byte[] cityname = stringToByteArray(record.getName()); |
Handle handle = memoryManager.insert(cityname, cityname.length); |
buffer.putInt(record.getX()); |
buffer.putInt(record.getY()); |
buffer.putInt((int)handle.getAddress()); |
Handle ret = memoryManager.insert(data, 12); |
return ret; |
} |
public CityRecord handleToCityRecord(Handle handle) { |
byte[] data = new byte[12]; |
memoryManager.get(data, handle); |
ByteBuffer buffer = ByteBuffer.wrap(data); |
int x = buffer.getInt(); |
int y = buffer.getInt(); |
int addr = buffer.getInt(); |
Handle cityhandle = new Handle(addr); |
byte[] city = new byte[memoryManager.getDataBlockSize(cityhandle)]; |
memoryManager.get(city, cityhandle); |
String cityname = byteArrayToString(city); |
CityRecord record = new CityRecord(cityname, x, y); |
return record; |
} |
} |
//Classwork/CS3114/Project 4/PRQuadTree.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/PRQuadTree.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/PRQuadTree.java |
---|
0,0 → 1,289 |
import java.util.LinkedList; |
import java.lang.Math; |
// Somewhat generic implementation of a PR QuadTree |
public class PRQuadTree { |
private Handle root; |
private Handle flyweight; |
private int maxSize = 16384; // Maximum size of the grid |
NodeSerializer serializer; |
// Constructor |
public PRQuadTree(MemManager memManager) { |
serializer = new NodeSerializer(memManager); |
// Initialize a singleton flyweight object |
flyweight = new Handle(-1); |
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, 0, 0, maxSize, 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, 0, 0, maxSize, 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, 0, 0, maxSize, maxSize); |
} |
// Removes all records from the tree |
public void clear() { |
// Set root to the flyweight to remove all nodes |
root = flyweight; |
serializer.clearMemory(); |
} |
// Prints out all records from the tree as well as memory manager and buffer information |
public void printDebug() { |
System.out.printf(">> "); |
debug(root); |
System.out.printf("\n"); |
serializer.printDebug(); |
} |
// Prints out all records below the root |
public void debug(Handle root) { |
PRQuadTreeNode r = serializer.handleToNode(root); |
// If root is the flyweight ... |
if (root.getAddress() == -1) { |
System.out.printf("*"); |
// If root is a leaf ... |
} else if (r instanceof PRQuadTreeNodeLeaf) { |
Record record = ((PRQuadTreeNodeLeaf) r).getFirst(); |
do { |
System.out.printf("%d,%d,%s:", record.getX(), record.getY(), ((CityRecord) record).getName()); |
record = ((PRQuadTreeNodeLeaf) r).getNext(record); |
} while (record != null); |
System.out.printf("|"); |
// If root is an internal node ... |
} else { |
System.out.printf("("); |
debug(((PRQuadTreeNodeInternal) r).getNW()); |
debug(((PRQuadTreeNodeInternal) r).getNE()); |
debug(((PRQuadTreeNodeInternal) r).getSW()); |
debug(((PRQuadTreeNodeInternal) r).getSE()); |
System.out.printf(")"); |
} |
} |
// Returns the root of the tree |
public Handle getRoot() { |
return root; |
} |
// Recursively insert a record into a root node |
private Handle insertRecursive(Handle root, Record record, int originX, int originY, int sizeX, int sizeY) { |
PRQuadTreeNode rootNode = serializer.handleToNode(root); |
serializer.removeHandle(root); |
// If root is the flyweight, create and return a leaf node with the record |
if (root.getAddress() == -1) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
newLeaf.insert(record); |
Handle newHandle = serializer.nodeToHandle(newLeaf); |
return newHandle; |
// If root is a leaf ... |
} else if (rootNode instanceof PRQuadTreeNodeLeaf) { |
// Try to insert the record into the leaf, return leaf if successful |
if (((PRQuadTreeNodeLeaf) rootNode).insert(record)) { |
return serializer.nodeToHandle(rootNode); |
// Otherwise all nodes in the leaf are filled |
} else { |
// Create new internal node and populate it with flyweights |
PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight, serializer); |
Handle newHandle = serializer.nodeToHandle(newNode); |
// Get the first record to insert into the internal node |
Record rec = ((PRQuadTreeNodeLeaf) rootNode).getFirst(); |
do { |
// Insert every record from the full leaf into the internal node |
newHandle = insertRecursive(newHandle, rec, originX, originY, sizeX, sizeY); |
rec = ((PRQuadTreeNodeLeaf) rootNode).getNext(rec); |
} while (rec != null); |
// Now insert the initial record into the internal node |
newHandle = insertRecursive(newHandle, record, originX, originY, sizeX, sizeY); |
// Remove the old node |
// Return the newly created internal node |
return newHandle; |
} |
// If root is an internal node ... |
} else { |
// Insert the record into the correct quadrant |
if (record.getX() < originX + sizeX/2 && record.getY() < originY + sizeY/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) rootNode).setNW(insertRecursive(((PRQuadTreeNodeInternal) rootNode).getNW(), record, originX, originY, sizeX/2, sizeY/2)); |
} else if (record.getX() >= originX + sizeX/2 && record.getY() < originY + sizeY/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) rootNode).setNE(insertRecursive(((PRQuadTreeNodeInternal) rootNode).getNE(), record, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2)); |
} else if (record.getX() < originX + sizeX/2 && record.getY() >= originY + sizeY/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) rootNode).setSW(insertRecursive(((PRQuadTreeNodeInternal) rootNode).getSW(), record, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2)); |
} else if (record.getX() >= originX + sizeX/2 && record.getY() >= originY + sizeY/2) { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) rootNode).setSE(insertRecursive(((PRQuadTreeNodeInternal) rootNode).getSE(), record, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2)); |
} |
// Return the internal node after inserting a record into it |
return serializer.nodeToHandle(rootNode); |
} |
} |
// Recursively remove a record from a root node given the coordinates |
private Handle removeRecursive(Handle root, int x, int y, int originX, int originY, int sizeX, int sizeY) { |
PRQuadTreeNode rootNode = serializer.handleToNode(root); |
// If root is the flyweight, return the root |
if (root.getAddress() == -1) { |
return root; |
// If root is a leaf ... |
} else if (rootNode instanceof PRQuadTreeNodeLeaf) { |
if (((PRQuadTreeNodeLeaf) rootNode).find(x, y) != null) { |
serializer.removeHandle(root); |
((PRQuadTreeNodeLeaf) rootNode).remove(x, y); |
if (rootNode.isEmpty()) { |
return flyweight; |
} |
} |
return serializer.nodeToHandle(rootNode); |
// If root is an internal node ... |
} else { |
// Remove the record from the correct quadrant |
if (x < originX + sizeX/2 && y < originY + sizeY/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) rootNode).setNW(removeRecursive(((PRQuadTreeNodeInternal) rootNode).getNW(), x, y, originX, originY, sizeX/2, sizeY/2)); |
} else if (x >= originX + sizeX/2 && y < originY + sizeY/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) rootNode).setNE(removeRecursive(((PRQuadTreeNodeInternal) rootNode).getNE(), x, y, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2)); |
} else if (x < originX + sizeX/2 && y >= originY + sizeY/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) rootNode).setSW(removeRecursive(((PRQuadTreeNodeInternal) rootNode).getSW(), x, y, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2)); |
} else if (x >= originX + sizeX/2 && y >= originY + sizeY/2) { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) rootNode).setSE(removeRecursive(((PRQuadTreeNodeInternal) rootNode).getSE(), x, y, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2)); |
} |
// Return a flyweight if the internal node is empty after removal |
if (rootNode.isEmpty()) { |
serializer.removeHandle(root); |
return flyweight; |
// Otherwise if the internal node contains all leaves or flyweights ... |
} else if (((PRQuadTreeNodeInternal) rootNode).containsAllLeavesOrFlyweight()) { |
// If the number of records in subleaves is under 3, create and return a new leaf holding all records |
if (((PRQuadTreeNodeInternal) rootNode).countOfAllLeafNodes() <= 3) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNW())) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNW())); |
serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getNW()); |
} |
if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNE())) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNE())); |
serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getNE()); |
} |
if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSW())) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSW())); |
serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getSW()); |
} |
if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSE())) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSE())); |
serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getSE()); |
} |
// Remove the internal node |
serializer.removeHandle(root); |
// Return the new leaf that holds all records from the internal node |
return serializer.nodeToHandle(newLeaf); |
// If there are more than 3 records in subleaves, return the internal node |
} else { |
serializer.removeHandle(root); |
return serializer.nodeToHandle(rootNode); |
} |
// Otherwise return the internal node if it contains internal nodes |
} else { |
// Remove the internal node |
serializer.removeHandle(root); |
return serializer.nodeToHandle(rootNode); |
} |
} |
} |
// Recursively searches for records within radius of given coordinates |
private int searchRecursive(Handle root, int x, int y, int radius, LinkedList<Record> results, int originX, int originY, int sizeX, int sizeY) { |
PRQuadTreeNode rootNode = serializer.handleToNode(root); |
// If root is the flyweight ... |
if (root.getAddress() == -1) { |
return 1; |
// If root is a leaf ... |
} else if (rootNode instanceof PRQuadTreeNodeLeaf) { |
// Loop through each record in the leaf node |
Record record = ((PRQuadTreeNodeLeaf) rootNode).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) rootNode).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, sizeX/2.0, sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) rootNode).getNW(), x, y, radius, results, originX, originY, sizeX/2, sizeY/2); |
} |
// NE quadrant |
if (intersects(x, y, radius, sizeX - sizeX/2.0, sizeY/2.0, originX + (sizeX-1) - (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) rootNode).getNE(), x, y, radius, results, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
// SW quadrant |
if (intersects(x, y, radius, sizeX/2.0, sizeY - sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1) - (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) rootNode).getSW(), x, y, radius, results, originX, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
// SE quadrant |
if (intersects(x, y, radius, sizeX - sizeX/2.0, sizeY - sizeY/2.0, originX + (sizeX-1) - (sizeX-1)/4.0, originY + (sizeY-1) - (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) rootNode).getSE(), x, y, radius, results, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
ret++; |
return ret; |
} |
} |
// Calculates if any points in a circle intersects with a rectangle |
private boolean intersects(int cX, int cY, int cR, double rW, double rH, double rX, double rY) { |
// Reference: http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection/402010#402010 |
// Distance from center of circle to center of rectangle |
double xCircleDistance = Math.abs(cX - rX); |
double 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 |
double cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) + |
(yCircleDistance - rH/2) * (yCircleDistance - rH/2); |
return (cornerDist <= cR * cR); |
} |
} |
//Classwork/CS3114/Project 4/PRQuadTreeNode.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/PRQuadTreeNode.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/PRQuadTreeNode.java |
---|
0,0 → 1,5 |
// Interface for a generic PRQuadTree node |
public interface PRQuadTreeNode { |
public boolean isEmpty(); |
} |
//Classwork/CS3114/Project 4/PRQuadTreeNodeFlyweight.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/PRQuadTreeNodeFlyweight.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/PRQuadTreeNodeFlyweight.java |
---|
0,0 → 1,7 |
public class PRQuadTreeNodeFlyweight implements PRQuadTreeNode { |
public boolean isEmpty() { |
return true; |
} |
} |
//Classwork/CS3114/Project 4/PRQuadTreeNodeInternal.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/PRQuadTreeNodeInternal.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/PRQuadTreeNodeInternal.java |
---|
0,0 → 1,84 |
// Internal node for the PRQuadTree |
public class PRQuadTreeNodeInternal implements PRQuadTreeNode { |
// Node in each quadrant |
private Handle NW; |
private Handle NE; |
private Handle SW; |
private Handle SE; |
private Handle flyweight; |
private NodeSerializer serializer; |
// Constructor to initialize the node with flyweights |
public PRQuadTreeNodeInternal(Handle flyweight, NodeSerializer mem) { |
serializer = mem; |
// 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 (serializer.handleToNode(NW) instanceof PRQuadTreeNodeLeaf || serializer.handleToNode(NW) instanceof PRQuadTreeNodeFlyweight) && |
(serializer.handleToNode(NE) instanceof PRQuadTreeNodeLeaf || serializer.handleToNode(NE) instanceof PRQuadTreeNodeFlyweight) && |
(serializer.handleToNode(SW) instanceof PRQuadTreeNodeLeaf || serializer.handleToNode(SW) instanceof PRQuadTreeNodeFlyweight) && |
(serializer.handleToNode(SE) instanceof PRQuadTreeNodeLeaf || serializer.handleToNode(SE) instanceof PRQuadTreeNodeFlyweight); |
} |
// Returns the number of all records in all subleaves |
public int countOfAllLeafNodes() { |
int ret = 0; |
if (serializer.handleToNode(NW) instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) serializer.handleToNode(NW)).getCount(); |
if (serializer.handleToNode(NE) instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) serializer.handleToNode(NE)).getCount(); |
if (serializer.handleToNode(SW) instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) serializer.handleToNode(SW)).getCount(); |
if (serializer.handleToNode(SE) instanceof PRQuadTreeNodeLeaf) |
ret += ((PRQuadTreeNodeLeaf) serializer.handleToNode(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 Handle getNW() { |
return NW; |
} |
public void setNW(Handle nW) { |
NW = nW; |
} |
public Handle getNE() { |
return NE; |
} |
public void setNE(Handle nE) { |
NE = nE; |
} |
public Handle getSW() { |
return SW; |
} |
public void setSW(Handle sW) { |
SW = sW; |
} |
public Handle getSE() { |
return SE; |
} |
public void setSE(Handle sE) { |
SE = sE; |
} |
} |
//Classwork/CS3114/Project 4/PRQuadTreeNodeLeaf.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/PRQuadTreeNodeLeaf.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/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/Project 4/Record.class |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/Record.class |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
//Classwork/CS3114/Project 4/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/Project 4/Schedule.xls |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
//Classwork/CS3114/Project 4/Schedule.xls |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |