cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bened...@apache.org
Subject [1/9] cassandra git commit: Back Columns by a BTree, not an array
Date Thu, 06 Aug 2015 12:37:37 GMT
Repository: cassandra
Updated Branches:
  refs/heads/cassandra-3.0 c3ed25b0a -> ace28c928
  refs/heads/trunk f512995e0 -> 9cd4f8293


Back Columns by a BTree, not an array

patch by benedict; reviewed by branimir for CASSANDRA-9471


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/ace28c92
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/ace28c92
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/ace28c92

Branch: refs/heads/cassandra-3.0
Commit: ace28c9283358da75538c4e2250f8437efb7168f
Parents: f54580d
Author: Benedict Elliott Smith <benedict@apache.org>
Authored: Mon Jul 27 17:28:02 2015 +0100
Committer: Benedict Elliott Smith <benedict@apache.org>
Committed: Thu Aug 6 14:36:07 2015 +0200

----------------------------------------------------------------------
 src/java/org/apache/cassandra/db/Columns.java   | 266 +++++--------------
 .../cassandra/db/view/MaterializedView.java     |   2 +-
 .../org/apache/cassandra/utils/btree/BTree.java |  13 +-
 .../org/apache/cassandra/db/ColumnsTest.java    | 244 +++++++++++++++++
 4 files changed, 320 insertions(+), 205 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/ace28c92/src/java/org/apache/cassandra/db/Columns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/Columns.java b/src/java/org/apache/cassandra/db/Columns.java
index 03d2e14..231b529 100644
--- a/src/java/org/apache/cassandra/db/Columns.java
+++ b/src/java/org/apache/cassandra/db/Columns.java
@@ -23,16 +23,20 @@ import java.util.function.Predicate;
 import java.nio.ByteBuffer;
 import java.security.MessageDigest;
 
-import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterators;
 
 import org.apache.cassandra.config.CFMetaData;
 import org.apache.cassandra.config.ColumnDefinition;
+import org.apache.cassandra.cql3.ColumnIdentifier;
+import org.apache.cassandra.db.marshal.SetType;
 import org.apache.cassandra.db.marshal.UTF8Type;
-import org.apache.cassandra.db.marshal.MapType;
 import org.apache.cassandra.io.util.DataInputPlus;
 import org.apache.cassandra.io.util.DataOutputPlus;
 import org.apache.cassandra.utils.ByteBufferUtil;
+import org.apache.cassandra.utils.SearchIterator;
+import org.apache.cassandra.utils.btree.BTree;
+import org.apache.cassandra.utils.btree.BTreeSearchIterator;
 
 /**
  * An immutable and sorted list of (non-PK) columns for a given table.
@@ -43,19 +47,21 @@ import org.apache.cassandra.utils.ByteBufferUtil;
 public class Columns implements Iterable<ColumnDefinition>
 {
     public static final Serializer serializer = new Serializer();
-    public static final Columns NONE = new Columns(new ColumnDefinition[0], 0);
+    public static final Columns NONE = new Columns(BTree.empty(), 0);
+    public static final ColumnDefinition FIRST_COMPLEX = new ColumnDefinition("", "", ColumnIdentifier.getInterned(ByteBufferUtil.EMPTY_BYTE_BUFFER,
UTF8Type.instance),
+                                                                              SetType.getInstance(UTF8Type.instance,
true), null, ColumnDefinition.Kind.REGULAR);
 
-    public final ColumnDefinition[] columns;
-    public final int complexIdx; // Index of the first complex column
+    private final Object[] columns;
+    private final int complexIdx; // Index of the first complex column
 
-    private Columns(ColumnDefinition[] columns, int complexIdx)
+    private Columns(Object[] columns, int complexIdx)
     {
-        assert complexIdx <= columns.length;
+        assert complexIdx <= BTree.size(columns);
         this.columns = columns;
         this.complexIdx = complexIdx;
     }
 
-    private Columns(ColumnDefinition[] columns)
+    private Columns(Object[] columns)
     {
         this(columns, findFirstComplexIdx(columns));
     }
@@ -69,30 +75,28 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public static Columns of(ColumnDefinition c)
     {
-        ColumnDefinition[] columns = new ColumnDefinition[]{ c };
-        return new Columns(columns, c.isComplex() ? 0 : 1);
+        return new Columns(BTree.singleton(c), c.isComplex() ? 0 : 1);
     }
 
     /**
      * Returns a new {@code Columns} object holing the same columns than the provided set.
      *
-     * @param param s the set from which to create the new {@code Columns}.
-     *
+     * @param s the set from which to create the new {@code Columns}.
      * @return the newly created {@code Columns} containing the columns from {@code s}.
      */
     public static Columns from(Set<ColumnDefinition> s)
     {
-        ColumnDefinition[] columns = s.toArray(new ColumnDefinition[s.size()]);
-        Arrays.sort(columns);
-        return new Columns(columns, findFirstComplexIdx(columns));
+        Object[] tree = BTree.<ColumnDefinition>builder(Comparator.naturalOrder()).addAll(s).build();
+        return new Columns(tree, findFirstComplexIdx(tree));
     }
 
