cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bened...@apache.org
Subject [5/9] cassandra git commit: Remove ArrayBackedPartition and hierarchy
Date Wed, 12 Aug 2015 21:53:44 GMT
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/PartitionTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/PartitionTest.java b/test/unit/org/apache/cassandra/db/PartitionTest.java
index e35e996..f651093 100644
--- a/test/unit/org/apache/cassandra/db/PartitionTest.java
+++ b/test/unit/org/apache/cassandra/db/PartitionTest.java
@@ -73,7 +73,7 @@ public class PartitionTest
                                  .add("val", "val1")
                                  .buildUpdate();
 
-        ArrayBackedCachedPartition partition = ArrayBackedCachedPartition.create(update.unfilteredIterator(),
FBUtilities.nowInSeconds());
+        CachedBTreePartition partition = CachedBTreePartition.create(update.unfilteredIterator(),
FBUtilities.nowInSeconds());
 
         DataOutputBuffer bufOut = new DataOutputBuffer();
         CachedPartition.cacheSerializer.serialize(partition, bufOut);
@@ -98,7 +98,7 @@ public class PartitionTest
 
         PartitionUpdate update = builder.buildUpdate();
 
-        ArrayBackedCachedPartition partition = ArrayBackedCachedPartition.create(update.unfilteredIterator(),
FBUtilities.nowInSeconds());
+        CachedBTreePartition partition = CachedBTreePartition.create(update.unfilteredIterator(),
FBUtilities.nowInSeconds());
 
         DataOutputBuffer bufOut = new DataOutputBuffer();
         CachedPartition.cacheSerializer.serialize(partition, bufOut);
@@ -125,8 +125,8 @@ public class PartitionTest
 
         new RowUpdateBuilder(cfs.metadata, 5, "key2").clustering("c").add("val", "val2").build().applyUnsafe();
 
-        ArrayBackedPartition p1 = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, "key1").build());
-        ArrayBackedPartition p2 = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, "key2").build());
+        ImmutableBTreePartition p1 = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, "key1").build());
+        ImmutableBTreePartition p2 = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, "key2").build());
 
         MessageDigest digest1 = MessageDigest.getInstance("MD5");
         MessageDigest digest2 = MessageDigest.getInstance("MD5");
@@ -165,7 +165,7 @@ public class PartitionTest
         builder.build().applyUnsafe();
 
         RowUpdateBuilder.deleteRowAt(cfs.metadata, 10L, localDeletionTime, "key1", "c").applyUnsafe();
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, "key1").build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
"key1").build());
         EncodingStats stats = partition.stats();
         assertEquals(localDeletionTime, stats.minLocalDeletionTime);
     }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java b/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
index c20fa46..1538665 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
@@ -144,7 +144,7 @@ public class RangeTombstoneTest
 
         new RowUpdateBuilder(cfs.metadata, 2, key).addRangeTombstone(15, 20).build().applyUnsafe();
 
-        ArrayBackedPartition partition;
+        ImmutableBTreePartition partition;
 
         partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, key).fromIncl(11).toIncl(14).build());
         Collection<RangeTombstone> rt = rangeTombstones(partition);
@@ -215,7 +215,7 @@ public class RangeTombstoneTest
         assertEquals(2, rt.size());
     }
 
-    private Collection<RangeTombstone> rangeTombstones(ArrayBackedPartition partition)
+    private Collection<RangeTombstone> rangeTombstones(ImmutableBTreePartition partition)
     {
         List<RangeTombstone> tombstones = new ArrayList<RangeTombstone>();
         Iterators.addAll(tombstones, partition.deletionInfo().rangeIterator(false));

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/RowIndexEntryTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RowIndexEntryTest.java b/test/unit/org/apache/cassandra/db/RowIndexEntryTest.java
index 1d91069..e4ae9ac 100644
--- a/test/unit/org/apache/cassandra/db/RowIndexEntryTest.java
+++ b/test/unit/org/apache/cassandra/db/RowIndexEntryTest.java
@@ -56,7 +56,7 @@ public class RowIndexEntryTest extends CQLTester
             execute("INSERT INTO %s (a, b, c) VALUES (?, ?, ?)", 0, "" + i, i);
 
         buffer = new DataOutputBuffer();
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs).build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs).build());
 
         File tempFile = File.createTempFile("row_index_entry_test", null);
         tempFile.deleteOnExit();

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/RowTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RowTest.java b/test/unit/org/apache/cassandra/db/RowTest.java
index 373cf6a..3aaf21f 100644
--- a/test/unit/org/apache/cassandra/db/RowTest.java
+++ b/test/unit/org/apache/cassandra/db/RowTest.java
@@ -127,7 +127,7 @@ public class RowTest
         ColumnDefinition defA = cfm.getColumnDefinition(new ColumnIdentifier("a", true));
         ColumnDefinition defB = cfm.getColumnDefinition(new ColumnIdentifier("b", true));
 
