Added search cursor for the r tree
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@470 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java
new file mode 100644
index 0000000..b9a0907
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeCursor.java
@@ -0,0 +1,28 @@
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.PathList;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface IRTreeCursor {
+ public void reset();
+
+ public boolean hasNext() throws Exception;
+
+ public void next() throws Exception;
+
+ public void open(PathList pathList, ITupleReference searchKey, int rootPage, MultiComparator interiorCmp,
+ MultiComparator leafCmp) throws Exception;
+
+ public ICachedPage getPage();
+
+ public void close() throws Exception;
+
+ public void setBufferCache(IBufferCache bufferCache);
+
+ public void setFileId(int fileId);
+
+ public ITupleReference getTuple();
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
index b07c284..75a74ca 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -11,6 +11,8 @@
public interface IRTreeFrame extends ITreeIndexFrame {
+ public ITreeIndexTupleReference createTupleReference();
+
public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
@@ -44,7 +46,9 @@
public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception;
- public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+ public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+ public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index 1cd795d..e4bdf93 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -32,11 +32,10 @@
private static final double splitFactor = 0.4;
private static final int nearMinimumOverlapFactor = 32;
- public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter) {
+ public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
super(tupleWriter, new UnorderedSlotManager());
- // TODO: change this to number of dim * 2 (at least it must be 4)
- this.tuples = new ITreeIndexTupleReference[4];
- for (int i = 0; i < 4; i++) {
+ this.tuples = new ITreeIndexTupleReference[keyFieldCount];
+ for (int i = 0; i < keyFieldCount; i++) {
this.tuples[i] = tupleWriter.createTupleReference();
}
cmpFrameTuple = tupleWriter.createTupleReference();
@@ -105,77 +104,6 @@
public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
- // RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
- // RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame =
- // ((RTreeTypeAwareTupleWriter) tupleWriter);
- // RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame =
- // ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
- // frameTuple.setFieldCount(cmp.getFieldCount());
- // rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
- //
- // ByteBuffer right = rightFrame.getBuffer();
- // int tupleCount = getTupleCount();
- //
- // int tuplesToLeft;
- // int mid = tupleCount / 2;
- // ITreeIndexFrame targetFrame = null;
- // int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(mid));
- // frameTuple.resetByTupleOffset(buf, tupleOff);
- // if (cmp.compare(tuple, frameTuple) >= 0) {
- // tuplesToLeft = mid + (tupleCount % 2);
- // targetFrame = rightFrame;
- // } else {
- // tuplesToLeft = mid;
- // targetFrame = this;
- // }
- // int tuplesToRight = tupleCount - tuplesToLeft;
- //
- // // copy entire page
- // System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
- //
- // // on right page we need to copy rightmost slots to left
- // int src = rightFrame.getSlotManager().getSlotEndOff();
- // int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
- // * rightFrame.getSlotManager().getSlotSize();
- // int length = rightFrame.getSlotManager().getSlotSize() *
- // tuplesToRight;
- // System.arraycopy(right.array(), src, right.array(), dest, length);
- // right.putInt(tupleCountOff, tuplesToRight);
- //
- // // on left page only change the tupleCount indicator
- // buf.putInt(tupleCountOff, tuplesToLeft);
- //
- // // compact both pages
- // rightFrame.compact(cmp);
- // compact(cmp);
- //
- // // insert last key
- // targetFrame.insert(tuple, cmp);
- //
- // // set split key to be highest value in left page
- // // TODO: find a better way to find the key size
- // tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- // frameTuple.resetByTupleOffset(buf, tupleOff);
- //
- // int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
- // cmp.getKeyFieldCount());
- // splitKey.initData(splitKeySize);
- // this.adjustMBR(tuples, cmp);
- // rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
- // rTreeSplitKey.getLeftPageBuffer(), 0);
- // rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
- // 0);
- //
- // ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame)
- // rightFrame).getTuples(), cmp);
- // rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
- // rightFrame).getTuples(), 0,
- // rTreeSplitKey.getRightPageBuffer(), 0);
- // rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(),
- // 0);
- //
- // return 0;
-
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
@@ -361,6 +289,11 @@
}
@Override
+ public ITreeIndexTupleReference createTupleReference() {
+ return tupleWriter.createTupleReference();
+ }
+
+ @Override
public int getBestChildPageId(MultiComparator cmp) {
return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
}
@@ -731,7 +664,30 @@
}
@Override
- public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j));
+ if (c > 0) {
+ return false;
+ }
+ c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+
+ if (c < 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getFieldCount());
frameTuple.resetByTupleIndex(this, tupleIndex);
int maxFieldPos = cmp.getKeyFieldCount() / 2;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
index 729bf36..56875b7 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
@@ -23,13 +23,15 @@
private static final long serialVersionUID = 1L;
private ITreeIndexTupleWriterFactory tupleWriterFactory;
+ private int keyFieldCount;
- public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
+ public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
this.tupleWriterFactory = tupleWriterFactory;
+ this.keyFieldCount = keyFieldCount;
}
@Override
public IRTreeFrame getFrame() {
- return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter());
+ return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
}
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 9cc6e00..0c6fb24 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -14,6 +14,7 @@
import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrame;
@@ -38,7 +39,6 @@
private final IRTreeFrameFactory leafFrameFactory;
private final MultiComparator interiorCmp;
private final MultiComparator leafCmp;
- public final int dim;
public int rootSplits = 0;
public int[] splitsByLevel = new int[500];
@@ -51,14 +51,13 @@
public byte currentLevel = 0;
public RTree(IBufferCache bufferCache, IFreePageManager freePageManager, IRTreeFrameFactory interiorFrameFactory,
- IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp, int dim) {
+ IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp) {
this.bufferCache = bufferCache;
this.freePageManager = freePageManager;
this.interiorFrameFactory = interiorFrameFactory;
this.leafFrameFactory = leafFrameFactory;
this.interiorCmp = interiorCmp;
this.leafCmp = leafCmp;
- this.dim = dim;
globalNsn = new AtomicInteger();
this.treeLatch = new ReentrantReadWriteLock(true);
}
@@ -169,7 +168,7 @@
incrementReadLatchesReleased();
bufferCache.unpin(node);
incrementUnpins();
- e.printStackTrace();
+ throw e;
}
}
@@ -220,7 +219,8 @@
public RTreeOpContext createOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
ITreeIndexMetaDataFrame metaFrame, String threadName) {
// TODO: figure out better tree-height hint
- return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, dim, threadName);
+ return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, interiorCmp.getKeyFieldCount() / 2,
+ threadName);
}
public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
@@ -821,6 +821,16 @@
}
}
+ public void search(IRTreeCursor cursor, ITupleReference searchKey, RTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.tuple = searchKey;
+ ctx.cursor = cursor;
+
+ cursor.setBufferCache(bufferCache);
+ cursor.setFileId(fileId);
+ ctx.cursor.open(ctx.pathList, ctx.tuple, rootPage, interiorCmp, leafCmp);
+ }
+
public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
throws Exception {
ctx.reset();
@@ -857,7 +867,7 @@
// check intersection, if intersect, add the tuple to
// the
// result set
- Rectangle rec = ctx.leafFrame.intersect(ctx.tuple, i, leafCmp);
+ Rectangle rec = ctx.leafFrame.checkIntersect(ctx.tuple, i, leafCmp);
if (rec != null) {
// add the tuple to the result set
results.add(rec);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index 0faea4e..91a2e24 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -3,12 +3,14 @@
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
public final class RTreeOpContext {
public final TreeIndexOp op;
public final IRTreeFrame interiorFrame;
public final IRTreeFrame leafFrame;
+ public IRTreeCursor cursor;
public final ITreeIndexMetaDataFrame metaFrame;
public final RTreeSplitKey splitKey;
public final SpatialUtils spatialUtils;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java
new file mode 100644
index 0000000..f8ad9ca
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchCursor.java
@@ -0,0 +1,173 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class SearchCursor implements IRTreeCursor {
+
+ private int fileId = -1;
+ private ICachedPage page = null;
+ private IRTreeFrame interiorFrame = null;
+ private IRTreeFrame leafFrame = null;
+ private IBufferCache bufferCache = null;
+
+ private PathList pathList;
+ private int rootPage;
+ ITupleReference searchKey;
+
+ private int tupleIndex = 0;
+ private int tupleIndexInc = 0;
+
+ private MultiComparator leafCmp;
+ private MultiComparator interiorCmp;
+
+ private ITreeIndexTupleReference frameTuple;
+
+ private int pin = 0;
+ private int unpin = 0;
+
+ public SearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
+ this.interiorFrame = interiorFrame;
+ this.leafFrame = leafFrame;
+ this.frameTuple = leafFrame.createTupleReference();
+ }
+
+ @Override
+ public void close() throws Exception {
+ if (page != null) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+ tupleIndex = 0;
+ tupleIndexInc = 0;
+ page = null;
+ pathList.clear();
+ }
+
+ public ITupleReference getTuple() {
+ return frameTuple;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return page;
+ }
+
+ public boolean fetchNextLeafPage() throws HyracksDataException {
+ while (!pathList.isEmpty()) {
+ int pageId = pathList.getLastPageId();
+ int parentLsn = pathList.getLastPageLsn();
+ pathList.removeLast();
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pin++;
+ node.acquireReadLatch();
+ interiorFrame.setPage(node);
+ boolean isLeaf = interiorFrame.isLeaf();
+ int pageLsn = interiorFrame.getPageLsn();
+
+ if (pageId != rootPage && parentLsn < interiorFrame.getPageNsn()) {
+ // Concurrent split detected, we need to visit the right page
+ int rightPage = interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ pathList.add(rightPage, parentLsn, -1);
+ }
+ }
+
+ if (!isLeaf) {
+ for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+ int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, interiorCmp);
+ if (childPageId != -1) {
+ pathList.add(childPageId, pageLsn, -1);
+ }
+ }
+ } else {
+ if (page != null) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ unpin++;
+ }
+ page = node;
+ leafFrame.setPage(page);
+ tupleIndex = 0;
+ return true;
+ }
+ node.releaseReadLatch();
+ bufferCache.unpin(node);
+ unpin++;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean hasNext() throws Exception {
+ if (tupleIndex == leafFrame.getTupleCount()) {
+ if (!fetchNextLeafPage()) {
+ return false;
+ }
+ }
+
+ do {
+ for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
+ if (leafFrame.intersect(searchKey, i, leafCmp)) {
+ frameTuple.resetByTupleIndex(leafFrame, i);
+ tupleIndexInc = i + 1;
+ return true;
+ }
+ }
+ } while (fetchNextLeafPage());
+ return false;
+ }
+
+ @Override
+ public void next() throws Exception {
+ tupleIndex = tupleIndexInc;
+ }
+
+ @Override
+ public void open(PathList pathList, ITupleReference searchKey, int rootPage, MultiComparator interiorCmp,
+ MultiComparator leafCmp) throws Exception {
+ // in case open is called multiple times without closing
+ if (this.page != null) {
+ this.page.releaseReadLatch();
+ bufferCache.unpin(this.page);
+ this.pathList.clear();
+ }
+
+ this.pathList = pathList;
+ this.searchKey = searchKey;
+ this.rootPage = rootPage;
+ this.interiorCmp = interiorCmp;
+ this.leafCmp = leafCmp;
+
+ this.pathList.add(this.rootPage, -1, -1);
+ frameTuple.setFieldCount(this.leafCmp.getFieldCount());
+ tupleIndex = 0;
+ fetchNextLeafPage();
+ }
+
+ @Override
+ public void reset() {
+ try {
+ close();
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ this.bufferCache = bufferCache;
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ this.fileId = fileId;
+ }
+}
\ No newline at end of file
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
index 36d4988..2090bb2 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -2,12 +2,12 @@
<modelVersion>4.0.0</modelVersion>
<groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-storage-am-rtree-test</artifactId>
- <version>0.1.4</version>
+ <version>0.1.5</version>
<parent>
<groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-tests</artifactId>
- <version>0.1.4</version>
+ <version>0.1.5</version>
</parent>
<build>
@@ -40,14 +40,14 @@
<dependency>
<groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-storage-am-rtree</artifactId>
- <version>0.1.4</version>
+ <version>0.1.5</version>
<type>jar</type>
<scope>compile</scope>
</dependency>
<dependency>
<groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-test-support</artifactId>
- <version>0.1.4</version>
+ <version>0.1.5</version>
<type>jar</type>
<scope>test</scope>
</dependency>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
deleted file mode 100644
index f93a6b6..0000000
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
+++ /dev/null
@@ -1,133 +0,0 @@
-/*
- * package edu.uci.ics.hyracks.storage.am.rtree;
- *
- * import java.io.DataOutput; import java.io.File; import java.nio.ByteBuffer;
- * import java.util.Random;
- *
- * import org.junit.Test;
- *
- * import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor; import
- * edu.uci.ics.hyracks.api.context.IHyracksStageletContext; import
- * edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator; import
- * edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer; import
- * edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait; import
- * edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor; import
- * edu.uci.ics.hyracks.api.dataflow.value.TypeTrait; import
- * edu.uci.ics.hyracks.api.io.FileReference; import
- * edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder; import
- * edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor; import
- * edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender; import
- * edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
- * import edu.uci.ics.hyracks.dataflow.common.data.comparators.
- * DoubleBinaryComparatorFactory; import
- * edu.uci.ics.hyracks.dataflow.common.data
- * .marshalling.DoubleSerializerDeserializer; import
- * edu.uci.ics.hyracks.dataflow
- * .common.data.marshalling.IntegerSerializerDeserializer; import
- * edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator; import
- * edu.uci.ics.hyracks.storage.am.btree.impls.SpaceStatus; import
- * edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriter; import
- * edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrame; import
- * edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache; import
- * edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage; import
- * edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle; import
- * edu.uci.ics.hyracks.storage.common.file.IFileMapProvider; import
- * edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder; import
- * edu.uci.ics.hyracks.test.support.TestUtils;
- *
- * public class RTreeFrameTest extends AbstractRTreeTest {
- *
- * private static final int PAGE_SIZE = 256; private static final int NUM_PAGES
- * = 10; private static final int HYRACKS_FRAME_SIZE = 128; private
- * IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
- *
- * private String tmpDir = System.getProperty("java.io.tmpdir");
- *
- * @Test public void frameInsertTest() throws Exception {
- *
- * TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES); IBufferCache
- * bufferCache = TestStorageManagerComponentHolder .getBufferCache(ctx);
- * IFileMapProvider fmp = TestStorageManagerComponentHolder
- * .getFileMapProvider(ctx); FileReference file = new FileReference(new
- * File(fileName)); bufferCache.createFile(file); int fileId =
- * fmp.lookupFileId(file); bufferCache.openFile(fileId);
- *
- * // declare fields int fieldCount = 5; ITypeTrait[] typeTraits = new
- * ITypeTrait[fieldCount]; typeTraits[0] = new TypeTrait(8); typeTraits[1] = new
- * TypeTrait(8); typeTraits[2] = new TypeTrait(8); typeTraits[3] = new
- * TypeTrait(8); typeTraits[4] = new TypeTrait(4);
- *
- * // declare keys int keyFieldCount = 4; IBinaryComparator[] cmps = new
- * IBinaryComparator[keyFieldCount]; cmps[0] =
- * DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator(); cmps[1] =
- * cmps[0]; cmps[2] = cmps[0]; cmps[3] = cmps[0];
- *
- * MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- *
- * TypeAwareTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
- * //SimpleTupleWriter tupleWriter = new SimpleTupleWriter(); NSMRTreeFrame
- * rtreeFrame = new NSMRTreeFrame(tupleWriter);
- *
- * ByteBuffer hyracksFrame = ctx.allocateFrame(); FrameTupleAppender appender =
- * new FrameTupleAppender(ctx.getFrameSize()); ArrayTupleBuilder tb = new
- * ArrayTupleBuilder(cmp.getFieldCount()); DataOutput dos = tb.getDataOutput();
- *
- * ISerializerDeserializer[] recDescSers = {
- * DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- * DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- * DoubleSerializerDeserializer.INSTANCE }; RecordDescriptor recDesc = new
- * RecordDescriptor(recDescSers); IFrameTupleAccessor accessor = new
- * FrameTupleAccessor(ctx .getFrameSize(), recDesc); FrameTupleReference tuple =
- * new FrameTupleReference();
- *
- * ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId,
- * 0), true); try {
- *
- * rtreeFrame.setPage(page); rtreeFrame.initBuffer((byte)0);
- *
- * // insert some random stuff...
- *
- * Random rnd = new Random(50);
- *
- * int numInserts = 10; for (int i = 0; i < numInserts; i++) { double p1x =
- * rnd.nextDouble(); double p1y = rnd.nextDouble(); double p2x =
- * rnd.nextDouble(); double p2y = rnd.nextDouble();
- *
- * int pk = rnd.nextInt();
- *
- * tb.reset(); DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- * tb.addFieldEndOffset(); DoubleSerializerDeserializer.INSTANCE.serialize(p1y,
- * dos); tb.addFieldEndOffset();
- * DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- * tb.addFieldEndOffset(); DoubleSerializerDeserializer.INSTANCE.serialize(p2y,
- * dos); tb.addFieldEndOffset();
- * IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- * tb.addFieldEndOffset();
- *
- * appender.reset(hyracksFrame, true); appender.append(tb.getFieldEndOffsets(),
- * tb.getByteArray(), 0, tb.getSize());
- *
- * tuple.reset(accessor, 0);
- *
- * SpaceStatus status = rtreeFrame.hasSpaceInsert(tuple, cmp); switch(status) {
- * case SUFFICIENT_CONTIGUOUS_SPACE: { rtreeFrame.insert(tuple, cmp); break; }
- *
- * case SUFFICIENT_SPACE: { rtreeFrame.compact(cmp); rtreeFrame.insert(tuple,
- * cmp); break; }
- *
- * case INSUFFICIENT_SPACE: { // split
- * System.out.println("PLEASE STOP, NO MORE SPACE"); break; } }
- *
- *
- *
- * String contents = rtreeFrame.printKeys(cmp, recDescSers);
- * System.out.println(contents);
- *
- * } } finally { bufferCache.unpin(page); }
- *
- * bufferCache.closeFile(fileId); bufferCache.close();
- *
- * }
- *
- * }
- */
\ No newline at end of file
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index 815ef19..b105588 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -53,7 +53,7 @@
private static final int HYRACKS_FRAME_SIZE = 128;
private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
- @Test
+ @Test
public void test01() throws Exception {
TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
@@ -97,8 +97,8 @@
interiorTypeTraits);
RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
- IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory);
- IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+ IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+ IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
@@ -106,9 +106,8 @@
IRTreeFrame leafFrame = leafFrameFactory.getFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- int dim = 2;
RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
- leafCmp, dim);
+ leafCmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
@@ -126,7 +125,8 @@
accessor.reset(hyracksFrame);
FrameTupleReference tuple = new FrameTupleReference();
- RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame, "unittest");
+ RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+ "unittest");
Random rnd = new Random();
rnd.setSeed(50);
@@ -172,7 +172,8 @@
// rtree.printTree(leafFrame, interiorFrame, recDescSers);
// System.out.println();
- RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame, "unittest");
+ RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+ "unittest");
ArrayList<Rectangle> results = new ArrayList<Rectangle>();
rtree.search(s, tuple, searchOpCtx, results);
@@ -194,7 +195,7 @@
}
- //@Test
+ // @Test
public void test02() throws Exception {
TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
@@ -238,8 +239,8 @@
interiorTypeTraits);
RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
- IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory);
- IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+ IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+ IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
@@ -247,9 +248,8 @@
IRTreeFrame leafFrame = leafFrameFactory.getFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- int dim = 2;
RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
- leafCmp, dim);
+ leafCmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
@@ -267,7 +267,8 @@
accessor.reset(hyracksFrame);
FrameTupleReference tuple = new FrameTupleReference();
- RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame, "unittest");
+ RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+ "unittest");
File datasetFile = new File("/home/salsubaiee/dataset.txt");
BufferedReader reader = new BufferedReader(new FileReader(datasetFile));
@@ -284,7 +285,7 @@
double p1x = 0;
double p1y = 0;
-
+
try {
p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
@@ -294,7 +295,6 @@
}
double p2x = p1x;
double p2y = p1y;
-
int pk = rnd.nextInt();
@@ -325,21 +325,22 @@
} catch (Exception e) {
e.printStackTrace();
}
-
+
if (index == 1000) {
break;
}
inputLine = reader.readLine();
index++;
-// rtree.printTree(leafFrame, interiorFrame, recDescSers);
-// System.out.println();
+ // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+ // System.out.println();
}
- //rtree.printTree(leafFrame, interiorFrame, recDescSers);
- //System.out.println();
+ // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+ // System.out.println();
- RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame, "unittest");
+ RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+ "unittest");
File querysetFile = new File("/home/salsubaiee/queryset.txt");
BufferedReader reader2 = new BufferedReader(new FileReader(querysetFile));
@@ -353,7 +354,6 @@
String[] splittedLine1 = inputLine.split(",");
String[] splittedLine2 = splittedLine1[0].split("\\s");
-
double p1x;
double p1y;
double p2x;
@@ -368,7 +368,7 @@
inputLine = reader2.readLine();
continue;
}
-
+
int pk = rnd.nextInt();
tb.reset();
@@ -408,16 +408,12 @@
System.out.println("Number of Results: " + totalResults);
-// String stats = rtree.printStats();
-// print(stats);
-
-
-
-
-
- RTreeOpContext deleteOpCtx = rtree.createOpContext(TreeIndexOp.TI_DELETE, interiorFrame, leafFrame, metaFrame, "unittest");
+ // String stats = rtree.printStats();
+ // print(stats);
-
+ RTreeOpContext deleteOpCtx = rtree.createOpContext(TreeIndexOp.TI_DELETE, interiorFrame, leafFrame, metaFrame,
+ "unittest");
+
BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
inputLine = reader3.readLine();
index = 0;
@@ -429,7 +425,7 @@
double p1x = 0;
double p1y = 0;
-
+
try {
p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
@@ -468,22 +464,17 @@
} catch (Exception e) {
e.printStackTrace();
}
-
+
if (index == 1000) {
break;
}
inputLine = reader3.readLine();
index++;
-// rtree.printTree(leafFrame, interiorFrame, recDescSers);
-// System.out.println();
+ // rtree.printTree(leafFrame, interiorFrame, recDescSers);
+ // System.out.println();
}
-
-
-
-
-
-
+
BufferedReader reader4 = new BufferedReader(new FileReader(querysetFile));
inputLine = reader4.readLine();
@@ -538,19 +529,12 @@
System.out.println("Number of Results: " + totalResults);
-// stats = rtree.printStats();
-// print(stats);
-
-
-
-
-
+ // stats = rtree.printStats();
+ // print(stats);
+
rtree.printTree(leafFrame, interiorFrame, recDescSers);
System.out.println();
-
-
-
rtree.close();
bufferCache.closeFile(fileId);
bufferCache.close();
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
new file mode 100644
index 0000000..a5f0594
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -0,0 +1,198 @@
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Random;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class SearchCursorTest extends AbstractRTreeTest {
+ private static final int PAGE_SIZE = 256;
+ private static final int NUM_PAGES = 10;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+ private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ @Test
+ public void searchCursorTest() throws Exception {
+
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+
+ // declare interior-frame-tuple fields
+ int interiorFieldCount = 5;
+ ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
+ interiorTypeTraits[0] = new TypeTrait(8);
+ interiorTypeTraits[1] = new TypeTrait(8);
+ interiorTypeTraits[2] = new TypeTrait(8);
+ interiorTypeTraits[3] = new TypeTrait(8);
+ interiorTypeTraits[4] = new TypeTrait(4);
+
+ // declare keys
+ int keyFieldCount = 4;
+ IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+ cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+ cmps[1] = cmps[0];
+ cmps[2] = cmps[0];
+ cmps[3] = cmps[0];
+
+ // declare leaf-frame-tuple fields
+ int leafFieldCount = 5;
+ ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
+ leafTypeTraits[0] = new TypeTrait(8);
+ leafTypeTraits[1] = new TypeTrait(8);
+ leafTypeTraits[2] = new TypeTrait(8);
+ leafTypeTraits[3] = new TypeTrait(8);
+ leafTypeTraits[4] = new TypeTrait(4);
+
+ MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
+ MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+
+ RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
+ interiorTypeTraits);
+ RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+
+ IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
+ IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory, keyFieldCount);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+
+ IRTreeFrame interiorFrame = interiorFrameFactory.getFrame();
+ IRTreeFrame leafFrame = leafFrameFactory.getFrame();
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+
+ RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
+ leafCmp);
+ rtree.create(fileId, leafFrame, metaFrame);
+ rtree.open(fileId);
+
+ ByteBuffer hyracksFrame = ctx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+ DataOutput dos = tb.getDataOutput();
+
+ @SuppressWarnings("rawtypes")
+ ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+ RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+ accessor.reset(hyracksFrame);
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ RTreeOpContext insertOpCtx = rtree.createOpContext(TreeIndexOp.TI_INSERT, interiorFrame, leafFrame, metaFrame,
+ "unittest");
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+ for (int i = 0; i < 10000; i++) {
+
+ double p1x = rnd.nextDouble();
+ double p1y = rnd.nextDouble();
+ double p2x = rnd.nextDouble();
+ double p2y = rnd.nextDouble();
+
+ int pk = rnd.nextInt();
+
+ tb.reset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(hyracksFrame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ print("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
+ + " " + Math.max(p1y, p2y) + "\n");
+
+ try {
+ rtree.insert(tuple, insertOpCtx);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ }
+
+ IRTreeCursor searchCursor = new SearchCursor(interiorFrame, leafFrame);
+ RTreeOpContext searchOpCtx = rtree.createOpContext(TreeIndexOp.TI_SEARCH, interiorFrame, leafFrame, metaFrame,
+ "cursortest");
+ rtree.search(searchCursor, tuple, searchOpCtx);
+
+ ArrayList<Integer> results = new ArrayList<Integer>();
+ try {
+ while (searchCursor.hasNext()) {
+ searchCursor.next();
+ ITupleReference frameTuple = searchCursor.getTuple();
+ ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(0),
+ frameTuple.getFieldStart(0), frameTuple.getFieldLength(0));
+ DataInput dataIn = new DataInputStream(inStream);
+ Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+ results.add(res);
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ searchCursor.close();
+ }
+
+ rtree.close();
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+ }
+}
diff --git a/hyracks-tests/pom.xml b/hyracks-tests/pom.xml
index 64b150f..a4d2c04 100644
--- a/hyracks-tests/pom.xml
+++ b/hyracks-tests/pom.xml
@@ -14,5 +14,6 @@
<modules>
<module>hyracks-storage-am-btree-test</module>
<module>hyracks-storage-am-invertedindex-test</module>
+ <module>hyracks-storage-am-rtree-test</module>
</modules>
</project>
diff --git a/pom.xml b/pom.xml
index e4ba074..643f2d1 100644
--- a/pom.xml
+++ b/pom.xml
@@ -64,6 +64,7 @@
<module>hyracks-storage-am-common</module>
<module>hyracks-storage-am-btree</module>
<module>hyracks-storage-am-invertedindex</module>
+ <module>hyracks-storage-am-rtree</module>
<module>hyracks-test-support</module>
<module>hyracks-tests</module>
<module>hyracks-server</module>