Support sorting of arrays.

5 files changed, 392 insertions, 31 deletions

diff --git a/src/main/java/com/amazon/carbonado/cursor/Comparators.java b/src/main/java/com/amazon/carbonado/cursor/Comparators.java
new file mode 100644
index 0000000..bddd883
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/cursor/Comparators.java
@@ -0,0 +1,315 @@
+/*

+ * Copyright 2007 Amazon Technologies, Inc. or its affiliates.

+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks

+ * of Amazon Technologies, Inc. or its affiliates.  All rights reserved.

+ *

+ * 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 at

+ *

+ *     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 com.amazon.carbonado.cursor;

+

+import java.util.Comparator;

+

+import org.cojen.classfile.TypeDesc;

+

+/**

+ * Collection of utility comparators.

+ *

+ * @author Brian S O'Neill

+ */

+class Comparators {

+    /**

+     * Returns a comparator which can sort single or multi-dimensional arrays

+     * of primitves or Comparables.

+     *

+     * @param unsigned applicable only to arrays of bytes, shorts, ints, or longs

+     * @return null if unsupported

+     */

+    static <T> Comparator<T> arrayComparator(Class<T> arrayType, boolean unsigned) {

+        if (!arrayType.isArray()) {

+            throw new IllegalArgumentException();

+        }

+

+        Comparator c;

+

+        TypeDesc componentType = TypeDesc.forClass(arrayType.getComponentType());

+        switch (componentType.getTypeCode()) {

+        case TypeDesc.BYTE_CODE:

+            c = unsigned ? UnsignedByteArray : SignedByteArray;

+            break;

+        case TypeDesc.SHORT_CODE:

+            c = unsigned ? UnsignedShortArray : SignedShortArray;

+            break;

+        case TypeDesc.INT_CODE:

+            c = unsigned ? UnsignedIntArray : SignedIntArray;

+            break;

+        case TypeDesc.LONG_CODE:

+            c = unsigned ? UnsignedLongArray : SignedLongArray;

+            break;

+        case TypeDesc.BOOLEAN_CODE:

+            c = BooleanArray;

+            break;

+        case TypeDesc.CHAR_CODE:

+            c = CharArray;

+            break;

+        case TypeDesc.FLOAT_CODE:

+            c = FloatArray;

+            break;

+        case TypeDesc.DOUBLE_CODE:

+            c = DoubleArray;

+            break;

+        case TypeDesc.OBJECT_CODE: default:

+            if (componentType.isArray()) {

+                c = new ComparatorArray(arrayComparator(componentType.toClass(), unsigned));

+            } else if (Comparable.class.isAssignableFrom(componentType.toClass())) {

+                c = ComparableArray;

+            } else {

+                c = null;

+            }

+            break;

+        }

+

+        return (Comparator<T>) c;

+    }

+

+    private static final Comparator<byte[]> SignedByteArray = new Comparator<byte[]>() {

+        public int compare(byte[] a, byte[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                byte ai = a[i];

+                byte bi = b[i];

+                if (ai != bi) {

+                    return ai - bi;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<byte[]> UnsignedByteArray = new Comparator<byte[]>() {

+        public int compare(byte[] a, byte[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                byte ai = a[i];

+                byte bi = b[i];

+                if (ai != bi) {

+                    return (ai & 0xff) - (bi & 0xff);

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<short[]> SignedShortArray = new Comparator<short[]>() {

+        public int compare(short[] a, short[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                short ai = a[i];

+                short bi = b[i];

+                if (ai != bi) {

+                    return ai - bi;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<short[]> UnsignedShortArray = new Comparator<short[]>() {

+        public int compare(short[] a, short[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                short ai = a[i];

+                short bi = b[i];

+                if (ai != bi) {

+                    return (ai & 0xffff) - (bi & 0xffff);

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<int[]> SignedIntArray = new Comparator<int[]>() {

+        public int compare(int[] a, int[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                int ai = a[i];

+                int bi = b[i];

+                if (ai != bi) {

+                    return ai < bi ? -1 : 1;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<int[]> UnsignedIntArray = new Comparator<int[]>() {

+        public int compare(int[] a, int[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                int ai = a[i];

+                int bi = b[i];

+                if (ai != bi) {

+                    return (ai & 0xffffffffL) < (bi & 0xffffffffL) ? -1 : 1;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<long[]> SignedLongArray = new Comparator<long[]>() {

+        public int compare(long[] a, long[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                long ai = a[i];

+                long bi = b[i];

+                if (ai != bi) {

+                    return ai < bi ? -1 : 1;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<long[]> UnsignedLongArray = new Comparator<long[]>() {

+        public int compare(long[] a, long[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                long ai = a[i];

+                long bi = b[i];

+                if (ai != bi) {

+                    long sai = ai >>> 1;

+                    long sbi = bi >>> 1;

+                    if (sai < sbi) {

+                        return -1;

+                    }

+                    if (sai > sbi) {

+                        return 1;

+                    }

+                    return (ai & 1) == 0 ? -1 : 1;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<boolean[]> BooleanArray = new Comparator<boolean[]>() {

+        public int compare(boolean[] a, boolean[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                boolean ai = a[i];

+                boolean bi = b[i];

+                if (ai != bi) {

+                    return ai ? 1 : -1;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<char[]> CharArray = new Comparator<char[]>() {

+        public int compare(char[] a, char[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                char ai = a[i];

+                char bi = b[i];

+                if (ai != bi) {

+                    return ai - bi;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<float[]> FloatArray = new Comparator<float[]>() {

+        public int compare(float[] a, float[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                float ai = a[i];

+                float bi = b[i];

+                if (ai != bi) {

+                    return Float.compare(ai, bi);

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<double[]> DoubleArray = new Comparator<double[]>() {

+        public int compare(double[] a, double[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                double ai = a[i];

+                double bi = b[i];

+                if (ai != bi) {

+                    return Double.compare(ai, bi);

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static final Comparator<Comparable[]> ComparableArray = new Comparator<Comparable[]>()

+    {

+        public int compare(Comparable[] a, Comparable[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                Comparable ai = a[i];

+                Comparable bi = b[i];

+                if (ai == bi) {

+                    continue;

+                }

+                if (ai == null) {

+                    return 1;

+                }

+                if (bi == null) {

+                    return -1;

+                }

+                int compare = ai.compareTo(bi);

+                if (compare != 0) {

+                    return compare;

+                }

+            }

+            return a.length - b.length;

+        }

+    };

+

+    private static class ComparatorArray implements Comparator<Object[]> {

+        private final Comparator<Object> mComparator;

+

+        ComparatorArray(Comparator<Object> comparator) {

+            mComparator = comparator;

+        }

+

+        public int compare(Object[] a, Object[] b) {

+            int len = Math.min(a.length, b.length);

+            for (int i=0; i<len; i++) {

+                Object ai = a[i];

+                Object bi = b[i];

+                if (ai == bi) {

+                    continue;

+                }

+                if (ai == null) {

+                    return 1;

+                }

+                if (bi == null) {

+                    return -1;

+                }

+                int compare = mComparator.compare(ai, bi);

+                if (compare != 0) {

+                    return compare;

+                }

+            }

+            return a.length - b.length;

+        }

+    }

+}

diff --git a/src/main/java/com/amazon/carbonado/cursor/SortedCursor.java b/src/main/java/com/amazon/carbonado/cursor/SortedCursor.java
index 15a72d9..3c26caa 100644
--- a/src/main/java/com/amazon/carbonado/cursor/SortedCursor.java
+++ b/src/main/java/com/amazon/carbonado/cursor/SortedCursor.java
@@ -22,9 +22,14 @@ import java.lang.reflect.UndeclaredThrowableException;
 import java.util.Comparator;

 import java.util.Iterator;

 import java.util.List;

+import java.util.Map;

 import java.util.NoSuchElementException;

 

 import org.cojen.util.BeanComparator;

+import org.cojen.util.BeanIntrospector;

+import org.cojen.util.BeanProperty;

+

+import org.cojen.classfile.TypeDesc;

 

 import com.amazon.carbonado.FetchException;

 import com.amazon.carbonado.FetchInterruptedException;

@@ -58,13 +63,39 @@ public class SortedCursor<S> extends AbstractCursor<S> {
     public static <S> Comparator<S> createComparator(Class<S> type, String... orderProperties) {

         BeanComparator bc = BeanComparator.forClass(type);

         for (String property : orderProperties) {

-            bc = bc.orderBy(property);

-            bc = bc.caseSensitive();

+            Class propertyType;

+            {

+                String name = property;

+                if (name.startsWith("+") || name.startsWith("-")) {

+                    name = name.substring(1);

+                }

+                propertyType = propertyType(type, name);

+            }

+            bc = orderBy(bc, property, propertyType, Direction.ASCENDING);

         }

         return bc;

     }

 

     /**

+     * @return null if unknown

+     */

+    private static Class propertyType(Class enclosingType, String propertyName) {

+        Map<String, BeanProperty> properties = BeanIntrospector.getAllProperties(enclosingType);

+        int dotIndex = propertyName.indexOf('.');

+        if (dotIndex < 0) {

+            BeanProperty bp = properties.get(propertyName);

+            return bp == null ? null : bp.getType();

+        } else {

+            String parentName = propertyName.substring(0, dotIndex);

+            BeanProperty bp = properties.get(parentName);

+            if (bp == null) {

+                return null;

+            }

+            return propertyType(bp.getType(), propertyName.substring(dotIndex + 1));

+        }

+    }

+

+    /**

      * Convenience method to create a comparator which orders storables by the

      * given properties.

      *

@@ -86,16 +117,14 @@ public class SortedCursor<S> extends AbstractCursor<S> {
             if (property == null) {

                 throw new IllegalArgumentException();

             }

-            bc = bc.orderBy(property.getChainedProperty().toString());

-            bc = bc.caseSensitive();

-            if (property.getDirection() == Direction.DESCENDING) {

-                bc = bc.reverse();

-            }

+            bc = orderBy(bc, property.getChainedProperty().toString(),

+                         property.getChainedProperty().getType(), property.getDirection());

         }

 

         return bc;

     }

 

+

     /**

      * Convenience method to create a comparator which orders storables by the

      * given properties.

@@ -119,11 +148,35 @@ public class SortedCursor<S> extends AbstractCursor<S> {
             if (property == null) {

                 throw new IllegalArgumentException();

             }

-            bc = bc.orderBy(property.getChainedProperty().toString());

-            bc = bc.caseSensitive();

-            if (property.getDirection() == Direction.DESCENDING) {

-                bc = bc.reverse();

+            bc = orderBy(bc, property.getChainedProperty().toString(),

+                         property.getChainedProperty().getType(), property.getDirection());

+        }

+

+        return bc;

+    }

+

+    private static BeanComparator orderBy(BeanComparator bc, String property,

+                                          Class type, Direction direction)

+    {

+        bc = bc.orderBy(property);

+

+        if (type != null && type.isArray()) {

+            TypeDesc td = TypeDesc.forClass(type);

+            if (td.getRootComponentType() == TypeDesc.BYTE) {

+                bc = bc.using(Comparators.arrayComparator(type, true));

+            } else {

+                bc = bc.using(Comparators.arrayComparator(type, false));

+                if (bc == null) {

+                    throw new IllegalArgumentException("Cannot sort by property type of " +

+                                                       type.getName() + " for " + property);

+                }

             }

+        } else {

+            bc = bc.caseSensitive();

+        }

+

+        if (direction == Direction.DESCENDING) {

+            bc = bc.reverse();

         }

 

         return bc;

diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
index 73469db..2d7f983 100644
--- a/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/ManagedIndex.java
@@ -287,7 +287,7 @@ class ManagedIndex<S extends Storable> implements IndexEntryAccessor<S> {
                         buffer.close();

                         throw new UniqueConstraintException

                             ("Cannot build unique index because duplicates exist: "

-                             + this);

+                             + this + ", " + last + " == " + obj);

                     }

                 }

                 last = obj;

diff --git a/src/main/java/com/amazon/carbonado/repo/replicated/ReplicatedRepository.java b/src/main/java/com/amazon/carbonado/repo/replicated/ReplicatedRepository.java
index 2c73200..b28fab5 100644
--- a/src/main/java/com/amazon/carbonado/repo/replicated/ReplicatedRepository.java
+++ b/src/main/java/com/amazon/carbonado/repo/replicated/ReplicatedRepository.java
@@ -24,8 +24,6 @@ import java.util.Set;
 import org.apache.commons.logging.Log;

 import org.apache.commons.logging.LogFactory;

 

-import org.cojen.util.BeanComparator;

-

 import com.amazon.carbonado.CorruptEncodingException;

 import com.amazon.carbonado.Cursor;

 import com.amazon.carbonado.FetchException;

@@ -49,6 +47,8 @@ import com.amazon.carbonado.capability.ResyncCapability;
 import com.amazon.carbonado.capability.ShutdownCapability;

 import com.amazon.carbonado.capability.StorableInfoCapability;

 

+import com.amazon.carbonado.cursor.SortedCursor;

+

 import com.amazon.carbonado.info.Direction;

 import com.amazon.carbonado.info.StorableInfo;

 import com.amazon.carbonado.info.StorableIntrospector;

@@ -389,11 +389,7 @@ class ReplicatedRepository
             }

         }

 

-        BeanComparator bc = BeanComparator.forClass(type);

-        for (String order : orderBy) {

-            bc = bc.orderBy(order);

-            bc = bc.caseSensitive();

-        }

+        Comparator comparator = SortedCursor.createComparator(type, orderBy);

 

         replicaQuery = replicaQuery.orderBy(orderBy);

         masterQuery = masterQuery.orderBy(orderBy);

@@ -417,7 +413,7 @@ class ReplicatedRepository
                    replicaStorage, replicaQuery,

                    masterStorage, masterQuery,

                    throttle, desiredSpeed,

-                   bc, replicaTxn);

+                   comparator, replicaTxn);

 

             replicaTxn.commit();

         } finally {

diff --git a/src/main/java/com/amazon/carbonado/synthetic/SyntheticStorableReferenceBuilder.java b/src/main/java/com/amazon/carbonado/synthetic/SyntheticStorableReferenceBuilder.java
index f9db620..4fddcd5 100644
--- a/src/main/java/com/amazon/carbonado/synthetic/SyntheticStorableReferenceBuilder.java
+++ b/src/main/java/com/amazon/carbonado/synthetic/SyntheticStorableReferenceBuilder.java
@@ -29,6 +29,7 @@ import java.util.Set;
 

 import com.amazon.carbonado.Storable;

 import com.amazon.carbonado.SupportException;

+import com.amazon.carbonado.cursor.SortedCursor;

 import com.amazon.carbonado.info.Direction;

 import com.amazon.carbonado.info.StorableInfo;

 import com.amazon.carbonado.info.StorableIntrospector;

@@ -219,18 +220,14 @@ public class SyntheticStorableReferenceBuilder<S extends Storable>
             mSyntheticClass = mBuilder.getStorableClass();

 

             // We need a comparator which follows the same order as the generated

-            // storable.  We can't construct it until we get here

-            {

-                BeanComparator bc = BeanComparator.forClass(mSyntheticClass);

-                Iterator<String> props = mPrimaryKey.getProperties();

-                while (props.hasNext()) {

-                    String prop = props.next();

-                    // BeanComparator knows how to handle the '+' or '-' prefix.

-                    bc = bc.orderBy(prop);

-                    bc = bc.caseSensitive();

-                }

-                mComparator = bc;

+            // storable. We can't construct it until we get here.

+            String[] orderBy = new String[mPrimaryKey.getPropertyCount()];

+            int i=0;

+            Iterator<String> it = mPrimaryKey.getProperties();

+            while (it.hasNext()) {

+                orderBy[i++] = it.next();

             }

+            mComparator = SortedCursor.createComparator(mSyntheticClass, orderBy);

         }

         return mSyntheticClass;

     }