-    private static int findFirstComplexIdx(ColumnDefinition[] columns)
+    private static int findFirstComplexIdx(Object[] tree)
     {
-        for (int i = 0; i < columns.length; i++)
-            if (columns[i].isComplex())
-                return i;
-        return columns.length;
+        // have fast path for common no-complex case
+        int size = BTree.size(tree);
+        if (!BTree.isEmpty(tree) && BTree.<ColumnDefinition>findByIndex(tree,
size - 1).isSimple())
+            return size;
+        return BTree.ceilIndex(tree, Comparator.naturalOrder(), FIRST_COMPLEX);
     }
 
     /**
@@ -102,7 +106,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public boolean isEmpty()
     {
-        return columns.length == 0;
+        return BTree.isEmpty(columns);
     }
 
     /**
@@ -122,7 +126,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public int complexColumnCount()
     {
-        return columns.length - complexIdx;
+        return BTree.size(columns) - complexIdx;
     }
 
     /**
@@ -132,7 +136,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public int columnCount()
     {
-        return columns.length;
+        return BTree.size(columns);
     }
 
     /**
@@ -152,7 +156,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public boolean hasComplex()
     {
-        return complexIdx < columns.length;
+        return complexIdx < BTree.size(columns);
     }
 
     /**
@@ -165,7 +169,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public ColumnDefinition getSimple(int i)
     {
-        return columns[i];
+        return BTree.findByIndex(columns, i);
     }
 
     /**
@@ -178,7 +182,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public ColumnDefinition getComplex(int i)
     {
-        return columns[complexIdx + i];
+        return BTree.findByIndex(columns, complexIdx + i);
     }
 
     /**
@@ -186,19 +190,13 @@ public class Columns implements Iterable<ColumnDefinition>
      * the provided column).
      *
      * @param c the simple column for which to return the index of.
-     * @param from the index to start the search from.
      *
      * @return the index for simple column {@code c} if it is contains in this
-     * object (starting from index {@code from}), {@code -1} otherwise.
+     * object
      */
-    public int simpleIdx(ColumnDefinition c, int from)
+    public int simpleIdx(ColumnDefinition c)
     {
-        assert !c.isComplex();
-        for (int i = from; i < complexIdx; i++)
-            // We know we only use "interned" ColumnIdentifier so == is ok.
-            if (columns[i].name == c.name)
-                return i;
-        return -1;
+        return BTree.findIndex(columns, Comparator.naturalOrder(), c);
     }
 
     /**
@@ -206,19 +204,13 @@ public class Columns implements Iterable<ColumnDefinition>
      * the provided column).
      *
      * @param c the complex column for which to return the index of.
-     * @param from the index to start the search from.
      *
      * @return the index for complex column {@code c} if it is contains in this
-     * object (starting from index {@code from}), {@code -1} otherwise.
+     * object
      */
