| /Classwork/CS3114/GIS/.classpath |
|---|
| 0,0 → 1,6 |
| <?xml version="1.0" encoding="UTF-8"?> |
| <classpath> |
| <classpathentry kind="src" path=""/> |
| <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/> |
| <classpathentry kind="output" path=""/> |
| </classpath> |
| /Classwork/CS3114/GIS/.project |
|---|
| 0,0 → 1,17 |
| <?xml version="1.0" encoding="UTF-8"?> |
| <projectDescription> |
| <name>CS3114P2</name> |
| <comment></comment> |
| <projects> |
| </projects> |
| <buildSpec> |
| <buildCommand> |
| <name>org.eclipse.jdt.core.javabuilder</name> |
| <arguments> |
| </arguments> |
| </buildCommand> |
| </buildSpec> |
| <natures> |
| <nature>org.eclipse.jdt.core.javanature</nature> |
| </natures> |
| </projectDescription> |
| /Classwork/CS3114/GIS/.settings/org.eclipse.jdt.core.prefs |
|---|
| 0,0 → 1,12 |
| #Mon Oct 03 14:51:02 EDT 2011 |
| eclipse.preferences.version=1 |
| org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled |
| org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6 |
| org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve |
| org.eclipse.jdt.core.compiler.compliance=1.6 |
| org.eclipse.jdt.core.compiler.debug.lineNumber=generate |
| org.eclipse.jdt.core.compiler.debug.localVariable=generate |
| org.eclipse.jdt.core.compiler.debug.sourceFile=generate |
| org.eclipse.jdt.core.compiler.problem.assertIdentifier=error |
| org.eclipse.jdt.core.compiler.problem.enumIdentifier=error |
| org.eclipse.jdt.core.compiler.source=1.6 |
| /Classwork/CS3114/GIS/BSTree.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/BSTree.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/BSTree.java |
|---|
| 0,0 → 1,161 |
| import java.util.ArrayList; |
| // Generic BST implementation |
| public class BSTree<K extends Comparable<? super K>, E> implements Dictionary<K, E> { |
| private BSTreeNode<K,E> root; // Root of the BST |
| // Constructor |
| public BSTree() { |
| this.root = null; |
| } |
| // Inserts a node into the BST |
| public void insert(K key, E element) { |
| // Set the BST root as the returned node |
| this.root = insertRecursive(root, key, element); |
| } |
| // Removes a node from the BST given the key |
| public void remove(K key) { |
| // Adds invalid coordinates if none are specified |
| this.remove(key, -1, -1); |
| } |
| public void remove(K key, int x, int y) { |
| // Check if node exists |
| E temp = findRecursive(root, key); |
| if (temp != null) { |
| // Remove the node |
| this.root = removeRecursive(root, key, x, y); |
| } |
| } |
| // Returns a node from the BST given the key |
| public E find(K key) { |
| return findRecursive(root, key); |
| } |
| // Returns a list of all nodes with the given key |
| public ArrayList<E> findAll(K key) { |
| ArrayList<E> elementList = new ArrayList<E>(); |
| findAllRecursive(root, key, elementList); |
| return elementList; |
| } |
| // Removes all nodes from the BST |
| public void clear() { |
| this.root = null; |
| } |
| // Recursively inserts a node into the BST |
| private BSTreeNode<K,E> insertRecursive(BSTreeNode<K,E> root, K key, E element) { |
| if (root == null) |
| // If there are no nodes in the BST, create and return a new node |
| return new BSTreeNode<K,E>(key, element); |
| if (root.getKey().compareTo(key) > 0) |
| // If passed key is smaller, insert into left child |
| root.setLeft(insertRecursive(root.getLeft(), key, element)); |
| else |
| // If passed key is greater, insert into right child |
| root.setRight(insertRecursive(root.getRight(), key, element)); |
| return root; |
| } |
| // Recursively searches minimal nodes for matches to the given key |
| private E findRecursive(BSTreeNode<K,E> root, K key) { |
| if (root == null) |
| return null; |
| if (root.getKey().compareTo(key) > 0) |
| // If passed key is smaller, search the left child |
| return findRecursive(root.getLeft(), key); |
| else if (root.getKey().compareTo(key) == 0) |
| // If key is found, return with the found element |
| return root.getElement(); |
| else |
| // If key is not found, search the right child |
| return findRecursive(root.getRight(), key); |
| } |
| // Recursively searches all nodes for matches to the given key |
| private void findAllRecursive(BSTreeNode<K,E> root, K key, ArrayList<E> elementList) { |
| if (root == null) |
| return; |
| // If key matches, save to list |
| if (root.getKey().compareTo(key) == 0) |
| elementList.add(root.getElement()); |
| // Recursively call search on all possible nodes |
| if (root.getKey().compareTo(key) > 0) |
| findAllRecursive(root.getLeft(), key, elementList); |
| else |
| findAllRecursive(root.getRight(), key, elementList); |
| } |
| // Recursively removes a node from the BST given a key |
| private BSTreeNode<K,E> removeRecursive(BSTreeNode<K,E> root, K key, int x, int y) { |
| if (root == null) |
| return null; |
| // Find the node to remove |
| if (root.getKey().compareTo(key) > 0) |
| root.setLeft(removeRecursive(root.getLeft(), key, x, y)); |
| else if (root.getKey().compareTo(key) < 0) |
| root.setRight(removeRecursive(root.getRight(), key, x, y)); |
| // Node's key matches |
| else { |
| // If we want to narrow it down by coordinates as well |
| if (x >= 0 && y >= 0) { |
| // If coordinates do not match, keep searching from the right child |
| if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) { |
| root.setRight(removeRecursive(root.getRight(), key, x, y)); |
| } else { |
| // If one of the leaves is null, just return the other leaf |
| if (root.getLeft() == null) |
| return root.getRight(); |
| else if (root.getRight() == null) |
| return root.getLeft(); |
| else { |
| // Otherwise create a new node with the smallest value on the right leaf |
| BSTreeNode<K,E> temp = getMin(root.getRight()); |
| root.setElement(temp.getElement()); |
| root.setKey(temp.getKey()); |
| root.setRight(deleteMin(root.getRight())); |
| } |
| } |
| // Otherwise just remove the node |
| } else { |
| // If one of the leaves is null, just return the other leaf |
| if (root.getLeft() == null) |
| return root.getRight(); |
| else if (root.getRight() == null) |
| return root.getLeft(); |
| else { |
| // Otherwise create a new node with the smallest value on the right leaf |
| BSTreeNode<K,E> temp = getMin(root.getRight()); |
| root.setElement(temp.getElement()); |
| root.setKey(temp.getKey()); |
| root.setRight(deleteMin(root.getRight())); |
| } |
| } |
| } |
| return root; |
| } |
| // Recursively returns the minimum key node |
| private BSTreeNode<K,E> getMin(BSTreeNode<K,E> root) { |
| if (root.getLeft() == null) |
| return root; |
| else |
| return getMin(root.getLeft()); |
| } |
| // Recursively deletes the minimum key node |
| private BSTreeNode<K,E> deleteMin(BSTreeNode<K,E> root) { |
| if (root.getLeft() == null) |
| return root.getRight(); |
| else { |
| root.setLeft(deleteMin(root.getLeft())); |
| return root; |
| } |
| } |
| } |
| /Classwork/CS3114/GIS/BSTreeNode.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/BSTreeNode.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/BSTreeNode.java |
|---|
| 0,0 → 1,60 |
| // Single generic node for the BSTree |
| public class BSTreeNode<K,E> { |
| private K key; // Key |
| private E element; // Value |
| private BSTreeNode<K,E> left; // Left child |
| private BSTreeNode<K,E> right; // Right child |
| // Empty constructor |
| public BSTreeNode() { |
| setLeft(setRight(null)); |
| } |
| // Constructor given key value pair |
| public BSTreeNode(K k, E e) { |
| setLeft(setRight(null)); |
| setKey(k); |
| setElement(e); |
| } |
| // Constructor given key value pair and children |
| public BSTreeNode(K k, E e, BSTreeNode<K,E> left, BSTreeNode<K,E> right) { |
| setKey(k); |
| setElement(e); |
| this.setLeft(left); |
| this.setRight(right); |
| } |
| // Query if node has leaves |
| public boolean isLeaf() { |
| return left == null && right == null; |
| } |
| // Encapsulation methods |
| public K getKey() { |
| return key; |
| } |
| public void setKey(K key) { |
| this.key = key; |
| } |
| public E getElement() { |
| return element; |
| } |
| public void setElement(E element) { |
| this.element = element; |
| } |
| public BSTreeNode<K,E> getLeft() { |
| return left; |
| } |
| public void setLeft(BSTreeNode<K,E> left) { |
| this.left = left; |
| } |
| public BSTreeNode<K,E> getRight() { |
| return right; |
| } |
| public BSTreeNode<K,E> setRight(BSTreeNode<K,E> right) { |
| this.right = right; |
| return right; |
| } |
| } |
| /Classwork/CS3114/GIS/CityRecord.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/CityRecord.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/CityRecord.java |
|---|
| 0,0 → 1,25 |
| // Specific implementation of CityRecord that stores coordinates and a city name |
| public class CityRecord implements Record { |
| private String name; // City name |
| private int x; // X-coordinate |
| private int y; // Y-coordinate |
| // Constructor initializing a new CityRecord |
| public CityRecord(String name, int x, int y) { |
| this.x = x; |
| this.y = y; |
| this.name = name; |
| } |
| // Encapsulation methods |
| public String getName() { |
| return name; |
| } |
| public int getX() { |
| return x; |
| } |
| public int getY() { |
| return y; |
| } |
| } |
| /Classwork/CS3114/GIS/CmdParser.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/CmdParser.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/CmdParser.java |
|---|
| 0,0 → 1,200 |
| import java.util.ArrayList; |
| import java.util.LinkedList; |
| // Class to parse a specific set of commands |
| public class CmdParser { |
| BSTree<String, CityRecord> GISTree; // Binary Search Tree |
| PRQuadTree CTree; // PR QuadTree |
| public CmdParser() { |
| // Initialize BSTree and PRQuadTree |
| GISTree = new BSTree<String, CityRecord>(); |
| CTree = new PRQuadTree(); |
| } |
| // Calls specific functions depending on input |
| public void Parse(String input) { |
| // Split the passed line into tokens |
| String delim = "[ ]+"; |
| String[] tokens = input.split(delim); |
| // Echo the command to the output |
| for (String token : tokens) { |
| System.out.printf(token + " "); |
| } |
| System.out.printf("\n"); |
| // Parse tokens to determine what action to take |
| if (tokens[0].compareToIgnoreCase("insert") == 0) { |
| Cmd_Insert(tokens); |
| } else if (tokens[0].compareToIgnoreCase("remove") == 0) { |
| Cmd_Remove(tokens); |
| } else if (tokens[0].compareToIgnoreCase("find") == 0) { |
| Cmd_Find(tokens); |
| } else if (tokens[0].compareToIgnoreCase("search") == 0) { |
| Cmd_Search(tokens); |
| } else if (tokens[0].compareToIgnoreCase("debug") == 0) { |
| Cmd_Debug(); |
| } else if (tokens[0].compareToIgnoreCase("makenull") == 0) { |
| Cmd_Makenull(); |
| } else { |
| System.out.printf(">> \"%s\" command is not supported\n", tokens[0]); |
| } |
| System.out.printf("\n"); |
| } |
| // Parse insert command |
| private void Cmd_Insert(String[] tokens) { |
| // Check to make sure there is a correct number of arguments for the command |
| if (tokens.length != 4) { |
| System.out.printf(">> Arguments must be in format \"insert x y name\"\n"); |
| } else { |
| try { |
| // Parse and check each argument token |
| int x = Integer.parseInt(tokens[1]); |
| int y = Integer.parseInt(tokens[2]); |
| String name = tokens[3]; |
| if (x < 0 || x > 16383 || y < 0 || y > 16383) { |
| System.out.printf(">> Insert failed: Coordinate values out of range\n"); |
| } else { |
| // If all arguments are ok, create a new record with the specified values |
| CityRecord newRecord = new CityRecord(name, x, y); |
| // Check if record with same coordinates already exists |
| LinkedList<Record> list = new LinkedList<Record>(); |
| CTree.search(x, y, 0, list); |
| if (list.size() != 0) { |
| System.out.printf(">> Insert failed: City at (%d,%d) already exists\n", x, y); |
| } else { |
| // Insert record into both trees |
| System.out.printf(">> Inserting city %s (%d,%d)\n", name, x, y); |
| GISTree.insert(name, newRecord); |
| CTree.insert(newRecord); |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf(">> Insert failed: Unable to parse given coordinates\n"); |
| } |
| } |
| } |
| // Parse remove command |
| private void Cmd_Remove(String[] tokens) { |
| // Check to make sure there is a correct number of arguments for the command |
| if (tokens.length < 2 || tokens.length > 3) { |
| System.out.printf(">> Arguments must be in format \"remove x y\" or \" remove name\"\n"); |
| } else { |
| // A single argument means search by name |
| if (tokens.length == 2) { |
| String name = tokens[1]; |
| // First check if city exists |
| CityRecord record = GISTree.find(name); |
| if (record != null) { |
| // Remove city if found |
| System.out.printf(">> Removing city %s (%d,%d)\n", |
| record.getName(), record.getX(), record.getY()); |
| GISTree.remove(name, record.getX(), record.getY()); |
| CTree.remove(record.getX(), record.getY()); |
| } else { |
| System.out.printf(">> Remove failed: City %s not found\n", name); |
| } |
| // Otherwise search by coordinates |
| } else { |
| try { |
| // Parse and check each argument token |
| int x = Integer.parseInt(tokens[1]); |
| int y = Integer.parseInt(tokens[2]); |
| if (x < 0 || x > 16383 || y < 0 || y > 16383) { |
| System.out.printf(">> Remove failed: Coordinate values out of range\n"); |
| } else { |
| // Check if city with coordinates exists |
| LinkedList<Record> list = new LinkedList<Record>(); |
| CTree.search(x, y, 0, list); |
| if (list.size() == 0) { |
| System.out.printf(">> Remove failed: City with coordinates (%d,%d) not found\n", x, y); |
| } else { |
| // Remove using coordinates |
| System.out.printf(">> Removing city %s (%d,%d)\n", |
| ((CityRecord)list.get(0)).getName(), list.get(0).getX(), list.get(0).getY()); |
| CTree.remove(x, y); |
| GISTree.remove(((CityRecord)list.get(0)).getName(), x, y); |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf(">> Remove failed: Unable to parse given coordinates\n"); |
| } |
| } |
| } |
| } |
| // Parse find command |
| private void Cmd_Find(String[] tokens) { |
| // Check to make sure there is a correct number of arguments for the command |
| if (tokens.length != 2) { |
| System.out.printf(">> Arguments must be in format \"find name\"\n"); |
| } else { |
| String name = tokens[1]; |
| // Get all records with the matching name |
| ArrayList<CityRecord> records = GISTree.findAll(name); |
| if (records.size() != 0) { |
| // For each city found, print the city details |
| for (CityRecord record : records) { |
| System.out.printf(">> City found: %s (%d,%d)\n", |
| record.getName(), record.getX(), record.getY()); |
| } |
| } else { |
| System.out.printf(">> Find failed: City %s not found\n", name); |
| } |
| } |
| } |
| // Parse search command |
| private void Cmd_Search(String[] tokens) { |
| // Check to make sure there is a correct number of arguments for the command |
| if (tokens.length != 4) { |
| System.out.printf(">> Arguments must be in format \"search x y radius\"\n"); |
| } else { |
| try { |
| // Parse and check each argument token |
| int x = Integer.parseInt(tokens[1]); |
| int y = Integer.parseInt(tokens[2]); |
| int r = Integer.parseInt(tokens[3]); |
| if (r < 0 || r > 16383) { |
| System.out.printf(">> Search failed: Radius value out of range\n"); |
| } else if (x < -16383 || x > 16383 || y < -16383 || y > 16383) { |
| System.out.printf(">> Search failed: Coordinate values out of range\n"); |
| } else { |
| // Get a list of all cities found within specified radius of point |
| LinkedList<Record> results = new LinkedList<Record>(); |
| int nodesLookedAt = CTree.search(x, y, r, results); |
| System.out.printf(">> %d nodes visited:\n", nodesLookedAt); |
| if (results.size() == 0) { |
| System.out.printf(">> No records found with specified coordinates\n"); |
| } else { |
| // Print the found cities |
| for (Record record : results) { |
| System.out.printf(">> %s (%d,%d)\n", ((CityRecord)record).getName(), record.getX(), record.getY()); |
| } |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf(">> Search failed: Unable to parse given coordinates\n"); |
| } |
| } |
| } |
| // Parse debug command |
| private void Cmd_Debug() { |
| System.out.printf(">> "); |
| CTree.debug(CTree.getRoot()); |
| System.out.printf("\n"); |
| } |
| // Parse makenull command |
| private void Cmd_Makenull() { |
| GISTree.clear(); |
| CTree.clear(); |
| System.out.printf(">> Makenull successful\n"); |
| } |
| } |
| /Classwork/CS3114/GIS/Dictionary.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/Dictionary.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/Dictionary.java |
|---|
| 0,0 → 1,10 |
| import java.util.ArrayList; |
| // Generic dictionary interface |
| public interface Dictionary<Key, Element> { |
| public void insert(Key k, Element e); |
| public void clear(); |
| public void remove(Key k); |
| public Element find(Key k); |
| public ArrayList<Element> findAll(Key k); |
| } |
| /Classwork/CS3114/GIS/P2.pdf |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/P2.pdf |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRProg.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRProg.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRProg.java |
|---|
| 0,0 → 1,86 |
| /* |
| * CS 3114 Project 2 |
| * Author: Kevin Lee |
| * Compiler: Eclipse 3.7.0 |
| * Operating System: Windows 7 x64 |
| * Date Completed: 10/7/2011 |
| * |
| * The following program is an implementation of two different |
| * trees that allows for efficient storing of records with |
| * coordinates. A binary search tree is used to allow for |
| * efficient search by name, while a point region quad tree is |
| * used to allow for efficient search by coordinates. The |
| * program parses an input file for commands, and outputs the |
| * results to standard out. |
| * |
| * On my honor: |
| * |
| * - I have not used source code obtained from another student, |
| * or any other unauthorized source, either modified or |
| * unmodified. |
| * |
| * - All source code and documentation used in my program is |
| * either my original work, or was derived by me from the |
| * source code published in the textbook for this course. |
| * |
| * - I have not discussed coding details about this project with |
| * anyone other than my partner (in the case of a joint |
| * submission), instructor, ACM/UPE tutors or the TAs assigned |
| * to this course. I understand that I may discuss the concepts |
| * of this program with other students, and that another student |
| * may help me debug my program so long as neither of us writes |
| * anything during the discussion or modifies any computer file |
| * during the discussion. I have violated neither the spirit nor |
| * letter of this restriction. |
| */ |
| import java.io.BufferedReader; |
| import java.io.File; |
| import java.io.FileNotFoundException; |
| import java.io.FileReader; |
| import java.io.IOException; |
| public class PRProg { |
| public static void main(String[] args) { |
| String input_commandFile; // Location of file to parse |
| // 3 arguments must be supplied to the program |
| if (args.length != 1) { |
| System.out.println("1 Arguments must be supplied!"); |
| return; |
| } |
| // Parses passed arguments into member variables |
| input_commandFile = args[0]; |
| // Check to make sure the command file exists |
| File cmdFile = new File(input_commandFile); |
| if (!cmdFile.exists()) { |
| System.out.printf("Command file not found"); |
| return; |
| } |
| CmdParser GISParser = new CmdParser(); |
| // Parse each command with the memory client |
| try { |
| BufferedReader reader = new BufferedReader(new FileReader(cmdFile)); |
| String cin; |
| while ((cin = reader.readLine()) != null) { |
| cin = cin.trim(); |
| if (cin.length() != 0) { |
| // Send string to command parser |
| GISParser.Parse(cin); |
| } |
| } |
| } catch (FileNotFoundException e) { |
| System.out.printf("Command file not found"); |
| return; |
| } catch (IOException e) { |
| System.out.printf("Unable to read input file"); |
| return; |
| } |
| } |
| } |
| /Classwork/CS3114/GIS/PRQuadTree.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRQuadTree.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRQuadTree.java |
|---|
| 0,0 → 1,257 |
| import java.util.LinkedList; |
| import java.lang.Math; |
| // Somewhat generic implementation of a PR QuadTree |
| public class PRQuadTree { |
| private PRQuadTreeNode root; // Root of the PR QuadTree |
| private PRQuadTreeNodeFlyweight flyweight; // Flyweight representing empty nodes |
| private int maxSize = 16384; // Maximum size of the grid |
| // Constructor |
| public PRQuadTree() { |
| // Initialize a singleton flyweight object |
| flyweight = new PRQuadTreeNodeFlyweight(); |
| root = flyweight; |
| } |
| // Inserts given record into the tree |
| public void insert(Record record) { |
| // Recursively call function to insert a record |
| this.root = insertRecursive(root, record, maxSize); |
| } |
| // Removes a record from the tree given a set of coordinates |
| public void remove(int x, int y) { |
| // Recursively call function to remove a record |
| this.root = removeRecursive(root, x, y, maxSize); |
| } |
| // Searches for all records within radius and returns the results in the passed list |
| public int search(int x, int y, int r, LinkedList<Record> results) { |
| // Searches for all cities in radius of given point |
| // Number of nodes looked at is returned while list of cities is stored in 'list' |
| return searchRecursive(root, x, y, r, results, maxSize); |
| } |
| // Removes all records from the tree |
| public void clear() { |
| // Set root to the flyweight to remove all nodes |
| root = flyweight; |
| } |
| // Prints out all records from the tree |
| public void debug(PRQuadTreeNode root) { |
| // If root is the flyweight ... |
| if (root == flyweight) { |
| System.out.printf("E"); |
| // If root is a leaf ... |
| } else if (root instanceof PRQuadTreeNodeLeaf) { |
| Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
| do { |
| System.out.printf("%d,%d,%s", record.getX(), record.getY(), ((CityRecord) record).getName()); |
| record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
| } while (record != null); |
| System.out.printf("|"); |
| // If root is an internal node ... |
| } else { |
| System.out.printf("I"); |
| debug(((PRQuadTreeNodeInternal) root).getNW()); |
| debug(((PRQuadTreeNodeInternal) root).getNE()); |
| debug(((PRQuadTreeNodeInternal) root).getSW()); |
| debug(((PRQuadTreeNodeInternal) root).getSE()); |
| } |
| } |
| // Returns the root of the tree |
| public PRQuadTreeNode getRoot() { |
| return root; |
| } |
| // Recursively insert a record into a root node |
| private PRQuadTreeNode insertRecursive(PRQuadTreeNode root, Record record, int size) { |
| // If root is the flyweight, create and return a leaf node with the record |
| if (root == flyweight) { |
| PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
| newLeaf.insert(record); |
| return newLeaf; |
| // If root is a leaf ... |
| } else if (root instanceof PRQuadTreeNodeLeaf) { |
| // Try to insert the record into the leaf, return leaf if successful |
| if (((PRQuadTreeNodeLeaf) root).insert(record)) { |
| return root; |
| // Otherwise all nodes in the leaf are filled |
| } else { |
| // Create new internal node and populate it with flyweights |
| PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight); |
| // Get the first record to insert into the internal node |
| Record rec = ((PRQuadTreeNodeLeaf) root).getFirst(); |
| do { |
| // Insert every record from the full leaf into the internal node |
| newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, rec, size); |
| } while ((rec = ((PRQuadTreeNodeLeaf) root).getNext(rec)) != null); |
| // Now insert the initial record into the internal node |
| newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, record, size); |
| // Return the newly created internal node |
| return newNode; |
| } |
| // If root is an internal node ... |
| } else { |
| // Insert the record into the correct quadrant |
| if (record.getX() < size/2 && record.getY() < size/2) { |
| // Insert into NW quadrant |
| ((PRQuadTreeNodeInternal) root).setNW(insertRecursive(((PRQuadTreeNodeInternal) root).getNW(), record, size/2)); |
| } else if (record.getX() >= size/2 && record.getY() < size/2) { |
| // Insert into NE quadrant |
| ((PRQuadTreeNodeInternal) root).setNE(insertRecursive(((PRQuadTreeNodeInternal) root).getNE(), record, size/2)); |
| } else if (record.getX() < size/2 && record.getY() >= size/2) { |
| // Insert into SW quadrant |
| ((PRQuadTreeNodeInternal) root).setSW(insertRecursive(((PRQuadTreeNodeInternal) root).getSW(), record, size/2)); |
| } else { |
| // Insert into SE quadrant |
| ((PRQuadTreeNodeInternal) root).setSE(insertRecursive(((PRQuadTreeNodeInternal) root).getSE(), record, size/2)); |
| } |
| // Return the internal node after inserting a record into it |
| return root; |
| } |
| } |
| // Recursively remove a record from a root node given the coordinates |
| private PRQuadTreeNode removeRecursive(PRQuadTreeNode root, int x, int y, int size) { |
| // If root is the flyweight, return the root |
| if (root == flyweight) { |
| return root; |
| // If root is a leaf ... |
| } else if (root instanceof PRQuadTreeNodeLeaf) { |
| // Try to remove element from the leaf |
| ((PRQuadTreeNodeLeaf) root).remove(x, y); |
| // If the leaf is empty, return the flyweight |
| if (root.isEmpty()) |
| return flyweight; |
| else |
| return root; |
| // If root is an internal node ... |
| } else { |
| // Remove the record from the correct quadrant |
| if (x < size/2 && y < size/2) { |
| // Insert into NW quadrant |
| ((PRQuadTreeNodeInternal) root).setNW(removeRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, size/2)); |
| } else if (x >= size/2 && y < size/2) { |
| // Insert into NE quadrant |
| ((PRQuadTreeNodeInternal) root).setNE(removeRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, size/2)); |
| } else if (x < size/2 && y >= size/2) { |
| // Insert into SW quadrant |
| ((PRQuadTreeNodeInternal) root).setSW(removeRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, size/2)); |
| } else { |
| // Insert into SE quadrant |
| ((PRQuadTreeNodeInternal) root).setSE(removeRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, size/2)); |
| } |
| // Return a flyweight if the internal node is empty after removal |
| if (root.isEmpty()) { |
| return flyweight; |
| // Otherwise if the internal node contains all leaves or flyweights ... |
| } else if (((PRQuadTreeNodeInternal) root).containsAllLeavesOrFlyweight()) { |
| // If the number of records in subleaves is under 3, create and return a new leaf holding all records |
| if (((PRQuadTreeNodeInternal) root).countOfAllLeafNodes() <= 3) { |
| PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
| if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNW()) != 0) { |
| newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNW()); |
| } |
| if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNE()) != 0) { |
| newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNE()); |
| } |
| if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSW()) != 0) { |
| newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSW()); |
| } |
| if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSE()) != 0) { |
| newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSE()); |
| } |
| // Return the new leaf that holds all records from the internal node |
| return newLeaf; |
| // If there are more than 3 records in subleaves, return the internal node |
| } else { |
| return root; |
| } |
| // Otherwise return the internal node if it contains internal nodes |
| } else { |
| return root; |
| } |
| } |
| } |
| // Recursively searches for records within radius of given coordinates |
| private int searchRecursive(PRQuadTreeNode root, int x, int y, int radius, LinkedList<Record> results, int size) { |
| // If root is the flyweight ... |
| if (root == flyweight) { |
| return 1; |
| // If root is a leaf ... |
| } else if (root instanceof PRQuadTreeNodeLeaf) { |
| // Loop through each record in the leaf node |
| Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
| do { // Note: the first record can never be null (else it'll be a flyweight) |
| // Check each record to see if it lies within the specified radius of the point |
| if ((x - record.getX()) * (x - record.getX()) + |
| (y - record.getY()) * (y - record.getY()) <= radius * radius) { |
| // If it is, add it to the list |
| results.add(record); |
| } |
| record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
| } while (record != null); |
| // Return the number of nodes looked at (1, this node) |
| return 1; |
| // If root is an internal node ... |
| } else { |
| int ret = 0; |
| // Check each quadrant to see if any intersect with the circle/radius |
| // NW quadrant |
| if (intersects(x, y, radius, size/2, size/2, size/4, size/4)) { |
| ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, radius, results, size/2); |
| } |
| // NE quadrant |
| if (intersects(x, y, radius, size/2, size/2, size/4 + size/2, size/4)) { |
| ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, radius, results, size/2); |
| } |
| // SW quadrant |
| if (intersects(x, y, radius, size/2, size/2, size/4, size/4 + size/2)) { |
| ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, radius, results, size/2); |
| } |
| // SE quadrant |
| if (intersects(x, y, radius, size/2, size/2, size/4 + size/2, size/4 + size/2)) { |
| ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, radius, results, size/2); |
| } |
| ret++; |
| return ret; |
| } |
| } |
| // Calculates if any points in a circle intersects with a rectangle |
| private boolean intersects(int cX, int cY, int cR, int rW, int rH, int rX, int rY) { |
| // Reference: http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection/402010#402010 |
| // Distance from center of circle to center of rectangle |
| int xCircleDistance = Math.abs(cX - rX); |
| int yCircleDistance = Math.abs(cY - rY); |
| // If Distance > width of rectangle + radius, circle cannot overlap rectangle |
| if (xCircleDistance > (rW/2 + cR)) { |
| return false; |
| } |
| if (yCircleDistance > (rH/2 + cR)) { |
| return false; |
| } |
| // If distance <= width of rectangle, circle must overlap rectangle |
| if (xCircleDistance <= (rW/2)) { |
| return true; |
| } |
| if (yCircleDistance <= (rH/2)) { |
| return true; |
| } |
| // Check for overlap on corners |
| int cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) + |
| (yCircleDistance - rH/2) * (yCircleDistance - rH/2); |
| return (cornerDist <= cR * cR); |
| } |
| } |
| /Classwork/CS3114/GIS/PRQuadTreeNode.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRQuadTreeNode.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRQuadTreeNode.java |
|---|
| 0,0 → 1,5 |
| // Interface for a generic PRQuadTree node |
| public interface PRQuadTreeNode { |
| public boolean isEmpty(); |
| } |
| /Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRQuadTreeNodeFlyweight.java |
|---|
| 0,0 → 1,7 |
| public class PRQuadTreeNodeFlyweight implements PRQuadTreeNode { |
| public boolean isEmpty() { |
| return true; |
| } |
| } |
| /Classwork/CS3114/GIS/PRQuadTreeNodeInternal.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRQuadTreeNodeInternal.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRQuadTreeNodeInternal.java |
|---|
| 0,0 → 1,79 |
| // Internal node for the PRQuadTree |
| public class PRQuadTreeNodeInternal implements PRQuadTreeNode { |
| private PRQuadTreeNode NW; // Node in each quadrant |
| private PRQuadTreeNode NE; |
| private PRQuadTreeNode SW; |
| private PRQuadTreeNode SE; |
| private PRQuadTreeNodeFlyweight flyweight; // Flyweight |
| // Constructor to initialize the node with flyweights |
| public PRQuadTreeNodeInternal(PRQuadTreeNodeFlyweight flyweight) { |
| // Initialize all subnodes with the flyweight |
| NW = NE = SW = SE = flyweight; |
| this.flyweight = flyweight; |
| } |
| // Queries if all subnodes are flyweights |
| public boolean isEmpty() { |
| return (NW == flyweight)&&(NE == flyweight)&& |
| (SW == flyweight)&&(SE == flyweight); |
| } |
| // Test if node contains other internal nodes |
| public boolean containsAllLeavesOrFlyweight() { |
| // Queries if all subnodes are either leaves or flyweights |
| return (NW instanceof PRQuadTreeNodeLeaf || NW instanceof PRQuadTreeNodeFlyweight)&& |
| (NE instanceof PRQuadTreeNodeLeaf || NE instanceof PRQuadTreeNodeFlyweight)&& |
| (SW instanceof PRQuadTreeNodeLeaf || SW instanceof PRQuadTreeNodeFlyweight)&& |
| (SE instanceof PRQuadTreeNodeLeaf || SE instanceof PRQuadTreeNodeFlyweight); |
| } |
| // Returns the number of all records in all subleaves |
| public int countOfAllLeafNodes() { |
| int ret = 0; |
| if (NW instanceof PRQuadTreeNodeLeaf) |
| ret += ((PRQuadTreeNodeLeaf) NW).getCount(); |
| if (NE instanceof PRQuadTreeNodeLeaf) |
| ret += ((PRQuadTreeNodeLeaf) NE).getCount(); |
| if (SW instanceof PRQuadTreeNodeLeaf) |
| ret += ((PRQuadTreeNodeLeaf) SW).getCount(); |
| if (SE instanceof PRQuadTreeNodeLeaf) |
| ret += ((PRQuadTreeNodeLeaf) SE).getCount(); |
| return ret; |
| } |
| // Returns the number of records in a node if it is a leaf node |
| public int countOfLeafNode(PRQuadTreeNode node) { |
| if (node instanceof PRQuadTreeNodeLeaf) |
| return ((PRQuadTreeNodeLeaf) node).getCount(); |
| else |
| return 0; |
| } |
| // Encapsulation functions |
| public PRQuadTreeNode getNW() { |
| return NW; |
| } |
| public void setNW(PRQuadTreeNode nW) { |
| NW = nW; |
| } |
| public PRQuadTreeNode getNE() { |
| return NE; |
| } |
| public void setNE(PRQuadTreeNode nE) { |
| NE = nE; |
| } |
| public PRQuadTreeNode getSW() { |
| return SW; |
| } |
| public void setSW(PRQuadTreeNode sW) { |
| SW = sW; |
| } |
| public PRQuadTreeNode getSE() { |
| return SE; |
| } |
| public void setSE(PRQuadTreeNode sE) { |
| SE = sE; |
| } |
| } |
| /Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/PRQuadTreeNodeLeaf.java |
|---|
| 0,0 → 1,119 |
| // Leaf node for the PRQuadTree |
| public class PRQuadTreeNodeLeaf implements PRQuadTreeNode { |
| private Record[] records; // Array holding the records in the leaf |
| private int numOfRecords; // Number of records in the leaf |
| // Initialize a new leaf node that holds 'size' records |
| public PRQuadTreeNodeLeaf(int size) { |
| records = new Record[size]; |
| numOfRecords = size; |
| } |
| // Inserts each record from input leaf into current leaf |
| public void insert(PRQuadTreeNodeLeaf leaf) { |
| Record record = leaf.getFirst(); |
| do { |
| this.insert(record); |
| record = leaf.getNext(record); |
| } |
| while (record != null); |
| } |
| // Inserts a record into the current leaf |
| public boolean insert(Record in) { |
| if (in == null) |
| return true; |
| boolean ret = false; |
| // If all records are filled, return false |
| for (Record record : records) { |
| if (record == null) { |
| ret = true; |
| break; |
| } |
| } |
| if (ret != false) { |
| // Otherwise insert record into the first avalaible slot |
| for (int i = 0; i < numOfRecords; i++) { |
| if (records[i] == null) { |
| records[i] = in; |
| break; |
| } |
| } |
| } |
| return ret; |
| } |
| // Removes a record from the leaf given a set of coordinates |
| public Record remove(int x, int y) { |
| Record ret = null; |
| // Check if any of the records have matching coordinates |
| ret = find(x, y); |
| if (ret != null) { |
| // If record is found, return record and shift other records forward |
| for (int i = 0; i < numOfRecords; i++) { |
| if (records[i] == ret) { |
| // Shift records forward |
| for (int j = i; j < numOfRecords; j++) { |
| if (j+1 < numOfRecords) |
| records[j] = records[j+1]; |
| else |
| records[j] = null; |
| } |
| break; |
| } |
| } |
| } |
| return ret; |
| } |
| // Returns a record with the specified coordinates if it exists |
| public Record find(int x, int y) { |
| Record ret = null; |
| // Check if any records have matching coordinates |
| for (Record record : records) { |
| if (record != null && record.getX() == x && record.getY() == y) { |
| // Return the record if found |
| ret = record; |
| break; |
| } |
| } |
| return ret; |
| } |
| // Returns the first record in the leaf node |
| public Record getFirst() { |
| return records[0]; |
| } |
| // Returns the next record given a record |
| public Record getNext(Record record) { |
| Record ret = null; |
| for (int i = 0; i < numOfRecords; i++) { |
| if (records[i] == record) { |
| if (i+1 < numOfRecords) |
| ret = records[i+1]; |
| break; |
| } |
| } |
| return ret; |
| } |
| // Returns the number of records in the leaf node |
| public int getCount() { |
| int ret = 0; |
| for (int i = 0; i < numOfRecords; i++) { |
| if (records[i] != null) |
| ret++; |
| else |
| break; |
| } |
| return ret; |
| } |
| // If first record is empty, the entire leaf is empty |
| public boolean isEmpty() { |
| return (records[0] == null); |
| } |
| } |
| /Classwork/CS3114/GIS/Record.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/Record.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/Record.java |
|---|
| 0,0 → 1,6 |
| // Interface for a generic record for the BSTree or PRQuadTree |
| public interface Record { |
| public int getX(); |
| public int getY(); |
| } |
| /Classwork/CS3114/GIS/Schedule.xls |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/GIS/Schedule.xls |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/GIS/p2SyntaxTest.txt |
|---|
| 0,0 → 1,54 |
| makenull |
| insert -1 1597 Blacksburg |
| insert 16384 4 Blacksburg |
| insert 16383 16834 Blacksburg |
| insert 8581 -8581 Blacksburg |
| insert 5001 5012 Blacksburg |
| insert 5001 5012 Christiansburg |
| insert 5001 6213 Blacksburg |
| insert 5001 8414 Christiansburg |
| insert 0 0 Floyd |
| insert 16383 16383 Virginia_Beach |
| debug |
| find Blacksbrug |
| find Blacksburg |
| remove -160 15958 |
| remove 0 -15958 |
| remove 581 3851 |
| remove 5001 5012 |
| remove 5001 5012 |
| remove Blacksbrug |
| remove Christiansburg |
| insert 5002 1019 Radford |
| search 0 16893 1 |
| search 100 159 -1 |
| search -100 159 500 |
| search 0 68 1000000 |
| search 5000 5000 100 |
| makenull |
| debug |
| /Classwork/CS3114/GIS/p2SyntaxTestOutput.txt |
|---|
| 0,0 → 1,94 |
| makenull |
| >> Makenull operation successful |
| insert -1 1597 Blacksburg |
| >> Insert rejected, bad X coordinate |
| insert 16384 4 Blacksburg |
| >> Insert rejected, bad X coordinate |
| insert 16383 16834 Blacksburg |
| >> Insert rejected, bad Y coordinate |
| insert 8581 -8581 Blacksburg |
| >> Insert rejected, bad Y coordinate |
| insert 5001 5012 Blacksburg |
| >> Insert operation successful |
| insert 5001 5012 Christiansburg |
| >> Insert rejected, coordinates duplicate an existing city record |
| insert 5001 6213 Blacksburg |
| >> Insert operation successful |
| insert 5001 8414 Christiansburg |
| >> Insert operation successful |
| insert 0 0 Floyd |
| >> Insert operation successful |
| insert 16383 16383 Virginia_Beach |
| >> Insert operation successful |
| debug |
| >> I5001,5012,Blacksburg5001,6213,Blacksburg0,0,Floyd|E5001,8414,Christiansburg|16383,16383,virginia_Beach| |
| find Blacksbrug |
| >> City record(s) found: |
| >> No records |
| find Blacksburg |
| >> City Records found: |
| >> 5001, 5012, Blacksburg |
| >> 5001, 6213, Blacksburg |
| remove -160 15958 |
| >> Remove operation failed: Bad X coordinate |
| [The Y coordinate is also bad, but one error is sufficient to report] |
| remove 0 -15958 |
| >> Remove operation failed: Bad Y coordinate |
| remove 581 3851 |
| >> No such City Record found |
| remove 5001 5012 |
| >> Removed 5001, 5012, Blacksburg |
| remove 5001 5012 |
| >> No such City Record found |
| remove Blacksbrug |
| >> No such City Record found |
| remove Christiansburg |
| >> Removed 5001, 8414, Christiansburg |
| insert 5002 1019 Radford |
| >> Insert operation successful |
| search 0 16893 1 |
| >> Search operation failed: Bad Y value |
| search 100 159 -1 |
| >> Search operation failed: Bad radius value |
| search -100 159 500 |
| >> City record(s) found: |
| >> 0, 0, Floyd |
| >> 2 nodes visited |
| search 0 68 1000000 |
| >> Search operation failed: Bad radius value |
| search 5000 5000 100 |
| >> City record(s) found: |
| >> No such record |
| >> 2 nodes visited |
| makenull |
| >> Makenull operation successful |
| debug |
| >> E |
| /Classwork/CS3114/Memory Manager/.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/Memory Manager/.project |
|---|
| 0,0 → 1,17 |
| <?xml version="1.0" encoding="UTF-8"?> |
| <projectDescription> |
| <name>CS3114P1</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/Memory Manager/.settings/org.eclipse.jdt.core.prefs |
|---|
| 0,0 → 1,12 |
| #Fri Aug 26 18:05:55 EDT 2011 |
| eclipse.preferences.version=1 |
| org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled |
| org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6 |
| org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve |
| org.eclipse.jdt.core.compiler.compliance=1.6 |
| org.eclipse.jdt.core.compiler.debug.lineNumber=generate |
| org.eclipse.jdt.core.compiler.debug.localVariable=generate |
| org.eclipse.jdt.core.compiler.debug.sourceFile=generate |
| org.eclipse.jdt.core.compiler.problem.assertIdentifier=error |
| org.eclipse.jdt.core.compiler.problem.enumIdentifier=error |
| org.eclipse.jdt.core.compiler.source=1.6 |
| /Classwork/CS3114/Memory Manager/ByteStringConverter.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/ByteStringConverter.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/ByteStringConverter.java |
|---|
| 0,0 → 1,40 |
| import java.nio.ByteBuffer; |
| // Assisting class for MemClient to convert values to a byte array and vice versa |
| public class ByteStringConverter { |
| // Converts the passed string array into a byte array |
| public static byte[] convertToByteArray(int int1, int int2, String str) { |
| // Use ByteBuffer to serialize to bytes |
| byte[] byteArray = new byte[8 + str.length()]; |
| byte[] bstr = str.getBytes(); |
| ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
| // Insert passed values into the byte array |
| buffer.putInt(int1); |
| buffer.putInt(int2); |
| buffer.put(bstr); |
| return byteArray; |
| } |
| // Converts the byte array into a string array |
| public static String[] convertToStringArray(byte[] byteArray) { |
| // Array of values to return from byte array |
| String[] strArray = new String[3]; |
| ByteBuffer buffer = ByteBuffer.wrap(byteArray); |
| int int1 = buffer.getInt(); |
| int int2 = buffer.getInt(); |
| byte[] bstr = new byte[byteArray.length - 8]; |
| buffer.get(bstr); |
| // Pull values from byte array into string array |
| strArray[0] = Integer.toString(int1); |
| strArray[1] = Integer.toString(int2); |
| strArray[2] = new String(bstr); |
| return strArray; |
| } |
| } |
| /Classwork/CS3114/Memory Manager/DoubleLinkedList.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/DoubleLinkedList.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/DoubleLinkedList.java |
|---|
| 0,0 → 1,138 |
| // Class for managing the linked list of free blocks |
| public class DoubleLinkedList { |
| private LinkedListEntry head; // Start of linked list |
| public void insert(LinkedListEntry 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; |
| } |
| LinkedListEntry 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 |
| LinkedListEntry newEntry = new LinkedListEntry(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 |
| LinkedListEntry newEntry = new LinkedListEntry(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 |
| LinkedListEntry 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(int address) { |
| // First check if list is empty |
| if (head == null) { |
| return false; |
| } else { |
| // Otherwise loop through and fine entry |
| LinkedListEntry 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) |
| LinkedListEntry 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 LinkedListEntry getFirstEntry() { |
| // First check if list is empty |
| if (head == null) { |
| return null; |
| } else { |
| // Otherwise return head entry |
| return head; |
| } |
| } |
| } |
| /Classwork/CS3114/Memory Manager/Handle.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/Handle.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/Handle.java |
|---|
| 0,0 → 1,17 |
| // Handle passed to and from MemManager |
| public class Handle { |
| private int address; // Location of block in memory pool |
| public Handle(int addr) { |
| this.address = addr; |
| } |
| public int getAddress() { |
| return address; |
| } |
| public void setAddress(int address) { |
| this.address = address; |
| } |
| } |
| /Classwork/CS3114/Memory Manager/LinkedListEntry.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/LinkedListEntry.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/LinkedListEntry.java |
|---|
| 0,0 → 1,46 |
| // Individual entries in the linked list |
| public class LinkedListEntry { |
| private int startAddress; // Start address of free block |
| private int endAddress; // End address of free block |
| private int size; // Total size of free block |
| private LinkedListEntry nextBlock; // Pointer to next block in list |
| private LinkedListEntry prevBlock; // Pointer to previous block in list |
| // Constructor |
| public LinkedListEntry(int start, int end, int size){ |
| this.startAddress = start; |
| this.endAddress = end; |
| this.size = size; |
| setNextBlock(null); |
| setPrevBlock(null); |
| } |
| public int getStartAddress() { |
| return startAddress; |
| } |
| public int getEndAddress() { |
| return endAddress; |
| } |
| public int getSize() { |
| return size; |
| } |
| public LinkedListEntry getNextBlock() { |
| return nextBlock; |
| } |
| public void setNextBlock(LinkedListEntry nextBlock) { |
| this.nextBlock = nextBlock; |
| } |
| public LinkedListEntry getPrevBlock() { |
| return prevBlock; |
| } |
| public void setPrevBlock(LinkedListEntry prevBlock) { |
| this.prevBlock = prevBlock; |
| } |
| } |
| /Classwork/CS3114/Memory Manager/MemClient.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/MemClient.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/MemClient.java |
|---|
| 0,0 → 1,126 |
| // Memory client that interfaces with MemManager |
| public class MemClient { |
| private Handle[] recordArray; // Client's array of handles |
| private MemManager memoryManager; // Instance of a memory manager |
| public MemClient(int input_numRecs, int input_poolSize) { |
| // Initialize the record array and create a new memory manager |
| recordArray = new Handle[input_numRecs]; |
| memoryManager = new MemManager(input_poolSize); |
| } |
| public void processLine(String line) { |
| // Split the passed line into tokens |
| String delim = "[ ]+"; |
| String[] tokens = line.split(delim); |
| // Parse tokens to determine what action to take |
| if (tokens[0].compareToIgnoreCase("insert") == 0) { |
| processInsertCommand(tokens, recordArray, memoryManager); |
| } else if (tokens[0].compareToIgnoreCase("remove") == 0) { |
| processRemoveCommand(tokens, recordArray, memoryManager); |
| } else if (tokens[0].compareToIgnoreCase("print") == 0) { |
| processPrintCommand(tokens, recordArray, memoryManager); |
| } else { |
| System.out.printf("\"%s\" command is not supported\n", tokens[0]); |
| } |
| } |
| public void processInsertCommand(String[] tokens, Handle[] recordArray, MemManager memoryManager) { |
| // Process insert command |
| if (tokens.length != 5) { |
| System.out.printf("Arguments must be in format \"insert recnum x y name\"\n"); |
| } else { |
| try { |
| // Check for array bounds for record array |
| int recordID = Integer.parseInt(tokens[1]); |
| if (recordID < 0 || recordID > recordArray.length - 1) { |
| System.out.printf("Arguments out of bound\n"); |
| } else { |
| // Delete record in record array if it exists |
| if (recordArray[recordID] != null) { |
| memoryManager.remove(recordArray[recordID]); |
| recordArray[recordID] = null; |
| } |
| // Serialize to byte array and send to memory manager |
| int xpos = Integer.parseInt(tokens[2]); |
| int ypos = Integer.parseInt(tokens[3]); |
| byte[] buffer = ByteStringConverter.convertToByteArray(xpos, ypos, tokens[4]); |
| Handle retHandle = memoryManager.insert(buffer, buffer.length); |
| if (retHandle == null) { |
| System.out.printf("No free space is avaliable to store the record\n"); |
| } else { |
| // Save returned handle to the record array |
| recordArray[recordID] = retHandle; |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf("Error attempting to parse int values\n"); |
| } |
| } |
| } |
| public void processRemoveCommand(String[] tokens, Handle[] recordArray, MemManager memoryManager) { |
| // Process remove command |
| if (tokens.length != 2) { |
| System.out.printf("A record ID must be supplied\n"); |
| } else { |
| try { |
| int recordID = Integer.parseInt(tokens[1]); |
| if (recordID < 0 || recordID > recordArray.length - 1) { |
| System.out.printf("Arguments out of bound\n"); |
| } else { |
| // Remove record from record array if it exists |
| if (recordArray[recordID] != null) { |
| memoryManager.remove(recordArray[recordID]); |
| recordArray[recordID] = null; |
| } else { |
| System.out.printf("No record found for record ID %d\n", recordID); |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf("Error attempting to parse int values\n"); |
| } |
| } |
| } |
| public void processPrintCommand(String[] tokens, Handle[] recordArray, MemManager memoryManager) { |
| byte[] fromPool = new byte[255]; |
| // Process print command |
| if (tokens.length == 1) { |
| // Print out every entry in recordArray |
| for (int i = 0; i < recordArray.length; i++) { |
| if (recordArray[i] != null) { |
| fromPool = new byte[255]; |
| System.out.printf("Record #%d at address %d: ", i, recordArray[i].getAddress()); |
| memoryManager.get(fromPool, recordArray[i], 255); |
| String[] strArray = ByteStringConverter.convertToStringArray(fromPool); |
| System.out.printf("%s (%s,%s)\n", strArray[2].trim(), strArray[0], strArray[1]); |
| } |
| } |
| // Print out free block list |
| memoryManager.dump(); |
| } else if (tokens.length == 2) { |
| // Print out specified record |
| try { |
| int recordID = Integer.parseInt(tokens[1]); |
| if (recordID < 0 || recordID > recordArray.length - 1) { |
| System.out.printf("Arguments out of bound\n"); |
| } else { |
| if (recordArray[recordID] != null) { |
| // Get and print out record |
| memoryManager.get(fromPool, recordArray[recordID], 255); |
| String[] strArray = ByteStringConverter.convertToStringArray(fromPool); |
| System.out.printf("Record #%d: %s (%s,%s)\n", recordID, strArray[2].trim(), strArray[0], strArray[1]); |
| } else { |
| System.out.printf("No record found for record ID %d\n", recordID); |
| } |
| } |
| } catch (NumberFormatException e) { |
| System.out.printf("Error attempting to parse int values\n"); |
| } |
| } else { |
| System.out.printf("Invalud number of arguments\n"); |
| } |
| } |
| } |
| /Classwork/CS3114/Memory Manager/MemManager.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/MemManager.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/MemManager.java |
|---|
| 0,0 → 1,117 |
| import java.nio.ByteBuffer; |
| // Memory manager that operates on the memory pool |
| public class MemManager { |
| private byte[] memoryPool; // Byte array representing the memory pool |
| private DoubleLinkedList emptyBlockList; // List of free blocks |
| // Constructor |
| public MemManager(int poolsize) { |
| // Initialize memory pool and list of free blocks |
| memoryPool = new byte[poolsize]; |
| emptyBlockList = new DoubleLinkedList(); |
| // Create the first empty block of the pool size |
| LinkedListEntry newEntry = new LinkedListEntry(0, poolsize - 1, poolsize); |
| emptyBlockList.insert(newEntry); |
| } |
| // Insert a record and return its position handle. |
| // space contains the record to be inserted, of length size. |
| public Handle insert(byte[] space, int size) { |
| LinkedListEntry start = emptyBlockList.getFirstEntry(); |
| if (start == null) { |
| // There are no free blocks |
| return null; |
| } |
| if ((size + 1) > start.getSize()) { |
| // Size to insert is greater than size of largest free block |
| return null; |
| } |
| while (start != null) { |
| if (start.getNextBlock() == null) { |
| // Current block is last block in list, insert into current block |
| Handle newHandle = insertDataIntoMemPool(start, space, size); |
| return newHandle; |
| } else if ((size + 1) > start.getNextBlock().getSize()) { |
| // Best fit block found, insert into current block |
| Handle newHandle = insertDataIntoMemPool(start, space, size); |
| 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.getAddress()); |
| // Needs to create a new empty block at the specified address |
| LinkedListEntry newEntry = new LinkedListEntry(handle.getAddress(), handle.getAddress() + size, size + 1); |
| emptyBlockList.insert(newEntry); |
| } |
| // Return the record with handle posHandle, up to size bytes. |
| // Data to be returned is copied to space. |
| public void get(byte[] space, Handle handle, int size) { |
| short shSize = getDataBlockSize(handle.getAddress()); |
| // Find max number of bytes to copy to byte array |
| int toRead; |
| if (size < shSize) { |
| toRead = size; |
| } else { |
| toRead = shSize; |
| } |
| // Copy bytes from memory pool to byte array |
| ByteBuffer memPool = ByteBuffer.wrap(memoryPool, handle.getAddress() + 1, toRead); |
| ByteBuffer dest = ByteBuffer.wrap(space); |
| dest.put(memPool); |
| } |
| // Dump a printout of the freeblock list |
| public void dump() { |
| LinkedListEntry head = emptyBlockList.getFirstEntry(); |
| while (head != null) { |
| System.out.printf("Empty block at address %d of size %d\n", head.getStartAddress(), head.getSize()); |
| head = head.getNextBlock(); |
| } |
| } |
| // Returns the value of the first byte for the data entry (size) |
| private short getDataBlockSize(int address) { |
| byte[] shortArr = new byte[2]; |
| ByteBuffer shortBuffer = ByteBuffer.wrap(shortArr, 1, 1); |
| shortBuffer.put(memoryPool[address]); |
| shortBuffer = ByteBuffer.wrap(shortArr); |
| short size = shortBuffer.getShort(); |
| return size; |
| } |
| // Copies the passed byte array into a free block in the memory pool |
| private Handle insertDataIntoMemPool(LinkedListEntry entry, byte[] space, int size) { |
| // Insert the data at the address of the given free block |
| ByteBuffer memBuffer = ByteBuffer.wrap(memoryPool, entry.getStartAddress(), size + 1); |
| memBuffer.put((byte)size); |
| memBuffer.put(space); |
| // Create a new free block with remaining free space |
| if (entry.getSize() - (size + 1) != 0) { |
| int startAddress = entry.getStartAddress() + size + 1; |
| int newSize = entry.getSize() - (size + 1); |
| int endAddress = startAddress + newSize - 1; |
| LinkedListEntry newEntry = new LinkedListEntry(startAddress, endAddress, newSize); |
| emptyBlockList.remove(entry.getStartAddress()); |
| emptyBlockList.insert(newEntry); |
| } else { |
| emptyBlockList.remove(entry.getStartAddress()); |
| } |
| Handle newHandle = new Handle(entry.getStartAddress()); |
| return newHandle; |
| } |
| } |
| /Classwork/CS3114/Memory Manager/P1 Notes.txt |
|---|
| 0,0 → 1,18 |
| P1 Notes |
| Components: |
| - Array of bytes representing the memory pool |
| = byte[size of pool] |
| - Doubly linked list that keeps track of the free blocks in the memory pool |
| IE, holds the address and size of each free block in the memory pool |
| = int (location of block start) |
| = int (size of block) |
| = handle (next handle) |
| = handle (previous handle) |
| - Record array that stores the 'handles' to the stored data records in the memory pool |
| - Handle class |
| = int (location of start address in memory pool) |
| /Classwork/CS3114/Memory Manager/P1.pdf |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/P1.pdf |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/P1testOutput.txt |
|---|
| 0,0 → 1,215 |
| > Let's assume that this was called with a 10 slot array and a 175 |
| > byte memory pool. |
| > Freelist: [0, 174] (175 bytes) |
| insert 0 4240 7345 Albany |
| > 15 bytes taken |
| > Freelist: [15, 174] (160 bytes) |
| insert 1 3455 13836 Albuquerque |
| > 20 bytes taken |
| > Freelist: [35, 174] (140 bytes) |
| insert 2 3511 10150 Amarillo |
| > 17 bytes taken |
| > Freelist: [52, 174] (123 bytes) |
| insert 3 6113 14954 Anchorage |
| > 18 bytes taken |
| > Freelist: [70, 174] (105 bytes) |
| insert 4 3345 8423 Atlanta |
| > 16 bytes taken |
| > Freelist: [86, 174] (89 bytes) |
| remove 4 |
| > This frees up the 16 bytes at the end, which merges with the free block |
| > Freelist: [70, 174] (105 bytes) |
| > 0: (4240, 7345) Albany |
| > 1: (3455, 13836) Albuquerque |
| > 2: (3511, 10150) Amarillo |
| > 3: (6113, 14954) Anchorage |
| > 4: [no record] |
| > 5: [no record] |
| print 0 |
| > 4240 7345 Albany |
| print 1 |
| > 3455 13836 Albuquerque |
| print 2 |
| > 3511 10150 Amarillo |
| print 3 |
| > 6113 14954 Anchorage |
| print 4 |
| > Slot 4 is empty |
| print 5 |
| > Slot 5 is empty |
| insert 5 2515 5740 Asuncion_Paraguay |
| > 26 bytes taken |
| > Freelist: [96, 174] (79 bytes) |
| print 5 |
| > 2515 5740 Asuncion_Paraguay |
| insert 6 4447 11750 Baker |
| > 14 bytes taken |
| > Freelist: [110, 174] (65 bytes) |
| insert 7 3918 7638 Baltimore |
| > 18 bytes taken |
| > Freelist: [128, 174] (47 bytes) |
| insert 7 3918 7638 Baltimore |
| > Since this is overwriting slot 7, the old message is deleted, |
| > freeing 18 bytes, which happen to be at the end and which merge with |
| > the existing free block. |
| > 18 bytes are then taken for the new message |
| > Freelist: [128, 174] (47 bytes) |
| insert 8 3955 11625 Beijing_China |
| > 22 bytes taken |
| > Freelist: [150, 174] (25 bytes) |
| insert 9 3330 8650 Birmingham |
| > 19 bytes taken |
| > Freelist: [169, 174] (6 bytes) |
| > [0] --> 0: (4240, 7345) Albany |
| > [15] --> 1: (3455, 13836) Albuquerque |
| > [35] --> 2: (3511, 10150) Amarillo |
| > [52] --> 3: (6113, 14954) Anchorage |
| > 4: [no record] |
| > [70] --> 5: (2515, 5740) Asuncion_Paraguay |
| > [96] --> 6: (4447, 11750) Baker |
| > [110] --> 7: (3918, 7638) Baltimore |
| > [128] --> 8: (3955, 11625) Beijing_China |
| > [150] --> 9: (3330, 8650) Birmingham |
| remove 9 |
| > This frees 19 bytes, which merge with the free block at the end. |
| > Freelist: [150, 174] (25 bytes) |
| print 9 |
| > Slot 9 is empty |
| insert 9 3355 1822 Cape_Town_South_Africa |
| > This requires 31 bytes, but there is not a block of this size |
| > available. Therefore, nothing is inserted (or otherwise changed) |
| > Freelist: [150, 174] (25 bytes) |
| print 9 |
| > Slot 9 is empty |
| remove 3 |
| > Free up 18 bytes |
| > Freelist: [52, 69] (18 bytes) |
| > [150, 174] (25 bytes) |
| remove 4 |
| > Nothing happens since Slot 4 is empty |
| remove 6 |
| > Free up 14 bytes starting at position 96 |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 109] (14 bytes); |
| > [150, 174] (25 bytes) |
| remove 7 |
| > Free up 18 bytes starting at position 110. Since this is adjacent to |
| > an existing free block, they merge. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 127] (32 bytes); |
| > [150, 174] (25 bytes) |
| remove 7 |
| > Since Slot 7 is empty, nothing happens. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 127] (32 bytes); |
| > [150, 174] (25 bytes) |
| remove 8 |
| > Free 22 bytes starting at postion 128. Since there are free blocks |
| > to either side, all three merge together. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 174] (79 bytes); |
| insert 7 2308 8223 Havana_Cuba |
| > 20 bytes taken. The first free block is not big enough, so take from |
| > the second. |
| > Freelist: [52, 69] (18 bytes); |
| > [116, 174] (59 bytes); |
| insert 7 2946 10634 Chongqing_China |
| > First the 20 bytes from the message currently stored is freed, whose |
| > space merges with the block at the end of the list. Then 24 bytes |
| > are reserved from the second block, since the first is not big enough. |
| > Freelist: [52, 69] (18 bytes); |
| > [120, 174] (55 bytes); |
| insert 8 616 10648 Jakarta_Indonesia |
| > 26 bytes taken from the second block |
| > Freelist: [52, 69] (18 bytes); |
| > [146, 174] (29 bytes); |
| > Print out the current records in the array |
| > [0] --> 0: 4240 7345 Albany |
| > [15] --> 1: 3455 13836 Albuquerque |
| > [35] --> 2: 3511 10150 Amarillo |
| > 3: [no record] |
| > 4: [no record] |
| > [70] --> 5: (2515, 5740) Asuncion_Paraguay |
| > 6: [no record] |
| > [96] --> 7: 2946 10634 Chongqing_China |
| > [120] --> 8: 616 10648 Jakarta_Indonesia |
| > 9: [no record] |
| remove 8 |
| > Free 26 bytes and merge with second block. |
| > Freelist: [52, 69] (18 bytes); |
| > [120, 174] (55 bytes); |
| /Classwork/CS3114/Memory Manager/Schedule.xls |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/Schedule.xls |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/memman.class |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/CS3114/Memory Manager/memman.class |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/CS3114/Memory Manager/memman.java |
|---|
| 0,0 → 1,108 |
| /* |
| * CS 3114 Project 1 |
| * Author: Kevin Lee |
| * Compiler: Eclipse 3.7.0 |
| * Operating System: Windows 7 x64 |
| * Date Completed: 9/1/2011 |
| * |
| * The following program is designed to provide an interface to |
| * client side code that allows the client to store and retrieve |
| * byte arrays of data. The memory manager has no information on |
| * the actual data to be stored, other than the size of the byte |
| * array. The memory manager allocates a memory pool when the |
| * object is created, and executes all operations on the memory |
| * pool. The memory manager also keeps a doubly linked list of |
| * empty blocks from which it finds the best fit block to store |
| * the passed data in. The client is responsible for parsing the |
| * command file as well as creating the byte array holding the |
| * data to be stored. The client also has a record array which |
| * stores handles passed back from the memory manager from which |
| * it uses to retrieve stored data from the memory manager. |
| * |
| * The stored data is saved in the following format: |
| * byte[0] = size of data record |
| * byte[1-4] = int (x-coordinate) |
| * byte[5-8] = int (y-coordinate) |
| * byte[9-?] = string (name of city name) |
| * The first byte is only used by the memory manager and is not |
| * returned to the client when the data record is retrieved. |
| * |
| * 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.*; |
| public class memman { |
| public static void main(String[] args) { |
| int input_poolSize; // Size of memory pool to allocate |
| int input_numRecs; // Total number of records to hold |
| String input_commandFile; // Location of file to parse |
| // 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 |
| try { |
| input_poolSize = Integer.parseInt(args[0]); |
| input_numRecs = Integer.parseInt(args[1]); |
| input_commandFile = args[2]; |
| } catch (NumberFormatException e) { |
| System.out.printf("The first two arguments must be an integer"); |
| return; |
| } |
| // Handles error if the passed arguments are negative numbers |
| if (input_poolSize < 0 || input_numRecs < 0) { |
| System.out.printf("Int arguments cannot be negative"); |
| return; |
| } |
| // Check to make sure the command file exists |
| File cmdFile = new File(input_commandFile); |
| if (!cmdFile.exists()) { |
| System.out.printf("Command file not found"); |
| return; |
| } |
| MemClient memoryClient = new MemClient(input_numRecs, input_poolSize); |
| // 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) { |
| memoryClient.processLine(cin); |
| } |
| } |
| } catch (FileNotFoundException e) { |
| System.out.printf("Command file not found"); |
| return; |
| } catch (IOException e) { |
| System.out.printf("Unable to read input file"); |
| return; |
| } |
| } |
| } |
| /Classwork/CS3114/Memory Manager/p1_testData.txt |
|---|
| 0,0 → 1,54 |
| insert 0 4240 7345 Albany |
| insert 1 3455 13836 Albuquerque |
| insert 2 3511 10150 Amarillo |
| insert 3 6113 14954 Anchorage |
| insert 4 3345 8423 Atlanta |
| remove 4 |
| print 0 |
| print 1 |
| print 2 |
| print 3 |
| print 4 |
| print 5 |
| insert 5 2515 5740 Asuncion_Paraguay |
| print 5 |
| insert 6 4447 11750 Baker |
| insert 7 3918 7638 Baltimore |
| insert 7 3918 7638 Baltimore |
| insert 8 3955 11625 Beijing_China |
| insert 9 3330 8650 Birmingham |
| remove 9 |
| print 9 |
| insert 9 3355 1822 Cape_Town_South_Africa |
| print 9 |
| remove 3 |
| remove 4 |
| remove 6 |
| remove 7 |
| remove 7 |
| remove 8 |
| insert 7 2308 8223 Havana_Cuba |
| insert 7 2946 10634 Chongqing_China |
| insert 8 616 10648 Jakarta_Indonesia |
| remove 8 |