From 90bd381e91c873af5956da9e5f0cfa2b29675633 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Thu, 11 Oct 2007 21:00:12 +0000
Subject: Support sorting of arrays.

---
 .../com/amazon/carbonado/cursor/Comparators.java   | 315 +++++++++++++++++++++
 .../com/amazon/carbonado/cursor/SortedCursor.java  |  75 ++++-
 .../carbonado/repo/indexed/ManagedIndex.java       |   2 +-
 .../repo/replicated/ReplicatedRepository.java      |  12 +-
 .../SyntheticStorableReferenceBuilder.java         |  19 +-
 5 files changed, 392 insertions(+), 31 deletions(-)
 create mode 100644 src/main/java/com/amazon/carbonado/cursor/Comparators.java

(limited to 'src')

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,12 +63,38 @@ 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;
     }
-- 
cgit v1.2.3