001: package org.garret.perst.impl;
002:
003: import org.garret.perst.*;
004: import java.util.ArrayList;
005:
006: public class RtreePage extends Persistent {
007: static final int card = (Page.pageSize - ObjectHeader.sizeof - 4 * 3)
008: / (4 * 4 + 4);
009: static final int minFill = card / 2;
010:
011: int n;
012: Rectangle[] b;
013: Link branch;
014:
015: RtreePage(Storage storage, IPersistent obj, Rectangle r) {
016: branch = storage.createLink(card);
017: branch.setSize(card);
018: b = new Rectangle[card];
019: setBranch(0, new Rectangle(r), obj);
020: n = 1;
021: for (int i = 1; i < card; i++) {
022: b[i] = new Rectangle();
023: }
024: }
025:
026: RtreePage(Storage storage, RtreePage root, RtreePage p) {
027: branch = storage.createLink(card);
028: branch.setSize(card);
029: b = new Rectangle[card];
030: n = 2;
031: setBranch(0, root.cover(), root);
032: setBranch(1, p.cover(), p);
033: for (int i = 2; i < card; i++) {
034: b[i] = new Rectangle();
035: }
036: }
037:
038: RtreePage() {
039: }
040:
041: RtreePage insert(Storage storage, Rectangle r, IPersistent obj,
042: int level) {
043: modify();
044: if (--level != 0) {
045: // not leaf page
046: int i, mini = 0;
047: long minIncr = Long.MAX_VALUE;
048: long minArea = Long.MAX_VALUE;
049: for (i = 0; i < n; i++) {
050: long area = b[i].area();
051: long incr = Rectangle.joinArea(b[i], r) - area;
052: if (incr < minIncr) {
053: minIncr = incr;
054: minArea = area;
055: mini = i;
056: } else if (incr == minIncr && area < minArea) {
057: minArea = area;
058: mini = i;
059: }
060: }
061: RtreePage p = (RtreePage) branch.get(mini);
062: RtreePage q = p.insert(storage, r, obj, level);
063: if (q == null) {
064: // child was not split
065: b[mini].join(r);
066: return null;
067: } else {
068: // child was split
069: setBranch(mini, p.cover(), p);
070: return addBranch(storage, q.cover(), q);
071: }
072: } else {
073: return addBranch(storage, new Rectangle(r), obj);
074: }
075: }
076:
077: int remove(Rectangle r, IPersistent obj, int level,
078: ArrayList reinsertList) {
079: if (--level != 0) {
080: for (int i = 0; i < n; i++) {
081: if (r.intersects(b[i])) {
082: RtreePage pg = (RtreePage) branch.get(i);
083: int reinsertLevel = pg.remove(r, obj, level,
084: reinsertList);
085: if (reinsertLevel >= 0) {
086: if (pg.n >= minFill) {
087: setBranch(i, pg.cover(), pg);
088: modify();
089: } else {
090: // not enough entries in child
091: reinsertList.add(pg);
092: reinsertLevel = level - 1;
093: removeBranch(i);
094: }
095: return reinsertLevel;
096: }
097: }
098: }
099: } else {
100: for (int i = 0; i < n; i++) {
101: if (branch.containsElement(i, obj)) {
102: removeBranch(i);
103: return 0;
104: }
105: }
106: }
107: return -1;
108: }
109:
110: void find(Rectangle r, ArrayList result, int level) {
111: if (--level != 0) { /* this is an internal node in the tree */
112: for (int i = 0; i < n; i++) {
113: if (r.intersects(b[i])) {
114: ((RtreePage) branch.get(i)).find(r, result, level);
115: }
116: }
117: } else { /* this is a leaf node */
118: for (int i = 0; i < n; i++) {
119: if (r.intersects(b[i])) {
120: result.add(branch.get(i));
121: }
122: }
123: }
124: }
125:
126: void purge(int level) {
127: if (--level != 0) { /* this is an internal node in the tree */
128: for (int i = 0; i < n; i++) {
129: ((RtreePage) branch.get(i)).purge(level);
130: }
131: }
132: deallocate();
133: }
134:
135: final void setBranch(int i, Rectangle r, IPersistent obj) {
136: b[i] = r;
137: branch.setObject(i, obj);
138: }
139:
140: final void removeBranch(int i) {
141: n -= 1;
142: System.arraycopy(b, i + 1, b, i, n - i);
143: branch.remove(i);
144: branch.setSize(card);
145: modify();
146: }
147:
148: final RtreePage addBranch(Storage storage, Rectangle r,
149: IPersistent obj) {
150: if (n < card) {
151: setBranch(n++, r, obj);
152: return null;
153: } else {
154: return splitPage(storage, r, obj);
155: }
156: }
157:
158: final RtreePage splitPage(Storage storage, Rectangle r,
159: IPersistent obj) {
160: int i, j, seed0 = 0, seed1 = 0;
161: long[] rectArea = new long[card + 1];
162: long waste;
163: long worstWaste = Long.MIN_VALUE;
164: //
165: // As the seeds for the two groups, find two rectangles which waste
166: // the most area if covered by a single rectangle.
167: //
168: rectArea[0] = r.area();
169: for (i = 0; i < card; i++) {
170: rectArea[i + 1] = b[i].area();
171: }
172: Rectangle bp = r;
173: for (i = 0; i < card; i++) {
174: for (j = i + 1; j <= card; j++) {
175: waste = Rectangle.joinArea(bp, b[j - 1]) - rectArea[i]
176: - rectArea[j];
177: if (waste > worstWaste) {
178: worstWaste = waste;
179: seed0 = i;
180: seed1 = j;
181: }
182: }
183: bp = b[i];
184: }
185: byte[] taken = new byte[card];
186: Rectangle group0, group1;
187: long groupArea0, groupArea1;
188: int groupCard0, groupCard1;
189: RtreePage pg;
190:
191: taken[seed1 - 1] = 2;
192: group1 = new Rectangle(b[seed1 - 1]);
193:
194: if (seed0 == 0) {
195: group0 = new Rectangle(r);
196: pg = new RtreePage(storage, obj, r);
197: } else {
198: group0 = new Rectangle(b[seed0 - 1]);
199: pg = new RtreePage(storage, branch.getRaw(seed0 - 1),
200: group0);
201: setBranch(seed0 - 1, r, obj);
202: }
203: groupCard0 = groupCard1 = 1;
204: groupArea0 = rectArea[seed0];
205: groupArea1 = rectArea[seed1];
206: //
207: // Split remaining rectangles between two groups.
208: // The one chosen is the one with the greatest difference in area
209: // expansion depending on which group - the rect most strongly
210: // attracted to one group and repelled from the other.
211: //
212: while (groupCard0 + groupCard1 < card + 1
213: && groupCard0 < card + 1 - minFill
214: && groupCard1 < card + 1 - minFill) {
215: int betterGroup = -1, chosen = -1;
216: long biggestDiff = -1;
217: for (i = 0; i < card; i++) {
218: if (taken[i] == 0) {
219: long diff = (Rectangle.joinArea(group0, b[i]) - groupArea0)
220: - (Rectangle.joinArea(group1, b[i]) - groupArea1);
221: if (diff > biggestDiff || -diff > biggestDiff) {
222: chosen = i;
223: if (diff < 0) {
224: betterGroup = 0;
225: biggestDiff = -diff;
226: } else {
227: betterGroup = 1;
228: biggestDiff = diff;
229: }
230: }
231: }
232: }
233: Assert.that(chosen >= 0);
234: if (betterGroup == 0) {
235: group0.join(b[chosen]);
236: groupArea0 = group0.area();
237: taken[chosen] = 1;
238: pg.setBranch(groupCard0++, b[chosen], branch
239: .getRaw(chosen));
240: } else {
241: groupCard1 += 1;
242: group1.join(b[chosen]);
243: groupArea1 = group1.area();
244: taken[chosen] = 2;
245: }
246: }
247: //
248: // If one group gets too full, then remaining rectangle are
249: // split between two groups in such way to balance cards of two groups.
250: //
251: if (groupCard0 + groupCard1 < card + 1) {
252: for (i = 0; i < card; i++) {
253: if (taken[i] == 0) {
254: if (groupCard0 >= groupCard1) {
255: taken[i] = 2;
256: groupCard1 += 1;
257: } else {
258: taken[i] = 1;
259: pg.setBranch(groupCard0++, b[i], branch
260: .getRaw(i));
261: }
262: }
263: }
264: }
265: pg.n = groupCard0;
266: n = groupCard1;
267: for (i = 0, j = 0; i < groupCard1; j++) {
268: if (taken[j] == 2) {
269: setBranch(i++, b[j], branch.getRaw(j));
270: }
271: }
272: return pg;
273: }
274:
275: final Rectangle cover() {
276: Rectangle r = new Rectangle(b[0]);
277: for (int i = 1; i < n; i++) {
278: r.join(b[i]);
279: }
280: return r;
281: }
282: }
|