From b60ad1c1452bfbd99530deffe66bfc21c9640be9 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Mon, 21 Jan 2008 19:28:53 +0000
Subject: Move StorableIndexSet to qe package.

---
 .../com/amazon/carbonado/qe/StorableIndexSet.java  | 542 +++++++++++++++++++++
 .../carbonado/repo/indexed/IndexAnalysis.java      |   3 +-
 .../carbonado/repo/indexed/IndexedStorage.java     |   3 +-
 .../carbonado/repo/sleepycat/BDBStorage.java       |   2 +-
 .../com/amazon/carbonado/spi/StorableIndexSet.java | 542 ---------------------
 5 files changed, 545 insertions(+), 547 deletions(-)
 create mode 100644 src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java
 delete mode 100644 src/main/java/com/amazon/carbonado/spi/StorableIndexSet.java

(limited to 'src/main/java/com/amazon')

diff --git a/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java b/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java
new file mode 100644
index 0000000..976d5a1
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/qe/StorableIndexSet.java
@@ -0,0 +1,542 @@
+/*
+ * Copyright 2006 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.qe;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.info.Direction;
+import com.amazon.carbonado.info.OrderedProperty;
+import com.amazon.carbonado.info.StorableIndex;
+import com.amazon.carbonado.info.StorableInfo;
+import com.amazon.carbonado.info.StorableKey;
+import com.amazon.carbonado.info.StorableProperty;
+
+/**
+ * Manages a set of {@link StorableIndex} objects, intended for reducing the
+ * set such that the minimal amount of physical indexes need to be defined for
+ * a specific type of {@link Storable}.
+ *
+ * @author Brian S O'Neill
+ */
+public class StorableIndexSet<S extends Storable> extends TreeSet<StorableIndex<S>> {
+
+    private static final long serialVersionUID = -5840661016235340456L;
+
+    private static final Comparator<StorableIndex<?>> STORABLE_INDEX_COMPARATOR =
+        new StorableIndexComparator();
+
+    public StorableIndexSet() {
+        super(STORABLE_INDEX_COMPARATOR);
+    }
+
+    /**
+     * Copy constructor.
+     */
+    public StorableIndexSet(StorableIndexSet<S> set) {
+        super(STORABLE_INDEX_COMPARATOR);
+        addAll(set);
+    }
+
+    /**
+     * Adds all the indexes of the given storable.
+     *
+     * @throws IllegalArgumentException if info is null
+     */
+    public void addIndexes(StorableInfo<S> info) {
+        for (int i=info.getIndexCount(); --i>=0; ) {
+            add(info.getIndex(i));
+        }
+    }
+
+    /**
+     * Adds all the indexes of the given storable.
+     *
+     * @param defaultDirection default ordering direction to apply to each
+     * index property
+     * @throws IllegalArgumentException if any argument is null
+     */
+    public void addIndexes(StorableInfo<S> info, Direction defaultDirection) {
+        for (int i=info.getIndexCount(); --i>=0; ) {
+            add(info.getIndex(i).setDefaultDirection(defaultDirection));
+        }
+    }
+
+    /**
+     * Adds all of the alternate keys of the given storable as indexes by
+     * calling {@link #addKey addKey}.
+     *
+     * @throws IllegalArgumentException if info is null
+     */
+    public void addAlternateKeys(StorableInfo<S> info) {
+        if (info == null) {
+            throw new IllegalArgumentException();
+        }
+        for (int i=info.getAlternateKeyCount(); --i>=0; ) {
+            addKey(info.getAlternateKey(i));
+        }
+    }
+
+    /**
+     * Adds the primary key of the given storable as indexes by calling {@link
+     * #addKey addKey}. This method should not be called if the primary key
+     * cannot be altered because persistent data is already stored against
+     * it. Instead, the primary key index should be added as a normal index.
+     *
+     * <p>After adding the primary key via this method and after reducing the
+     * set, call {@link #findPrimaryKeyIndex findPrimaryKeyIndex} to get the
+     * best index to represent the primary key.
+     *
+     * @throws IllegalArgumentException if info is null
+     */
+    public void addPrimaryKey(StorableInfo<S> info) {
+        if (info == null) {
+            throw new IllegalArgumentException();
+        }
+        addKey(info.getPrimaryKey());
+    }
+
+    /**
+     * Adds the key as a unique index, preserving the property arrangement.
+     *
+     * @throws IllegalArgumentException if key is null
+     */
+    @SuppressWarnings("unchecked")
+    public void addKey(StorableKey<S> key) {
+        if (key == null) {
+            throw new IllegalArgumentException();
+        }
+        add(new StorableIndex<S>(key, Direction.UNSPECIFIED));
+    }
+
+    /**
+     * Reduces the size of the set by removing redundant indexes, and merges
+     * others together.
+     */
+    public void reduce() {
+        reduce(Direction.UNSPECIFIED);
+    }
+
+    /**
+     * Reduces the size of the set by removing redundant indexes, and merges
+     * others together.
+     *
+     * @param defaultDirection replace unspecified property directions with this
+     */
+    public void reduce(Direction defaultDirection) {
+        List<StorableIndex<S>> group = new ArrayList<StorableIndex<S>>();
+        Map<StorableIndex<S>, StorableIndex<S>> mergedReplacements =
+            new TreeMap<StorableIndex<S>, StorableIndex<S>>(STORABLE_INDEX_COMPARATOR);
+
+        Iterator<StorableIndex<S>> it = iterator();
+        while (it.hasNext()) {
+            StorableIndex<S> candidate = it.next();
+
+            if (group.size() == 0 || isDifferentGroup(group.get(0), candidate)) {
+                group.clear();
+                group.add(candidate);
+                continue;
+            }
+
+            if (isRedundant(group, candidate, mergedReplacements)) {
+                it.remove();
+            } else {
+                group.add(candidate);
+            }
+        }
+
+        // Now replace merged indexes.
+        replaceEntries(mergedReplacements);
+
+        setDefaultDirection(defaultDirection);
+    }
+
+    /**
+     * Set the default direction for all index properties.
+     *
+     * @param defaultDirection replace unspecified property directions with this
+     */
+    public void setDefaultDirection(Direction defaultDirection) {
+        // Apply default sort direction to those unspecified.
+        if (defaultDirection != Direction.UNSPECIFIED) {
+            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
+            for (StorableIndex<S> index : this) {
+                StorableIndex<S> replacement = index.setDefaultDirection(defaultDirection);
+                if (replacement != index) {
+                    if (replacements == null) {
+                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
+                    }
+                    replacements.put(index, replacement);
+                }
+            }
+            replaceEntries(replacements);
+        }
+    }
+
+    /**
+     * Marks all indexes as clustered or non-clustered.
+     *
+     * @param clustered true to mark clustered; false to mark non-clustered
+     * @see StorableIndex#isClustered()
+     * @since 1.2
+     */
+    public void markClustered(boolean clustered) {
+        Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
+        for (StorableIndex<S> index : this) {
+            StorableIndex<S> replacement = index.clustered(clustered);
+            if (replacement != index) {
+                if (replacements == null) {
+                    replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
+                }
+                replacements.put(index, replacement);
+            }
+        }
+        replaceEntries(replacements);
+    }
+
+    /**
+     * Augment non-unique indexes with primary key properties, thus making them
+     * unique.
+     *
+     * @throws IllegalArgumentException if info is null
+     */
+    public void uniquify(StorableInfo<S> info) {
+        if (info == null) {
+            throw new IllegalArgumentException();
+        }
+        uniquify(info.getPrimaryKey());
+    }
+
+    /**
+     * Augment non-unique indexes with key properties, thus making them unique.
+     *
+     * @throws IllegalArgumentException if key is null
+     */
+    public void uniquify(StorableKey<S> key) {
+        if (key == null) {
+            throw new IllegalArgumentException();
+        }
+
+
+        // Replace indexes which were are implied unique, even if they are not
+        // declared as such.
+        {
+            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
+            for (StorableIndex<S> index : this) {
+                if (!index.isUnique() && isUniqueImplied(index)) {
+                    if (replacements == null) {
+                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
+                    }
+                    replacements.put(index, index.unique(true));
+                }
+            }
+            replaceEntries(replacements);
+        }
+
+        // Now augment with key properties.
+        {
+            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
+            for (StorableIndex<S> index : this) {
+                StorableIndex<S> replacement = index.uniquify(key);
+                if (replacement != index) {
+                    if (replacements == null) {
+                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
+                    }
+                    replacements.put(index, replacement);
+                }
+            }
+            replaceEntries(replacements);
+        }
+    }
+
+    /**
+     * Finds the best index to represent the primary key. Should be called
+     * after calling reduce. As long as the primary key was added via {@link
+     * #addPrimaryKey addPrimaryKey}, this method should never return null.
+     *
+     * @throws IllegalArgumentException if info is null
+     */
+    public StorableIndex<S> findPrimaryKeyIndex(StorableInfo<S> info) {
+        if (info == null) {
+            throw new IllegalArgumentException();
+        }
+        return findKeyIndex(info.getPrimaryKey());
+    }
+
+    /**
+     * Finds the best index to represent the given key. Should be called after
+     * calling reduce. As long as the key was added via {@link #addKey addKey},
+     * this method should never return null.
+     *
+     * @throws IllegalArgumentException if key is null
+     */
+    public StorableIndex<S> findKeyIndex(StorableKey<S> key) {
+        if (key == null) {
+            throw new IllegalArgumentException();
+        }
+
+        Set<? extends OrderedProperty<S>> orderedProps = key.getProperties();
+
+        Set<StorableProperty<S>> keyProps = new HashSet<StorableProperty<S>>();
+        for (OrderedProperty<S> orderedProp : orderedProps) {
+            keyProps.add(orderedProp.getChainedProperty().getPrimeProperty());
+        }
+
+        search: for (StorableIndex<S> index : this) {
+            if (!index.isUnique() || index.getPropertyCount() != keyProps.size()) {
+                continue search;
+            }
+            for (int i=index.getPropertyCount(); --i>=0; ) {
+                if (!keyProps.contains(index.getProperty(i))) {
+                    continue search;
+                }
+            }
+            return index;
+        }
+
+        return null;
+    }
+
+    /**
+     * Return true if index is unique or fully contains the members of a unique index.
+     */
+    private boolean isUniqueImplied(StorableIndex<S> candidate) {
+        if (candidate.isUnique()) {
+            return true;
+        }
+        if (this.size() <= 1) {
+            return false;
+        }
+
+        Set<StorableProperty<S>> candidateProps = new HashSet<StorableProperty<S>>();
+        for (int i=candidate.getPropertyCount(); --i>=0; ) {
+            candidateProps.add(candidate.getProperty(i));
+        }
+
+        search: for (StorableIndex<S> index : this) {
+            if (!index.isUnique()) {
+                continue search;
+            }
+            for (int i=index.getPropertyCount(); --i>=0; ) {
+                if (!candidateProps.contains(index.getProperty(i))) {
+                    continue search;
+                }
+            }
+            return true;
+        }
+
+        return false;
+    }
+
+    private boolean isDifferentGroup(StorableIndex<S> groupLeader, StorableIndex<S> candidate) {
+        int count = candidate.getPropertyCount();
+        if (count > groupLeader.getPropertyCount()) {
+            return true;
+        }
+        for (int i=0; i<count; i++) {
+            StorableProperty aProp = groupLeader.getProperty(i);
+            StorableProperty bProp = candidate.getProperty(i);
+            if (aProp.getName().compareTo(bProp.getName()) != 0) {
+                return true;
+            }
+        }
+        return candidate.isUnique() && (count < groupLeader.getPropertyCount());
+    }
+
+    /**
+     * Returns true if candidate index is less qualified than an existing group
+     * member, or if it was merged with another group member. If it was merged,
+     * then an entry is placed in the merged map, and the given group list is
+     * updated.
+     */
+    private boolean isRedundant(List<StorableIndex<S>> group, StorableIndex<S> candidate,
+                                Map<StorableIndex<S>, StorableIndex<S>> mergedReplacements) {
+        // All visited group members will have an equal or greater number of
+        // properties. This is ensured by the ordering of the set.
+        int count = candidate.getPropertyCount();
+
+        ListIterator<StorableIndex<S>> it = group.listIterator();
+        groupScan:
+        while (it.hasNext()) {
+            StorableIndex<S> member = it.next();
+
+            boolean moreQualified = false;
+            boolean canReverse = true;
+            boolean reverse = false;
+
+            for (int i=0; i<count; i++) {
+                Direction candidateOrder = candidate.getPropertyDirection(i);
+                if (candidateOrder == Direction.UNSPECIFIED) {
+                    // Property direction is unspecified, so no need to compare
+                    // direction. Move on to next property.
+                    continue;
+                }
+
+                Direction memberOrder = member.getPropertyDirection(i);
+                if (memberOrder == Direction.UNSPECIFIED) {
+                    // Candidate index is more qualified because member
+                    // property under examination hasn't specified a
+                    // direction. Move on to next property to continue checking
+                    // if a merge is possible.
+                    moreQualified = true;
+                    continue;
+                }
+
+                if (reverse) {
+                    candidateOrder = candidateOrder.reverse();
+                }
+
+                if (candidateOrder == memberOrder) {
+                    // Direction exactly matches, move on to next property.
+                    canReverse = false;
+                    continue;
+                }
+
+                // If this point is reached, then the direction would match if
+                // one was reversed. For an index to fully match, all
+                // properties must be reversed.
+
+                if (canReverse) {
+                    // Switch to reverse mode and move on to next property.
+                    reverse = true;
+                    canReverse = false;
+                    continue;
+                }
+
+                // Match failed and merge is not possible.
+                continue groupScan;
+            }
+
+            if (moreQualified) {
+                // Candidate is more qualified than all members compared to so
+                // far, but it can be merged. Once merged, it is redundant.
+                Direction[] directions = member.getPropertyDirections();
+                for (int i=0; i<count; i++) {
+                    if (directions[i] == Direction.UNSPECIFIED) {
+                        Direction direction = candidate.getPropertyDirection(i);
+                        directions[i] = reverse ? direction.reverse() : direction;
+                    }
+                }
+
+                StorableIndex<S> merged =
+                    new StorableIndex<S>(member.getProperties(), directions)
+                    .unique(member.isUnique());
+                mergedReplacements.put(member, merged);
+                it.set(merged);
+            }
+
+            // Candidate is redundant.
+            return true;
+        }
+
+        return false;
+    }
+
+    private void replaceEntries(Map<StorableIndex<S>, StorableIndex<S>> replacements) {
+        if (replacements != null) {
+            for (Map.Entry<StorableIndex<S>, StorableIndex<S>> e : replacements.entrySet()) {
+                remove(e.getKey());
+                add(e.getValue());
+            }
+        }
+    }
+
+    /**
+     * Orders indexes such that they are grouped by property names. Within
+     * those groups, indexes are ordered most qualified to least qualified.
+     */
+    private static class StorableIndexComparator implements Comparator<StorableIndex<?>> {
+        public int compare(StorableIndex<?> a, StorableIndex<?> b) {
+            if (a == b) {
+                return 0;
+            }
+
+            int aCount = a.getPropertyCount();
+            int bCount = b.getPropertyCount();
+
+            int count = Math.min(aCount, bCount);
+
+            for (int i=0; i<count; i++) {
+                StorableProperty aProp = a.getProperty(i);
+                StorableProperty bProp = b.getProperty(i);
+                int result = aProp.getName().compareTo(bProp.getName());
+                if (aProp.getName().compareTo(bProp.getName()) != 0) {
+                    return result;
+                }
+            }
+
+            // Index with more properties is first.
+            if (aCount > bCount) {
+                return -1;
+            } else if (aCount < bCount) {
+                return 1;
+            }
+
+            // Counts are the same, property names are the same. Unique indexes
+            // are first, followed by index with more leading directions. Favor
+            // ascending direction.
+
+            for (int i=0; i<count; i++) {
+                if (a.isUnique()) {
+                    if (!b.isUnique()) {
+                        return -1;
+                    }
+                } else if (b.isUnique()) {
+                    return 1;
+                }
+
+                Direction aDirection = a.getPropertyDirection(i);
+                Direction bDirection = b.getPropertyDirection(i);
+
+                if (aDirection == bDirection) {
+                    continue;
+                }
+
+                // These order in which these tests are performed must not be
+                // altered without careful examination.
+
+                if (aDirection == Direction.ASCENDING) {
+                    return -1;
+                }
+                if (bDirection == Direction.ASCENDING) {
+                    return 1;
+                }
+                if (aDirection == Direction.DESCENDING) {
+                    return -1;
+                }
+                if (bDirection == Direction.DESCENDING) {
+                    return 1;
+                }
+            }
+
+            return 0;
+        }
+    }
+}
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexAnalysis.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexAnalysis.java
index 31f5d7e..d65e32e 100644
--- a/src/main/java/com/amazon/carbonado/repo/indexed/IndexAnalysis.java
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexAnalysis.java
@@ -35,8 +35,7 @@ import com.amazon.carbonado.info.StorableIntrospector;
 import com.amazon.carbonado.info.StorableProperty;
 
 import com.amazon.carbonado.qe.FilteringScore;
