Added the r-tree package
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@376 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-rtree/.project b/hyracks-storage-am-rtree/.project
new file mode 100644
index 0000000..4989318
--- /dev/null
+++ b/hyracks-storage-am-rtree/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+ <name>hyracks-storage-am-rtree</name>
+ <comment></comment>
+ <projects>
+ </projects>
+ <buildSpec>
+ <buildCommand>
+ <name>org.eclipse.jdt.core.javabuilder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ <buildCommand>
+ <name>org.maven.ide.eclipse.maven2Builder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ </buildSpec>
+ <natures>
+ <nature>org.eclipse.jdt.core.javanature</nature>
+ <nature>org.maven.ide.eclipse.maven2Nature</nature>
+ </natures>
+</projectDescription>
diff --git a/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs b/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..6884501
--- /dev/null
+++ b/hyracks-storage-am-rtree/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Wed Feb 02 19:49:23 PST 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs b/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..ba4f536
--- /dev/null
+++ b/hyracks-storage-am-rtree/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,9 @@
+#Wed Feb 02 19:49:19 PST 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+includeModules=false
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks-storage-am-rtree/pom.xml b/hyracks-storage-am-rtree/pom.xml
new file mode 100644
index 0000000..d0c48c1
--- /dev/null
+++ b/hyracks-storage-am-rtree/pom.xml
@@ -0,0 +1,70 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree</artifactId>
+ <version>0.1.4</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.1.4</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-common</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-dataflow-common</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-dataflow-std</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-control-nc</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-btree</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
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
new file mode 100644
index 0000000..6cfa40e
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -0,0 +1,19 @@
+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.api.ITreeIndexFrame;
+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.impls.RTreeSplitKey;
+
+public interface IRTreeFrame extends ITreeIndexFrame {
+
+ public int getChildPageId(ITupleReference tuple, MultiComparator cmp);
+
+ public int split(IRTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, RTreeSplitKey leftSplitKey,
+ RTreeSplitKey rightSplitKey) throws Exception;
+
+ public void adjustNode(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
+
+ public void adjustTuple(ITupleReference tuple, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java
new file mode 100644
index 0000000..177c8a1
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrameFactory.java
@@ -0,0 +1,22 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import java.io.Serializable;
+
+public interface IRTreeFrameFactory extends Serializable {
+ public IRTreeFrame getFrame();
+}
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
new file mode 100644
index 0000000..61af92b
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -0,0 +1,292 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+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.ISplitKey;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.frames.TreeIndexNSMFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMRTreeFrame extends TreeIndexNSMFrame implements IRTreeFrame {
+
+ public ITreeIndexTupleReference[] tuples;
+ private final IBinaryComparator intComp = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+
+ public NSMRTreeFrame(ITreeIndexTupleWriter tupleWriter) {
+ super(tupleWriter, new UnorderedSlotManager());
+ this.tuples = new ITreeIndexTupleReference[4]; // change this to number
+ // of dim * 2
+ for (int i = 0; i < 4; i++) {
+ this.tuples[i] = tupleWriter.createTupleReference();
+ }
+ }
+
+ public ITreeIndexTupleReference[] getTuples() {
+ return tuples;
+ }
+
+ public void setTuples(ITreeIndexTupleReference[] tuples) {
+ this.tuples = tuples;
+ }
+
+ // for debugging
+ public ArrayList<Integer> getChildren(MultiComparator cmp) {
+ ArrayList<Integer> ret = new ArrayList<Integer>();
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ int tupleCount = buf.getInt(tupleCountOff);
+ for (int i = 0; i < tupleCount; i++) {
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+
+ int intVal = IntegerSerializerDeserializer.getInt(
+ buf.array(),
+ frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+ + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1));
+ ret.add(intVal);
+ }
+ return ret;
+ }
+
+ @Override
+ public int split(IRTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, RTreeSplitKey leftSplitKey,
+ RTreeSplitKey rightSplitKey) throws Exception {
+
+ 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;
+ IRTreeFrame 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());
+ leftSplitKey.initData(splitKeySize);
+ this.adjustNode(tuples, cmp);
+ rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, leftSplitKey.getBuffer(), 0);
+ leftSplitKey.getTuple().resetByTupleOffset(leftSplitKey.getBuffer(), 0);
+
+ rightSplitKey.initData(splitKeySize);
+ rightFrame.adjustNode(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
+ rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame) rightFrame).getTuples(), 0, rightSplitKey.getBuffer(), 0);
+ rightSplitKey.getTuple().resetByTupleOffset(rightSplitKey.getBuffer(), 0);
+
+ return 0;
+ }
+
+ @Override
+ public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+ try {
+ insert(tuple, cmp);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ @Override
+ public int getChildPageId(ITupleReference tuple, MultiComparator cmp) {
+ // find least overlap enlargement, use minimum enlarged area to
+ // break tie, if tie still exists use minimum area to break it
+
+ int bestChild = 0;
+ double minEnlargedArea = Double.MAX_VALUE;
+
+ // if (getLevel() == 1) {
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+ if (enlargedArea < minEnlargedArea) {
+ minEnlargedArea = enlargedArea;
+ bestChild = i;
+ }
+
+ else if (enlargedArea == minEnlargedArea) {
+ double area = area(frameTuple, cmp);
+ frameTuple.resetByTupleIndex(this, bestChild);
+ double bestArea = area(frameTuple, cmp);
+ if (area < bestArea) {
+ bestChild = i;
+ }
+ }
+ }
+ // } else { // find minimum enlarged area, use minimum area to break
+ // tie
+
+ // }
+ frameTuple.resetByTupleIndex(this, bestChild);
+ if (minEnlargedArea > 0.0) {
+ enlarge(frameTuple, tuple, cmp);
+ }
+
+ // return the page id of the bestChild tuple
+ return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+ }
+
+ public double area(ITupleReference tuple, MultiComparator cmp) {
+ double area = 1.0;
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ area *= DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j))
+ - DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ }
+ return area;
+ }
+
+ public double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+ double areaBeforeEnlarge = area(tuple, cmp);
+ double areaAfterEnlarge = 1.0;
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ double pHigh, pLow;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+ tupleToBeInserted.getFieldLength(i));
+ if (c < 0) {
+ pLow = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ } else {
+ pLow = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
+ tupleToBeInserted.getFieldStart(i));
+ }
+
+ c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+ tupleToBeInserted.getFieldLength(j));
+ if (c > 0) {
+ pHigh = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
+ } else {
+ pHigh = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
+ tupleToBeInserted.getFieldStart(j));
+ }
+ areaAfterEnlarge *= pHigh - pLow;
+ }
+ return areaAfterEnlarge - areaBeforeEnlarge;
+ }
+
+ public void enlarge(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+ 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), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+ tupleToBeInserted.getFieldLength(i));
+ if (c > 0) {
+ System.arraycopy(tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+ tuple.getFieldData(i), tuple.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
+ }
+ c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+ tupleToBeInserted.getFieldLength(j));
+ if (c < 0) {
+ System.arraycopy(tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+ tuple.getFieldData(j), tuple.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
+ }
+ }
+ }
+
+ @Override
+ public void adjustTuple(ITupleReference tuple, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+
+ int c = intComp.compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+ frameTuple.getFieldStart(cmp.getKeyFieldCount()),
+ frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
+ tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
+ if (c == 0) {
+ tupleWriter.writeTuple(tuple, buf, getTupleOffset(i));
+ break;
+ }
+ }
+ }
+
+ @Override
+ public void adjustNode(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+ for (int i = 0; i < tuples.length; i++) {
+ tuples[i].setFieldCount(cmp.getKeyFieldCount());
+ tuples[i].resetByTupleIndex(this, 0);
+ }
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 1; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ int c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j), tuples[j].getFieldData(j), tuples[j].getFieldStart(j),
+ tuples[j].getFieldLength(j));
+ if (c < 0) {
+ tuples[j].resetByTupleIndex(this, i);
+ }
+ c = cmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
+ frameTuple.getFieldLength(k), tuples[k].getFieldData(k), tuples[k].getFieldStart(k),
+ tuples[k].getFieldLength(k));
+ if (c > 0) {
+ tuples[k].resetByTupleIndex(this, i);
+ }
+ }
+ }
+ }
+
+ @Override
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+ throws Exception {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+}
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
new file mode 100644
index 0000000..729bf36
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrameFactory.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
+
+public class NSMRTreeFrameFactory implements IRTreeFrameFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITreeIndexTupleWriterFactory tupleWriterFactory;
+
+ public NSMRTreeFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory) {
+ this.tupleWriterFactory = tupleWriterFactory;
+ }
+
+ @Override
+ public IRTreeFrame getFrame() {
+ return new NSMRTreeFrame(tupleWriterFactory.createTupleWriter());
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
new file mode 100644
index 0000000..7fa5ba4
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
@@ -0,0 +1,49 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+public class ByteArrayList {
+ private byte[] data;
+ private int size;
+ private final int growth;
+
+ public ByteArrayList(int initialCapacity, int growth) {
+ data = new byte[initialCapacity];
+ size = 0;
+ this.growth = growth;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public void add(byte i) {
+ if (size == data.length) {
+ byte[] newData = new byte[data.length + growth];
+ System.arraycopy(data, 0, newData, 0, data.length);
+ data = newData;
+ }
+
+ data[size++] = i;
+ }
+
+ public void removeLast() {
+ if (size > 0)
+ size--;
+ }
+
+ // WARNING: caller is responsible for checking size > 0
+ public int getLast() {
+ return data[size - 1];
+ }
+
+ public int get(int i) {
+ return data[i];
+ }
+
+ public void clear() {
+ size = 0;
+ }
+
+ public boolean isEmpty() {
+ return size == 0;
+ }
+}
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
new file mode 100644
index 0000000..ca7404a
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -0,0 +1,374 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+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.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.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
+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;
+
+public class RTree {
+
+ private boolean created = false;
+ private final int metaDataPage = 0; // page containing meta data, e.g.,
+ // maxPage
+ private final int rootPage = 1; // the root page never changes
+
+ private final IFreePageManager freePageManager;
+ private final IBufferCache bufferCache;
+ private int fileId;
+
+ private final IRTreeFrameFactory interiorFrameFactory;
+ private final IRTreeFrameFactory leafFrameFactory;
+ private final MultiComparator interiorCmp;
+ private final MultiComparator leafCmp;
+
+ public long pins = 0;
+ public long unpins = 0;
+ public byte currentLevel = 0;
+
+ public RTree(IBufferCache bufferCache, IFreePageManager freePageManager, IRTreeFrameFactory interiorFrameFactory,
+ IRTreeFrameFactory leafFrameFactory, MultiComparator interiorCmp, MultiComparator leafCmp) {
+ this.bufferCache = bufferCache;
+ this.freePageManager = freePageManager;
+ this.interiorFrameFactory = interiorFrameFactory;
+ this.leafFrameFactory = leafFrameFactory;
+ this.interiorCmp = interiorCmp;
+ this.leafCmp = leafCmp;
+ }
+
+ public void printTree(IRTreeFrame leafFrame, IRTreeFrame interiorFrame, ISerializerDeserializer[] fields)
+ throws Exception {
+ printTree(rootPage, null, false, leafFrame, interiorFrame, fields);
+ }
+
+ public void printTree(int pageId, ICachedPage parent, boolean unpin, IRTreeFrame leafFrame,
+ IRTreeFrame interiorFrame, ISerializerDeserializer[] fields) throws Exception {
+
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+
+ try {
+ if (parent != null && unpin == true) {
+ bufferCache.unpin(parent);
+ unpins++;
+ }
+
+ interiorFrame.setPage(node);
+ int level = interiorFrame.getLevel();
+
+ System.out.format("%1d ", level);
+ System.out.format("%3d ", pageId);
+ for (int i = 0; i < currentLevel - level; i++)
+ System.out.format(" ");
+
+ String keyString;
+ if (interiorFrame.isLeaf()) {
+ leafFrame.setPage(node);
+ keyString = leafFrame.printKeys(leafCmp, fields);
+ } else {
+ keyString = interiorFrame.printKeys(interiorCmp, fields);
+ }
+
+ System.out.format(keyString);
+ if (!interiorFrame.isLeaf()) {
+ ArrayList<Integer> children = ((NSMRTreeFrame) (interiorFrame)).getChildren(interiorCmp);
+
+ //System.out.println("num of children for page id " + pageId + " is: "+ children.size());
+ for (int i = 0; i < children.size(); i++) {
+ printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, fields);
+ }
+ //System.out.println();
+ } else {
+ bufferCache.unpin(node);
+ unpins++;
+ }
+ } catch (Exception e) {
+ bufferCache.unpin(node);
+ unpins++;
+ e.printStackTrace();
+ }
+ }
+
+ public void create(int fileId, IRTreeFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception {
+ if (created)
+ return;
+
+ // initialize meta data page
+ ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
+ pins++;
+
+ metaNode.acquireWriteLatch();
+ try {
+ metaFrame.setPage(metaNode);
+ metaFrame.initBuffer((byte) -1);
+ metaFrame.setMaxPage(rootPage);
+ } finally {
+ bufferCache.unpin(metaNode);
+ unpins++;
+ }
+
+ // initialize root page
+ ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
+ pins++;
+
+ try {
+ leafFrame.setPage(rootNode);
+ leafFrame.initBuffer((byte) 0);
+ } finally {
+ bufferCache.unpin(rootNode);
+ unpins++;
+ }
+ currentLevel = 0;
+ created = true;
+ }
+
+ public void open(int fileId) {
+ this.fileId = fileId;
+ }
+
+ public void close() {
+ fileId = -1;
+ }
+
+ public RTreeOpContext createOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+ ITreeIndexMetaDataFrame metaFrame) {
+ // TODO: figure out better tree-height hint
+ return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 6);
+ }
+
+ private void createNewRoot(RTreeOpContext ctx) throws Exception {
+ currentLevel++;
+
+ // make sure the root is always at the same level
+ ICachedPage leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, ctx.leftSplitKey.getPage()),
+ false);
+ pins++;
+ try {
+ ICachedPage rightNode = bufferCache.pin(
+ BufferedFileHandle.getDiskPageId(fileId, ctx.rightSplitKey.getPage()), false);
+ pins++;
+ try {
+ int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
+ ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
+ pins++;
+ try {
+ // copy left child to new left child
+ System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
+ .getBuffer().capacity());
+
+ // initialize new root (leftNode becomes new root)
+ ctx.interiorFrame.setPage(leftNode);
+ ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
+
+ ctx.leftSplitKey.setPage(newLeftId);
+
+ ctx.interiorFrame.insert(ctx.leftSplitKey.getTuple(), interiorCmp);
+ ctx.interiorFrame.insert(ctx.rightSplitKey.getTuple(), interiorCmp);
+
+ //System.out.println("R Created page id: " + newLeftId + "level: " + ctx.interiorFrame.getLevel());
+
+ System.out.println("Created new root");
+
+ } finally {
+ bufferCache.unpin(newLeftNode);
+ unpins++;
+ }
+ } finally {
+ bufferCache.unpin(rightNode);
+ unpins++;
+ }
+ } finally {
+ bufferCache.unpin(leftNode);
+ unpins++;
+ }
+ }
+
+ public int temp = 0;
+
+ public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.setTuple(tuple);
+ ctx.leftSplitKey.reset();
+ ctx.rightSplitKey.reset();
+ ctx.leftSplitKey.getTuple().setFieldCount(interiorCmp.getFieldCount());
+ ctx.rightSplitKey.getTuple().setFieldCount(interiorCmp.getFieldCount());
+ ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+ temp++;
+ insertImpl(rootPage, null, (byte) 0, ctx);
+
+ // we split the root, here is the key for a new root
+ if (ctx.leftSplitKey.getBuffer() != null && ctx.rightSplitKey.getBuffer() != null) {
+ createNewRoot(ctx);
+ }
+ }
+
+ public void insertImpl(int pageId, ICachedPage parent, byte desiredLevel, RTreeOpContext ctx) throws Exception {
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+ ctx.interiorFrame.setPage(node);
+
+ // latch coupling TODO: check the correctness of this
+ if (parent != null) {
+ bufferCache.unpin(parent);
+ unpins++;
+ }
+ if (temp >= 36) {
+ //System.out.println("HHHHHHHHHHHHHH");
+ }
+ boolean isLeaf = ctx.interiorFrame.isLeaf();
+ //System.out.println("level: " + ctx.interiorFrame.getLevel());
+ // the children pointers in the node point to leaves
+ if (ctx.interiorFrame.getLevel() > desiredLevel) {
+ int childPageId = ctx.interiorFrame.getChildPageId(ctx.getTuple(), interiorCmp);
+ //System.out.println("PAGE ID: " + childPageId);
+ insertImpl(childPageId, node, desiredLevel, ctx);
+
+ if (ctx.leftSplitKey.getBuffer() != null && ctx.rightSplitKey.getBuffer() != null) { // TODO:
+ // checking
+ // one
+ // is
+ // enough?
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+ try {
+ ctx.interiorFrame.setPage(node);
+ ctx.interiorFrame.adjustTuple(ctx.leftSplitKey.getTuple(), interiorCmp);
+ insertTuple(pageId, ctx.rightSplitKey.getTuple(), ctx, isLeaf);
+ // RTreeSplitKey splitKey =
+ // ctx.rightSplitKey.duplicate(ctx.interiorFrame.getTupleWriter().createTupleReference());
+ // insertTuple(pageId, splitKey.getTuple(), ctx, isLeaf);
+ } finally {
+ bufferCache.unpin(node);
+ unpins++;
+ }
+ }
+ } else {
+ try {
+ if (isLeaf) {
+ ctx.leafFrame.setPage(node);
+ ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+ }
+ insertTuple(pageId, ctx.getTuple(), ctx, isLeaf);
+ } finally {
+ bufferCache.unpin(node);
+ unpins++;
+ }
+ }
+ }
+
+ private void insertTuple(int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf) throws Exception {
+ FrameOpSpaceStatus spaceStatus;
+ if (!isLeaf) {
+ spaceStatus = ctx.interiorFrame.hasSpaceInsert(ctx.getTuple(), interiorCmp);
+ } else {
+ spaceStatus = ctx.leafFrame.hasSpaceInsert(ctx.getTuple(), leafCmp);
+ }
+
+ switch (spaceStatus) {
+ case SUFFICIENT_CONTIGUOUS_SPACE: {
+ if (!isLeaf) {
+ ctx.interiorFrame.insert(tuple, interiorCmp);
+ } else {
+ ctx.leafFrame.insert(tuple, leafCmp);
+ }
+ ctx.leftSplitKey.reset();
+ ctx.rightSplitKey.reset();
+ break;
+ }
+
+ case SUFFICIENT_SPACE: {
+ if (!isLeaf) {
+ ctx.interiorFrame.compact(interiorCmp);
+ ctx.interiorFrame.insert(tuple, interiorCmp);
+ } else {
+ ctx.leafFrame.compact(leafCmp);
+ ctx.leafFrame.insert(tuple, leafCmp);
+ }
+ ctx.leftSplitKey.reset();
+ ctx.rightSplitKey.reset();
+ break;
+ }
+
+ case INSUFFICIENT_SPACE: {
+ int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
+ ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
+ pins++;
+
+ try {
+ IRTreeFrame rightFrame;
+ int ret;
+ if (!isLeaf) {
+ rightFrame = interiorFrameFactory.getFrame();
+ rightFrame.setPage(rightNode);
+ rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
+ rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+ ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.leftSplitKey,
+ ctx.rightSplitKey);
+ rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+ ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1);
+
+// System.out.println("I Created page id: " +
+// rightPageId + "level: "
+// + ctx.interiorFrame.getLevel());
+ } else {
+ rightFrame = leafFrameFactory.getFrame();
+ rightFrame.setPage(rightNode);
+ rightFrame.initBuffer((byte) 0);
+ rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+ ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.leftSplitKey, ctx.rightSplitKey);
+ rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+ ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
+
+// System.out.println("L Created page id: " +
+// rightPageId + "level: " + 0);
+ }
+
+ if (ret != 0) {
+ ctx.leftSplitKey.reset();
+ ctx.rightSplitKey.reset();
+ } else {
+ ctx.leftSplitKey.setPage(pageId);
+ ctx.rightSplitKey.setPage(rightPageId);
+ }
+
+ } finally {
+ bufferCache.unpin(rightNode);
+ unpins++;
+ }
+ // System.out.println("Splitted");
+ break;
+ }
+ }
+ }
+
+ public IRTreeFrameFactory getInteriorFrameFactory() {
+ return interiorFrameFactory;
+ }
+
+ public IRTreeFrameFactory getLeafFrameFactory() {
+ return leafFrameFactory;
+ }
+
+ public MultiComparator getInteriorCmp() {
+ return interiorCmp;
+ }
+
+ public MultiComparator getLeafCmp() {
+ return leafCmp;
+ }
+
+ public IFreePageManager getFreePageManager() {
+ return freePageManager;
+ }
+}
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
new file mode 100644
index 0000000..94e16d2
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -0,0 +1,42 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+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.IRTreeFrame;
+
+public final class RTreeOpContext {
+ public final TreeIndexOp op;
+ public final IRTreeFrame interiorFrame;
+ public final IRTreeFrame leafFrame;
+ public final ITreeIndexMetaDataFrame metaFrame;
+ public final ByteArrayList overflowArray;
+ public final RTreeSplitKey leftSplitKey;
+ public final RTreeSplitKey rightSplitKey;
+ public int insertLevel;
+ public ITupleReference tuple;
+
+ public RTreeOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+ ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
+ this.op = op;
+ this.interiorFrame = interiorFrame;
+ this.leafFrame = leafFrame;
+ this.metaFrame = metaFrame;
+ leftSplitKey = new RTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
+ rightSplitKey = new RTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
+ overflowArray = new ByteArrayList(treeHeightHint, treeHeightHint);
+ }
+
+ public ITupleReference getTuple() {
+ return tuple;
+ }
+
+ public void setTuple(ITupleReference tuple) {
+ this.tuple = tuple;
+ }
+
+ public void reset() {
+ if (overflowArray != null)
+ overflowArray.clear();
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java
new file mode 100644
index 0000000..7c33a9a
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSplitKey.java
@@ -0,0 +1,62 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class RTreeSplitKey {
+ public byte[] data = null;
+ public ByteBuffer buf = null;
+ public ITreeIndexTupleReference tuple;
+ public int keySize = 0;
+
+ public RTreeSplitKey(ITreeIndexTupleReference tuple) {
+ this.tuple = tuple;
+ }
+
+ public void initData(int keySize) {
+ // try to reuse existing memory from a lower-level split if possible
+ this.keySize = keySize;
+ if (data != null) {
+ if (data.length < keySize + 4) {
+ data = new byte[keySize + 4]; // add 4 for the page
+ buf = ByteBuffer.wrap(data);
+ }
+ } else {
+ data = new byte[keySize + 4]; // add 4 for the page
+ buf = ByteBuffer.wrap(data);
+ }
+
+ tuple.resetByTupleOffset(buf, 0);
+ }
+
+ public void reset() {
+ data = null;
+ buf = null;
+ }
+
+ public ByteBuffer getBuffer() {
+ return buf;
+ }
+
+ public ITreeIndexTupleReference getTuple() {
+ return tuple;
+ }
+
+ public int getPage() {
+ return buf.getInt(keySize);
+ }
+
+ public void setPage(int Page) {
+ buf.putInt(keySize, Page);
+ }
+
+ public RTreeSplitKey duplicate(ITreeIndexTupleReference copyTuple) {
+ RTreeSplitKey copy = new RTreeSplitKey(copyTuple);
+ copy.data = data.clone();
+ copy.buf = ByteBuffer.wrap(copy.data);
+ copy.tuple.setFieldCount(tuple.getFieldCount());
+ copy.tuple.resetByTupleOffset(copy.buf, 0);
+ return copy;
+ }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
new file mode 100644
index 0000000..95a89bc
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -0,0 +1,32 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+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.frames.AbstractSlotManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class UnorderedSlotManager extends AbstractSlotManager {
+ public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
+ FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
+ if (mode == FindTupleMode.FTM_EXACT) {
+ for (int i = 0; i < frame.getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(frame, i);
+ int cmp = multiCmp.compare(searchKey, frameTuple);
+ if (cmp == 0) {
+ return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public int insertSlot(int tupleIndex, int tupleOff) {
+ int slotOff = getSlotEndOff() - slotSize;
+ setSlot(slotOff, tupleOff);
+ return slotOff;
+ }
+
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java
new file mode 100644
index 0000000..f512cc8
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriter.java
@@ -0,0 +1,45 @@
+package edu.uci.ics.hyracks.storage.am.rtree.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
+
+public class RTreeTypeAwareTupleWriter extends TypeAwareTupleWriter {
+
+ public RTreeTypeAwareTupleWriter(ITypeTrait[] typeTraits) {
+ super(typeTraits);
+ }
+
+ public int writeTupleFields(ITreeIndexTupleReference[] refs, int startField, ByteBuffer targetBuf, int targetOff) {
+ int runner = targetOff;
+ int nullFlagsBytes = getNullFlagsBytes(refs.length);
+ // write null indicator bits
+ for (int i = 0; i < nullFlagsBytes; i++) {
+ targetBuf.put(runner++, (byte) 0);
+ }
+
+ // write field slots for variable length fields
+ // since the r-tree has fixed length keys, we don't actually need this?
+ encDec.reset(targetBuf.array(), runner);
+ for (int i = startField; i < startField + refs.length; i++) {
+ if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+ encDec.encode(refs[i].getFieldLength(i));
+ }
+ }
+ runner = encDec.getPos();
+
+ // write data
+ for (int i = 0; i < refs.length; i++) {
+ double d3 = DoubleSerializerDeserializer.getDouble(refs[i].getFieldData(i), refs[i].getFieldStart(i));
+
+ System.arraycopy(refs[i].getFieldData(i), refs[i].getFieldStart(i), targetBuf.array(), runner,
+ refs[i].getFieldLength(i));
+ runner += refs[i].getFieldLength(i);
+ }
+ return runner - targetOff;
+
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..18fbd71
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tuples/RTreeTypeAwareTupleWriterFactory.java
@@ -0,0 +1,21 @@
+package edu.uci.ics.hyracks.storage.am.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class RTreeTypeAwareTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITypeTrait[] typeTraits;
+
+ public RTreeTypeAwareTupleWriterFactory(ITypeTrait[] typeTraits) {
+ this.typeTraits = typeTraits;
+ }
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ return new RTreeTypeAwareTupleWriter(typeTraits);
+ }
+
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.project b/hyracks-tests/hyracks-storage-am-rtree-test/.project
new file mode 100644
index 0000000..ea7e36b
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+ <name>hyracks-storage-am-rtree-test</name>
+ <comment></comment>
+ <projects>
+ </projects>
+ <buildSpec>
+ <buildCommand>
+ <name>org.eclipse.jdt.core.javabuilder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ <buildCommand>
+ <name>org.maven.ide.eclipse.maven2Builder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ </buildSpec>
+ <natures>
+ <nature>org.eclipse.jdt.core.javanature</nature>
+ <nature>org.maven.ide.eclipse.maven2Nature</nature>
+ </natures>
+</projectDescription>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..3cd389e
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Thu Jan 06 11:27:16 PST 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..99b89a6
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,9 @@
+#Thu Jan 06 11:27:16 PST 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+includeModules=false
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
new file mode 100644
index 0000000..36d4988
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -0,0 +1,55 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree-test</artifactId>
+ <version>0.1.4</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.1.4</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-control-nc</artifactId>
+ <version>0.1.4</version>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree</artifactId>
+ <version>0.1.4</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>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
new file mode 100644
index 0000000..54c6cb3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
@@ -0,0 +1,25 @@
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+
+import org.junit.AfterClass;
+
+public abstract class AbstractRTreeTest {
+
+ protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final static String sep = System.getProperty("file.separator");
+ protected final static String fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+
+ protected void print(String str) {
+ System.out.print(str);
+ }
+
+ @AfterClass
+ public static void cleanup() throws Exception {
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+}
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
new file mode 100644
index 0000000..01a3989
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeFrameTest.java
@@ -0,0 +1,166 @@
+/*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
new file mode 100644
index 0000000..f92855c
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -0,0 +1,189 @@
+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.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.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.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 RTreeTest 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 test01() 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 interiorTieldCount = 5;
+ ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorTieldCount];
+ 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);
+ IRTreeFrameFactory leafFrameFactory = new NSMRTreeFrameFactory(leafTupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+
+ IRTreeFrame interiorFrame = interiorFrameFactory.getFrame();
+ IRTreeFrame leafFrame = leafFrameFactory.getFrame();
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ 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);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ for (int i = 0; i < 33; i++) {
+
+ double p1x = rnd.nextDouble();
+ double p1y = rnd.nextDouble();
+ double p2x = rnd.nextDouble();
+ double p2y = rnd.nextDouble();
+
+// System.out.println(p1x);
+// System.out.println(p1y);
+// System.out.println(p2x);
+// System.out.println(p2y);
+//
+ System.out.println("=================================");
+
+ 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);
+
+ //if (i % 1000 == 0) {
+ long end = System.currentTimeMillis();
+ print("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + "\n");
+ //}
+
+ try {
+ if(i == 22)
+ System.out.print("");
+ rtree.insert(tuple, insertOpCtx);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ rtree.printTree(leafFrame, interiorFrame, recDescSers);
+ System.out.println();
+ }
+
+// rtree.printTree(leafFrame, interiorFrame, recDescSers);
+// System.out.println();
+ rtree.close();
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+
+ }
+}
diff --git a/hyracks-tests/pom.xml b/hyracks-tests/pom.xml
index f4e1984..c79442d 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 619c635..0b59a29 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>