Changes to fix issue 802
commit 2ddbfc584ec2869efb380d7f0e03f450f7f73c0a
Author: Young-Seok <kisskys@gmail.com>
Date: Thu Sep 25 10:10:10 2014 -0700
Change-Id: I1a36af2712e809588b9d579d81bfeda27eb2b5c2
Reviewed-on: http://fulliautomatix.ics.uci.edu:8443/141
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Taewoo Kim <wangsaeu@gmail.com>
diff --git a/algebricks/algebricks-data/src/main/java/edu/uci/ics/hyracks/algebricks/data/ILinearizeComparatorFactoryProvider.java b/algebricks/algebricks-data/src/main/java/edu/uci/ics/hyracks/algebricks/data/ILinearizeComparatorFactoryProvider.java
new file mode 100644
index 0000000..fdc5114
--- /dev/null
+++ b/algebricks/algebricks-data/src/main/java/edu/uci/ics/hyracks/algebricks/data/ILinearizeComparatorFactoryProvider.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2009-2013 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.algebricks.data;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+
+public interface ILinearizeComparatorFactoryProvider {
+ public ILinearizeComparatorFactory getLinearizeComparatorFactory(Object type, boolean ascending, int dimension)
+ throws AlgebricksException;
+}
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/HilbertDoubleComparator.java b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/HilbertDoubleComparator.java
index 55b341b..9aa9a53 100644
--- a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/HilbertDoubleComparator.java
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/HilbertDoubleComparator.java
@@ -12,183 +12,183 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.rtree.linearize;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
-import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
-import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProvider;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.DoublePrimitiveValueProviderFactory;
-
-/*
- * This compares two points based on the hilbert curve. Currently, it only supports
- * doubles (this can be changed by changing all doubles to ints as there are no
- * number generics in Java) in the two-dimensional space. For more dimensions, the
- * state machine has to be automatically generated. The idea of the fractal generation
- * of the curve is described e.g. in http://dl.acm.org/ft_gateway.cfm?id=383528&type=pdf
- *
- * Unlike the described approach, this comparator does not compute the hilbert value at
- * any point. Instead, it only evaluates how the two inputs compare to each other. This
- * is done by starting at the lowest hilbert resolution and zooming in on the fractal until
- * the two points are in different quadrants.
- *
- * As a performance optimization, the state of the state machine is saved in a stack and
- * maintained over comparisons. The idea behind this is that comparisons are usually in a
- * similar area (e.g. geo coordinates). Zooming in from [-MAX_VALUE, MAX_VALUE] would take
- * ~300 steps every time. Instead, the comparator start from the previous state and zooms out
- * if necessary
- */
-
-public class HilbertDoubleComparator implements ILinearizeComparator {
- private final int dim; // dimension
- private final HilbertState[] states;
-
- private double[] bounds;
- private double stepsize;
- private int state;
- private IntArrayList stateStack = new IntArrayList(1000, 200);
- private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
-
- private IPrimitiveValueProvider valueProvider = DoublePrimitiveValueProviderFactory.INSTANCE
- .createPrimitiveValueProvider();
-
- private double[] a;
- private double[] b;
-
- private class HilbertState {
- public final int[] nextState;
- public final int[] position;
-
- public HilbertState(int[] nextState, int[] order) {
- this.nextState = nextState;
- this.position = order;
- }
- }
-
- public HilbertDoubleComparator(int dimension) {
- if (dimension != 2)
- throw new IllegalArgumentException();
- dim = dimension;
- a = new double[dim];
- b = new double[dim];
-
- states = new HilbertState[] { new HilbertState(new int[] { 3, 0, 1, 0 }, new int[] { 0, 1, 3, 2 }),
- new HilbertState(new int[] { 1, 1, 0, 2 }, new int[] { 2, 1, 3, 0 }),
- new HilbertState(new int[] { 2, 3, 2, 1 }, new int[] { 2, 3, 1, 0 }),
- new HilbertState(new int[] { 0, 2, 3, 3 }, new int[] { 0, 3, 1, 2 }) };
-
- resetStateMachine();
- }
-
- private void resetStateMachine() {
- state = 0;
- stateStack.clear();
- stepsize = Double.MAX_VALUE / 2;
- bounds = new double[dim];
- boundsStack.clear();
- }
-
- public int compare() {
- boolean equal = true;
- for (int i = 0; i < dim; i++) {
- if (a[i] != b[i])
- equal = false;
- }
- if (equal)
- return 0;
-
- // We keep the state of the state machine after a comparison. In most
- // cases,
- // the needed zoom factor is close to the old one. In this step, we
- // check if we have
- // to zoom out
- while (true) {
- if (stateStack.size() <= dim) {
- resetStateMachine();
- break;
- }
- boolean zoomOut = false;
- for (int i = 0; i < dim; i++) {
- if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
- || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
- zoomOut = true;
- break;
- }
- }
- state = stateStack.getLast();
- stateStack.removeLast();
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- if (!zoomOut) {
- state = stateStack.getLast();
- stateStack.removeLast();
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- break;
- }
- }
-
- while (true) {
- stateStack.add(state);
- for (int j = 0; j < dim; j++) {
- boundsStack.add(bounds[j]);
- }
-
- // Find the quadrant in which A and B are
- int quadrantA = 0, quadrantB = 0;
- for (int i = dim - 1; i >= 0; i--) {
- if (a[i] >= bounds[i])
- quadrantA ^= (1 << (dim - i - 1));
- if (b[i] >= bounds[i])
- quadrantB ^= (1 << (dim - i - 1));
-
- if (a[i] >= bounds[i]) {
- bounds[i] += stepsize;
- } else {
- bounds[i] -= stepsize;
- }
- }
-
- stepsize /= 2;
- if (stepsize <= 2 * DoublePointable.getEpsilon())
- return 0;
- // avoid infinite loop due to machine epsilon problems
-
- if (quadrantA != quadrantB) {
- // find the position of A and B's quadrants
- int posA = states[state].position[quadrantA];
- int posB = states[state].position[quadrantB];
-
- if (posA < posB)
- return -1;
- else
- return 1;
- }
-
- state = states[state].nextState[quadrantA];
- }
- }
-
- @Override
- public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
- for (int i = 0; i < dim; i++) {
- a[i] = DoubleSerializerDeserializer.getDouble(b1, s1 + (i * 8));
- b[i] = DoubleSerializerDeserializer.getDouble(b2, s2 + (i * 8));
- }
-
- return compare();
- }
-
- @Override
- public int getDimensions() {
- return dim;
- }
-}
+package edu.uci.ics.hyracks.storage.am.rtree.linearize;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProvider;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.DoublePrimitiveValueProviderFactory;
+
+/*
+ * This compares two points based on the hilbert curve. Currently, it only supports
+ * doubles (this can be changed by changing all doubles to ints as there are no
+ * number generics in Java) in the two-dimensional space. For more dimensions, the
+ * state machine has to be automatically generated. The idea of the fractal generation
+ * of the curve is described e.g. in http://dl.acm.org/ft_gateway.cfm?id=383528&type=pdf
+ *
+ * Unlike the described approach, this comparator does not compute the hilbert value at
+ * any point. Instead, it only evaluates how the two inputs compare to each other. This
+ * is done by starting at the lowest hilbert resolution and zooming in on the fractal until
+ * the two points are in different quadrants.
+ *
+ * As a performance optimization, the state of the state machine is saved in a stack and
+ * maintained over comparisons. The idea behind this is that comparisons are usually in a
+ * similar area (e.g. geo coordinates). Zooming in from [-MAX_VALUE, MAX_VALUE] would take
+ * ~300 steps every time. Instead, the comparator start from the previous state and zooms out
+ * if necessary
+ */
+
+public class HilbertDoubleComparator implements ILinearizeComparator {
+ private final int dim; // dimension
+ private final HilbertState[] states;
+
+ private double[] bounds;
+ private double stepsize;
+ private int state;
+ private IntArrayList stateStack = new IntArrayList(1000, 200);
+ private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
+
+ private IPrimitiveValueProvider valueProvider = DoublePrimitiveValueProviderFactory.INSTANCE
+ .createPrimitiveValueProvider();
+
+ private double[] a;
+ private double[] b;
+
+ private class HilbertState {
+ public final int[] nextState;
+ public final int[] position;
+
+ public HilbertState(int[] nextState, int[] order) {
+ this.nextState = nextState;
+ this.position = order;
+ }
+ }
+
+ public HilbertDoubleComparator(int dimension) {
+ if (dimension != 2)
+ throw new IllegalArgumentException();
+ dim = dimension;
+ a = new double[dim];
+ b = new double[dim];
+
+ states = new HilbertState[] { new HilbertState(new int[] { 3, 0, 1, 0 }, new int[] { 0, 1, 3, 2 }),
+ new HilbertState(new int[] { 1, 1, 0, 2 }, new int[] { 2, 1, 3, 0 }),
+ new HilbertState(new int[] { 2, 3, 2, 1 }, new int[] { 2, 3, 1, 0 }),
+ new HilbertState(new int[] { 0, 2, 3, 3 }, new int[] { 0, 3, 1, 2 }) };
+
+ resetStateMachine();
+ }
+
+ private void resetStateMachine() {
+ state = 0;
+ stateStack.clear();
+ stepsize = Double.MAX_VALUE / 2;
+ bounds = new double[dim];
+ boundsStack.clear();
+ }
+
+ public int compare() {
+ boolean equal = true;
+ for (int i = 0; i < dim; i++) {
+ if (a[i] != b[i])
+ equal = false;
+ }
+ if (equal)
+ return 0;
+
+ // We keep the state of the state machine after a comparison. In most
+ // cases,
+ // the needed zoom factor is close to the old one. In this step, we
+ // check if we have
+ // to zoom out
+ while (true) {
+ if (stateStack.size() <= dim) {
+ resetStateMachine();
+ break;
+ }
+ boolean zoomOut = false;
+ for (int i = 0; i < dim; i++) {
+ if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
+ || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
+ zoomOut = true;
+ break;
+ }
+ }
+ state = stateStack.getLast();
+ stateStack.removeLast();
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ if (!zoomOut) {
+ state = stateStack.getLast();
+ stateStack.removeLast();
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ break;
+ }
+ }
+
+ while (true) {
+ stateStack.add(state);
+ for (int j = 0; j < dim; j++) {
+ boundsStack.add(bounds[j]);
+ }
+
+ // Find the quadrant in which A and B are
+ int quadrantA = 0, quadrantB = 0;
+ for (int i = dim - 1; i >= 0; i--) {
+ if (a[i] >= bounds[i])
+ quadrantA ^= (1 << (dim - i - 1));
+ if (b[i] >= bounds[i])
+ quadrantB ^= (1 << (dim - i - 1));
+
+ if (a[i] >= bounds[i]) {
+ bounds[i] += stepsize;
+ } else {
+ bounds[i] -= stepsize;
+ }
+ }
+
+ stepsize /= 2;
+ if (stepsize <= 2 * DoublePointable.getEpsilon())
+ return 0;
+ // avoid infinite loop due to machine epsilon problems
+
+ if (quadrantA != quadrantB) {
+ // find the position of A and B's quadrants
+ int posA = states[state].position[quadrantA];
+ int posB = states[state].position[quadrantB];
+
+ if (posA < posB)
+ return -1;
+ else
+ return 1;
+ }
+
+ state = states[state].nextState[quadrantA];
+ }
+ }
+
+ @Override
+ public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
+ for (int i = 0; i < dim; i++) {
+ a[i] = DoubleSerializerDeserializer.getDouble(b1, s1 + (i * l1));
+ b[i] = DoubleSerializerDeserializer.getDouble(b2, s2 + (i * l2));
+ }
+
+ return compare();
+ }
+
+ @Override
+ public int getDimensions() {
+ return dim;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveDoubleComparator.java b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveDoubleComparator.java
index 5c90c7d..d470eea 100644
--- a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveDoubleComparator.java
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveDoubleComparator.java
@@ -12,139 +12,139 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.rtree.linearize;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
-import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
-import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProvider;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.DoublePrimitiveValueProviderFactory;
-
-/*
- * This compares two points based on the z curve. For doubles, we cannot use
- * the simple bit magic approach. There may, however, be a better approach than this.
- */
-
-public class ZCurveDoubleComparator implements ILinearizeComparator {
- private final int dim; // dimension
-
- private double[] bounds;
- private double stepsize;
- private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
-
- private IPrimitiveValueProvider valueProvider = DoublePrimitiveValueProviderFactory.INSTANCE
- .createPrimitiveValueProvider();
-
- private double[] a;
- private double[] b;
-
- public ZCurveDoubleComparator(int dimension) {
- dim = dimension;
- a = new double[dim];
- b = new double[dim];
-
- resetStateMachine();
- }
-
- private void resetStateMachine() {
- stepsize = Double.MAX_VALUE / 2;
- bounds = new double[dim];
- boundsStack.clear();
- }
-
- public int compare() {
- boolean equal = true;
- for (int i = 0; i < dim; i++) {
- if (a[i] != b[i])
- equal = false;
- }
- if (equal)
- return 0;
-
- // We keep the state of the state machine after a comparison. In most
- // cases,
- // the needed zoom factor is close to the old one. In this step, we
- // check if we have
- // to zoom out
- while (true) {
- if (boundsStack.size() <= dim) {
- resetStateMachine();
- break;
- }
- boolean zoomOut = false;
- for (int i = 0; i < dim; i++) {
- if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
- || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
- zoomOut = true;
- break;
- }
- }
-
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- if (!zoomOut) {
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- break;
- }
- }
-
- while (true) {
- for (int j = 0; j < dim; j++) {
- boundsStack.add(bounds[j]);
- }
-
- // Find the quadrant in which A and B are
- int quadrantA = 0, quadrantB = 0;
- for (int i = dim - 1; i >= 0; i--) {
- if (a[i] >= bounds[i])
- quadrantA ^= (1 << (dim - i - 1));
- if (b[i] >= bounds[i])
- quadrantB ^= (1 << (dim - i - 1));
-
- if (a[i] >= bounds[i]) {
- bounds[i] += stepsize;
- } else {
- bounds[i] -= stepsize;
- }
- }
-
- stepsize /= 2;
- if (stepsize <= 2 * DoublePointable.getEpsilon())
- return 0;
- // avoid infinite loop due to machine epsilon problems
-
- if (quadrantA != quadrantB) {
- // find the position of A and B's quadrants
- if (quadrantA < quadrantB)
- return -1;
- else if (quadrantA > quadrantB)
- return 1;
- else
- return 0;
- }
- }
- }
-
- @Override
- public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
- for (int i = 0; i < dim; i++) {
- a[i] = DoubleSerializerDeserializer.getDouble(b1, s1 + (i * 8));
- b[i] = DoubleSerializerDeserializer.getDouble(b2, s2 + (i * 8));
- }
-
- return compare();
- }
-
- @Override
- public int getDimensions() {
- return dim;
- }
-}
+package edu.uci.ics.hyracks.storage.am.rtree.linearize;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProvider;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.DoublePrimitiveValueProviderFactory;
+
+/*
+ * This compares two points based on the z curve. For doubles, we cannot use
+ * the simple bit magic approach. There may, however, be a better approach than this.
+ */
+
+public class ZCurveDoubleComparator implements ILinearizeComparator {
+ private final int dim; // dimension
+
+ private double[] bounds;
+ private double stepsize;
+ private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
+
+ private IPrimitiveValueProvider valueProvider = DoublePrimitiveValueProviderFactory.INSTANCE
+ .createPrimitiveValueProvider();
+
+ private double[] a;
+ private double[] b;
+
+ public ZCurveDoubleComparator(int dimension) {
+ dim = dimension;
+ a = new double[dim];
+ b = new double[dim];
+
+ resetStateMachine();
+ }
+
+ private void resetStateMachine() {
+ stepsize = Double.MAX_VALUE / 2;
+ bounds = new double[dim];
+ boundsStack.clear();
+ }
+
+ public int compare() {
+ boolean equal = true;
+ for (int i = 0; i < dim; i++) {
+ if (a[i] != b[i])
+ equal = false;
+ }
+ if (equal)
+ return 0;
+
+ // We keep the state of the state machine after a comparison. In most
+ // cases,
+ // the needed zoom factor is close to the old one. In this step, we
+ // check if we have
+ // to zoom out
+ while (true) {
+ if (boundsStack.size() <= dim) {
+ resetStateMachine();
+ break;
+ }
+ boolean zoomOut = false;
+ for (int i = 0; i < dim; i++) {
+ if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
+ || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
+ zoomOut = true;
+ break;
+ }
+ }
+
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ if (!zoomOut) {
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ break;
+ }
+ }
+
+ while (true) {
+ for (int j = 0; j < dim; j++) {
+ boundsStack.add(bounds[j]);
+ }
+
+ // Find the quadrant in which A and B are
+ int quadrantA = 0, quadrantB = 0;
+ for (int i = dim - 1; i >= 0; i--) {
+ if (a[i] >= bounds[i])
+ quadrantA ^= (1 << (dim - i - 1));
+ if (b[i] >= bounds[i])
+ quadrantB ^= (1 << (dim - i - 1));
+
+ if (a[i] >= bounds[i]) {
+ bounds[i] += stepsize;
+ } else {
+ bounds[i] -= stepsize;
+ }
+ }
+
+ stepsize /= 2;
+ if (stepsize <= 2 * DoublePointable.getEpsilon())
+ return 0;
+ // avoid infinite loop due to machine epsilon problems
+
+ if (quadrantA != quadrantB) {
+ // find the position of A and B's quadrants
+ if (quadrantA < quadrantB)
+ return -1;
+ else if (quadrantA > quadrantB)
+ return 1;
+ else
+ return 0;
+ }
+ }
+ }
+
+ @Override
+ public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
+ for (int i = 0; i < dim; i++) {
+ a[i] = DoubleSerializerDeserializer.getDouble(b1, s1 + (i * l1));
+ b[i] = DoubleSerializerDeserializer.getDouble(b2, s2 + (i * l2));
+ }
+
+ return compare();
+ }
+
+ @Override
+ public int getDimensions() {
+ return dim;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveIntComparator.java b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveIntComparator.java
index cc8cbf8..46e2579 100644
--- a/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveIntComparator.java
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/linearize/ZCurveIntComparator.java
@@ -12,132 +12,132 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.rtree.linearize;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
-import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
-
-/*
- * This compares two points based on the z curve. For doubles, we cannot use
- * the simple bit magic approach. There may, however, be a better approach than this.
- */
-
-public class ZCurveIntComparator implements ILinearizeComparator {
- private final int dim; // dimension
-
- private double[] bounds;
- private double stepsize;
- private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
-
- private int[] a;
- private int[] b;
-
- public ZCurveIntComparator(int dimension) {
- dim = dimension;
- a = new int[dim];
- b = new int[dim];
-
- resetStateMachine();
- }
-
- private void resetStateMachine() {
- stepsize = Integer.MAX_VALUE / 2;
- bounds = new double[dim];
- boundsStack.clear();
- }
-
- public int compare() {
- boolean equal = true;
- for (int i = 0; i < dim; i++) {
- if (a[i] != b[i])
- equal = false;
- }
- if (equal)
- return 0;
-
- // We keep the state of the state machine after a comparison. In most cases,
- // the needed zoom factor is close to the old one. In this step, we check if we have
- // to zoom out
- while (true) {
- if (boundsStack.size() <= dim) {
- resetStateMachine();
- break;
- }
- boolean zoomOut = false;
- for (int i = 0; i < dim; i++) {
- if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
- || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
- zoomOut = true;
- break;
- }
- }
-
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- if (!zoomOut) {
- for (int j = dim - 1; j >= 0; j--) {
- bounds[j] = boundsStack.getLast();
- boundsStack.removeLast();
- }
- stepsize *= 2;
- break;
- }
- }
-
- while (true) {
- for (int j = 0; j < dim; j++) {
- boundsStack.add(bounds[j]);
- }
-
- // Find the quadrant in which A and B are
- int quadrantA = 0, quadrantB = 0;
- for (int i = dim - 1; i >= 0; i--) {
- if (a[i] >= bounds[i])
- quadrantA ^= (1 << (dim - i - 1));
- if (b[i] >= bounds[i])
- quadrantB ^= (1 << (dim - i - 1));
-
- if (a[i] >= bounds[i]) {
- bounds[i] += stepsize;
- } else {
- bounds[i] -= stepsize;
- }
- }
-
- stepsize /= 2;
- if (stepsize <= 2 * DoublePointable.getEpsilon())
- return 0;
- // avoid infinite loop due to machine epsilon problems
-
- if (quadrantA != quadrantB) {
- // find the position of A and B's quadrants
- if (quadrantA < quadrantB)
- return -1;
- else if (quadrantA > quadrantB)
- return 1;
- else
- return 0;
- }
- }
- }
-
- @Override
- public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
- for (int i = 0; i < dim; i++) {
- a[i] = IntegerSerializerDeserializer.getInt(b1, s1 + (i * 8));
- b[i] = IntegerSerializerDeserializer.getInt(b2, s2 + (i * 8));
- }
-
- return compare();
- }
-
- @Override
- public int getDimensions() {
- return dim;
- }
-}
+package edu.uci.ics.hyracks.storage.am.rtree.linearize;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.DoubleArrayList;
+
+/*
+ * This compares two points based on the z curve. For doubles, we cannot use
+ * the simple bit magic approach. There may, however, be a better approach than this.
+ */
+
+public class ZCurveIntComparator implements ILinearizeComparator {
+ private final int dim; // dimension
+
+ private double[] bounds;
+ private double stepsize;
+ private DoubleArrayList boundsStack = new DoubleArrayList(2000, 400);
+
+ private int[] a;
+ private int[] b;
+
+ public ZCurveIntComparator(int dimension) {
+ dim = dimension;
+ a = new int[dim];
+ b = new int[dim];
+
+ resetStateMachine();
+ }
+
+ private void resetStateMachine() {
+ stepsize = Integer.MAX_VALUE / 2;
+ bounds = new double[dim];
+ boundsStack.clear();
+ }
+
+ public int compare() {
+ boolean equal = true;
+ for (int i = 0; i < dim; i++) {
+ if (a[i] != b[i])
+ equal = false;
+ }
+ if (equal)
+ return 0;
+
+ // We keep the state of the state machine after a comparison. In most cases,
+ // the needed zoom factor is close to the old one. In this step, we check if we have
+ // to zoom out
+ while (true) {
+ if (boundsStack.size() <= dim) {
+ resetStateMachine();
+ break;
+ }
+ boolean zoomOut = false;
+ for (int i = 0; i < dim; i++) {
+ if (Math.min(a[i], b[i]) <= bounds[i] - 2 * stepsize
+ || Math.max(a[i], b[i]) >= bounds[i] + 2 * stepsize) {
+ zoomOut = true;
+ break;
+ }
+ }
+
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ if (!zoomOut) {
+ for (int j = dim - 1; j >= 0; j--) {
+ bounds[j] = boundsStack.getLast();
+ boundsStack.removeLast();
+ }
+ stepsize *= 2;
+ break;
+ }
+ }
+
+ while (true) {
+ for (int j = 0; j < dim; j++) {
+ boundsStack.add(bounds[j]);
+ }
+
+ // Find the quadrant in which A and B are
+ int quadrantA = 0, quadrantB = 0;
+ for (int i = dim - 1; i >= 0; i--) {
+ if (a[i] >= bounds[i])
+ quadrantA ^= (1 << (dim - i - 1));
+ if (b[i] >= bounds[i])
+ quadrantB ^= (1 << (dim - i - 1));
+
+ if (a[i] >= bounds[i]) {
+ bounds[i] += stepsize;
+ } else {
+ bounds[i] -= stepsize;
+ }
+ }
+
+ stepsize /= 2;
+ if (stepsize <= 2 * DoublePointable.getEpsilon())
+ return 0;
+ // avoid infinite loop due to machine epsilon problems
+
+ if (quadrantA != quadrantB) {
+ // find the position of A and B's quadrants
+ if (quadrantA < quadrantB)
+ return -1;
+ else if (quadrantA > quadrantB)
+ return 1;
+ else
+ return 0;
+ }
+ }
+ }
+
+ @Override
+ public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
+ for (int i = 0; i < dim; i++) {
+ a[i] = IntegerSerializerDeserializer.getInt(b1, s1 + (i * l1));
+ b[i] = IntegerSerializerDeserializer.getInt(b2, s2 + (i * l2));
+ }
+
+ return compare();
+ }
+
+ @Override
+ public int getDimensions() {
+ return dim;
+ }
+}