-
-import com.amazon.carbonado.spi.StorableIndexSet;
+import com.amazon.carbonado.qe.StorableIndexSet;
 
 /**
  * Collection of static methods which perform index analysis.
diff --git a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
index 87e8eb9..35a3ae3 100644
--- a/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
+++ b/src/main/java/com/amazon/carbonado/repo/indexed/IndexedStorage.java
@@ -57,10 +57,9 @@ import com.amazon.carbonado.cursor.SortBuffer;
 import com.amazon.carbonado.qe.BoundaryType;
 import com.amazon.carbonado.qe.QueryEngine;
 import com.amazon.carbonado.qe.QueryExecutorFactory;
+import com.amazon.carbonado.qe.StorableIndexSet;
 import com.amazon.carbonado.qe.StorageAccess;
 
-import com.amazon.carbonado.spi.StorableIndexSet;
-
 import com.amazon.carbonado.util.Throttle;
 
 import static com.amazon.carbonado.repo.indexed.ManagedIndex.*;
diff --git a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java
index 77ea7d7..e7368ac 100644
--- a/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java
+++ b/src/main/java/com/amazon/carbonado/repo/sleepycat/BDBStorage.java
@@ -66,6 +66,7 @@ import com.amazon.carbonado.lob.Clob;
 import com.amazon.carbonado.qe.BoundaryType;
 import com.amazon.carbonado.qe.QueryEngine;
 import com.amazon.carbonado.qe.QueryExecutorFactory;
+import com.amazon.carbonado.qe.StorableIndexSet;
 import com.amazon.carbonado.qe.StorageAccess;
 
 import com.amazon.carbonado.raw.StorableCodec;
@@ -77,7 +78,6 @@ import com.amazon.carbonado.sequence.SequenceValueProducer;
 
 import com.amazon.carbonado.spi.IndexInfoImpl;
 import com.amazon.carbonado.spi.LobEngine;
-import com.amazon.carbonado.spi.StorableIndexSet;
 import com.amazon.carbonado.spi.TransactionScope;
 import com.amazon.carbonado.spi.TriggerManager;
 
diff --git a/src/main/java/com/amazon/carbonado/spi/StorableIndexSet.java b/src/main/java/com/amazon/carbonado/spi/StorableIndexSet.java
deleted file mode 100644
index f43bdd4..0000000
--- a/src/main/java/com/amazon/carbonado/spi/StorableIndexSet.java
+++ /dev/null
@@ -1,542 +0,0 @@
-/*
- * Copyright 2006 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.spi;
-
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ListIterator;
-import java.util.Map;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
-
-import com.amazon.carbonado.Storable;
-
-import com.amazon.carbonado.info.Direction;
-import com.amazon.carbonado.info.OrderedProperty;
-import com.amazon.carbonado.info.StorableIndex;
-import com.amazon.carbonado.info.StorableInfo;
-import com.amazon.carbonado.info.StorableKey;
-import com.amazon.carbonado.info.StorableProperty;
-
-/**
- * Manages a set of {@link StorableIndex} objects, intended for reducing the
- * set such that the minimal amount of physical indexes need to be defined for
- * a specific type of {@link Storable}.
- *
- * @author Brian S O'Neill
- */
-public class StorableIndexSet<S extends Storable> extends TreeSet<StorableIndex<S>> {
-
-    private static final long serialVersionUID = -5840661016235340456L;
-
-    private static final Comparator<StorableIndex<?>> STORABLE_INDEX_COMPARATOR =
-        new StorableIndexComparator();
-
-    public StorableIndexSet() {
-        super(STORABLE_INDEX_COMPARATOR);
-    }
-
-    /**
-     * Copy constructor.
-     */
-    public StorableIndexSet(StorableIndexSet<S> set) {
-        super(STORABLE_INDEX_COMPARATOR);
-        addAll(set);
-    }
-
-    /**
-     * Adds all the indexes of the given storable.
-     *
-     * @throws IllegalArgumentException if info is null
-     */
-    public void addIndexes(StorableInfo<S> info) {
-        for (int i=info.getIndexCount(); --i>=0; ) {
-            add(info.getIndex(i));
-        }
-    }
-
-    /**
-     * Adds all the indexes of the given storable.
-     *
-     * @param defaultDirection default ordering direction to apply to each
-     * index property
-     * @throws IllegalArgumentException if any argument is null
-     */
-    public void addIndexes(StorableInfo<S> info, Direction defaultDirection) {
-        for (int i=info.getIndexCount(); --i>=0; ) {
-            add(info.getIndex(i).setDefaultDirection(defaultDirection));
-        }
-    }
-
-    /**
-     * Adds all of the alternate keys of the given storable as indexes by
-     * calling {@link #addKey addKey}.
-     *
-     * @throws IllegalArgumentException if info is null
-     */
-    public void addAlternateKeys(StorableInfo<S> info) {
-        if (info == null) {
-            throw new IllegalArgumentException();
-        }
-        for (int i=info.getAlternateKeyCount(); --i>=0; ) {
-            addKey(info.getAlternateKey(i));
-        }
-    }
-
-    /**
-     * Adds the primary key of the given storable as indexes by calling {@link
-     * #addKey addKey}. This method should not be called if the primary key
-     * cannot be altered because persistent data is already stored against
-     * it. Instead, the primary key index should be added as a normal index.
-     *
-     * <p>After adding the primary key via this method and after reducing the
-     * set, call {@link #findPrimaryKeyIndex findPrimaryKeyIndex} to get the
-     * best index to represent the primary key.
-     *
-     * @throws IllegalArgumentException if info is null
-     */
-    public void addPrimaryKey(StorableInfo<S> info) {
-        if (info == null) {
-            throw new IllegalArgumentException();
-        }
-        addKey(info.getPrimaryKey());
-    }
-
-    /**
-     * Adds the key as a unique index, preserving the property arrangement.
-     *
-     * @throws IllegalArgumentException if key is null
-     */
-    @SuppressWarnings("unchecked")
-    public void addKey(StorableKey<S> key) {
-        if (key == null) {
-            throw new IllegalArgumentException();
-        }
-        add(new StorableIndex<S>(key, Direction.UNSPECIFIED));
-    }
-
-    /**
-     * Reduces the size of the set by removing redundant indexes, and merges
-     * others together.
-     */
-    public void reduce() {
-        reduce(Direction.UNSPECIFIED);
-    }
-
-    /**
-     * Reduces the size of the set by removing redundant indexes, and merges
-     * others together.
-     *
-     * @param defaultDirection replace unspecified property directions with this
-     */
-    public void reduce(Direction defaultDirection) {
-        List<StorableIndex<S>> group = new ArrayList<StorableIndex<S>>();
-        Map<StorableIndex<S>, StorableIndex<S>> mergedReplacements =
-            new TreeMap<StorableIndex<S>, StorableIndex<S>>(STORABLE_INDEX_COMPARATOR);
-
-        Iterator<StorableIndex<S>> it = iterator();
-        while (it.hasNext()) {
-            StorableIndex<S> candidate = it.next();
-
-            if (group.size() == 0 || isDifferentGroup(group.get(0), candidate)) {
-                group.clear();
-                group.add(candidate);
-                continue;
-            }
-
-            if (isRedundant(group, candidate, mergedReplacements)) {
-                it.remove();
-            } else {
-                group.add(candidate);
-            }
-        }
-
-        // Now replace merged indexes.
-        replaceEntries(mergedReplacements);
-
-        setDefaultDirection(defaultDirection);
-    }
-
-    /**
-     * Set the default direction for all index properties.
-     *
-     * @param defaultDirection replace unspecified property directions with this
-     */
-    public void setDefaultDirection(Direction defaultDirection) {
-        // Apply default sort direction to those unspecified.
-        if (defaultDirection != Direction.UNSPECIFIED) {
-            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
-            for (StorableIndex<S> index : this) {
-                StorableIndex<S> replacement = index.setDefaultDirection(defaultDirection);
-                if (replacement != index) {
-                    if (replacements == null) {
-                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
-                    }
-                    replacements.put(index, replacement);
-                }
-            }
-            replaceEntries(replacements);
-        }
-    }
-
-    /**
-     * Marks all indexes as clustered or non-clustered.
-     *
-     * @param clustered true to mark clustered; false to mark non-clustered
-     * @see StorableIndex#isClustered()
-     * @since 1.2
-     */
-    public void markClustered(boolean clustered) {
-        Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
-        for (StorableIndex<S> index : this) {
-            StorableIndex<S> replacement = index.clustered(clustered);
-            if (replacement != index) {
-                if (replacements == null) {
-                    replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
-                }
-                replacements.put(index, replacement);
-            }
-        }
-        replaceEntries(replacements);
-    }
-
-    /**
-     * Augment non-unique indexes with primary key properties, thus making them
-     * unique.
-     *
-     * @throws IllegalArgumentException if info is null
-     */
-    public void uniquify(StorableInfo<S> info) {
-        if (info == null) {
-            throw new IllegalArgumentException();
-        }
-        uniquify(info.getPrimaryKey());
-    }
-
-    /**
-     * Augment non-unique indexes with key properties, thus making them unique.
-     *
-     * @throws IllegalArgumentException if key is null
-     */
-    public void uniquify(StorableKey<S> key) {
-        if (key == null) {
-            throw new IllegalArgumentException();
-        }
-
-
-        // Replace indexes which were are implied unique, even if they are not
-        // declared as such.
-        {
-            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
-            for (StorableIndex<S> index : this) {
-                if (!index.isUnique() && isUniqueImplied(index)) {
-                    if (replacements == null) {
-                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
-                    }
-                    replacements.put(index, index.unique(true));
-                }
-            }
-            replaceEntries(replacements);
-        }
-
-        // Now augment with key properties.
-        {
-            Map<StorableIndex<S>, StorableIndex<S>> replacements = null;
-            for (StorableIndex<S> index : this) {
-                StorableIndex<S> replacement = index.uniquify(key);
-                if (replacement != index) {
-                    if (replacements == null) {
-                        replacements = new HashMap<StorableIndex<S>, StorableIndex<S>>();
-                    }
-                    replacements.put(index, replacement);
-                }
-            }
-            replaceEntries(replacements);
-        }
-    }
-
-    /**
-     * Finds the best index to represent the primary key. Should be called
-     * after calling reduce. As long as the primary key was added via {@link
-     * #addPrimaryKey addPrimaryKey}, this method should never return null.
-     *
-     * @throws IllegalArgumentException if info is null
-     */
-    public StorableIndex<S> findPrimaryKeyIndex(StorableInfo<S> info) {
-        if (info == null) {
-            throw new IllegalArgumentException();
-        }
-        return findKeyIndex(info.getPrimaryKey());
-    }
-
-    /**
-     * Finds the best index to represent the given key. Should be called after
-     * calling reduce. As long as the key was added via {@link #addKey addKey},
-     * this method should never return null.
-     *
-     * @throws IllegalArgumentException if key is null
-     */
-    public StorableIndex<S> findKeyIndex(StorableKey<S> key) {
-        if (key == null) {
-            throw new IllegalArgumentException();
-        }
-
-        Set<? extends OrderedProperty<S>> orderedProps = key.getProperties();
-
-        Set<StorableProperty<S>> keyProps = new HashSet<StorableProperty<S>>();
-        for (OrderedProperty<S> orderedProp : orderedProps) {
-            keyProps.add(orderedProp.getChainedProperty().getPrimeProperty());
-        }
-
-        search: for (StorableIndex<S> index : this) {
-            if (!index.isUnique() || index.getPropertyCount() != keyProps.size()) {
-                continue search;
-            }
-            for (int i=index.getPropertyCount(); --i>=0; ) {
-                if (!keyProps.contains(index.getProperty(i))) {
-                    continue search;
-                }
-            }
-            return index;
-        }
-
-        return null;
-    }
-
-    /**
-     * Return true if index is unique or fully contains the members of a unique index.
-     */
-    private boolean isUniqueImplied(StorableIndex<S> candidate) {
-        if (candidate.isUnique()) {
-            return true;
-        }
-        if (this.size() <= 1) {
-            return false;
-        }
-
-        Set<StorableProperty<S>> candidateProps = new HashSet<StorableProperty<S>>();
-        for (int i=candidate.getPropertyCount(); --i>=0; ) {
-            candidateProps.add(candidate.getProperty(i));
-        }
-
-        search: for (StorableIndex<S> index : this) {
-            if (!index.isUnique()) {
-                continue search;
-            }
-            for (int i=index.getPropertyCount(); --i>=0; ) {
-                if (!candidateProps.contains(index.getProperty(i))) {
-                    continue search;
-                }
-            }
-            return true;
-        }
-
-        return false;
-    }
-
-    private boolean isDifferentGroup(StorableIndex<S> groupLeader, StorableIndex<S> candidate) {
-        int count = candidate.getPropertyCount();
-        if (count > groupLeader.getPropertyCount()) {
-            return true;
-        }
-        for (int i=0; i<count; i++) {
-            StorableProperty aProp = groupLeader.getProperty(i);
-            StorableProperty bProp = candidate.getProperty(i);
-            if (aProp.getName().compareTo(bProp.getName()) != 0) {
-                return true;
-            }
-        }
-        return candidate.isUnique() && (count < groupLeader.getPropertyCount());
-    }
-
-    /**
-     * Returns true if candidate index is less qualified than an existing group
-     * member, or if it was merged with another group member. If it was merged,
-     * then an entry is placed in the merged map, and the given group list is
-     * updated.
-     */
-    private boolean isRedundant(List<StorableIndex<S>> group, StorableIndex<S> candidate,
-                                Map<StorableIndex<S>, StorableIndex<S>> mergedReplacements) {
-        // All visited group members will have an equal or greater number of
-        // properties. This is ensured by the ordering of the set.
-        int count = candidate.getPropertyCount();
-
-        ListIterator<StorableIndex<S>> it = group.listIterator();
-        groupScan:
-        while (it.hasNext()) {
-            StorableIndex<S> member = it.next();
-
-            boolean moreQualified = false;
-            boolean canReverse = true;
-            boolean reverse = false;
-
-            for (int i=0; i<count; i++) {
-                Direction candidateOrder = candidate.getPropertyDirection(i);
-                if (candidateOrder == Direction.UNSPECIFIED) {
-                    // Property direction is unspecified, so no need to compare
-                    // direction. Move on to next property.
-                    continue;
-                }
-
-                Direction memberOrder = member.getPropertyDirection(i);
-                if (memberOrder == Direction.UNSPECIFIED) {
-                    // Candidate index is more qualified because member
-                    // property under examination hasn't specified a
-                    // direction. Move on to next property to continue checking
-                    // if a merge is possible.
-                    moreQualified = true;
-                    continue;
-                }
-
-                if (reverse) {
-                    candidateOrder = candidateOrder.reverse();
-                }
-
-                if (candidateOrder == memberOrder) {
-                    // Direction exactly matches, move on to next property.
-                    canReverse = false;
-                    continue;
-                }
-
-                // If this point is reached, then the direction would match if
-                // one was reversed. For an index to fully match, all
-                // properties must be reversed.
-
-                if (canReverse) {
-                    // Switch to reverse mode and move on to next property.
-                    reverse = true;
-                    canReverse = false;
-                    continue;
-                }
-
-                // Match failed and merge is not possible.
-                continue groupScan;
-            }
-
-            if (moreQualified) {
-                // Candidate is more qualified than all members compared to so
-                // far, but it can be merged. Once merged, it is redundant.
-                Direction[] directions = member.getPropertyDirections();
-                for (int i=0; i<count; i++) {
-                    if (directions[i] == Direction.UNSPECIFIED) {
-                        Direction direction = candidate.getPropertyDirection(i);
-                        directions[i] = reverse ? direction.reverse() : direction;
-                    }
-                }
-
-                StorableIndex<S> merged =
-                    new StorableIndex<S>(member.getProperties(), directions)
-                    .unique(member.isUnique());
-                mergedReplacements.put(member, merged);
-                it.set(merged);
-            }
-
-            // Candidate is redundant.
-            return true;
-        }
-
-        return false;
-    }
-
-    private void replaceEntries(Map<StorableIndex<S>, StorableIndex<S>> replacements) {
-        if (replacements != null) {
-            for (Map.Entry<StorableIndex<S>, StorableIndex<S>> e : replacements.entrySet()) {
-                remove(e.getKey());
-                add(e.getValue());
-            }
-        }
-    }
-
-    /**
-     * Orders indexes such that they are grouped by property names. Within
-     * those groups, indexes are ordered most qualified to least qualified.
-     */
-    private static class StorableIndexComparator implements Comparator<StorableIndex<?>> {
-        public int compare(StorableIndex<?> a, StorableIndex<?> b) {
-            if (a == b) {
-                return 0;
-            }
-
-            int aCount = a.getPropertyCount();
-            int bCount = b.getPropertyCount();
-
-            int count = Math.min(aCount, bCount);
-
-            for (int i=0; i<count; i++) {
-                StorableProperty aProp = a.getProperty(i);
-                StorableProperty bProp = b.getProperty(i);
-                int result = aProp.getName().compareTo(bProp.getName());
-                if (aProp.getName().compareTo(bProp.getName()) != 0) {
-                    return result;
-                }
-            }
-
-            // Index with more properties is first.
-            if (aCount > bCount) {
-                return -1;
-            } else if (aCount < bCount) {
-                return 1;
-            }
-
-            // Counts are the same, property names are the same. Unique indexes
-            // are first, followed by index with more leading directions. Favor
-            // ascending direction.
-
-            for (int i=0; i<count; i++) {
-                if (a.isUnique()) {
-                    if (!b.isUnique()) {
-                        return -1;
-                    }
-                } else if (b.isUnique()) {
-                    return 1;
-                }
-
-                Direction aDirection = a.getPropertyDirection(i);
-                Direction bDirection = b.getPropertyDirection(i);
-
-                if (aDirection == bDirection) {
-                    continue;
-                }
-
-                // These order in which these tests are performed must not be
-                // altered without careful examination.
-
-                if (aDirection == Direction.ASCENDING) {
-                    return -1;
-                }
-                if (bDirection == Direction.ASCENDING) {
-                    return 1;
-                }
-                if (aDirection == Direction.DESCENDING) {
-                    return -1;
-                }
-                if (bDirection == Direction.DESCENDING) {
-                    return 1;
-                }
-            }
-
-            return 0;
-        }
-    }
-}
-- 
cgit v1.2.3