Use OrderingList class everywhere.

9 files changed, 218 insertions, 222 deletions

diff --git a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java
index 2a85a32..c8e9490 100644
--- a/src/main/java/com/amazon/carbonado/qe/CompositeScore.java
+++ b/src/main/java/com/amazon/carbonado/qe/CompositeScore.java
@@ -45,13 +45,13 @@ public class CompositeScore<S extends Storable> {
      *

      * @param index index to evaluate

      * @param filter optional filter which cannot contain any logical 'or' operations.

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      * @throws IllegalArgumentException if index is null or filter is not supported

      */

     public static <S extends Storable> CompositeScore<S> evaluate

         (StorableIndex<S> index,

          Filter<S> filter,

-         List<OrderedProperty<S>> orderings)

+         OrderingList<S> ordering)

     {

         if (index == null) {

             throw new IllegalArgumentException("Index required");

@@ -61,7 +61,7 @@ public class CompositeScore<S extends Storable> {
                         index.isUnique(),

                         index.isClustered(),

                         filter,

-                        orderings);

+                        ordering);

     }

 

     /**

@@ -72,7 +72,7 @@ public class CompositeScore<S extends Storable> {
      * @param unique true if index is unique

      * @param clustered true if index is clustered

      * @param filter optional filter which cannot contain any logical 'or' operations.

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      * @throws IllegalArgumentException if index is null or filter is not supported

      */

     public static <S extends Storable> CompositeScore<S> evaluate

@@ -80,13 +80,13 @@ public class CompositeScore<S extends Storable> {
          boolean unique,

          boolean clustered,

          Filter<S> filter,

-         List<OrderedProperty<S>> orderings)

+         OrderingList<S> ordering)

     {

         FilteringScore<S> filteringScore = FilteringScore

             .evaluate(indexProperties, unique, clustered, filter);

 

         OrderingScore<S> orderingScore = OrderingScore

-            .evaluate(indexProperties, unique, clustered, filter, orderings);

+            .evaluate(indexProperties, unique, clustered, filter, ordering);

 

         return new CompositeScore<S>(filteringScore, orderingScore);

     }

