Subversion Repositories Code-Repo

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed


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