-    public int complexIdx(ColumnDefinition c, int from)
+    public int complexIdx(ColumnDefinition c)
     {
-        assert c.isComplex();
-        for (int i = complexIdx + from; i < columns.length; i++)
-            // We know we only use "interned" ColumnIdentifier so == is ok.
-            if (columns[i].name == c.name)
-                return i - complexIdx;
-        return -1;
+        return BTree.findIndex(columns, Comparator.naturalOrder(), c) - complexIdx;
     }
 
     /**
@@ -230,30 +222,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public boolean contains(ColumnDefinition c)
     {
-        return c.isComplex() ? complexIdx(c, 0) >= 0 : simpleIdx(c, 0) >= 0;
-    }
-
-    /**
-     * Whether or not there is some counter columns within those columns.
-     *
-     * @return whether or not there is some counter columns within those columns.
-     */
-    public boolean hasCounters()
-    {
-        for (int i = 0; i < complexIdx; i++)
-        {
-            if (columns[i].type.isCounter())
-                return true;
-        }
-
-        for (int i = complexIdx; i < columns.length; i++)
-        {
-            // We only support counter in maps because that's all we need for now (and we
need it for the sake of thrift super columns of counter)
-            if (columns[i].type instanceof MapType && (((MapType)columns[i].type).valueComparator().isCounter()))
-                return true;
-        }
-
-        return false;
+        return BTree.findIndex(columns, Comparator.naturalOrder(), c) >= 0;
     }
 
     /**
@@ -273,60 +242,13 @@ public class Columns implements Iterable<ColumnDefinition>
         if (this == NONE)
             return other;
 
-        int i = 0, j = 0;
-        int size = 0;
-        while (i < columns.length && j < other.columns.length)
-        {
-            ++size;
-            int cmp = columns[i].compareTo(other.columns[j]);
-            if (cmp == 0)
-            {
-                ++i;
-                ++j;
-            }
-            else if (cmp < 0)
-            {
-                ++i;
-            }
-            else
-            {
-                ++j;
-            }
-        }
-
-        // If every element was always counted on both array, we have the same
-        // arrays for the first min elements
-        if (i == size && j == size)
-        {
-            // We've exited because of either c1 or c2 (or both). The array that
-            // made us stop is thus a subset of the 2nd one, return that array.
-            return i == columns.length ? other : this;
-        }
+        Object[] tree = BTree.<ColumnDefinition>merge(this.columns, other.columns,
Comparator.naturalOrder());
+        if (tree == this.columns)
+            return this;
+        if (tree == other.columns)
+            return other;
 
-        size += i == columns.length ? other.columns.length - j : columns.length - i;
-        ColumnDefinition[] result = new ColumnDefinition[size];
-        i = 0;
-        j = 0;
-        for (int k = 0; k < size; k++)
-        {
-            int cmp = i >= columns.length ? 1
-                    : (j >= other.columns.length ? -1 : columns[i].compareTo(other.columns[j]));
-            if (cmp == 0)
-            {
-                result[k] = columns[i];
-                ++i;
-                ++j;
-            }
-            else if (cmp < 0)
-            {
-                result[k] = columns[i++];
-            }
-            else
-            {
-                result[k] = other.columns[j++];
-            }
-        }
-        return new Columns(result, findFirstComplexIdx(result));
+        return new Columns(tree, findFirstComplexIdx(tree));
     }
 
     /**
@@ -341,20 +263,10 @@ public class Columns implements Iterable<ColumnDefinition>
         if (other.columns.length > columns.length)
             return false;
 
-        int j = 0;
-        int cmp = 0;
-        for (ColumnDefinition def : other.columns)
-        {
-            while (j < columns.length && (cmp = columns[j].compareTo(def)) <
0)
-                j++;
-
-            if (j >= columns.length || cmp > 0)
+        BTreeSearchIterator<ColumnDefinition, ColumnDefinition> iter = BTree.slice(columns,
Comparator.naturalOrder(), BTree.Dir.ASC);
+        for (ColumnDefinition def : BTree.<ColumnDefinition>iterable(other.columns))
+            if (iter.next(def) == null)
                 return false;
-
-            // cmp == 0, we've found the definition. Ce can bump j once more since
-            // we know we won't need to compare that element again
-            j++;
-        }
         return true;
     }
 
@@ -365,7 +277,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public Iterator<ColumnDefinition> simpleColumns()
     {
-        return new ColumnIterator(0, complexIdx);
+        return BTree.iterator(columns, 0, complexIdx - 1, BTree.Dir.ASC);
     }
 
     /**
@@ -375,7 +287,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public Iterator<ColumnDefinition> complexColumns()
     {
-        return new ColumnIterator(complexIdx, columns.length);
+        return BTree.iterator(columns, complexIdx, BTree.size(columns) - 1, BTree.Dir.ASC);
     }
 
     /**
@@ -385,7 +297,7 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public Iterator<ColumnDefinition> iterator()
     {
-        return Iterators.forArray(columns);
+        return BTree.iterator(columns);
     }
 
     /**
@@ -399,23 +311,8 @@ public class Columns implements Iterable<ColumnDefinition>
     {
         // In wildcard selection, we want to return all columns in alphabetical order,
         // irregarding of whether they are complex or not
-        return new AbstractIterator<ColumnDefinition>()
-        {
-            private int regular;
-            private int complex = complexIdx;
-
-            protected ColumnDefinition computeNext()
-            {
-                if (complex >= columns.length)
-                    return regular >= complexIdx ? endOfData() : columns[regular++];
-                if (regular >= complexIdx)
-                    return columns[complex++];
-
-                return columns[regular].name.compareTo(columns[complex].name) < 0
-                     ? columns[regular++]
-                     : columns[complex++];
-            }
-        };
+        return Iterators.<ColumnDefinition>mergeSorted(ImmutableList.of(simpleColumns(),
complexColumns()),
+                                     (s, c) -> s.name.compareTo(c.name));
     }
 
     /**
@@ -428,15 +325,10 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public Columns without(ColumnDefinition column)
     {
-        int idx = column.isComplex() ? complexIdx(column, 0) : simpleIdx(column, 0);
-        if (idx < 0)
+        if (!contains(column))
             return this;
 
-        int realIdx = column.isComplex() ? complexIdx + idx : idx;
-
-        ColumnDefinition[] newColumns = new ColumnDefinition[columns.length - 1];
-        System.arraycopy(columns, 0, newColumns, 0, realIdx);
-        System.arraycopy(columns, realIdx + 1, newColumns, realIdx, newColumns.length - realIdx);
+        Object[] newColumns = BTree.<ColumnDefinition>transformAndFilter(columns, (c)
-> c.equals(column) ? null : c);
         return new Columns(newColumns);
     }
 
@@ -448,24 +340,8 @@ public class Columns implements Iterable<ColumnDefinition>
      */
     public Predicate<ColumnDefinition> inOrderInclusionTester()
     {
-        return new Predicate<ColumnDefinition>()
-        {
-            private int i = 0;
-
-            public boolean test(ColumnDefinition column)
-            {
-                while (i < columns.length)
-                {
-                    int cmp = column.compareTo(columns[i]);
-                    if (cmp < 0)
-                        return false;
-                    i++;
-                    if (cmp == 0)
-                        return true;
-                }
-                return false;
-            }
-        };
+        SearchIterator<ColumnDefinition, ColumnDefinition> iter = BTree.slice(columns,
Comparator.naturalOrder(), BTree.Dir.ASC);
+        return column -> iter.next(column) != null;
     }
 
     public void digest(MessageDigest digest)
