Created a test framework for the RTree and added the corresponding tests.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1119 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
index 8c482cb..b35dd75 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
@@ -25,29 +25,32 @@
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-@SuppressWarnings("rawtypes")
-public class TupleUtils {
+@SuppressWarnings("rawtypes")
+public class TupleUtils {
@SuppressWarnings("unchecked")
- public static void createTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes, final Object... fields) throws HyracksDataException {
+ public static void createTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple,
+ ISerializerDeserializer[] fieldSerdes, final Object... fields) throws HyracksDataException {
DataOutput dos = tupleBuilder.getDataOutput();
tupleBuilder.reset();
int numFields = Math.min(tupleBuilder.getFieldEndOffsets().length, fields.length);
- for (int i = 0; i < numFields; i++) {
+ for (int i = 0; i < numFields; i++) {
fieldSerdes[i].serialize(fields[i], dos);
tupleBuilder.addFieldEndOffset();
}
tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
}
- public static ITupleReference createTuple(ISerializerDeserializer[] fieldSerdes, final Object... fields) throws HyracksDataException {
+ public static ITupleReference createTuple(ISerializerDeserializer[] fieldSerdes, final Object... fields)
+ throws HyracksDataException {
ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fields.length);
ArrayTupleReference tuple = new ArrayTupleReference();
createTuple(tupleBuilder, tuple, fieldSerdes, fields);
return tuple;
}
-
+
public static void createIntegerTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple,
final int... fields) throws HyracksDataException {
DataOutput dos = tupleBuilder.getDataOutput();
@@ -65,14 +68,31 @@
createIntegerTuple(tupleBuilder, tuple, fields);
return tuple;
}
-
- public static String printTuple(ITupleReference tuple,
- ISerializerDeserializer[] fields) throws HyracksDataException {
+
+ public static void createDoubleTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple,
+ final double... fields) throws HyracksDataException {
+ DataOutput dos = tupleBuilder.getDataOutput();
+ tupleBuilder.reset();
+ for (final double i : fields) {
+ DoubleSerializerDeserializer.INSTANCE.serialize(i, dos);
+ tupleBuilder.addFieldEndOffset();
+ }
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+ }
+
+ public static ITupleReference createDoubleTuple(final double... fields) throws HyracksDataException {
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fields.length);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ createDoubleTuple(tupleBuilder, tuple, fields);
+ return tuple;
+ }
+
+ public static String printTuple(ITupleReference tuple, ISerializerDeserializer[] fields)
+ throws HyracksDataException {
StringBuilder strBuilder = new StringBuilder();
int numPrintFields = Math.min(tuple.getFieldCount(), fields.length);
for (int i = 0; i < numPrintFields; i++) {
- ByteArrayInputStream inStream = new ByteArrayInputStream(
- tuple.getFieldData(i), tuple.getFieldStart(i),
+ ByteArrayInputStream inStream = new ByteArrayInputStream(tuple.getFieldData(i), tuple.getFieldStart(i),
tuple.getFieldLength(i));
DataInput dataIn = new DataInputStream(inStream);
Object o = fields[i].deserialize(dataIn);
@@ -80,10 +100,10 @@
if (i != fields.length - 1) {
strBuilder.append(" ");
}
- }
+ }
return strBuilder.toString();
}
-
+
public static Object[] deserializeTuple(ITupleReference tuple, ISerializerDeserializer[] fields)
throws HyracksDataException {
int numFields = Math.min(tuple.getFieldCount(), fields.length);
@@ -96,7 +116,7 @@
}
return objs;
}
-
+
public static ITupleReference copyTuple(ITupleReference tuple) throws HyracksDataException {
ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(tuple.getFieldCount());
for (int i = 0; i < tuple.getFieldCount(); i++) {
diff --git a/hyracks-storage-am-common/pom.xml b/hyracks-storage-am-common/pom.xml
index 9f0e53a..2a9b89d 100644
--- a/hyracks-storage-am-common/pom.xml
+++ b/hyracks-storage-am-common/pom.xml
@@ -52,5 +52,12 @@
<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-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java
new file mode 100644
index 0000000..22cd5df
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java
@@ -0,0 +1,73 @@
+/*
+ * 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.common.test;
+
+@SuppressWarnings({"rawtypes", "unchecked"})
+public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
+ protected final int numKeys;
+ protected final Comparable[] tuple;
+ protected int pos;
+
+ public CheckTuple(int numFields, int numKeys) {
+ this.numKeys = numKeys;
+ this.tuple = new Comparable[numFields];
+ pos = 0;
+ }
+
+ public void add(T e) {
+ tuple[pos++] = e;
+ }
+
+ @Override
+ public int compareTo(T o) {
+ CheckTuple<T> other = (CheckTuple<T>)o;
+ for (int i = 0; i < numKeys; i++) {
+ int cmp = tuple[i].compareTo(other.get(i));
+ if (cmp != 0) {
+ return cmp;
+ }
+ }
+ return 0;
+ }
+
+ public T get(int idx) {
+ return (T)tuple[idx];
+ }
+
+ public void set(int idx, T e) {
+ tuple[idx] = e;
+ }
+
+ public int size() {
+ return tuple.length;
+ }
+
+ public int getNumKeys() {
+ return numKeys;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder strBuilder = new StringBuilder();
+ for (int i = 0; i < tuple.length; i++) {
+ strBuilder.append(tuple[i].toString());
+ if (i != tuple.length-1) {
+ strBuilder.append(" ");
+ }
+ }
+ return strBuilder.toString();
+ }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
new file mode 100644
index 0000000..cf9ca2e
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
@@ -0,0 +1,49 @@
+/*
+ * 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.common.test;
+
+import java.util.Collection;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+
+@SuppressWarnings("rawtypes")
+public interface ITreeIndexTestContext <T extends CheckTuple>{
+ public int getFieldCount();
+
+ public int getKeyFieldCount();
+
+ public ISerializerDeserializer[] getFieldSerdes();
+
+ public IBinaryComparatorFactory[] getComparatorFactories();
+
+ public ITreeIndexAccessor getIndexAccessor();
+
+ public ITreeIndex getIndex();
+
+ public ArrayTupleReference getTuple();
+
+ public ArrayTupleBuilder getTupleBuilder();
+
+ public void insertCheckTuple(T checkTuple, Collection<T> checkTuples);
+
+ public Collection<T> getCheckTuples();
+
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
new file mode 100644
index 0000000..4b0129c
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
@@ -0,0 +1,68 @@
+/*
+ * 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.common.test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+
+@SuppressWarnings("rawtypes")
+public abstract class TreeIndexTestContext<T extends CheckTuple> implements ITreeIndexTestContext<T> {
+ protected final ISerializerDeserializer[] fieldSerdes;
+ protected final ITreeIndex treeIndex;
+ protected final ArrayTupleBuilder tupleBuilder;
+ protected final ArrayTupleReference tuple = new ArrayTupleReference();
+ protected final ITreeIndexAccessor indexAccessor;
+
+ public TreeIndexTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ this.fieldSerdes = fieldSerdes;
+ this.treeIndex = treeIndex;
+ this.indexAccessor = treeIndex.createAccessor();
+ this.tupleBuilder = new ArrayTupleBuilder(fieldSerdes.length);
+ }
+
+ @Override
+ public int getFieldCount() {
+ return fieldSerdes.length;
+ }
+
+ @Override
+ public ITreeIndexAccessor getIndexAccessor() {
+ return indexAccessor;
+ }
+
+ @Override
+ public ArrayTupleReference getTuple() {
+ return tuple;
+ }
+
+ @Override
+ public ArrayTupleBuilder getTupleBuilder() {
+ return tupleBuilder;
+ }
+
+ @Override
+ public ISerializerDeserializer[] getFieldSerdes() {
+ return fieldSerdes;
+ }
+
+ @Override
+ public ITreeIndex getIndex() {
+ return treeIndex;
+ }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
new file mode 100644
index 0000000..5b21485
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
@@ -0,0 +1,237 @@
+package edu.uci.ics.hyracks.storage.am.common.test;
+
+import static org.junit.Assert.fail;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Random;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+@SuppressWarnings("rawtypes")
+public abstract class TreeIndexTestUtils {
+ private static final Logger LOGGER = Logger.getLogger(TreeIndexTestUtils.class.getName());
+
+ protected abstract CheckTuple createCheckTuple(int numfields, int numKeyFields);
+
+ protected abstract ISearchPredicate createNullSearchPredicate();
+
+ public abstract void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
+ ISerializerDeserializer[] fieldSerdes, int keyFieldCount) throws Exception;
+
+ protected abstract CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields);
+
+ protected abstract void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd);
+
+ protected abstract boolean insertTuple(ITreeIndexTestContext ctx) throws Exception;
+
+ protected abstract Collection createCheckTuplesCollection();
+
+ @SuppressWarnings("unchecked")
+ private static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder,
+ ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ int fieldCount = tupleBuilder.getFieldEndOffsets().length;
+ DataOutput dos = tupleBuilder.getDataOutput();
+ tupleBuilder.reset();
+ for (int i = 0; i < fieldCount; i++) {
+ fieldSerdes[i].serialize(checkTuple.get(i), dos);
+ tupleBuilder.addFieldEndOffset();
+ }
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+ }
+
+ @SuppressWarnings("unchecked")
+ public CheckTuple createCheckTupleFromTuple(ITupleReference tuple, ISerializerDeserializer[] fieldSerdes,
+ int numKeys) throws HyracksDataException {
+ CheckTuple checkTuple = createCheckTuple(fieldSerdes.length, numKeys);
+ int fieldCount = Math.min(fieldSerdes.length, tuple.getFieldCount());
+ for (int i = 0; i < fieldCount; i++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ DataInput dataIn = new DataInputStream(inStream);
+ Comparable fieldObj = (Comparable) fieldSerdes[i].deserialize(dataIn);
+ checkTuple.add(fieldObj);
+ }
+ return checkTuple;
+ }
+
+ public void checkScan(ITreeIndexTestContext ctx) throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Testing Scan.");
+ }
+ ITreeIndexCursor scanCursor = ctx.getIndexAccessor().createSearchCursor();
+ ISearchPredicate nullPred = createNullSearchPredicate();
+ ctx.getIndexAccessor().search(scanCursor, nullPred);
+ checkExpectedResults(scanCursor, ctx.getCheckTuples(), ctx.getFieldSerdes(), ctx.getKeyFieldCount());
+ }
+
+ public void checkDiskOrderScan(ITreeIndexTestContext ctx) throws Exception {
+ try {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Testing Disk-Order Scan.");
+ }
+ ITreeIndexCursor diskOrderCursor = ctx.getIndexAccessor().createDiskOrderScanCursor();
+ ctx.getIndexAccessor().diskOrderScan(diskOrderCursor);
+ int actualCount = 0;
+ try {
+ while (diskOrderCursor.hasNext()) {
+ diskOrderCursor.next();
+ ITupleReference tuple = diskOrderCursor.getTuple();
+ CheckTuple checkTuple = createCheckTupleFromTuple(tuple, ctx.getFieldSerdes(),
+ ctx.getKeyFieldCount());
+ if (!ctx.getCheckTuples().contains(checkTuple)) {
+ fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
+ }
+ actualCount++;
+ }
+ if (actualCount < ctx.getCheckTuples().size()) {
+ fail("Disk-order scan returned fewer answers than expected.\nExpected: "
+ + ctx.getCheckTuples().size() + "\nActual : " + actualCount);
+ }
+ if (actualCount > ctx.getCheckTuples().size()) {
+ fail("Disk-order scan returned more answers than expected.\nExpected: "
+ + ctx.getCheckTuples().size() + "\nActual : " + actualCount);
+ }
+ } finally {
+ diskOrderCursor.close();
+ }
+ } catch (UnsupportedOperationException e) {
+ // Ignore exception because some indexes, e.g. the LSMTrees, don't
+ // support disk-order scan.
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Ignoring disk-order scan since it's not supported.");
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public void insertIntTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ int[] fieldValues = new int[ctx.getFieldCount()];
+ // Scale range of values according to number of keys.
+ // For example, for 2 keys we want the square root of numTuples, for 3
+ // keys the cube root of numTuples, etc.
+ int maxValue = (int) Math.ceil(Math.pow(numTuples, 1.0 / (double) numKeyFields));
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+ TupleUtils.createIntegerTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
+ LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ }
+ boolean succeeded = insertTuple(ctx);
+ if (succeeded) {
+ ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public void bulkLoadIntTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ int[] fieldValues = new int[ctx.getFieldCount()];
+ int maxValue = (int) Math.ceil(Math.pow(numTuples, 1.0 / (double) numKeyFields));
+ Collection<CheckTuple> tmpCheckTuples = createCheckTuplesCollection();
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+
+ // Set expected values. (We also use these as the pre-sorted stream
+ // for ordered indexes bulk loading).
+ ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), tmpCheckTuples);
+ }
+ bulkLoadCheckTuples(ctx, tmpCheckTuples);
+
+ // Add tmpCheckTuples to ctx check tuples for comparing searches.
+ for (CheckTuple checkTuple : tmpCheckTuples) {
+ ctx.insertCheckTuple(checkTuple, ctx.getCheckTuples());
+ }
+ }
+
+ public static void bulkLoadCheckTuples(ITreeIndexTestContext ctx, Collection<CheckTuple> checkTuples)
+ throws HyracksDataException, TreeIndexException {
+ int fieldCount = ctx.getFieldCount();
+ int numTuples = checkTuples.size();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ // Perform bulk load.
+ IIndexBulkLoadContext bulkLoadCtx = ctx.getIndex().beginBulkLoad(0.7f);
+ int c = 1;
+ for (CheckTuple checkTuple : checkTuples) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (c % (numTuples / 10) == 0) {
+ LOGGER.info("Bulk Loading Tuple " + c + "/" + numTuples);
+ }
+ }
+ createTupleFromCheckTuple(checkTuple, tupleBuilder, tuple, ctx.getFieldSerdes());
+ ctx.getIndex().bulkLoadAddTuple(tuple, bulkLoadCtx);
+ c++;
+ }
+ ctx.getIndex().endBulkLoad(bulkLoadCtx);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void deleteTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
+ ArrayTupleReference deleteTuple = new ArrayTupleReference();
+ int numCheckTuples = ctx.getCheckTuples().size();
+ // Copy CheckTuple references into array, so we can randomly pick from
+ // there.
+ CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+ int idx = 0;
+ Iterator<CheckTuple> iter = ctx.getCheckTuples().iterator();
+ while (iter.hasNext()) {
+ CheckTuple checkTuple = iter.next();
+ checkTuples[idx++] = checkTuple;
+ }
+
+ for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
+ LOGGER.info("Deleting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ }
+ int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+ CheckTuple checkTuple = checkTuples[checkTupleIdx];
+ createTupleFromCheckTuple(checkTuple, deleteTupleBuilder, deleteTuple, ctx.getFieldSerdes());
+ ctx.getIndexAccessor().delete(deleteTuple);
+
+ // Remove check tuple from expected results.
+ ctx.getCheckTuples().remove(checkTuple);
+
+ // Swap with last "valid" CheckTuple.
+ CheckTuple tmp = checkTuples[numCheckTuples - 1];
+ checkTuples[numCheckTuples - 1] = checkTuple;
+ checkTuples[checkTupleIdx] = tmp;
+ numCheckTuples--;
+ }
+ }
+
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
index c63fbb4..33c930c 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
@@ -19,7 +19,6 @@
import java.nio.ByteBuffer;
import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
@@ -41,6 +40,7 @@
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
public class RTreeSearchOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
private TreeIndexDataflowHelper treeIndexHelper;
@@ -86,12 +86,8 @@
writer.open();
try {
rtree = (RTree) treeIndexHelper.getIndex();
- int keySearchFields = rtree.getComparatorFactories().length;
- IBinaryComparator[] keySearchComparators = new IBinaryComparator[keySearchFields];
- for (int i = 0; i < keySearchFields; i++) {
- keySearchComparators[i] = rtree.getComparatorFactories()[i].createBinaryComparator();
- }
- cmp = new MultiComparator(keySearchComparators);
+ cmp = RTreeUtils.getSearchMultiComparator(rtree.getComparatorFactories(), searchKey);
+
searchPred = new SearchPredicate(searchKey, cmp);
writeBuffer = treeIndexHelper.getHyracksTaskContext().allocateFrame();
tb = new ArrayTupleBuilder(rtree.getFieldCount());
@@ -140,7 +136,6 @@
for (int i = 0; i < tupleCount; i++) {
searchKey.reset(accessor, i);
- searchPred.setSearchKey(searchKey);
cursor.reset();
indexAccessor.search(cursor, searchPred);
writeSearchResults();
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java
new file mode 100644
index 0000000..a8f77c1
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeBulkLoadTest.java
@@ -0,0 +1,59 @@
+/*
+ * 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.tests;
+
+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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+@SuppressWarnings("rawtypes")
+public abstract class AbstractRTreeBulkLoadTest extends RTreeTestDriver {
+
+ private final RTreeTestUtils rTreeTestUtils;
+ private final int bulkLoadRounds;
+
+ public AbstractRTreeBulkLoadTest(int bulkLoadRounds) {
+ this.bulkLoadRounds = bulkLoadRounds;
+ this.rTreeTestUtils = new RTreeTestUtils();
+ }
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys, ITupleReference key) throws Exception {
+ AbstractRTreeTestContext ctx = createTestContext(fieldSerdes, valueProviderFactories, numKeys);
+ for (int i = 0; i < bulkLoadRounds; i++) {
+ // We assume all fieldSerdes are of the same type. Check the first
+ // one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ rTreeTestUtils.bulkLoadIntTuples(ctx, numTuplesToInsert, getRandom());
+ } else if (fieldSerdes[0] instanceof DoubleSerializerDeserializer) {
+ rTreeTestUtils.bulkLoadDoubleTuples(ctx, numTuplesToInsert, getRandom());
+ }
+
+ rTreeTestUtils.checkScan(ctx);
+ rTreeTestUtils.checkDiskOrderScan(ctx);
+ rTreeTestUtils.checkRangeSearch(ctx, key);
+ ctx.getIndex().close();
+ }
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "BulkLoad";
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java
new file mode 100644
index 0000000..796ba33
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeDeleteTest.java
@@ -0,0 +1,64 @@
+/*
+ * 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.tests;
+
+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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+@SuppressWarnings("rawtypes")
+public abstract class AbstractRTreeDeleteTest extends RTreeTestDriver {
+
+ private final RTreeTestUtils rTreeTestUtils;
+
+ private static final int numInsertRounds = 2;
+ private static final int numDeleteRounds = 2;
+
+ public AbstractRTreeDeleteTest() {
+ this.rTreeTestUtils = new RTreeTestUtils();
+ }
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys, ITupleReference key) throws Exception {
+ AbstractRTreeTestContext ctx = createTestContext(fieldSerdes, valueProviderFactories, numKeys);
+ for (int i = 0; i < numInsertRounds; i++) {
+ // We assume all fieldSerdes are of the same type. Check the first
+ // one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ rTreeTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+ } else if (fieldSerdes[0] instanceof DoubleSerializerDeserializer) {
+ rTreeTestUtils.insertDoubleTuples(ctx, numTuplesToInsert, getRandom());
+ }
+ int numTuplesPerDeleteRound = (int) Math
+ .ceil((float) ctx.getCheckTuples().size() / (float) numDeleteRounds);
+ for (int j = 0; j < numDeleteRounds; j++) {
+ rTreeTestUtils.deleteTuples(ctx, numTuplesPerDeleteRound, getRandom());
+ rTreeTestUtils.checkScan(ctx);
+ rTreeTestUtils.checkDiskOrderScan(ctx);
+ rTreeTestUtils.checkRangeSearch(ctx, key);
+ }
+ }
+ ctx.getIndex().close();
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "Delete";
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java
new file mode 100644
index 0000000..6f23a38
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeExamplesTest.java
@@ -0,0 +1,527 @@
+/*
+ * 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.tests;
+
+import java.util.Random;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+
+@SuppressWarnings("rawtypes")
+public abstract class AbstractRTreeExamplesTest {
+ protected static final Logger LOGGER = Logger.getLogger(AbstractRTreeExamplesTest.class.getName());
+ protected final Random rnd = new Random(50);
+
+ protected abstract ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories) throws TreeIndexException;
+
+ protected abstract int getIndexFileId();
+
+ /**
+ * Two Dimensions Example.
+ *
+ * Create an RTree index of two dimensions, where they keys are of type
+ * integer, and the payload is two integer values. Fill index with random
+ * values using insertions (not bulk load). Perform scans and range search.
+ */
+ @Test
+ public void twoDimensionsExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Fixed-Length Key,Value Example.");
+ }
+
+ // Declare fields.
+ int fieldCount = 6;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[5] = IntegerPointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+
+ // Declare keys.
+ int keyFieldCount = 4;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, IntegerPointable.FACTORY);
+
+ int indexFileId = getIndexFileId();
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+ treeIndex.create(indexFileId);
+ treeIndex.open(indexFileId);
+
+ long start = System.currentTimeMillis();
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Inserting into tree...");
+ }
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
+ int numInserts = 10000;
+ for (int i = 0; i < numInserts; i++) {
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+
+ int pk1 = 5;
+ int pk2 = 10;
+
+ TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), pk1, pk2);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 1000 == 0) {
+ LOGGER.info("Inserting " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
+ + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + ", " + pk1 + ", " + pk2);
+ }
+ }
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ }
+ }
+ long end = System.currentTimeMillis();
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(numInserts + " inserts in " + (end - start) + "ms");
+ }
+
+ scan(indexAccessor, fieldSerdes);
+ diskOrderScan(indexAccessor, fieldSerdes);
+
+ // Build key.
+ ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+ ArrayTupleReference key = new ArrayTupleReference();
+ TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
+
+ rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+
+ treeIndex.close();
+ }
+
+ /**
+ * Two Dimensions Example.
+ *
+ * Create an RTree index of three dimensions, where they keys are of type
+ * double, and the payload is one double value. Fill index with random
+ * values using insertions (not bulk load). Perform scans and range search.
+ */
+ @Test
+ public void threeDimensionsExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Fixed-Length Key,Value Example.");
+ }
+
+ // Declare fields.
+ int fieldCount = 7;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = DoublePointable.TYPE_TRAITS;
+ typeTraits[1] = DoublePointable.TYPE_TRAITS;
+ typeTraits[2] = DoublePointable.TYPE_TRAITS;
+ typeTraits[3] = DoublePointable.TYPE_TRAITS;
+ typeTraits[4] = DoublePointable.TYPE_TRAITS;
+ typeTraits[5] = DoublePointable.TYPE_TRAITS;
+ typeTraits[6] = DoublePointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
+
+ // Declare keys.
+ int keyFieldCount = 6;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+ cmpFactories[4] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+ cmpFactories[5] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, DoublePointable.FACTORY);
+
+ int indexFileId = getIndexFileId();
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+ treeIndex.create(indexFileId);
+ treeIndex.open(indexFileId);
+
+ long start = System.currentTimeMillis();
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Inserting into tree...");
+ }
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
+ int numInserts = 10000;
+ for (int i = 0; i < numInserts; i++) {
+ double p1x = rnd.nextDouble();
+ double p1y = rnd.nextDouble();
+ double p1z = rnd.nextDouble();
+ double p2x = rnd.nextDouble();
+ double p2y = rnd.nextDouble();
+ double p2z = rnd.nextDouble();
+
+ double pk = 5.0;
+
+ TupleUtils.createDoubleTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.min(p1z, p2z),
+ Math.max(p1x, p2x), Math.max(p1y, p2y), Math.max(p1z, p2z), pk);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 1000 == 0) {
+ LOGGER.info("Inserting " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
+ + Math.min(p1z, p2z) + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + " "
+ + Math.max(p1z, p2z) + ", " + pk);
+ }
+ }
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ }
+ }
+ long end = System.currentTimeMillis();
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(numInserts + " inserts in " + (end - start) + "ms");
+ }
+
+ scan(indexAccessor, fieldSerdes);
+ diskOrderScan(indexAccessor, fieldSerdes);
+
+ // Build key.
+ ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+ ArrayTupleReference key = new ArrayTupleReference();
+ TupleUtils.createDoubleTuple(keyTb, key, -1000.0, -1000.0, -1000.0, 1000.0, 1000.0, 1000.0);
+
+ rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+
+ treeIndex.close();
+ }
+
+ /**
+ * Deletion Example.
+ *
+ * Create an RTree index of two dimensions, where they keys are of type
+ * integer, and the payload is one integer value. Fill index with random
+ * values using insertions, then delete entries one-by-one. Repeat procedure
+ * a few times on same RTree.
+ */
+ @Test
+ public void deleteExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Deletion Example");
+ }
+
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+
+ // Declare keys.
+ int keyFieldCount = 4;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, IntegerPointable.FACTORY);
+
+ int indexFileId = getIndexFileId();
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+ treeIndex.create(indexFileId);
+ treeIndex.open(indexFileId);
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
+
+ int runs = 3;
+ for (int run = 0; run < runs; run++) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Deletion example run: " + (run + 1) + "/" + runs);
+ LOGGER.info("Inserting into tree...");
+ }
+
+ int numInserts = 10000;
+ int[] p1xs = new int[numInserts];
+ int[] p1ys = new int[numInserts];
+ int[] p2xs = new int[numInserts];
+ int[] p2ys = new int[numInserts];
+ int[] pks = new int[numInserts];
+ int insDone = 0;
+
+ int[] insDoneCmp = new int[numInserts];
+ for (int i = 0; i < numInserts; i++) {
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+ int pk = 5;
+
+ p1xs[i] = Math.min(p1x, p2x);
+ p1ys[i] = Math.min(p1y, p2y);
+ p2xs[i] = Math.max(p1x, p2x);
+ p2ys[i] = Math.max(p1y, p2y);
+ pks[i] = pk;
+
+ TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), pk);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 1000 == 0) {
+ LOGGER.info("Inserting " + i);
+ }
+ }
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ }
+ insDoneCmp[i] = insDone;
+ }
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Deleting from tree...");
+ }
+ int delDone = 0;
+ for (int i = 0; i < numInserts; i++) {
+ TupleUtils.createIntegerTuple(tb, tuple, p1xs[i], p1ys[i], p2xs[i], p2ys[i], pks[i]);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 1000 == 0) {
+ LOGGER.info("Deleting " + i);
+ }
+ }
+ try {
+ indexAccessor.delete(tuple);
+ delDone++;
+ } catch (TreeIndexException e) {
+ }
+ if (insDoneCmp[i] != delDone) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("INCONSISTENT STATE, ERROR IN DELETION EXAMPLE.");
+ LOGGER.info("INSDONECMP: " + insDoneCmp[i] + " " + delDone);
+ }
+ break;
+ }
+ }
+ if (insDone != delDone) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("ERROR! INSDONE: " + insDone + " DELDONE: " + delDone);
+ }
+ break;
+ }
+ }
+ treeIndex.close();
+ }
+
+ /**
+ * Bulk load example.
+ *
+ * Load a tree with 10,000 tuples.
+ *
+ */
+ @Test
+ public void bulkLoadExample() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Bulk load example");
+ }
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ // Declare keys.
+ int keyFieldCount = 4;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, IntegerPointable.FACTORY);
+
+ int indexFileId = getIndexFileId();
+ ITreeIndex treeIndex = createTreeIndex(typeTraits, cmpFactories, valueProviderFactories);
+ treeIndex.create(indexFileId);
+ treeIndex.open(indexFileId);
+
+ // Load records.
+ int numInserts = 10000;
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Bulk loading " + numInserts + " tuples");
+ }
+ long start = System.currentTimeMillis();
+ IIndexBulkLoadContext bulkLoadCtx = treeIndex.beginBulkLoad(0.7f);
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ for (int i = 0; i < numInserts; i++) {
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+
+ int pk = 5;
+
+ TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), pk);
+ treeIndex.bulkLoadAddTuple(tuple, bulkLoadCtx);
+ }
+
+ treeIndex.endBulkLoad(bulkLoadCtx);
+ long end = System.currentTimeMillis();
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(numInserts + " tuples loaded in " + (end - start) + "ms");
+ }
+
+ ITreeIndexAccessor indexAccessor = treeIndex.createAccessor();
+
+ // Build key.
+ ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+ ArrayTupleReference key = new ArrayTupleReference();
+ TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
+
+ rangeSearch(cmpFactories, indexAccessor, fieldSerdes, key);
+
+ treeIndex.close();
+ }
+
+ private void scan(ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes) throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Scan:");
+ }
+ ITreeIndexCursor scanCursor = indexAccessor.createSearchCursor();
+ SearchPredicate nullPred = new SearchPredicate(null, null);
+ indexAccessor.search(scanCursor, nullPred);
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ ITupleReference frameTuple = scanCursor.getTuple();
+ String rec = TupleUtils.printTuple(frameTuple, fieldSerdes);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(rec);
+ }
+ }
+ } finally {
+ scanCursor.close();
+ }
+ }
+
+ private void diskOrderScan(ITreeIndexAccessor indexAccessor, ISerializerDeserializer[] fieldSerdes)
+ throws Exception {
+ try {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Disk-Order Scan:");
+ }
+ TreeDiskOrderScanCursor diskOrderCursor = (TreeDiskOrderScanCursor) indexAccessor
+ .createDiskOrderScanCursor();
+ indexAccessor.diskOrderScan(diskOrderCursor);
+ try {
+ while (diskOrderCursor.hasNext()) {
+ diskOrderCursor.next();
+ ITupleReference frameTuple = diskOrderCursor.getTuple();
+ String rec = TupleUtils.printTuple(frameTuple, fieldSerdes);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(rec);
+ }
+ }
+ } finally {
+ diskOrderCursor.close();
+ }
+ } catch (UnsupportedOperationException e) {
+ // Ignore exception because some indexes, e.g. the LSMRTree, don't
+ // support disk-order scan.
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Ignoring disk-order scan since it's not supported.");
+ }
+ }
+ }
+
+ private void rangeSearch(IBinaryComparatorFactory[] cmpFactories, ITreeIndexAccessor indexAccessor,
+ ISerializerDeserializer[] fieldSerdes, ITupleReference key) throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ String kString = TupleUtils.printTuple(key, fieldSerdes);
+ LOGGER.info("Range-Search using key: " + kString);
+ }
+ ITreeIndexCursor rangeCursor = indexAccessor.createSearchCursor();
+ MultiComparator cmp = RTreeUtils.getSearchMultiComparator(cmpFactories, key);
+ SearchPredicate rangePred = new SearchPredicate(key, cmp);
+ indexAccessor.search(rangeCursor, rangePred);
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ ITupleReference frameTuple = rangeCursor.getTuple();
+ String rec = TupleUtils.printTuple(frameTuple, fieldSerdes);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(rec);
+ }
+ }
+ } finally {
+ rangeCursor.close();
+ }
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java
new file mode 100644
index 0000000..c23cbaf
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeInsertTest.java
@@ -0,0 +1,64 @@
+/*
+ * 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.tests;
+
+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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+/**
+ * Tests the RTree insert operation with integer and double fields using various
+ * numbers of dimensions and payload fields.
+ *
+ * Each tests first fills an RTree with randomly generated tuples. We compare
+ * the following operations against expected results: 1. RTree scan. 3.
+ * Disk-order scan. 4. Range search.
+ *
+ */
+@SuppressWarnings("rawtypes")
+public abstract class AbstractRTreeInsertTest extends RTreeTestDriver {
+
+ private final RTreeTestUtils rTreeTestUtils;
+
+ public AbstractRTreeInsertTest() {
+ this.rTreeTestUtils = new RTreeTestUtils();
+ }
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys, ITupleReference key) throws Exception {
+ AbstractRTreeTestContext ctx = createTestContext(fieldSerdes, valueProviderFactories, numKeys);
+ // We assume all fieldSerdes are of the same type. Check the first one
+ // to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ rTreeTestUtils.insertIntTuples(ctx, numTuplesToInsert, getRandom());
+ } else if (fieldSerdes[0] instanceof DoubleSerializerDeserializer) {
+ rTreeTestUtils.insertDoubleTuples(ctx, numTuplesToInsert, getRandom());
+ }
+
+ rTreeTestUtils.checkScan(ctx);
+ rTreeTestUtils.checkDiskOrderScan(ctx);
+ rTreeTestUtils.checkRangeSearch(ctx, key);
+ ctx.getIndex().close();
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "Insert";
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java
new file mode 100644
index 0000000..b4af787
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/AbstractRTreeTestContext.java
@@ -0,0 +1,43 @@
+/*
+ * 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.tests;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.test.TreeIndexTestContext;
+
+@SuppressWarnings("rawtypes")
+public abstract class AbstractRTreeTestContext extends TreeIndexTestContext<RTreeCheckTuple> {
+ private final ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
+
+ public AbstractRTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ super(fieldSerdes, treeIndex);
+ }
+
+ @Override
+ public void insertCheckTuple(RTreeCheckTuple checkTuple, Collection<RTreeCheckTuple> checkTuples) {
+ checkTuples.add(checkTuple);
+ }
+
+ @Override
+ public Collection<RTreeCheckTuple> getCheckTuples() {
+ return checkTuples;
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java
new file mode 100644
index 0000000..d1792f9
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeCheckTuple.java
@@ -0,0 +1,56 @@
+/*
+ * 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.tests;
+
+import edu.uci.ics.hyracks.storage.am.common.test.CheckTuple;
+
+@SuppressWarnings({ "rawtypes", "unchecked" })
+public class RTreeCheckTuple<T> extends CheckTuple {
+
+ public RTreeCheckTuple(int numFields, int numKeys) {
+ super(numFields, numKeys);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ RTreeCheckTuple<T> other = (RTreeCheckTuple<T>) o;
+ for (int i = 0; i < numKeys; i++) {
+ int cmp = tuple[i].compareTo(other.get(i));
+ if (cmp != 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public boolean intersect(T o) {
+ RTreeCheckTuple<T> other = (RTreeCheckTuple<T>) o;
+ int maxFieldPos = numKeys / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int cmp = tuple[i].compareTo(other.get(j));
+ if (cmp > 0) {
+ return false;
+ }
+ cmp = tuple[j].compareTo(other.get(i));
+ if (cmp < 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java
new file mode 100644
index 0000000..febb5b5
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestDriver.java
@@ -0,0 +1,116 @@
+/*
+ * 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.tests;
+
+import java.util.Random;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+
+@SuppressWarnings("rawtypes")
+public abstract class RTreeTestDriver {
+ protected final Logger LOGGER = Logger.getLogger(RTreeTestDriver.class.getName());
+
+ protected static final int numTuplesToInsert = 10000;
+
+ protected abstract AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception;
+
+ protected abstract Random getRandom();
+
+ protected abstract void runTest(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys, ITupleReference key) throws Exception;
+
+ protected abstract String getTestOpName();
+
+ @Test
+ public void twoDimensionsInt() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("RTree " + getTestOpName() + " Test With Two Dimensions With Integer Keys.");
+ }
+
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+
+ int numKeys = 4;
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ numKeys, IntegerPointable.FACTORY);
+ // Range search, the rectangle bottom left coordinates are -1000, -1000
+ // and the top right coordinates are 1000, 1000
+ ITupleReference key = TupleUtils.createIntegerTuple(-1000, -1000, 1000, 1000);
+
+ runTest(fieldSerdes, valueProviderFactories, numKeys, key);
+
+ }
+
+ @Test
+ public void twoDimensionsDouble() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("RTree " + getTestOpName() + " Test With Two Dimensions With Double Keys.");
+ }
+
+ ISerializerDeserializer[] fieldSerdes = { DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE };
+
+ int numKeys = 4;
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ numKeys, DoublePointable.FACTORY);
+ // Range search, the rectangle bottom left coordinates are -1000.0,
+ // -1000.0 and the top right coordinates are 1000.0, 1000.0
+ ITupleReference key = TupleUtils.createDoubleTuple(-1000.0, -1000.0, 1000.0, 1000.0);
+
+ runTest(fieldSerdes, valueProviderFactories, numKeys, key);
+
+ }
+
+ @Test
+ public void fourDimensionsDouble() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("RTree " + getTestOpName() + " Test With Four Dimensions With Double Keys.");
+ }
+
+ ISerializerDeserializer[] fieldSerdes = { DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE };
+
+ int numKeys = 8;
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ numKeys, DoublePointable.FACTORY);
+ // Range search, the rectangle bottom left coordinates are -1000.0,
+ // -1000.0, -1000.0, -1000.0 and the top right coordinates are 1000.0,
+ // 1000.0, 1000.0, 1000.0
+ ITupleReference key = TupleUtils.createDoubleTuple(-1000.0, -1000.0, -1000.0, -1000.0, 1000.0, 1000.0, 1000.0,
+ 1000.0);
+
+ runTest(fieldSerdes, valueProviderFactories, numKeys, key);
+
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java
new file mode 100644
index 0000000..8020be4
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/tests/RTreeTestUtils.java
@@ -0,0 +1,217 @@
+package edu.uci.ics.hyracks.storage.am.rtree.tests;
+
+import static org.junit.Assert.fail;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Random;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+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.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.test.CheckTuple;
+import edu.uci.ics.hyracks.storage.am.common.test.ITreeIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.common.test.TreeIndexTestUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+
+@SuppressWarnings("rawtypes")
+public class RTreeTestUtils extends TreeIndexTestUtils {
+ private static final Logger LOGGER = Logger.getLogger(RTreeTestUtils.class.getName());
+
+ @SuppressWarnings("unchecked")
+ // Create a new ArrayList containing the elements satisfying the search key
+ public ArrayList<RTreeCheckTuple> getRangeSearchExpectedResults(ArrayList<RTreeCheckTuple> checkTuples,
+ RTreeCheckTuple key) {
+ ArrayList<RTreeCheckTuple> expectedResult = new ArrayList<RTreeCheckTuple>();
+ Iterator<RTreeCheckTuple> iter = checkTuples.iterator();
+ while (iter.hasNext()) {
+ RTreeCheckTuple t = iter.next();
+ if (t.intersect(key)) {
+ expectedResult.add(t);
+ }
+ }
+ return expectedResult;
+ }
+
+ public void checkRangeSearch(ITreeIndexTestContext ictx, ITupleReference key) throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Testing Range Search.");
+ }
+ AbstractRTreeTestContext ctx = (AbstractRTreeTestContext) ictx;
+ MultiComparator cmp = RTreeUtils.getSearchMultiComparator(ctx.getComparatorFactories(), key);
+
+ ITreeIndexCursor searchCursor = ctx.getIndexAccessor().createSearchCursor();
+ SearchPredicate searchPred = new SearchPredicate(key, cmp);
+ ctx.getIndexAccessor().search(searchCursor, searchPred);
+
+ // Get the subset of elements from the expected set within given key
+ // range.
+ RTreeCheckTuple keyCheck = (RTreeCheckTuple) createCheckTupleFromTuple(key, ctx.getFieldSerdes(),
+ cmp.getKeyFieldCount());
+
+ ArrayList<RTreeCheckTuple> expectedResult = null;
+
+ expectedResult = getRangeSearchExpectedResults((ArrayList<RTreeCheckTuple>) ctx.getCheckTuples(), keyCheck);
+ checkExpectedResults(searchCursor, expectedResult, ctx.getFieldSerdes(), ctx.getKeyFieldCount());
+ }
+
+ @SuppressWarnings("unchecked")
+ public void insertDoubleTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ double[] fieldValues = new double[ctx.getFieldCount()];
+ // Scale range of values according to number of keys.
+ // For example, for 2 keys we want the square root of numTuples, for 3
+ // keys the cube root of numTuples, etc.
+ double maxValue = Math.ceil(Math.pow(numTuples, 1.0 / (double) numKeyFields));
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ setDoubleKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+ TupleUtils.createDoubleTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
+ LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ }
+ boolean succeeded = insertTuple(ctx);
+ if (succeeded) {
+ ctx.insertCheckTuple(createDoubleCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+ }
+ }
+ }
+
+ protected void setDoubleKeyFields(double[] fieldValues, int numKeyFields, double maxValue, Random rnd) {
+ int maxFieldPos = numKeyFields / 2;
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ double firstValue = rnd.nextDouble() % maxValue;
+ double secondValue;
+ do {
+ secondValue = rnd.nextDouble() % maxValue;
+ } while (secondValue < firstValue);
+ fieldValues[j] = firstValue;
+ fieldValues[k] = secondValue;
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ protected CheckTuple createDoubleCheckTuple(double[] fieldValues, int numKeyFields) {
+ RTreeCheckTuple<Double> checkTuple = new RTreeCheckTuple<Double>(fieldValues.length, numKeyFields);
+ for (double v : fieldValues) {
+ checkTuple.add(v);
+ }
+ return checkTuple;
+ }
+
+ @SuppressWarnings("unchecked")
+ public void bulkLoadDoubleTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ double[] fieldValues = new double[ctx.getFieldCount()];
+ double maxValue = Math.ceil(Math.pow(numTuples, 1.0 / (double) numKeyFields));
+ Collection<CheckTuple> tmpCheckTuples = createCheckTuplesCollection();
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ setDoubleKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+
+ // Set expected values.
+ ctx.insertCheckTuple(createDoubleCheckTuple(fieldValues, ctx.getKeyFieldCount()), tmpCheckTuples);
+ }
+ bulkLoadCheckTuples(ctx, tmpCheckTuples);
+
+ // Add tmpCheckTuples to ctx check tuples for comparing searches.
+ for (CheckTuple checkTuple : tmpCheckTuples) {
+ ctx.insertCheckTuple(checkTuple, ctx.getCheckTuples());
+ }
+ }
+
+ @Override
+ public void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
+ ISerializerDeserializer[] fieldSerdes, int keyFieldCount) throws Exception {
+ int actualCount = 0;
+ try {
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference tuple = cursor.getTuple();
+ RTreeCheckTuple checkTuple = (RTreeCheckTuple) createCheckTupleFromTuple(tuple, fieldSerdes,
+ keyFieldCount);
+ if (!checkTuples.contains(checkTuple)) {
+ fail("Scan or range search returned unexpected answer: " + checkTuple.toString());
+ }
+ actualCount++;
+ }
+ if (actualCount < checkTuples.size()) {
+ fail("Scan or range search returned fewer answers than expected.\nExpected: " + checkTuples.size()
+ + "\nActual : " + actualCount);
+ }
+ if (actualCount > checkTuples.size()) {
+ fail("Scan or range search returned more answers than expected.\nExpected: " + checkTuples.size()
+ + "\nActual : " + actualCount);
+ }
+ } finally {
+ cursor.close();
+ }
+ }
+
+ @Override
+ protected CheckTuple createCheckTuple(int numFields, int numKeyFields) {
+ return new RTreeCheckTuple(numFields, numKeyFields);
+ }
+
+ @Override
+ protected ISearchPredicate createNullSearchPredicate() {
+ return new SearchPredicate(null, null);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
+ RTreeCheckTuple<Integer> checkTuple = new RTreeCheckTuple<Integer>(fieldValues.length, numKeyFields);
+ for (int v : fieldValues) {
+ checkTuple.add(v);
+ }
+ return checkTuple;
+ }
+
+ @Override
+ protected void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd) {
+ int maxFieldPos = numKeyFields / 2;
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ int firstValue = rnd.nextInt() % maxValue;
+ int secondValue;
+ do {
+ secondValue = rnd.nextInt() % maxValue;
+ } while (secondValue < firstValue);
+ fieldValues[j] = firstValue;
+ fieldValues[k] = secondValue;
+ }
+ }
+
+ @Override
+ protected boolean insertTuple(ITreeIndexTestContext ctx) throws Exception {
+ ctx.getIndexAccessor().insert(ctx.getTuple());
+ return true;
+ }
+
+ @Override
+ protected Collection createCheckTuplesCollection() {
+ return new ArrayList<RTreeCheckTuple>();
+ }
+
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/util/RTreeUtils.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/util/RTreeUtils.java
index 74e4840..f17d1ab 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/util/RTreeUtils.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/util/RTreeUtils.java
@@ -15,11 +15,55 @@
package edu.uci.ics.hyracks.storage.am.rtree.util;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
import edu.uci.ics.hyracks.data.std.api.IPointableFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.data.PointablePrimitiveValueProviderFactory;
+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.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
public class RTreeUtils {
+ public static RTree createRTree(IBufferCache bufferCache, int rtreeFileId, ITypeTraits[] typeTraits,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, IBinaryComparatorFactory[] cmpFactories) {
+
+ RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+ ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, rtreeFileId, 0, metaFrameFactory);
+ RTree rtree = new RTree(bufferCache, typeTraits.length, cmpFactories, freePageManager, interiorFrameFactory,
+ leafFrameFactory);
+ return rtree;
+ }
+
+ // Creates a new MultiComparator by constructing new IBinaryComparators.
+ public static MultiComparator getSearchMultiComparator(IBinaryComparatorFactory[] cmpFactories,
+ ITupleReference searchKey) {
+ if (searchKey == null || cmpFactories.length == searchKey.getFieldCount()) {
+ return MultiComparator.create(cmpFactories);
+ }
+ IBinaryComparator[] newCmps = new IBinaryComparator[searchKey.getFieldCount()];
+ for (int i = 0; i < searchKey.getFieldCount(); i++) {
+ newCmps[i] = cmpFactories[i].createBinaryComparator();
+ }
+ return new MultiComparator(newCmps);
+ }
+
public static IPrimitiveValueProviderFactory[] createPrimitiveValueProviderFactories(int len, IPointableFactory pf) {
IPrimitiveValueProviderFactory[] pvpfs = new IPrimitiveValueProviderFactory[len];
for (int i = 0; i < len; ++i) {
@@ -27,4 +71,4 @@
}
return pvpfs;
}
-}
+}
\ 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/AbstractRTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
deleted file mode 100644
index 8f619a4..0000000
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTest.java
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- * 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;
-
-import java.io.File;
-import java.text.SimpleDateFormat;
-import java.util.Date;
-import java.util.logging.Logger;
-
-import org.junit.AfterClass;
-
-public abstract class AbstractRTreeTest {
-
- protected static final Logger LOGGER = Logger.getLogger(AbstractRTreeTest.class.getName());
- 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());
-
- @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/RTreeBulkLoadTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
new file mode 100644
index 0000000..9eeaf26
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeBulkLoadTest extends AbstractRTreeBulkLoadTest {
+
+ public RTreeBulkLoadTest() {
+ super(1);
+ }
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
+ fieldSerdes, valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
new file mode 100644
index 0000000..86b3684
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
@@ -0,0 +1,57 @@
+/*
+ * 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;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeDeleteTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeDeleteTest extends AbstractRTreeDeleteTest {
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
+ fieldSerdes, valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
new file mode 100644
index 0000000..9f31352
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
@@ -0,0 +1,53 @@
+/*
+ * 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;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeExamplesTest;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+public class RTreeExamplesTest extends AbstractRTreeExamplesTest {
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories) throws TreeIndexException {
+ return RTreeUtils.createRTree(harness.getBufferCache(), harness.getTreeFileId(), typeTraits,
+ valueProviderFactories, cmpFactories);
+ }
+
+ protected int getIndexFileId() {
+ return harness.getTreeFileId();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
new file mode 100644
index 0000000..6a0cb6b
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
@@ -0,0 +1,67 @@
+/*
+ * 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;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeInsertTest;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ *
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ *
+ */
+@SuppressWarnings("rawtypes")
+public class RTreeInsertTest extends AbstractRTreeInsertTest {
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return (AbstractRTreeTestContext) RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(),
+ fieldSerdes, valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
new file mode 100644
index 0000000..cacb9fc
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -0,0 +1,174 @@
+/*
+ * 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;
+
+import java.util.ArrayList;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+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.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.RTreeCheckTuple;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.RTreeTestUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.AbstractRTreeTest;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class RTreeSearchCursorTest extends AbstractRTreeTest {
+
+ private final RTreeTestUtils rTreeTestUtils;
+ private Random rnd = new Random(50);
+
+ public RTreeSearchCursorTest() {
+ this.rTreeTestUtils = new RTreeTestUtils();
+ }
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ super.setUp();
+ }
+
+ @SuppressWarnings({ "unchecked", "rawtypes" })
+ @Test
+ public void rangeSearchTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR FOR RTREE");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int rtreeFileId = harness.getTreeFileId();
+
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ // Declare keys.
+ int keyFieldCount = 4;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, IntegerPointable.FACTORY);
+
+ RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+ ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+
+ IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
+ IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, rtreeFileId, 0, metaFrameFactory);
+
+ RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory,
+ leafFrameFactory);
+ rtree.create(rtreeFileId);
+ rtree.open(rtreeFileId);
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = rtree.createAccessor();
+ int numInserts = 10000;
+ ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
+ for (int i = 0; i < numInserts; i++) {
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+
+ int pk = 5;
+
+ TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), pk);
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ }
+ RTreeCheckTuple checkTuple = new RTreeCheckTuple(fieldCount, keyFieldCount);
+ checkTuple.add(Math.min(p1x, p2x));
+ checkTuple.add(Math.min(p1y, p2y));
+ checkTuple.add(Math.max(p1x, p2x));
+ checkTuple.add(Math.max(p1y, p2y));
+
+ checkTuples.add(checkTuple);
+ }
+
+ // Build key.
+ ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+ ArrayTupleReference key = new ArrayTupleReference();
+ TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
+
+ MultiComparator cmp = MultiComparator.create(cmpFactories);
+ ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
+ SearchPredicate searchPredicate = new SearchPredicate(key, cmp);
+
+ RTreeCheckTuple keyCheck = (RTreeCheckTuple) rTreeTestUtils.createCheckTupleFromTuple(key, fieldSerdes,
+ keyFieldCount);
+ ArrayList<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+
+ rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+ indexAccessor.search(searchCursor, searchPredicate);
+
+ rTreeTestUtils.checkExpectedResults(searchCursor, expectedResult, fieldSerdes, keyFieldCount);
+
+ rtree.close();
+ }
+
+}
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
deleted file mode 100644
index e42e92e..0000000
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ /dev/null
@@ -1,760 +0,0 @@
-/*
- * 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;
-
-import java.io.DataOutput;
-import java.io.File;
-import java.nio.ByteBuffer;
-import java.util.Random;
-import java.util.logging.Level;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
-import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
-import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
-import edu.uci.ics.hyracks.api.io.FileReference;
-import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
-import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
-import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
-import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
-import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
-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.impls.TreeDiskOrderScanCursor;
-import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStats;
-import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
-import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
-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 MAX_OPEN_FILES = 10;
- private static final int HYRACKS_FRAME_SIZE = 128;
- private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
-
- // create an R-tree of two dimensions
- // fill the R-tree with random values using insertions
- // perform ordered scan
- @Test
- public void test01() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- 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 keys
- int keyFieldCount = 4;
- IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
- cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
- cmpFactories[1] = cmpFactories[0];
- cmpFactories[2] = cmpFactories[0];
- cmpFactories[3] = cmpFactories[0];
-
- // declare tuple fields
- int fieldCount = 7;
- ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- typeTraits[0] = DoublePointable.TYPE_TRAITS;
- typeTraits[1] = DoublePointable.TYPE_TRAITS;
- typeTraits[2] = DoublePointable.TYPE_TRAITS;
- typeTraits[3] = DoublePointable.TYPE_TRAITS;
- typeTraits[4] = DoublePointable.TYPE_TRAITS;
- typeTraits[5] = IntegerPointable.TYPE_TRAITS;
- typeTraits[6] = DoublePointable.TYPE_TRAITS;
-
- // create value providers
- IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
- cmpFactories.length, DoublePointable.FACTORY);
-
- RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
- rtree.create(fileId);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
- DataOutput dos = tb.getDataOutput();
-
- @SuppressWarnings("rawtypes")
- ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
- accessor.reset(hyracksFrame);
- FrameTupleReference tuple = new FrameTupleReference();
-
- ITreeIndexAccessor indexAccessor = rtree.createAccessor();
-
- Random rnd = new Random();
- rnd.setSeed(50);
-
- Random rnd2 = new Random();
- rnd2.setSeed(50);
- for (int i = 0; i < 5000; i++) {
-
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
-
- double pk1 = rnd2.nextDouble();
- int pk2 = rnd2.nextInt();
- double pk3 = rnd2.nextDouble();
-
- 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();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
- }
-
- try {
- indexAccessor.insert(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- String rtreeStats = rtree.printStats();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rtreeStats);
- }
-
- // disk-order scan
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info("DISK-ORDER SCAN:");
- }
- TreeDiskOrderScanCursor diskOrderCursor = new TreeDiskOrderScanCursor(leafFrame);
- indexAccessor.diskOrderScan(diskOrderCursor);
- try {
- while (diskOrderCursor.hasNext()) {
- diskOrderCursor.next();
- ITupleReference frameTuple = diskOrderCursor.getTuple();
- String rec = TupleUtils.printTuple(frameTuple, recDescSers);
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rec);
- }
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- diskOrderCursor.close();
- }
-
- TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
- rtree.getRootPageId());
- TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
- String string = stats.toString();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(string);
- }
-
- rtree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
-
- }
-
- // create an R-tree of two dimensions
- // fill the R-tree with random values using insertions
- // and then delete all the tuples which result of an empty R-tree
- @Test
- public void test02() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- 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 keys
- int keyFieldCount = 4;
- IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
- cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
- cmpFactories[1] = cmpFactories[0];
- cmpFactories[2] = cmpFactories[0];
- cmpFactories[3] = cmpFactories[0];
-
- // declare tuple fields
- int fieldCount = 7;
- ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- typeTraits[0] = DoublePointable.TYPE_TRAITS;
- typeTraits[1] = DoublePointable.TYPE_TRAITS;
- typeTraits[2] = DoublePointable.TYPE_TRAITS;
- typeTraits[3] = DoublePointable.TYPE_TRAITS;
- typeTraits[4] = DoublePointable.TYPE_TRAITS;
- typeTraits[5] = IntegerPointable.TYPE_TRAITS;
- typeTraits[6] = DoublePointable.TYPE_TRAITS;
-
- // create value providers
- IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
- cmpFactories.length, DoublePointable.FACTORY);
-
- RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
- rtree.create(fileId);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
- DataOutput dos = tb.getDataOutput();
-
- @SuppressWarnings("rawtypes")
- ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
- accessor.reset(hyracksFrame);
- FrameTupleReference tuple = new FrameTupleReference();
-
- ITreeIndexAccessor indexAccessor = rtree.createAccessor();
-
- Random rnd = new Random();
- rnd.setSeed(50);
-
- for (int i = 0; i < 5000; i++) {
-
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
-
- double pk1 = rnd.nextDouble();
- int pk2 = rnd.nextInt();
- double pk3 = rnd.nextDouble();
-
- 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();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
- }
-
- try {
- indexAccessor.insert(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- String rtreeStats = rtree.printStats();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rtreeStats);
- }
-
- rnd.setSeed(50);
- for (int i = 0; i < 5000; i++) {
-
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
-
- double pk1 = rnd.nextDouble();
- int pk2 = rnd.nextInt();
- double pk3 = rnd.nextDouble();
-
- 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();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("DELETING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
- }
-
- try {
- indexAccessor.delete(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
- rtree.getRootPageId());
- TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
- String string = stats.toString();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(string);
- }
-
- rtree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
-
- }
-
- // create an R-tree of three dimensions
- // fill the R-tree with random values using insertions
- // perform ordered scan
- @Test
- public void test03() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- 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 keys
- int keyFieldCount = 6;
- IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
- cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
- cmpFactories[1] = cmpFactories[0];
- cmpFactories[2] = cmpFactories[0];
- cmpFactories[3] = cmpFactories[0];
- cmpFactories[4] = cmpFactories[0];
- cmpFactories[5] = cmpFactories[0];
-
- // declare tuple fields
- int fieldCount = 9;
- ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- typeTraits[0] = DoublePointable.TYPE_TRAITS;
- typeTraits[1] = DoublePointable.TYPE_TRAITS;
- typeTraits[2] = DoublePointable.TYPE_TRAITS;
- typeTraits[3] = DoublePointable.TYPE_TRAITS;
- typeTraits[4] = DoublePointable.TYPE_TRAITS;
- typeTraits[5] = DoublePointable.TYPE_TRAITS;
- typeTraits[6] = DoublePointable.TYPE_TRAITS;
- typeTraits[7] = IntegerPointable.TYPE_TRAITS;
- typeTraits[8] = DoublePointable.TYPE_TRAITS;
-
- // create value providers
- IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
- cmpFactories.length, DoublePointable.FACTORY);
-
- RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
- rtree.create(fileId);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
- DataOutput dos = tb.getDataOutput();
-
- @SuppressWarnings("rawtypes")
- ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
- accessor.reset(hyracksFrame);
- FrameTupleReference tuple = new FrameTupleReference();
-
- ITreeIndexAccessor indexAccessor = rtree.createAccessor();
-
- Random rnd = new Random();
- rnd.setSeed(50);
-
- for (int i = 0; i < 5000; i++) {
-
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p1z = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
- double p2z = rnd.nextDouble();
-
- double pk1 = rnd.nextDouble();
- int pk2 = rnd.nextInt();
- double pk3 = rnd.nextDouble();
-
- 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.min(p1z, p2z), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1z, p2z), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.min(p1z, p2z) + " " + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + " "
- + Math.max(p1z, p2z));
- }
- }
-
- try {
- indexAccessor.insert(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- String rtreeStats = rtree.printStats();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rtreeStats);
- }
-
- // disk-order scan
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info("DISK-ORDER SCAN:");
- }
- TreeDiskOrderScanCursor diskOrderCursor = new TreeDiskOrderScanCursor(leafFrame);
- indexAccessor.diskOrderScan(diskOrderCursor);
- try {
- while (diskOrderCursor.hasNext()) {
- diskOrderCursor.next();
- ITupleReference frameTuple = diskOrderCursor.getTuple();
- String rec = TupleUtils.printTuple(frameTuple, recDescSers);
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rec);
- }
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- diskOrderCursor.close();
- }
-
- TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
- rtree.getRootPageId());
- TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
- String string = stats.toString();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(string);
- }
-
- rtree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
-
- }
-
- // create an R-tree of two dimensions
- // fill the R-tree with random integer key values using insertions
- // perform ordered scan
- @Test
- public void test04() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- 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 keys
- int keyFieldCount = 4;
- IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
- cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
- cmpFactories[1] = cmpFactories[0];
- cmpFactories[2] = cmpFactories[0];
- cmpFactories[3] = cmpFactories[0];
-
- // declare tuple fields
- int fieldCount = 7;
- ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- typeTraits[0] = IntegerPointable.TYPE_TRAITS;
- typeTraits[1] = IntegerPointable.TYPE_TRAITS;
- typeTraits[2] = IntegerPointable.TYPE_TRAITS;
- typeTraits[3] = IntegerPointable.TYPE_TRAITS;
- typeTraits[4] = DoublePointable.TYPE_TRAITS;
- typeTraits[5] = IntegerPointable.TYPE_TRAITS;
- typeTraits[6] = DoublePointable.TYPE_TRAITS;
-
- // create value providers
- IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
- cmpFactories.length, IntegerPointable.FACTORY);
-
- RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
- rtree.create(fileId);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
- DataOutput dos = tb.getDataOutput();
-
- @SuppressWarnings("rawtypes")
- ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
- accessor.reset(hyracksFrame);
- FrameTupleReference tuple = new FrameTupleReference();
-
- ITreeIndexAccessor indexAccessor = rtree.createAccessor();
-
- Random rnd = new Random();
- rnd.setSeed(50);
-
- Random rnd2 = new Random();
- rnd2.setSeed(50);
- for (int i = 0; i < 5000; i++) {
-
- int p1x = rnd.nextInt();
- int p1y = rnd.nextInt();
- int p2x = rnd.nextInt();
- int p2y = rnd.nextInt();
-
- double pk1 = rnd2.nextDouble();
- int pk2 = rnd2.nextInt();
- double pk3 = rnd2.nextDouble();
-
- tb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
- }
-
- try {
- indexAccessor.insert(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- String rtreeStats = rtree.printStats();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rtreeStats);
- }
-
- // disk-order scan
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info("DISK-ORDER SCAN:");
- }
- TreeDiskOrderScanCursor diskOrderCursor = new TreeDiskOrderScanCursor(leafFrame);
- indexAccessor.diskOrderScan(diskOrderCursor);
- try {
- while (diskOrderCursor.hasNext()) {
- diskOrderCursor.next();
- ITupleReference frameTuple = diskOrderCursor.getTuple();
- String rec = TupleUtils.printTuple(frameTuple, recDescSers);
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(rec);
- }
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- diskOrderCursor.close();
- }
-
- TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
- rtree.getRootPageId());
- TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
- String string = stats.toString();
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(string);
- }
-
- rtree.close();
- 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/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
deleted file mode 100644
index 3f36753..0000000
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ /dev/null
@@ -1,249 +0,0 @@
-/*
- * 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;
-
-import java.io.ByteArrayInputStream;
-import java.io.DataInput;
-import java.io.DataInputStream;
-import java.io.DataOutput;
-import java.io.File;
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.Random;
-import java.util.logging.Level;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
-import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
-import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
-import edu.uci.ics.hyracks.api.io.FileReference;
-import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
-import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
-import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
-import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.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.IPrimitiveValueProviderFactory;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
-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.rtree.api.IRTreeInteriorFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
-import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
-import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
-import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
-import edu.uci.ics.hyracks.test.support.TestUtils;
-
-public class SearchCursorTest extends AbstractRTreeTest {
- private static final int PAGE_SIZE = 256;
- private static final int NUM_PAGES = 10;
- private static final int MAX_OPEN_FILES = 10;
- private static final int HYRACKS_FRAME_SIZE = 128;
- private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
-
- // create an R-tree of two dimensions
- // fill the R-tree with random values using insertions
- // and then perform range search
- @Test
- public void searchCursorTest() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- 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 keys
- int keyFieldCount = 4;
- IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
- cmpFactories[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY);
- cmpFactories[1] = cmpFactories[0];
- cmpFactories[2] = cmpFactories[0];
- cmpFactories[3] = cmpFactories[0];
-
- // declare tuple fields
- int fieldCount = 5;
- ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- typeTraits[0] = DoublePointable.TYPE_TRAITS;
- typeTraits[1] = DoublePointable.TYPE_TRAITS;
- typeTraits[2] = DoublePointable.TYPE_TRAITS;
- typeTraits[3] = DoublePointable.TYPE_TRAITS;
- typeTraits[4] = IntegerPointable.TYPE_TRAITS;
-
- // create value providers
- IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
- cmpFactories.length, DoublePointable.FACTORY);
-
- RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
- valueProviderFactories);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
-
- IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
- IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
- rtree.create(fileId);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
- 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();
-
- ITreeIndexAccessor indexAccessor = rtree.createAccessor();
-
- Random rnd = new Random();
- rnd.setSeed(50);
- for (int i = 0; i < 5000; i++) {
-
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- if (i % 1000 == 0) {
- LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
- }
-
- try {
- indexAccessor.insert(tuple);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
-
- MultiComparator cmp = MultiComparator.create(cmpFactories);
- for (int i = 0; i < 50; i++) {
- double p1x = rnd.nextDouble();
- double p1y = rnd.nextDouble();
- double p2x = rnd.nextDouble();
- double p2y = rnd.nextDouble();
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info(i + " Searching for: " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
- + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
- }
-
- ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
- SearchPredicate searchPredicate = new SearchPredicate(tuple, cmp);
-
- indexAccessor.search(searchCursor, searchPredicate);
-
- ArrayList<Integer> results = new ArrayList<Integer>();
- try {
- while (searchCursor.hasNext()) {
- searchCursor.next();
- ITupleReference frameTuple = searchCursor.getTuple();
- ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(4),
- frameTuple.getFieldStart(4), frameTuple.getFieldLength(4));
- DataInput dataIn = new DataInputStream(inStream);
- Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
- results.add(res);
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- searchCursor.close();
- }
- if (LOGGER.isLoggable(Level.INFO)) {
- LOGGER.info("There are " + results.size() + " objects that satisfy the query");
- }
- }
-
- rtree.close();
- 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/utils/AbstractRTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
new file mode 100644
index 0000000..fccb29c
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
@@ -0,0 +1,46 @@
+/*
+ * 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.utils;
+
+import java.util.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public abstract class AbstractRTreeTest {
+ protected final Logger LOGGER = Logger.getLogger(RTreeTestHarness.class.getName());
+ protected final RTreeTestHarness harness;
+
+ public AbstractRTreeTest() {
+ harness = new RTreeTestHarness();
+ }
+
+ public AbstractRTreeTest(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ harness = new RTreeTestHarness(pageSize, numPages, maxOpenFiles, hyracksFrameSize);
+ }
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java
new file mode 100644
index 0000000..56a3c64
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java
@@ -0,0 +1,60 @@
+/*
+ * 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.utils;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.tests.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class RTreeTestContext extends AbstractRTreeTestContext {
+
+ public RTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ super(fieldSerdes, treeIndex);
+ }
+
+ @Override
+ public int getKeyFieldCount() {
+ RTree rtree = (RTree) treeIndex;
+ return rtree.getComparatorFactories().length;
+ }
+
+ @Override
+ public IBinaryComparatorFactory[] getComparatorFactories() {
+ RTree rtree = (RTree) treeIndex;
+ return rtree.getComparatorFactories();
+ }
+
+ public static RTreeTestContext create(IBufferCache bufferCache, int rtreeFileId,
+ ISerializerDeserializer[] fieldSerdes, IPrimitiveValueProviderFactory[] valueProviderFactories,
+ int numKeyFields) throws Exception {
+ ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+ IBinaryComparatorFactory[] cmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes, numKeyFields);
+ RTree rtree = RTreeUtils
+ .createRTree(bufferCache, rtreeFileId, typeTraits, valueProviderFactories, cmpFactories);
+ rtree.create(rtreeFileId);
+ rtree.open(rtreeFileId);
+ RTreeTestContext testCtx = new RTreeTestContext(fieldSerdes, rtree);
+ return testCtx;
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
new file mode 100644
index 0000000..c82d6e4
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
@@ -0,0 +1,123 @@
+/*
+ * 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.utils;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+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 RTreeTestHarness {
+
+ private static final long RANDOM_SEED = 50;
+ private static final int DEFAULT_PAGE_SIZE = 256;
+ private static final int DEFAULT_NUM_PAGES = 10;
+ private static final int DEFAULT_MAX_OPEN_FILES = 10;
+ private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+
+ protected final int pageSize;
+ protected final int numPages;
+ protected final int maxOpenFiles;
+ protected final int hyracksFrameSize;
+
+ protected IHyracksTaskContext ctx;
+ protected IBufferCache bufferCache;
+ protected int treeFileId;
+
+ protected final Random rnd = new Random();
+ protected final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final String sep = System.getProperty("file.separator");
+ protected String fileName;
+
+ public RTreeTestHarness() {
+ this.pageSize = DEFAULT_PAGE_SIZE;
+ this.numPages = DEFAULT_NUM_PAGES;
+ this.maxOpenFiles = DEFAULT_MAX_OPEN_FILES;
+ this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+ }
+
+ public RTreeTestHarness(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ this.pageSize = pageSize;
+ this.numPages = numPages;
+ this.maxOpenFiles = maxOpenFiles;
+ this.hyracksFrameSize = hyracksFrameSize;
+ }
+
+ public void setUp() throws HyracksDataException {
+ fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+ ctx = TestUtils.create(getHyracksFrameSize());
+ TestStorageManagerComponentHolder.init(pageSize, numPages, maxOpenFiles);
+ bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ treeFileId = fmp.lookupFileId(file);
+ bufferCache.openFile(treeFileId);
+ rnd.setSeed(RANDOM_SEED);
+ }
+
+ public void tearDown() throws HyracksDataException {
+ bufferCache.closeFile(treeFileId);
+ bufferCache.close();
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+
+ public IHyracksTaskContext getHyracksTaskContext() {
+ return ctx;
+ }
+
+ public IBufferCache getBufferCache() {
+ return bufferCache;
+ }
+
+ public int getTreeFileId() {
+ return treeFileId;
+ }
+
+ public String getFileName() {
+ return fileName;
+ }
+
+ public Random getRandom() {
+ return rnd;
+ }
+
+ public int getPageSize() {
+ return pageSize;
+ }
+
+ public int getNumPages() {
+ return numPages;
+ }
+
+ public int getHyracksFrameSize() {
+ return hyracksFrameSize;
+ }
+
+ public int getMaxOpenFiles() {
+ return maxOpenFiles;
+ }
+}