-        Row.Builder builder = BTreeBackedRow.unsortedBuilder(cfm.partitionColumns().regulars,
nowInSeconds);
+        Row.Builder builder = BTreeRow.unsortedBuilder(cfm.partitionColumns().regulars, nowInSeconds);
         builder.newRow(cfm.comparator.make("c1"));
         writeSimpleCellValue(builder, cfm, defA, "a1", 0);
         writeSimpleCellValue(builder, cfm, defA, "a2", 1);
@@ -152,7 +152,7 @@ public class RowTest
 
         Cell cell = BufferCell.expiring(def, 0, ttl, nowInSeconds, ((AbstractType) def.cellValueType()).decompose("a1"));
 
-        PartitionUpdate update = PartitionUpdate.singleRowUpdate(cfm, dk, BTreeBackedRow.singleCellRow(cfm.comparator.make("c1"),
cell));
+        PartitionUpdate update = PartitionUpdate.singleRowUpdate(cfm, dk, BTreeRow.singleCellRow(cfm.comparator.make("c1"),
cell));
         new Mutation(update).applyUnsafe();
 
         // when we read with a nowInSeconds before the cell has expired,

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/compaction/CompactionsPurgeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/compaction/CompactionsPurgeTest.java b/test/unit/org/apache/cassandra/db/compaction/CompactionsPurgeTest.java
index 22f3c6b..26d53ed 100644
--- a/test/unit/org/apache/cassandra/db/compaction/CompactionsPurgeTest.java
+++ b/test/unit/org/apache/cassandra/db/compaction/CompactionsPurgeTest.java
@@ -30,8 +30,8 @@ import org.apache.cassandra.config.CFMetaData;
 import org.apache.cassandra.cql3.QueryProcessor;
 import org.apache.cassandra.cql3.UntypedResultSet;
 import org.apache.cassandra.db.*;
+import org.apache.cassandra.db.partitions.ImmutableBTreePartition;
 import org.apache.cassandra.db.rows.Row;
-import org.apache.cassandra.db.partitions.ArrayBackedPartition;
 import org.apache.cassandra.db.partitions.PartitionUpdate;
 import org.apache.cassandra.exceptions.ConfigurationException;
 import org.apache.cassandra.io.sstable.format.SSTableReader;
@@ -118,7 +118,7 @@ public class CompactionsPurgeTest
         FBUtilities.waitOnFutures(CompactionManager.instance.submitMaximal(cfs, Integer.MAX_VALUE,
false));
         cfs.invalidateCachedPartition(dk(key));
 
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, key).build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
         assertEquals(1, partition.rowCount());
     }
 
@@ -175,7 +175,7 @@ public class CompactionsPurgeTest
 
         // verify that minor compaction still GC when key is present
         // in a non-compacted sstable but the timestamp ensures we won't miss anything
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, key1).build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key1).build());
         assertEquals(1, partition.rowCount());
     }
 
@@ -219,7 +219,7 @@ public class CompactionsPurgeTest
 
         // We should have both the c1 and c2 tombstones still. Since the min timestamp in
the c2 tombstone
         // sstable is older than the c1 tombstone, it is invalid to throw out the c1 tombstone.
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, key3).build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key3).build());
         assertEquals(2, partition.rowCount());
         for (Row row : partition)
             assertFalse(row.hasLiveData(FBUtilities.nowInSeconds()));
