Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /Classwork/CS3114 - Data Algorithms/Project 4 @ 96

  → /Classwork/CS3114 - Data Algorithms/Project 4 @ 105

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

No changes between revisions

Ignore whitespace Rev 96 → Rev 105

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/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 - Data Algorithms/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 - Data Algorithms/Project 4/BSTree.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/BSTree.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/BSTreeNode.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/BSTreeNode.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/Bindisk.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/Bindisk.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/BufferBlock.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/BufferBlock.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/CityRecord.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/CityRecord.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/CmdParser.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/CmdParser.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/Dictionary.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/Dictionary.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/DoubleLinkedList.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/DoubleLinkedList.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/Handle.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/Handle.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/LRUBuffer.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/LRUBuffer.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/LinkedListBlock.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/LinkedListBlock.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/MemManager.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/MemManager.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/NodeSerializer.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/NodeSerializer.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/PRQuadTree.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTree.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/PRQuadTreeNode.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNode.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNode.java
0,0 → 1,5
// Interface for a generic PRQuadTree node
public interface PRQuadTreeNode {
public boolean isEmpty();
}

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeFlyweight.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeFlyweight.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeFlyweight.java
0,0 → 1,7
public class PRQuadTreeNodeFlyweight implements PRQuadTreeNode {
public boolean isEmpty() {
return true;
}
}

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeInternal.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeInternal.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/PRQuadTreeNodeLeaf.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/PRQuadTreeNodeLeaf.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/Record.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/Record.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property

/Classwork/CS3114 - Data Algorithms/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 - Data Algorithms/Project 4/Schedule.xls
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

/Classwork/CS3114 - Data Algorithms/Project 4/Schedule.xls
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property