You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by be...@apache.org on 2015/08/12 23:53:44 UTC
[5/9] cassandra git commit: Remove ArrayBackedPartition and hierarchy
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);