@@ -327,7 +327,7 @@ public class CompactionsPurgeTest
         rm.add(PartitionUpdate.fullPartitionDelete(cfs.metadata, dk(key), 4, FBUtilities.nowInSeconds()));
         rm.applyUnsafe();
 
-        ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs, key).build());
+        ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
         assertFalse(partition.partitionLevelDeletion().isLive());
 
         // flush and major compact (with tombstone purging)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/marshal/CompositeTypeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/marshal/CompositeTypeTest.java b/test/unit/org/apache/cassandra/db/marshal/CompositeTypeTest.java
index 3454bf1..cc66e71 100644
--- a/test/unit/org/apache/cassandra/db/marshal/CompositeTypeTest.java
+++ b/test/unit/org/apache/cassandra/db/marshal/CompositeTypeTest.java
@@ -33,7 +33,7 @@ import org.apache.cassandra.config.ColumnDefinition;
 import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.rows.Cell;
 import org.apache.cassandra.db.rows.Row;
-import org.apache.cassandra.db.partitions.ArrayBackedPartition;
+import org.apache.cassandra.db.partitions.ImmutableBTreePartition;
 import org.apache.cassandra.exceptions.ConfigurationException;
 import org.apache.cassandra.exceptions.SyntaxException;
 import org.apache.cassandra.schema.KeyspaceParams;
@@ -197,7 +197,7 @@ public class CompositeTypeTest
 
         ColumnDefinition cdef = cfs.metadata.getColumnDefinition(ByteBufferUtil.bytes("val"));
 
-        ArrayBackedPartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
+        ImmutableBTreePartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
         Iterator<Row> iter = readPartition.iterator();
 
         compareValues(iter.next().getCell(cdef), "cname1");

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/marshal/DynamicCompositeTypeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/marshal/DynamicCompositeTypeTest.java b/test/unit/org/apache/cassandra/db/marshal/DynamicCompositeTypeTest.java
index 1fc3f2c..0a3c39c 100644
--- a/test/unit/org/apache/cassandra/db/marshal/DynamicCompositeTypeTest.java
+++ b/test/unit/org/apache/cassandra/db/marshal/DynamicCompositeTypeTest.java
@@ -35,7 +35,7 @@ import org.apache.cassandra.config.ColumnDefinition;
 import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.rows.Cell;
 import org.apache.cassandra.db.rows.Row;
-import org.apache.cassandra.db.partitions.ArrayBackedPartition;
+import org.apache.cassandra.db.partitions.ImmutableBTreePartition;
 import org.apache.cassandra.exceptions.ConfigurationException;
 import org.apache.cassandra.schema.KeyspaceParams;
 import org.apache.cassandra.serializers.MarshalException;
@@ -201,7 +201,7 @@ public class DynamicCompositeTypeTest
 
         ColumnDefinition cdef = cfs.metadata.getColumnDefinition(ByteBufferUtil.bytes("val"));
 
-        ArrayBackedPartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
+        ImmutableBTreePartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
         Iterator<Row> iter = readPartition.iterator();
 
         compareValues(iter.next().getCell(cdef), "cname1");
@@ -238,7 +238,7 @@ public class DynamicCompositeTypeTest
 
         ColumnDefinition cdef = cfs.metadata.getColumnDefinition(ByteBufferUtil.bytes("val"));
 