@@ -477,17 +353,19 @@ public class Columns implements Iterable<ColumnDefinition>
     @Override
     public boolean equals(Object other)
     {
+        if (other == this)
+            return true;
         if (!(other instanceof Columns))
             return false;
 
         Columns that = (Columns)other;
-        return this.complexIdx == that.complexIdx && Arrays.equals(this.columns,
that.columns);
+        return this.complexIdx == that.complexIdx && BTree.equals(this.columns, that.columns);
     }
 
     @Override
     public int hashCode()
     {
-        return Objects.hash(complexIdx, Arrays.hashCode(columns));
+        return Objects.hash(complexIdx, BTree.hashCode(columns));
     }
 
     @Override
@@ -503,25 +381,6 @@ public class Columns implements Iterable<ColumnDefinition>
         return sb.toString();
     }
 
-    private class ColumnIterator extends AbstractIterator<ColumnDefinition>
-    {
-        private final int to;
-        private int idx;
-
-        private ColumnIterator(int from, int to)
-        {
-            this.idx = from;
-            this.to = to;
-        }
-
-        protected ColumnDefinition computeNext()
-        {
-            if (idx >= to)
-                return endOfData();
-            return columns[idx++];
-        }
-    }
-
     public static class Serializer
     {
         public void serialize(Columns columns, DataOutputPlus out) throws IOException
@@ -542,7 +401,8 @@ public class Columns implements Iterable<ColumnDefinition>
         public Columns deserialize(DataInputPlus in, CFMetaData metadata) throws IOException
         {
             int length = (int)in.readVInt();
-            ColumnDefinition[] columns = new ColumnDefinition[length];
+            BTree.Builder<ColumnDefinition> builder = BTree.builder(Comparator.naturalOrder());
+            builder.auto(false);
             for (int i = 0; i < length; i++)
             {
                 ByteBuffer name = ByteBufferUtil.readWithVIntLength(in);
@@ -556,9 +416,9 @@ public class Columns implements Iterable<ColumnDefinition>
                     if (column == null)
                         throw new RuntimeException("Unknown column " + UTF8Type.instance.getString(name)
+ " during deserialization");
                 }
-                columns[i] = column;
+                builder.add(column);
             }
-            return new Columns(columns);
+            return new Columns(builder.build());
         }
     }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/ace28c92/src/java/org/apache/cassandra/db/view/MaterializedView.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/view/MaterializedView.java b/src/java/org/apache/cassandra/db/view/MaterializedView.java
