Subversion Repositories Code-Repo

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);
        }
}