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