Subversion Repositories Code-Repo

Rev

Rev 94 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
94 Kevin 1 
 
2 
// Leaf node for the PRQuadTree
3 
public class PRQuadTreeNodeLeaf implements PRQuadTreeNode {
4 
	private Record[] records;	// Array holding the records in the leaf
5 
	private int numOfRecords;	// Number of records in the leaf
6 
 
7 
	// Initialize a new leaf node that holds 'size' records
8 
	public PRQuadTreeNodeLeaf(int size) {
9 
		records = new Record[size];
10 
		numOfRecords = size;
11 
	}
12 
 
13 
	// Inserts each record from input leaf into current leaf
14 
	public void insert(PRQuadTreeNodeLeaf leaf) {
15 
		Record record = leaf.getFirst();
16 
		do {
17 
			this.insert(record);
18 
			record = leaf.getNext(record);
19 
		}
20 
		while (record != null);
21 
	}
22 
 
23 
	// Inserts a record into the current leaf
24 
	public boolean insert(Record in) {
25 
		if (in == null)
26 
			return true;
27 
 
28 
		boolean ret = false;
29 
		// If all records are filled, return false
30 
		for (Record record : records) {
31 
			if (record == null) {
32 
				ret = true;
33 
				break;
34 
			}
35 
		}
36 
		if (ret != false) {
37 
			// Otherwise insert record into the first avalaible slot
38 
			for (int i = 0; i < numOfRecords; i++) {
39 
				if (records[i] == null) {
40 
					records[i] = in;
41 
					break;
42 
				}
43 
			}
44 
		}
45 
		return ret;
46 
	}
47 
 
48 
	// Removes a record from the leaf given a set of coordinates
49 
	public Record remove(int x, int y) {
50 
		Record ret = null;
51 
		// Check if any of the records have matching coordinates
52 
		ret = find(x, y);
53 
		if (ret != null) {
54 
			// If record is found, return record and shift other records forward
55 
			for (int i = 0; i < numOfRecords; i++) {
56 
				if (records[i] == ret) {
57 
					// Shift records forward
58 
					for (int j = i; j < numOfRecords; j++) {
59 
						if (j+1 < numOfRecords)
60 
							records[j] = records[j+1];
61 
						else
62 
							records[j] = null;
63 
					}
64 
					break;
65 
				}
66 
			}
67 
		}
68 
		return ret;
69 
	}
70 
 
71 
	// Returns a record with the specified coordinates if it exists
72 
	public Record find(int x, int y) {
73 
		Record ret = null;
74 
		// Check if any records have matching coordinates
75 
		for (Record record : records) {
76 
			if (record != null && record.getX() == x && record.getY() == y) {
77 
				// Return the record if found
78 
				ret = record;
79 
				break;
80 
			}
81 
		}
82 
		return ret;
83 
	}
84 
 
85 
	// Returns the first record in the leaf node
86 
	public Record getFirst() {
87 
		return records[0];
88 
	}
89 
 
90 
	// Returns the next record given a record
91 
	public Record getNext(Record record) {
92 
		Record ret = null;
93 
		for (int i = 0; i < numOfRecords; i++) {
94 
			if (records[i] == record) {
95 
				if (i+1 < numOfRecords)
96 
					ret =  records[i+1];
97 
				break;
98 
			}
99 
		}
100 
		return ret;
101 
	}
102 
 
103 
	// Returns the number of records in the leaf node
104 
	public int getCount() {
105 
		int ret = 0;
106 
		for (int i = 0; i < numOfRecords; i++) {
107 
			if (records[i] != null)
108 
				ret++;
109 
			else
110 
				break;
111 
		}
112 
		return ret;
113 
	}
114 
 
115 
	// If first record is empty, the entire leaf is empty
116 
	public boolean isEmpty() {
117 
		return (records[0] == null);
118 
	}
119 
}