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