index 988bfc5..06c4dc2 100644
--- a/src/java/org/apache/cassandra/db/view/MaterializedView.java
+++ b/src/java/org/apache/cassandra/db/view/MaterializedView.java
@@ -666,7 +666,7 @@ public class MaterializedView
             viewBuilder.addClusteringColumn(ident, properties.getReversableType(ident, column.type));
         }
 
-        for (ColumnDefinition column : baseCf.partitionColumns().regulars.columns)
+        for (ColumnDefinition column : baseCf.partitionColumns().regulars)
         {
             if (column != nonPkTarget && (includeAll || included.contains(column)))
             {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/ace28c92/src/java/org/apache/cassandra/utils/btree/BTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java
index 62942b4..353e7a5 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -669,7 +669,18 @@ public class BTree
 
     public static boolean equals(Object[] a, Object[] b)
     {
-        return Iterators.elementsEqual(iterator(a), iterator(b));
+        return size(a) == size(b) && Iterators.elementsEqual(iterator(a), iterator(b));
+    }
+
+    public static int hashCode(Object[] btree)
+    {
+        // we can't just delegate to Arrays.deepHashCode(),
+        // because two equivalent trees may be represented by differently shaped trees
+        int result = 1;
+        for (Object v : iterable(btree))
+            result = 31 * result + Objects.hashCode(v);
+        return result;
+
     }
 
     /**

http://git-wip-us.apache.org/repos/asf/cassandra/blob/ace28c92/test/unit/org/apache/cassandra/db/ColumnsTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/ColumnsTest.java b/test/unit/org/apache/cassandra/db/ColumnsTest.java
new file mode 100644
index 0000000..5447fcc
--- /dev/null
+++ b/test/unit/org/apache/cassandra/db/ColumnsTest.java
@@ -0,0 +1,244 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements.  See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership.  The ASF licenses this file
+* to you 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 org.apache.cassandra.db;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Predicate;
+
+import com.google.common.collect.Lists;
+
+import org.junit.AfterClass;
+import org.junit.Test;
+
+import junit.framework.Assert;
+import org.apache.cassandra.MockSchema;
+import org.apache.cassandra.config.CFMetaData;
+import org.apache.cassandra.config.ColumnDefinition;
+import org.apache.cassandra.db.marshal.SetType;
+import org.apache.cassandra.db.marshal.UTF8Type;
+import org.apache.cassandra.utils.ByteBufferUtil;
+import org.apache.cassandra.utils.btree.BTreeSet;
+
+public class ColumnsTest
+{
+
+    private static CFMetaData cfMetaData = MockSchema.newCFS().metadata;
+
+    @Test
+    public void testContainsWithoutAndMergeTo()
+    {
+        for (RandomColumns randomColumns : random())
+            testContainsWithoutAndMergeTo(randomColumns.columns, randomColumns.definitions);
+    }
+
+    private void testContainsWithoutAndMergeTo(Columns columns, List<ColumnDefinition>
definitions)
+    {
+        // pick some arbitrary groupings of columns to remove at-once (to avoid factorial
complexity)
+        // whatever is left after each removal, we perform this logic on again, recursively
+        List<List<ColumnDefinition>> removeGroups = shuffleAndGroup(Lists.newArrayList(definitions));
+        for (List<ColumnDefinition> defs : removeGroups)
+        {
+            Columns subset = columns;
+            for (ColumnDefinition def : defs)
+                subset = subset.without(def);
+            Assert.assertEquals(columns.columnCount() - defs.size(), subset.columnCount());
+            List<ColumnDefinition> remainingDefs = Lists.newArrayList(columns);
+            remainingDefs.removeAll(defs);
+
+            // test contents after .without
+            assertContents(subset, remainingDefs);
+
+            // test .contains
+            assertSubset(columns, subset);
+
+            // test .mergeTo
+            Columns otherSubset = columns;
+            for (ColumnDefinition def : remainingDefs)
+            {
+                otherSubset = otherSubset.without(def);
+                assertContents(otherSubset.mergeTo(subset), definitions);
+            }
+
+            testContainsWithoutAndMergeTo(subset, remainingDefs);
+        }
+    }
+
+    private void assertSubset(Columns superset, Columns subset)
+    {
+        Assert.assertTrue(superset.contains(superset));
+        Assert.assertTrue(superset.contains(subset));
+        Assert.assertFalse(subset.contains(superset));
+    }
+
+    private static void assertContents(Columns columns, List<ColumnDefinition> defs)
+    {
+        Assert.assertEquals(defs, Lists.newArrayList(columns));
+        boolean hasSimple = false, hasComplex = false;
+        int firstComplexIdx = 0;
+        int i = 0;
+        Iterator<ColumnDefinition> simple = columns.simpleColumns();
+        Iterator<ColumnDefinition> complex = columns.complexColumns();
+        Iterator<ColumnDefinition> all = columns.iterator();
+        Predicate<ColumnDefinition> predicate = columns.inOrderInclusionTester();
+        for (ColumnDefinition def : defs)
+        {
+            Assert.assertEquals(def, all.next());
+            Assert.assertTrue(columns.contains(def));
+            Assert.assertTrue(predicate.test(def));
+            if (def.isSimple())
+            {
+                hasSimple = true;
+                Assert.assertEquals(i, columns.simpleIdx(def));
+                Assert.assertEquals(def, simple.next());
+                ++firstComplexIdx;
+            }
+            else
+            {
+                Assert.assertFalse(simple.hasNext());
+                hasComplex = true;
+                Assert.assertEquals(i - firstComplexIdx, columns.complexIdx(def));
+                Assert.assertEquals(def, complex.next());
+            }
+            i++;
+        }
+        Assert.assertEquals(defs.isEmpty(), columns.isEmpty());
+        Assert.assertFalse(simple.hasNext());
+        Assert.assertFalse(complex.hasNext());
+        Assert.assertFalse(all.hasNext());
+        Assert.assertEquals(hasSimple, columns.hasSimple());
+        Assert.assertEquals(hasComplex, columns.hasComplex());
+    }
+
+    private static <V> List<List<V>> shuffleAndGroup(List<V> list)
+    {
+        // first shuffle
+        ThreadLocalRandom random = ThreadLocalRandom.current();
+        for (int i = 0 ; i < list.size() - 1 ; i++)
+        {
+            int j = random.nextInt(i, list.size());
+            V v = list.get(i);
+            list.set(i, list.get(j));
+            list.set(j, v);
+        }
+
+        // then group
+        List<List<V>> result = new ArrayList<>();
+        for (int i = 0 ; i < list.size() ;)
+        {
+            List<V> group = new ArrayList<>();
+            int maxCount = list.size() - i;
+            int count = maxCount <= 2 ? maxCount : random.nextInt(1, maxCount);
+            for (int j = 0 ; j < count ; j++)
+                group.add(list.get(i + j));
+            i += count;
+            result.add(group);
+        }
+        return result;
+    }
+
+    @AfterClass
+    public static void cleanup()
+    {
+        MockSchema.cleanup();
+    }
+
+    private static class RandomColumns
+    {
+        final Columns columns;
+        final List<ColumnDefinition> definitions;
+
+        private RandomColumns(List<ColumnDefinition> definitions)
+        {
+            this.columns = Columns.from(BTreeSet.of(definitions));
+            this.definitions = definitions;
+        }
+    }
+
+    private static List<RandomColumns> random()
+    {
+        List<RandomColumns> random = new ArrayList<>();
+        for (int i = 1 ; i <= 3 ; i++)
+        {
+            random.add(random(i, i - 1, i - 1, i - 1));
+            random.add(random(i - 1, i, i - 1, i - 1));
+            random.add(random(i - 1, i - 1, i, i - 1));
+            random.add(random(i - 1, i - 1, i - 1, i));
+        }
+        return random;
+    }
+
+    private static RandomColumns random(int pkCount, int clCount, int regularCount, int complexCount)
+    {
+        List<Character> chars = new ArrayList<>();
+        for (char c = 'a' ; c <= 'z' ; c++)
+            chars.add(c);
+
+        List<ColumnDefinition> result = new ArrayList<>();
+        addPartition(select(chars, pkCount), result);
+        addClustering(select(chars, clCount), result);
+        addRegular(select(chars, regularCount), result);
+        addComplex(select(chars, complexCount), result);
+        Collections.sort(result);
+        return new RandomColumns(result);
+    }
+
+    private static List<Character> select(List<Character> chars, int count)
+    {
+        List<Character> result = new ArrayList<>();
+        ThreadLocalRandom random = ThreadLocalRandom.current();
+        for (int i = 0 ; i < count ; i++)
+        {
+            int v = random.nextInt(chars.size());
+            result.add(chars.get(v));
+            chars.remove(v);
+        }
+        return result;
+    }
+
+    private static void addPartition(List<Character> chars, List<ColumnDefinition>
results)
+    {
+        addSimple(ColumnDefinition.Kind.PARTITION_KEY, chars, results);
+    }
+
+    private static void addClustering(List<Character> chars, List<ColumnDefinition>
results)
+    {
+        addSimple(ColumnDefinition.Kind.CLUSTERING, chars, results);
+    }
+
+    private static void addRegular(List<Character> chars, List<ColumnDefinition>
results)
+    {
+        addSimple(ColumnDefinition.Kind.REGULAR, chars, results);
+    }
+
+    private static void addSimple(ColumnDefinition.Kind kind, List<Character> chars,
List<ColumnDefinition> results)
+    {
+        for (Character c : chars)
+            results.add(new ColumnDefinition(cfMetaData, ByteBufferUtil.bytes(c.toString()),
UTF8Type.instance, null, kind));
+    }
+
+    private static void addComplex(List<Character> chars, List<ColumnDefinition>
results)
+    {
+        for (Character c : chars)
+            results.add(new ColumnDefinition(cfMetaData, ByteBufferUtil.bytes(c.toString()),
SetType.getInstance(UTF8Type.instance, true), null, ColumnDefinition.Kind.REGULAR));
+    }
+}


Mime
View raw message