Repository: cassandra Updated Branches: refs/heads/cassandra-3.0 a186ac6ee -> e51f83b60 refs/heads/trunk 095de832d -> bfd2e0820
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);