@@ -133,7 +133,7 @@ public class CompositeScore<S extends Storable> {
      */

     public boolean canMergeRemainder(CompositeScore<S> other) {

         return getFilteringScore().canMergeRemainderFilter(other.getFilteringScore())

-            && getOrderingScore().canMergeRemainderOrderings(other.getOrderingScore());

+            && getOrderingScore().canMergeRemainderOrdering(other.getOrderingScore());

     }

 

     /**

@@ -149,8 +149,8 @@ public class CompositeScore<S extends Storable> {
      * Merges the remainder orderings of this score with the one given. Call

      * canMergeRemainder first to verify if the merge makes any sense.

      */

-    public List<OrderedProperty<S>> mergeRemainderOrderings(CompositeScore<S> other) {

-        return getOrderingScore().mergeRemainderOrderings(other.getOrderingScore());

+    public OrderingList<S> mergeRemainderOrdering(CompositeScore<S> other) {

+        return getOrderingScore().mergeRemainderOrdering(other.getOrderingScore());

     }

 

     public String toString() {

diff --git a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java
index 16a8f26..5da585a 100644
--- a/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java
+++ b/src/main/java/com/amazon/carbonado/qe/EmptyQuery.java
@@ -44,21 +44,21 @@ public final class EmptyQuery<S extends Storable> extends AbstractQuery<S> {
     private final Storage<S> mRootStorage;

 

     // Properties that this query is ordered by.

-    private final OrderingList<S> mOrderings;

+    private final OrderingList<S> mOrdering;

 

     /**

      * @param rootStorage required root storage object, used by 'or' and 'not' methods

-     * @param orderings optional order-by properties

+     * @param ordering optional order-by properties

      */

-    public EmptyQuery(Storage<S> rootStorage, OrderingList<S> orderings) {

+    public EmptyQuery(Storage<S> rootStorage, OrderingList<S> ordering) {

         if (rootStorage == null) {

             throw new IllegalArgumentException();

         }

         mRootStorage = rootStorage;

-        if (orderings == null) {

-            orderings = OrderingList.emptyList();

+        if (ordering == null) {

+            ordering = OrderingList.emptyList();

         }

-        mOrderings = orderings;

+        mOrdering = ordering;

     }

 

     /**

@@ -194,8 +194,8 @@ public final class EmptyQuery<S extends Storable> extends AbstractQuery<S> {
      */

     public Query<S> not() throws FetchException {

         Query<S> query = mRootStorage.query();

-        if (mOrderings.size() > 0) {

-            query = query.orderBy(mOrderings.asStringArray());

+        if (mOrdering.size() > 0) {

+            query = query.orderBy(mOrdering.asStringArray());

         }

         return query;

     }

@@ -255,13 +255,13 @@ public final class EmptyQuery<S extends Storable> extends AbstractQuery<S> {
         app.append(", filter=");

         getFilter().appendTo(app);

 

-        if (mOrderings != null && mOrderings.size() > 0) {

+        if (mOrdering != null && mOrdering.size() > 0) {

             app.append(", orderBy=[");

-            for (int i=0; i<mOrderings.size(); i++) {

+            for (int i=0; i<mOrdering.size(); i++) {

                 if (i > 0) {

                     app.append(", ");

                 }

-                app.append(mOrderings.get(i).toString());

+                app.append(mOrdering.get(i).toString());

             }

             app.append(']');

         }

diff --git a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java
index d0bd63f..594fcc1 100644
--- a/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java
+++ b/src/main/java/com/amazon/carbonado/qe/IndexedQueryAnalyzer.java
@@ -76,10 +76,10 @@ public class IndexedQueryAnalyzer<S extends Storable> {
     /**

      * @param filter optional filter which which must be {@link Filter#isBound

      * bound} and cannot contain any logical 'or' operations.

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      * @throws IllegalArgumentException if filter is not supported

      */

-    public Result analyze(Filter<S> filter, List<OrderedProperty<S>> orderings) {

+    public Result analyze(Filter<S> filter, OrderingList<S> ordering) {

         if (!filter.isBound()) {

             // Strictly speaking, this is not required, but it detects the

             // mistake of not properly calling initialFilterValues.

@@ -96,7 +96,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
         if (localIndexes != null) {

             for (StorableIndex<S> index : localIndexes) {

                 CompositeScore<S> candidateScore =

-                    CompositeScore.evaluate(index, filter, orderings);

+                    CompositeScore.evaluate(index, filter, ordering);

 

                 if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) {

                     bestScore = candidateScore;

@@ -128,7 +128,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
                      index.isUnique(),

                      index.isClustered(),

                      filter,

-                     orderings);

+                     ordering);

 

                 if (bestScore == null || comparator.compare(candidateScore, bestScore) < 0) {

                     bestScore = candidateScore;

@@ -249,7 +249,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
         private final ChainedProperty<S> mForeignProperty;

 

         private final Filter<S> mRemainderFilter;

-        private final List<OrderedProperty<S>> mRemainderOrderings;

+        private final OrderingList<S> mRemainderOrdering;

 

         Result(Filter<S> filter,

                CompositeScore<S> score,

@@ -263,13 +263,13 @@ public class IndexedQueryAnalyzer<S extends Storable> {
             mForeignIndex = foreignIndex;

             mForeignProperty = foreignProperty;

             mRemainderFilter = score.getFilteringScore().getRemainderFilter();

-            mRemainderOrderings = score.getOrderingScore().getRemainderOrderings();

+            mRemainderOrdering = score.getOrderingScore().getRemainderOrdering();

         }

 

         // Called by mergeRemainder.

         private Result(Result result,

                        Filter<S> remainderFilter,

-                       List<OrderedProperty<S>> remainderOrderings)

+                       OrderingList<S> remainderOrdering)

         {

             mFilter = result.mFilter == null ? remainderFilter

                 : (remainderFilter == null ? result.mFilter : result.mFilter.or(remainderFilter));

@@ -279,7 +279,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
             mForeignIndex = result.mForeignIndex;

             mForeignProperty = result.mForeignProperty;

             mRemainderFilter = remainderFilter;

-            mRemainderOrderings = remainderOrderings;

+            mRemainderOrdering = remainderOrdering;

         }

 

         /**

@@ -302,24 +302,8 @@ public class IndexedQueryAnalyzer<S extends Storable> {
         /**

          * Returns combined handled and remainder orderings for this result.

          */

-        public List<OrderedProperty<S>> getOrderings() {

-            List<OrderedProperty<S>> handled = mScore.getOrderingScore().getHandledOrderings();

-            List<OrderedProperty<S>> remainder = getRemainderOrderings();

-

-            if (handled.size() == 0) {

-                return remainder;

-            }

-            if (remainder.size() == 0) {

-                return handled;

-            }

-

-            List<OrderedProperty<S>> combined =

-                new ArrayList<OrderedProperty<S>>(handled.size() + remainder.size());

-

-            combined.addAll(handled);

-            combined.addAll(remainder);

-

-            return combined;

+        public OrderingList<S> getOrdering() {

+            return mScore.getOrderingScore().getHandledOrdering().concat(getRemainderOrdering());

         }

 

         /**

@@ -342,8 +326,8 @@ public class IndexedQueryAnalyzer<S extends Storable> {
         /**

          * Remainder orderings which override that in composite score.

          */

-        public List<OrderedProperty<S>> getRemainderOrderings() {

-            return mRemainderOrderings;

+        public OrderingList<S> getRemainderOrdering() {

+            return mRemainderOrdering;

         }

 

         /**

@@ -406,7 +390,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
             return new Result

                 (this,

                  getCompositeScore().mergeRemainderFilter(other.getCompositeScore()),

-                 getCompositeScore().mergeRemainderOrderings(other.getCompositeScore()));

+                 getCompositeScore().mergeRemainderOrdering(other.getCompositeScore()));

         }

 

         /**

@@ -428,7 +412,7 @@ public class IndexedQueryAnalyzer<S extends Storable> {
          * Returns a new result with the remainder filter replaced.

          */

         public Result setRemainderFilter(Filter<S> filter) {

-            return new Result(this, filter, getRemainderOrderings());

+            return new Result(this, filter, getRemainderOrdering());

         }

 

         public String toString() {

@@ -437,8 +421,8 @@ public class IndexedQueryAnalyzer<S extends Storable> {
                 + getLocalIndex() + ", foreignIndex="

                 + getForeignIndex() + ", foreignProperty="

                 + getForeignProperty() + ", remainderFilter="

-                + getRemainderFilter() + ", remainderOrderings="

-                + getRemainderOrderings() + '}';

+                + getRemainderFilter() + ", remainderOrdering="

+                + getRemainderOrdering() + '}';

         }

 

         private boolean equals(Object a, Object b) {

diff --git a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java
index 9557b31..ebcb60a 100644
--- a/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java
+++ b/src/main/java/com/amazon/carbonado/qe/JoinedQueryExecutor.java
@@ -20,10 +20,6 @@ package com.amazon.carbonado.qe;
 

 import java.io.IOException;

 

-import java.util.ArrayList;

-import java.util.Collections;

-import java.util.List;

-

 import com.amazon.carbonado.Cursor;

 import com.amazon.carbonado.FetchException;

 import com.amazon.carbonado.Repository;

diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingList.java b/src/main/java/com/amazon/carbonado/qe/OrderingList.java
index 0cb1fc4..b32f430 100644
--- a/src/main/java/com/amazon/carbonado/qe/OrderingList.java
+++ b/src/main/java/com/amazon/carbonado/qe/OrderingList.java
@@ -59,10 +59,11 @@ public class OrderingList<S extends Storable> extends AbstractList<OrderedProper
      * @throws IllegalArgumentException if ordering property is not in S

      */

     public static <S extends Storable> OrderingList<S> get(Class<S> type, String property) {

-        if (property == null) {

-            return EMPTY_LIST;

+        OrderingList<S> list = emptyList();

+        if (property != null) {

+            list = list.concat(type, property);

         }

-        return getListNode(type).nextNode(type, property);

+        return list;

     }

 

     /**

@@ -71,37 +72,29 @@ public class OrderingList<S extends Storable> extends AbstractList<OrderedProper
      * @throws IllegalArgumentException if any ordering property is not in S

      */

     public static <S extends Storable> OrderingList<S> get(Class<S> type, String... orderings) {

-        if (orderings == null || orderings.length == 0) {

-            return EMPTY_LIST;

-        }

-

-        OrderingList<S> node = getListNode(type);

-        for (String property : orderings) {

-            node = node.nextNode(type, property);

+        OrderingList<S> list = emptyList();

+        if (orderings != null && orderings.length > 0) {

+            for (String property : orderings) {

+                list = list.concat(type, property);

+            }

         }

-

-        return node;

+        return list;

     }

 

     /**

      * Returns a canonical instance composed of the given orderings.

      */

     public static <S extends Storable> OrderingList<S> get(OrderedProperty<S>... orderings) {

-        if (orderings == null || orderings.length == 0) {

-            return EMPTY_LIST;

-        }

-

-        Class<S> type = orderings[0].getChainedProperty().getPrimeProperty().getEnclosingType();

-

-        OrderingList<S> node = getListNode(type);

-        for (OrderedProperty<S> property : orderings) {

-            node = node.nextNode(property);

+        OrderingList<S> list = emptyList();

+        if (orderings != null && orderings.length > 0) {

+            for (OrderedProperty<S> property : orderings) {

+                list = list.concat(property);

+            }

         }

-

-        return node;

+        return list;

     }

 

-    private static <S extends Storable> OrderingList<S> getListNode(Class<S> type) {

+    private static <S extends Storable> OrderingList<S> getListHead(Class<S> type) {

         OrderingList<S> node;

         synchronized (cCache) {

             node = (OrderingList<S>) cCache.get(type);

@@ -146,28 +139,79 @@ public class OrderingList<S extends Storable> extends AbstractList<OrderedProper
     }

 

     /**

+     * Returns a list which concatenates this one with the given property.

+     */

+    public OrderingList<S> concat(Class<S> type, String property) {

+        OrderingList<S> newList = this;

+        if (newList == EMPTY_LIST) {

+            // Cannot concat from singleton EMPTY_LIST.

+            newList = getListHead(type);

+        }

+        return newList.nextNode(type, property);

+    }

+

+    /**

+     * Returns a list which concatenates this one with the given property.

+     */

+    public OrderingList<S> concat(OrderedProperty<S> property) {

+        OrderingList<S> newList = this;

+        if (newList == EMPTY_LIST) {

+            // Cannot concat from singleton EMPTY_LIST.

+            newList = getListHead

+                (property.getChainedProperty().getPrimeProperty().getEnclosingType());

+        }

+        return newList.nextNode(property);

+    }

+

+    /**

      * Returns a list which concatenates this one with the other one.

      */

     public OrderingList<S> concat(OrderingList<S> other) {

         if (size() == 0) {

             return other;

         }

-

-        OrderingList<S> node = this;

-

+        OrderingList<S> newList = this;

         if (other.size() > 0) {

             for (OrderedProperty<S> property : other) {

-                node = node.nextNode(property);

+                newList = newList.concat(property);

             }

         }

+        return newList;

+    }

 

-        return node;

+    /**

+     * Returns this list with all orderings in reverse.

+     */

+    public OrderingList<S> reverseDirections() {

+        if (size() == 0) {

+            return this;

+        }

+        OrderingList<S> reversedList = emptyList();

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

+            reversedList = reversedList.concat(get(i).reverse());

+        }

+        return reversedList;

+    }

+

+    /**

+     * Returns a list with the given element replaced.

+     */

+    public OrderingList<S> replace(int index, OrderedProperty<S> property) {

+        int size = size();

+        if (index < 0 || index >= size) {

+            throw new IndexOutOfBoundsException();

+        }

+        OrderingList<S> newList = emptyList();

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

+            newList = newList.concat(i == index ? property : get(i));

+        }

+        return newList;

     }

 

     /**

      * This method is not public because the array is not a clone.

      */

-    private OrderedProperty<S>[] asArray() {

+    OrderedProperty<S>[] asArray() {

         if (mOrderings == null) {

             OrderedProperty<S>[] orderings = new OrderedProperty[mSize];

             OrderingList<S> node = this;

diff --git a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java
index 82d44a7..97ac4e8 100644
--- a/src/main/java/com/amazon/carbonado/qe/OrderingScore.java
+++ b/src/main/java/com/amazon/carbonado/qe/OrderingScore.java
@@ -18,9 +18,7 @@
 

 package com.amazon.carbonado.qe;

 

-import java.util.ArrayList;

 import java.util.Comparator;

-import java.util.Collections;

 import java.util.HashSet;

 import java.util.List;

 import java.util.Map;

@@ -68,13 +66,13 @@ public class OrderingScore<S extends Storable> {
      *

      * @param index index to evaluate

      * @param filter optional filter which cannot contain any logical 'or' operations.

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      * @throws IllegalArgumentException if index is null or filter is not supported

      */

     public static <S extends Storable> OrderingScore<S> evaluate

         (StorableIndex<S> index,

          Filter<S> filter,

-         List<OrderedProperty<S>> orderings)

+         OrderingList<S> ordering)

     {

         if (index == null) {

             throw new IllegalArgumentException("Index required");

@@ -84,7 +82,7 @@ public class OrderingScore<S extends Storable> {
                         index.isUnique(),

                         index.isClustered(),

                         filter,

-                        orderings);

+                        ordering);

     }

 

     /**

@@ -95,7 +93,7 @@ public class OrderingScore<S extends Storable> {
      * @param unique true if index is unique

      * @param clustered true if index is clustered

      * @param filter optional filter which cannot contain any logical 'or' operations.

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      * @throws IllegalArgumentException if index is null or filter is not supported

      */

     public static <S extends Storable> OrderingScore<S> evaluate

@@ -103,7 +101,7 @@ public class OrderingScore<S extends Storable> {
          boolean unique,

          boolean clustered,

          Filter<S> filter,

-         List<OrderedProperty<S>> orderings)

+         OrderingList<S> ordering)

     {

         if (indexProperties == null) {

             throw new IllegalArgumentException("Index properties required");

@@ -112,8 +110,8 @@ public class OrderingScore<S extends Storable> {
         // Get filter list early to detect errors.

         List<PropertyFilter<S>> filterList = PropertyFilterList.get(filter);

 

-        if (orderings == null) {

-            orderings = Collections.emptyList();

+        if (ordering == null) {

+            ordering = OrderingList.emptyList();

         }

 

         // Ordering properties which match identity filters don't affect order

@@ -127,15 +125,18 @@ public class OrderingScore<S extends Storable> {
             }

         }

 

-        // Build up list of unused properties that were filtered out.

-        List<OrderedProperty<S>> unusedProperties = new ArrayList<OrderedProperty<S>>();

+        OrderingList<S> handledOrdering = OrderingList.emptyList();

+        OrderingList<S> remainderOrdering = OrderingList.emptyList();

+        OrderingList<S> freeOrdering = OrderingList.emptyList();

+        OrderingList<S> unusedOrdering = OrderingList.emptyList();

 

+        // Build up list of unused properties that were filtered out.

         for (int i=0; i<indexProperties.length; i++) {

             OrderedProperty<S> indexProp = indexProperties[i];

             ChainedProperty<S> indexChained = indexProp.getChainedProperty();

 

             if (identityPropSet.contains(indexChained)) {

-                unusedProperties.add(indexProp.direction(UNSPECIFIED));

+                unusedOrdering = unusedOrdering.concat(indexProp.direction(UNSPECIFIED));

             }

         }

 

@@ -153,16 +154,13 @@ public class OrderingScore<S extends Storable> {
 

             return new OrderingScore<S>(clustered,

                                         indexProperties.length,

-                                        null,   // no handled properties

-                                        null,   // no remainder properties

-                                        false,  // no need to reverse order

-                                        null,   // no free properties

-                                        unusedProperties);

+                                        handledOrdering,   // no handled properties

+                                        remainderOrdering, // no remainder properties

+                                        false,             // no need to reverse order

+                                        freeOrdering,      // no free properties

+                                        unusedOrdering);

         }

 

-        List<OrderedProperty<S>> handledProperties = new ArrayList<OrderedProperty<S>>();

-        List<OrderedProperty<S>> remainderProperties = new ArrayList<OrderedProperty<S>>();

-

         Boolean shouldReverseOrder = null;

 

         Set<ChainedProperty<S>> seen = new HashSet<ChainedProperty<S>>();

@@ -170,8 +168,8 @@ public class OrderingScore<S extends Storable> {
         boolean gap = false;

         int indexPos = 0;

         calcScore:

-        for (int i=0; i<orderings.size(); i++) {

-            OrderedProperty<S> property = orderings.get(i);

+        for (int i=0; i<ordering.size(); i++) {

+            OrderedProperty<S> property = ordering.get(i);

             ChainedProperty<S> chained = property.getChainedProperty();

 

             if (seen.contains(chained)) {

@@ -211,16 +209,14 @@ public class OrderingScore<S extends Storable> {
                         // originally unspecified. They might need to be

                         // reversed now.

                         if (shouldReverseOrder) {

-                            for (int hpi = 0; hpi < handledProperties.size(); hpi++) {

-                                handledProperties.set(hpi, handledProperties.get(hpi).reverse());

-                            }

+                            handledOrdering = handledOrdering.reverseDirections();

                         }

                     } else if (indexDir != property.getDirection()) {

                         // Direction mismatch, so cannot be handled.

                         break indexPosMatch;

                     }

 

-                    handledProperties.add(property);

+                    handledOrdering = handledOrdering.concat(property);

 

                     indexPos++;

                     continue calcScore;

@@ -239,13 +235,11 @@ public class OrderingScore<S extends Storable> {
             }

 

             // Property not handled and not an identity filter.

-            remainderProperties.add(property);

+            remainderOrdering = remainderOrdering.concat(property);

             gap = true;

         }

 

         // Walk through all remaining index properties and list them as free.

-        List<OrderedProperty<S>> freeProperties = new ArrayList<OrderedProperty<S>>();

-

         while (indexPos < indexProperties.length) {

             OrderedProperty<S> freeProp = indexProperties[indexPos];

             ChainedProperty<S> freeChained = freeProp.getChainedProperty();

@@ -263,7 +257,7 @@ public class OrderingScore<S extends Storable> {
                         freeProp = freeProp.direction(freePropDir.reverse());

                     }

                 }

-                freeProperties.add(freeProp);

+                freeOrdering = freeOrdering.concat(freeProp);

             }

 

             indexPos++;

@@ -275,11 +269,11 @@ public class OrderingScore<S extends Storable> {
 

         return new OrderingScore<S>(clustered,

                                     indexProperties.length,

-                                    handledProperties,

-                                    remainderProperties,

+                                    handledOrdering,

+                                    remainderOrdering,

                                     shouldReverseOrder,

-                                    freeProperties,

-                                    unusedProperties);

+                                    freeOrdering,

+                                    unusedOrdering);

     }

 

     /**

@@ -295,8 +289,8 @@ public class OrderingScore<S extends Storable> {
     private final boolean mIndexClustered;

     private final int mIndexPropertyCount;

 

-    private final List<OrderedProperty<S>> mHandledOrderings;

-    private final List<OrderedProperty<S>> mRemainderOrderings;

+    private final OrderingList<S> mHandledOrdering;

+    private final OrderingList<S> mRemainderOrdering;

 

     private final boolean mShouldReverseOrder;

 

@@ -304,24 +298,24 @@ public class OrderingScore<S extends Storable> {
     // are useful for determining a total ordering that does not adversely

     // affect a query plan. Combining handled, free, and unused ordering lists

     // produces all the properties of the evaluated index.

-    private final List<OrderedProperty<S>> mFreeOrderings;

-    private final List<OrderedProperty<S>> mUnusedOrderings;

+    private final OrderingList<S> mFreeOrdering;

+    private final OrderingList<S> mUnusedOrdering;

 

     private OrderingScore(boolean indexClustered,

                           int indexPropertyCount,

-                          List<OrderedProperty<S>> handledOrderings,

-                          List<OrderedProperty<S>> remainderOrderings,

+                          OrderingList<S> handledOrdering,

+                          OrderingList<S> remainderOrdering,

                           boolean shouldReverseOrder,

-                          List<OrderedProperty<S>> freeOrderings,

-                          List<OrderedProperty<S>> unusedOrderings)

+                          OrderingList<S> freeOrdering,

+                          OrderingList<S> unusedOrdering)

     {

         mIndexClustered = indexClustered;

         mIndexPropertyCount = indexPropertyCount;

-        mHandledOrderings = FilteringScore.prepareList(handledOrderings);

-        mRemainderOrderings = FilteringScore.prepareList(remainderOrderings);

+        mHandledOrdering = handledOrdering;

+        mRemainderOrdering = remainderOrdering;

         mShouldReverseOrder = shouldReverseOrder;

-        mFreeOrderings = FilteringScore.prepareList(freeOrderings);

-        mUnusedOrderings = FilteringScore.prepareList(unusedOrderings);

+        mFreeOrdering = freeOrdering;

+        mUnusedOrdering = unusedOrdering;

     }

 

     /**

@@ -344,7 +338,7 @@ public class OrderingScore<S extends Storable> {
      * supports. The number of orderings is reduced to eliminate redundancies.

      */

     public int getHandledCount() {

-        return mHandledOrderings.size();

+        return mHandledOrdering.size();

     }

 

     /**

@@ -355,8 +349,8 @@ public class OrderingScore<S extends Storable> {
      *

      * @return handled orderings, never null

      */

-    public List<OrderedProperty<S>> getHandledOrderings() {

-        return mHandledOrderings;

+    public OrderingList<S> getHandledOrdering() {

+        return mHandledOrdering;

     }

 

     /**

@@ -366,7 +360,7 @@ public class OrderingScore<S extends Storable> {
      * evaluated index must perform a sort.

      */

     public int getRemainderCount() {

-        return mRemainderOrderings.size();

+        return mRemainderOrdering.size();

     }

 

     /**

@@ -375,8 +369,8 @@ public class OrderingScore<S extends Storable> {
      *

      * @return remainder orderings, never null

      */

-    public List<OrderedProperty<S>> getRemainderOrderings() {

-        return mRemainderOrderings;

+    public OrderingList<S> getRemainderOrdering() {

+        return mRemainderOrdering;

     }

 

     /**

@@ -395,8 +389,8 @@ public class OrderingScore<S extends Storable> {
      *

      * @return free orderings, never null

      */

-    public List<OrderedProperty<S>> getFreeOrderings() {

-        return mFreeOrderings;

+    public OrderingList<S> getFreeOrdering() {

+        return mFreeOrdering;

     }

 

     /**

@@ -406,8 +400,8 @@ public class OrderingScore<S extends Storable> {
      *

      * @return unused orderings, never null

      */

-    public List<OrderedProperty<S>> getUnusedOrderings() {

-        return mUnusedOrderings;

+    public OrderingList<S> getUnusedOrdering() {

+        return mUnusedOrdering;

     }

 

     /**

@@ -415,7 +409,7 @@ public class OrderingScore<S extends Storable> {
      * one. The only allowed differences are in the count of remainder

      * orderings.

      */

-    public boolean canMergeRemainderOrderings(OrderingScore<S> other) {

+    public boolean canMergeRemainderOrdering(OrderingScore<S> other) {

         if (this == other || (getHandledCount() == 0 && other.getHandledCount() == 0)) {

             return true;

         }

@@ -423,15 +417,15 @@ public class OrderingScore<S extends Storable> {
         if (isIndexClustered() == other.isIndexClustered()

             && getIndexPropertyCount() == other.getIndexPropertyCount()

             && shouldReverseOrder() == other.shouldReverseOrder()

-            && getHandledOrderings().equals(other.getHandledOrderings()))

+            && getHandledOrdering().equals(other.getHandledOrdering()))

         {

             // The remainder orderings cannot conflict.

-            List<OrderedProperty<S>> thisRemainderOrderings = getRemainderOrderings();

-            List<OrderedProperty<S>> otherRemainderOrderings = other.getRemainderOrderings();

+            OrderingList<S> thisRemainderOrdering = getRemainderOrdering();

+            OrderingList<S> otherRemainderOrdering = other.getRemainderOrdering();

 

-            int size = Math.min(thisRemainderOrderings.size(), otherRemainderOrderings.size());

+            int size = Math.min(thisRemainderOrdering.size(), otherRemainderOrdering.size());

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

-                if (!thisRemainderOrderings.get(i).equals(otherRemainderOrderings.get(i))) {

+                if (!thisRemainderOrdering.get(i).equals(otherRemainderOrdering.get(i))) {

                     return false;

                 }

             }

@@ -444,28 +438,28 @@ public class OrderingScore<S extends Storable> {
 

     /**

      * Merges the remainder orderings of this score with the one given. Call

-     * canMergeRemainderOrderings first to verify if the merge makes any sense.

+     * canMergeRemainderOrdering first to verify if the merge makes any sense.

      */

-    public List<OrderedProperty<S>> mergeRemainderOrderings(OrderingScore<S> other) {

-        List<OrderedProperty<S>> thisRemainderOrderings = getRemainderOrderings();

+    public OrderingList<S> mergeRemainderOrdering(OrderingScore<S> other) {

+        OrderingList<S> thisRemainderOrdering = getRemainderOrdering();

 

         if (this == other) {

-            return thisRemainderOrderings;

+            return thisRemainderOrdering;

         }

 

-        List<OrderedProperty<S>> otherRemainderOrderings = other.getRemainderOrderings();

+        OrderingList<S> otherRemainderOrdering = other.getRemainderOrdering();

 

         // Choose the longer list.

 

-        if (thisRemainderOrderings.size() == 0) {

-            return otherRemainderOrderings;

+        if (thisRemainderOrdering.size() == 0) {

+            return otherRemainderOrdering;

         } else {

-            if (otherRemainderOrderings.size() == 0) {

-                return thisRemainderOrderings;

-            } else if (thisRemainderOrderings.size() >= otherRemainderOrderings.size()) {

-                return thisRemainderOrderings;

+            if (otherRemainderOrdering.size() == 0) {

+                return thisRemainderOrdering;

+            } else if (thisRemainderOrdering.size() >= otherRemainderOrdering.size()) {

+                return thisRemainderOrdering;

             } else {

-                return otherRemainderOrderings;

+                return otherRemainderOrdering;

             }

         }

     }

diff --git a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java
index b5fdcb9..05474ed 100644
--- a/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java
+++ b/src/main/java/com/amazon/carbonado/qe/SortedQueryExecutor.java
@@ -20,10 +20,7 @@ package com.amazon.carbonado.qe;
 

 import java.io.IOException;

 

-import java.util.ArrayList;

-import java.util.Collections;

 import java.util.Comparator;

-import java.util.List;

 

 import com.amazon.carbonado.Cursor;

 import com.amazon.carbonado.FetchException;

@@ -107,12 +104,6 @@ public abstract class SortedQueryExecutor<S extends Storable> extends AbstractQu
     }

 

     public OrderingList<S> getOrdering() {

-        if (mHandledOrdering.size() == 0) {

-            return mRemainderOrdering;

-        }

-        if (mRemainderOrdering.size() == 0) {

-            return mHandledOrdering;

-        }

         return mHandledOrdering.concat(mRemainderOrdering);

     }

 

diff --git a/src/main/java/com/amazon/carbonado/qe/StandardQuery.java b/src/main/java/com/amazon/carbonado/qe/StandardQuery.java
index 8c423e6..a347b66 100644
--- a/src/main/java/com/amazon/carbonado/qe/StandardQuery.java
+++ b/src/main/java/com/amazon/carbonado/qe/StandardQuery.java
@@ -54,7 +54,7 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
     // Values for this query, which may be null.

     private final FilterValues<S> mValues;

     // Properties that this query is ordered by.

-    private final OrderingList<S> mOrderings;

+    private final OrderingList<S> mOrdering;

 

     private volatile QueryExecutor<S> mExecutor;

 

@@ -67,14 +67,14 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
 

     /**

      * @param values optional values object, defaults to open filter if null

-     * @param orderings optional order-by properties

+     * @param ordering optional order-by properties

      */

-    protected StandardQuery(FilterValues<S> values, OrderingList<S> orderings) {

+    protected StandardQuery(FilterValues<S> values, OrderingList<S> ordering) {

         mValues = values;

-        if (orderings == null) {

-            orderings = OrderingList.emptyList();

+        if (ordering == null) {

+            ordering = OrderingList.emptyList();

         }

-        mOrderings = orderings;

+        mOrdering = ordering;

     }

 

     public Class<S> getStorableType() {

@@ -149,7 +149,7 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
             newQuery = getStorage().query(values.getFilter().and(filter));

             newQuery = newQuery.withValues(values.getValues());

         }

-        return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray());

+        return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray());

     }

 

     public Query<S> or(Filter<S> filter) throws FetchException {

@@ -159,17 +159,17 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
         }

         Query<S> newQuery = getStorage().query(values.getFilter().or(filter));

         newQuery = newQuery.withValues(values.getValues());

-        return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray());

+        return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray());

     }

 

     public Query<S> not() throws FetchException {

         FilterValues<S> values = mValues;

         if (values == null) {

-            return new EmptyQuery<S>(getStorage(), mOrderings);

+            return new EmptyQuery<S>(getStorage(), mOrdering);

         }

         Query<S> newQuery = getStorage().query(values.getFilter().not());

         newQuery = newQuery.withValues(values.getSuppliedValues());

-        return mOrderings.size() == 0 ? newQuery : newQuery.orderBy(mOrderings.asStringArray());

+        return mOrdering.size() == 0 ? newQuery : newQuery.orderBy(mOrdering.asStringArray());

     }

 

     public Query<S> orderBy(String property) throws FetchException {

@@ -186,7 +186,7 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
 

     public Cursor<S> fetchAfter(S start) throws FetchException {

         OrderingList<S> orderings;

-        if (start == null || (orderings = mOrderings).size() == 0) {

+        if (start == null || (orderings = mOrdering).size() == 0) {

             return fetch();

         }

 

@@ -328,13 +328,13 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
             app.append('"');

         }

 

-        if (mOrderings != null && mOrderings.size() > 0) {

+        if (mOrdering != null && mOrdering.size() > 0) {

             app.append(", orderBy=[");

-            for (int i=0; i<mOrderings.size(); i++) {

+            for (int i=0; i<mOrdering.size(); i++) {

                 if (i > 0) {

                     app.append(", ");

                 }

-                app.append(mOrderings.get(i).toString());

+                app.append(mOrdering.get(i).toString());

             }

             app.append(']');

         }

@@ -384,13 +384,13 @@ public abstract class StandardQuery<S extends Storable> extends AbstractQuery<S>
                                                     OrderingList<S> orderings);

 

     private StandardQuery<S> newInstance(FilterValues<S> values) {

-        return newInstance(values, mOrderings);

+        return newInstance(values, mOrdering);

     }

 

     private QueryExecutor<S> executor() {

         QueryExecutor<S> executor = mExecutor;

         if (executor == null) {

-            mExecutor = executor = getExecutor(mValues, mOrderings);

+            mExecutor = executor = getExecutor(mValues, mOrdering);

         }

         return executor;

     }

diff --git a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java
index 5648d21..039aea4 100644
--- a/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java
+++ b/src/main/java/com/amazon/carbonado/qe/UnionQueryAnalyzer.java
@@ -68,53 +68,46 @@ public class UnionQueryAnalyzer<S extends Storable> {
 

     /**

      * @param filter optional filter which must be {@link Filter#isBound bound}

-     * @param orderings optional properties which define desired ordering

+     * @param ordering optional properties which define desired ordering

      */

-    public Result analyze(Filter<S> filter, List<OrderedProperty<S>> orderings) {

+    public Result analyze(Filter<S> filter, OrderingList<S> ordering) {

         if (!filter.isBound()) {

             // Strictly speaking, this is not required, but it detects the

             // mistake of not properly calling initialFilterValues.

             throw new IllegalArgumentException("Filter must be bound");

         }

 

-        if (orderings == null) {

-            orderings = Collections.emptyList();

+        if (ordering == null) {

+            ordering = OrderingList.emptyList();

         }

 

-        List<IndexedQueryAnalyzer<S>.Result> subResults = splitIntoSubResults(filter, orderings);

+        List<IndexedQueryAnalyzer<S>.Result> subResults = splitIntoSubResults(filter, ordering);

 

         if (subResults.size() <= 1) {

             // Total ordering not required.

             return new Result(subResults);

         }

 

-        boolean canMutateOrderings = false;

-

         // If any orderings have an unspecified direction, switch to ASCENDING

         // or DESCENDING, depending on which is more popular. Then build new

         // sub-results.

-        for (int pos = 0; pos < orderings.size(); pos++) {

-            OrderedProperty<S> ordering = orderings.get(pos);

-            if (ordering.getDirection() != Direction.UNSPECIFIED) {

+        for (int pos = 0; pos < ordering.size(); pos++) {

+            OrderedProperty<S> op = ordering.get(pos);

+            if (op.getDirection() != Direction.UNSPECIFIED) {

                 continue;

             }

 

             // Find out which direction is most popular for this property.

-            Tally tally = new Tally(ordering.getChainedProperty());

+            Tally tally = new Tally(op.getChainedProperty());

             for (IndexedQueryAnalyzer<S>.Result result : subResults) {

-                tally.increment(findHandledDirection(result, ordering));

-            }

-

-            if (!canMutateOrderings) {

-                orderings = new ArrayList<OrderedProperty<S>>(orderings);

-                canMutateOrderings = true;

+                tally.increment(findHandledDirection(result, op));

             }

 

-            orderings.set(pos, ordering.direction(tally.getBestDirection()));

+            ordering = ordering.replace(pos, op.direction(tally.getBestDirection()));

 

             // Re-calc with specified direction. Only do one property at a time

             // since one simple change might alter the query plan.

-            subResults = splitIntoSubResults(filter, orderings);

+            subResults = splitIntoSubResults(filter, ordering);

 

             if (subResults.size() <= 1) {

                 // Total ordering no longer required.

@@ -128,8 +121,8 @@ public class UnionQueryAnalyzer<S extends Storable> {
         List<Set<ChainedProperty<S>>> keys = getKeys();

 

         // Check if current ordering is total.

-        for (OrderedProperty<S> ordering : orderings) {

-            ChainedProperty<S> property = ordering.getChainedProperty();

+        for (OrderedProperty<S> op : ordering) {

+            ChainedProperty<S> property = op.getChainedProperty();

             if (pruneKeys(keys, property)) {

                 // Found a key which is fully covered, indicating total ordering.

                 return new Result(subResults);

@@ -152,12 +145,6 @@ public class UnionQueryAnalyzer<S extends Storable> {
             }

         }

 

-        // Prepare to augment orderings to ensure a total ordering.

-        if (!canMutateOrderings) {

-            orderings = new ArrayList<OrderedProperty<S>>(orderings);

-            canMutateOrderings = true;

-        }

-

         // Keep looping until total ordering achieved.

         while (true) {

             // For each ordering score, find the next free property. If

@@ -169,7 +156,7 @@ public class UnionQueryAnalyzer<S extends Storable> {
 

             for (IndexedQueryAnalyzer<S>.Result result : subResults) {

                 OrderingScore<S> score = result.getCompositeScore().getOrderingScore();

-                List<OrderedProperty<S>> free = score.getFreeOrderings();

+                OrderingList<S> free = score.getFreeOrdering();

                 if (free.size() > 0) {

                     OrderedProperty<S> prop = free.get(0);

                     ChainedProperty<S> chainedProp = prop.getChainedProperty();

@@ -184,8 +171,8 @@ public class UnionQueryAnalyzer<S extends Storable> {
             ChainedProperty<S> bestProperty = best.getProperty();

 

             // Now augment the orderings and create new sub-results.

-            orderings.add(OrderedProperty.get(bestProperty, best.getBestDirection()));

-            subResults = splitIntoSubResults(filter, orderings);

+            ordering = ordering.concat(OrderedProperty.get(bestProperty, best.getBestDirection()));

+            subResults = splitIntoSubResults(filter, ordering);

 

             if (subResults.size() <= 1) {

                 // Total ordering no longer required.

@@ -267,7 +254,7 @@ public class UnionQueryAnalyzer<S extends Storable> {
     {

         ChainedProperty<S> chained = unspecified.getChainedProperty();

         OrderingScore<S> score = result.getCompositeScore().getOrderingScore();

-        List<OrderedProperty<S>> handled = score.getHandledOrderings();

+        OrderingList<S> handled = score.getHandledOrdering();

         for (OrderedProperty<S> property : handled) {

             if (chained.equals(property)) {

                 return property.getDirection();

@@ -277,12 +264,12 @@ public class UnionQueryAnalyzer<S extends Storable> {
     }

 

     private List<IndexedQueryAnalyzer<S>.Result>

-        splitIntoSubResults(Filter<S> filter, List<OrderedProperty<S>> orderings)

+        splitIntoSubResults(Filter<S> filter, OrderingList<S> ordering)

     {

         // Required for split to work.

         Filter<S> dnfFilter = filter.disjunctiveNormalForm();

 

-        Splitter splitter = new Splitter(orderings);

+        Splitter splitter = new Splitter(ordering);

         dnfFilter.accept(splitter, null);

 

         List<IndexedQueryAnalyzer<S>.Result> subResults = splitter.mSubResults;

@@ -451,12 +438,12 @@ public class UnionQueryAnalyzer<S extends Storable> {
      * only contain 'and' operations.

      */

     private class Splitter extends Visitor<S, Object, Object> {

-        private final List<OrderedProperty<S>> mOrderings;

+        private final OrderingList<S> mOrdering;

 

         final List<IndexedQueryAnalyzer<S>.Result> mSubResults;

 

-        Splitter(List<OrderedProperty<S>> orderings) {

-            mOrderings = orderings;

+        Splitter(OrderingList<S> ordering) {

+            mOrdering = ordering;

             mSubResults = new ArrayList<IndexedQueryAnalyzer<S>.Result>();

         }

 

@@ -493,7 +480,7 @@ public class UnionQueryAnalyzer<S extends Storable> {
 

         private void subAnalyze(Filter<S> subFilter) {

             IndexedQueryAnalyzer<S>.Result subResult =

-                mIndexAnalyzer.analyze(subFilter, mOrderings);

+                mIndexAnalyzer.analyze(subFilter, mOrdering);

 

             // Rather than blindly add to mSubResults, try to merge with

             // another result. This in turn reduces the number of cursors