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);
+ }
+
+}