-        ArrayBackedPartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
+        ImmutableBTreePartition readPartition = Util.getOnlyPartitionUnfiltered(Util.cmd(cfs,
key).build());
         Iterator<Row> iter = readPartition.iterator();
 
         compareValues(iter.next().getCell(cdef), "cname5");

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/rows/RowAndDeletionMergeIteratorTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/rows/RowAndDeletionMergeIteratorTest.java b/test/unit/org/apache/cassandra/db/rows/RowAndDeletionMergeIteratorTest.java
index 84bbc57..98ad2bc 100644
--- a/test/unit/org/apache/cassandra/db/rows/RowAndDeletionMergeIteratorTest.java
+++ b/test/unit/org/apache/cassandra/db/rows/RowAndDeletionMergeIteratorTest.java
@@ -380,7 +380,7 @@ public class RowAndDeletionMergeIteratorTest
 
     private void addRow(PartitionUpdate update, int col1, int a)
     {
-        update.add(BTreeBackedRow.singleCellRow(update.metadata().comparator.make(col1),
makeCell(cfm, defA, a, 0)));
+        update.add(BTreeRow.singleCellRow(update.metadata().comparator.make(col1), makeCell(cfm,
defA, a, 0)));
     }
 
     private Cell makeCell(CFMetaData cfm, ColumnDefinition columnDefinition, int value, long
timestamp)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/db/rows/UnfilteredRowIteratorsMergeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/rows/UnfilteredRowIteratorsMergeTest.java b/test/unit/org/apache/cassandra/db/rows/UnfilteredRowIteratorsMergeTest.java
index c16365a..08b9b8e 100644
--- a/test/unit/org/apache/cassandra/db/rows/UnfilteredRowIteratorsMergeTest.java
+++ b/test/unit/org/apache/cassandra/db/rows/UnfilteredRowIteratorsMergeTest.java
@@ -371,7 +371,7 @@ public class UnfilteredRowIteratorsMergeTest
     {
         final Clustering clustering = clusteringFor(pos);
         final LivenessInfo live = LivenessInfo.create(metadata, timeGenerator.apply(pos),
nowInSec);
-        return BTreeBackedRow.noCellLiveRow(clustering, live);
+        return BTreeRow.noCellLiveRow(clustering, live);
     }
 
     private void dumpList(List<Unfiltered> list)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/io/sstable/SSTableRewriterTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/io/sstable/SSTableRewriterTest.java b/test/unit/org/apache/cassandra/io/sstable/SSTableRewriterTest.java
index f8b8fa7..fd801ad 100644
--- a/test/unit/org/apache/cassandra/io/sstable/SSTableRewriterTest.java
+++ b/test/unit/org/apache/cassandra/io/sstable/SSTableRewriterTest.java
@@ -51,7 +51,7 @@ import org.apache.cassandra.db.compaction.CompactionController;
 import org.apache.cassandra.db.compaction.CompactionIterator;
 import org.apache.cassandra.db.compaction.OperationType;
 import org.apache.cassandra.db.compaction.SSTableSplitter;
-import org.apache.cassandra.db.partitions.ArrayBackedPartition;
+import org.apache.cassandra.db.partitions.ImmutableBTreePartition;
 import org.apache.cassandra.dht.Range;
 import org.apache.cassandra.dht.Token;
 import org.apache.cassandra.db.lifecycle.SSTableSet;
@@ -915,7 +915,7 @@ public class SSTableRewriterTest extends SchemaLoader
         for (int i = 0; i < 100; i++)
         {
             DecoratedKey key = Util.dk(Integer.toString(i));
-            ArrayBackedPartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(ks.getColumnFamilyStore(CF),
key).build());
+            ImmutableBTreePartition partition = Util.getOnlyPartitionUnfiltered(Util.cmd(ks.getColumnFamilyStore(CF),
key).build());
             assertTrue(partition != null && partition.rowCount() > 0);
         }
     }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/streaming/StreamingTransferTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/streaming/StreamingTransferTest.java b/test/unit/org/apache/cassandra/streaming/StreamingTransferTest.java
index 85090dc..f21a89d 100644
--- a/test/unit/org/apache/cassandra/streaming/StreamingTransferTest.java
+++ b/test/unit/org/apache/cassandra/streaming/StreamingTransferTest.java
@@ -189,7 +189,7 @@ public class StreamingTransferTest
         assertEquals(1, cfs.getLiveSSTables().size());
 
         // and that the index and filter were properly recovered
-        List<ArrayBackedPartition> partitions = Util.getAllUnfiltered(Util.cmd(cfs).build());
+        List<ImmutableBTreePartition> partitions = Util.getAllUnfiltered(Util.cmd(cfs).build());
         assertEquals(offs.length, partitions.size());
         for (int i = 0; i < offs.length; i++)
         {
@@ -197,7 +197,7 @@ public class StreamingTransferTest
             String col = "col" + offs[i];
 
             assert !Util.getAll(Util.cmd(cfs, key).build()).isEmpty();
-            ArrayBackedPartition partition = partitions.get(i);
+            ImmutableBTreePartition partition = partitions.get(i);
             assert ByteBufferUtil.compareUnsigned(partition.partitionKey().getKey(), ByteBufferUtil.bytes(key))
== 0;
             assert ByteBufferUtil.compareUnsigned(partition.iterator().next().clustering().get(0),
ByteBufferUtil.bytes(col)) == 0;
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/triggers/TriggerExecutorTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/triggers/TriggerExecutorTest.java b/test/unit/org/apache/cassandra/triggers/TriggerExecutorTest.java
index 316a23c..09a337a 100644
--- a/test/unit/org/apache/cassandra/triggers/TriggerExecutorTest.java
+++ b/test/unit/org/apache/cassandra/triggers/TriggerExecutorTest.java
@@ -268,7 +268,7 @@ public class TriggerExecutorTest
 
     private static PartitionUpdate makeCf(CFMetaData metadata, String key, String columnValue1,
String columnValue2)
     {
-        Row.Builder builder = BTreeBackedRow.unsortedBuilder(metadata.partitionColumns().regulars,
FBUtilities.nowInSeconds());
+        Row.Builder builder = BTreeRow.unsortedBuilder(metadata.partitionColumns().regulars,
FBUtilities.nowInSeconds());
         builder.newRow(Clustering.EMPTY);
         long ts = FBUtilities.timestampMicros();
         if (columnValue1 != null)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e51f83b6/test/unit/org/apache/cassandra/utils/BTreeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/utils/BTreeTest.java b/test/unit/org/apache/cassandra/utils/BTreeTest.java
index ec4c359..ffd7315 100644
--- a/test/unit/org/apache/cassandra/utils/BTreeTest.java
+++ b/test/unit/org/apache/cassandra/utils/BTreeTest.java
@@ -194,58 +194,121 @@ public class BTreeTest
     }
 
     /**
-     * Tests that the apply method of the <code>UpdateFunction</code> is only
called once per value with each build call.
+     * Tests that the apply method of the <code>QuickResolver</code> is called
exactly once per duplicate value
      */
     @Test
-    public void testBuilder_Resolver()
+    public void testBuilder_QuickResolver()
+    {
+        // for numbers x in 1..N, we repeat x x times, and resolve values to their sum,
+        // so that the resulting tree is of square numbers
+        BTree.Builder.QuickResolver<Accumulator> resolver = (a, b) -> new Accumulator(a.base,
a.sum + b.sum);
+
+        for (int count = 0 ; count < 10 ; count ++)
+        {
+            BTree.Builder<Accumulator> builder;
+            // first check we produce the right output for sorted input
+            List<Accumulator> sorted = resolverInput(count, false);
+            builder = BTree.builder(Comparator.naturalOrder());
+            builder.setQuickResolver(resolver);
+            for (Accumulator i : sorted)
+                builder.add(i);
+            // for sorted input, check non-resolve path works before checking resolution
path
+            checkResolverOutput(count, builder.build(), BTree.Dir.ASC);
+            builder.reuse();
+            for (int i = 0 ; i < 10 ; i++)
+            {
+                // now do a few runs of randomized inputs
+                for (Accumulator j : resolverInput(count, true))
+                    builder.add(j);
+                checkResolverOutput(count, builder.build(), BTree.Dir.ASC);
+                builder.reuse();
+            }
+            for (List<Accumulator> add : splitResolverInput(count))
+            {
+                if (ThreadLocalRandom.current().nextBoolean())
+                    builder.addAll(add);
+                else
+                    builder.addAll(new TreeSet<>(add));
+            }
+            checkResolverOutput(count, builder.build(), BTree.Dir.ASC);
+            builder.reuse();
+        }
+    }
+
+    private static class Accumulator extends Number implements Comparable<Accumulator>
+    {
+        final int base;
+        final int sum;
+        private Accumulator(int base, int sum)
+        {
+            this.base = base;
+            this.sum = sum;
+        }
+
+        public int compareTo(Accumulator that) { return Integer.compare(base, that.base);
}
+        public int intValue() { return sum; }
+        public long longValue() { return sum; }
+        public float floatValue() { return sum; }
+        public double doubleValue() { return sum; }
+    }
+
+    /**
+     * Tests that the apply method of the <code>Resolver</code> is called exactly
once per unique value
+     */
+    @Test
+    public void testBuilder_ResolverAndReverse()
     {
         // for numbers x in 1..N, we repeat x x times, and resolve values to their sum,
         // so that the resulting tree is of square numbers
         BTree.Builder.Resolver resolver = (array, lb, ub) -> {
             int sum = 0;
             for (int i = lb ; i < ub ; i++)
-                sum += (Integer) array[i];
-            return sum;
+                sum += ((Accumulator) array[i]).sum;
+            return new Accumulator(((Accumulator) array[lb]).base, sum);
         };
 
         for (int count = 0 ; count < 10 ; count ++)
         {
-            BTree.Builder<Integer> builder;
+            BTree.Builder<Accumulator> builder;
             // first check we produce the right output for sorted input
-            List<Integer> sorted = resolverInput(count, false);
+            List<Accumulator> sorted = resolverInput(count, false);
             builder = BTree.builder(Comparator.naturalOrder());
             builder.auto(false);
-            for (Integer i : sorted)
+            for (Accumulator i : sorted)
                 builder.add(i);
             // for sorted input, check non-resolve path works before checking resolution
path
             Assert.assertTrue(Iterables.elementsEqual(sorted, BTree.iterable(builder.build())));
-            checkResolverOutput(count, builder.resolve(resolver).build());
+            checkResolverOutput(count, builder.resolve(resolver).build(), BTree.Dir.ASC);
             builder = BTree.builder(Comparator.naturalOrder());
             builder.auto(false);
             for (int i = 0 ; i < 10 ; i++)
             {
                 // now do a few runs of randomized inputs
-                for (Integer j : resolverInput(count, true))
+                for (Accumulator j : resolverInput(count, true))
                     builder.add(j);
-                checkResolverOutput(count, builder.sort().resolve(resolver).build());
+                checkResolverOutput(count, builder.sort().resolve(resolver).build(), BTree.Dir.ASC);
+                builder.reuse();
+                for (Accumulator j : resolverInput(count, true))
+                    builder.add(j);
+                checkResolverOutput(count, builder.sort().reverse().resolve(resolver).build(),
BTree.Dir.DESC);
                 builder.reuse();
             }
         }
     }
 
-    private static List<Integer> resolverInput(int count, boolean shuffled)
+    private static List<Accumulator> resolverInput(int count, boolean shuffled)
     {
-        List<Integer> result = new ArrayList<>();
+        List<Accumulator> result = new ArrayList<>();
         for (int i = 1 ; i <= count ; i++)
             for (int j = 0 ; j < i ; j++)
-                result.add(i);
+                result.add(new Accumulator(i, i));
         if (shuffled)
         {
             ThreadLocalRandom random = ThreadLocalRandom.current();
             for (int i = 0 ; i < result.size() ; i++)
             {
                 int swapWith = random.nextInt(i, result.size());
-                Integer t = result.get(swapWith);
+                Accumulator t = result.get(swapWith);
                 result.set(swapWith, result.get(i));
                 result.set(i, t);
             }
@@ -253,12 +316,33 @@ public class BTreeTest
         return result;
     }
 
-    private static void checkResolverOutput(int count, Object[] btree)
+    private static List<List<Accumulator>> splitResolverInput(int count)
+    {
+        List<Accumulator> all = resolverInput(count, false);
+        List<List<Accumulator>> result = new ArrayList<>();
+        while (!all.isEmpty())
+        {
+            List<Accumulator> is = new ArrayList<>();
+            int prev = -1;
+            for (Accumulator i : new ArrayList<>(all))
+            {
+                if (i.base == prev)
+                    continue;
+                is.add(i);
+                all.remove(i);
+                prev = i.base;
+            }
+            result.add(is);
+        }
+        return result;
+    }
+
+    private static void checkResolverOutput(int count, Object[] btree, BTree.Dir dir)
     {
         int i = 1;
-        for (Integer current : BTree.<Integer>iterable(btree))
+        for (Accumulator current : BTree.<Accumulator>iterable(btree, dir))
         {
-            Assert.assertEquals(i * i, current.intValue());
+            Assert.assertEquals(i * i, current.sum);
             i++;
         }
         Assert.assertEquals(i, count + 1);


Mime
View raw message