com.bigdata.btree

Class TestSplitJoinThreeLevels

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

junit.framework.TestCase2

com.bigdata.btree.AbstractBTreeTestCase

com.bigdata.btree.TestSplitJoinThreeLevels

All Implemented Interfaces:

junit.framework.Test

public class TestSplitJoinThreeLevels
extends AbstractBTreeTestCase

Test suite using AbstractBTree.insert(Object, Object) to split a tree to height two (2) (three levels) and then using AbstractBTree.remove(Object) to reduce the tree back to a single, empty root leaf. This test suite is focused on m := 3 since we are capable of exercising all split() and join() code paths with that branching factor.

Note: This also tests the AbstractNode.isLeftMostNode() and AbstractNode.isRightMostNode() methods. In order to test those methods as applied to track the #of head splits and tail splits we need a btree with at least 2 levels of nodes above a layer of leaves. This is because the methods are tested on a leaf, which checks its parent, which, really, needs to test a non-root parent before we can say that this is working as it should.

Version:

$Id$

Author:

Bryan Thompson

See Also:

for the examples used in this test suite.

Nested Class Summary

Nested classes/interfaces inherited from class junit.framework.TestCase2

TestCase2.MyProperties, TestCase2.RandomType

Field Summary

Fields inherited from class com.bigdata.btree.AbstractBTreeTestCase

keyBuilder, log, r

Fields inherited from class junit.framework.TestCase2

_randomType

Constructor Summary

Constructors

Constructor and Description
TestSplitJoinThreeLevels()
TestSplitJoinThreeLevels(String name)

Method Summary

Methods

Modifier and Type	Method and Description
void	test_removeOrder3a() Test ability to split and join a tree of order m == 3 driven by the insertion and then the removal of a known sequence of keys.
void	test_removeOrder3b() Variant of test_removeOrder3a() that excercises some different code paths while removing keys by choosing a different order in which to remove some keys.
void	test_removeOrder3c() Variant of test_removeOrder3a() that is focused on testing the redistribution of keys among the left and right siblings of a node when that node underflows during a deletion operation.

Methods inherited from class com.bigdata.btree.AbstractBTreeTestCase

assertChildKeys, assertEntryCounts, assertKeys, assertKeys, assertKeys, assertSameAbstractNodeData, assertSameBTree, assertSameEntryIterator, assertSameEntryIterator, assertSameIterator, assertSameIterator, assertSameLeaf, assertSameLeafData, assertSameNode, assertSameNodeData, assertSameNodeOrLeaf, assertSameRaba, assertValues, assertValues, doEntryIteratorTest, doInsertKeySequenceTest, doInsertLookupRemoveStressTest, doInsertRandomKeySequenceTest, doInsertRandomKeySequenceTest, doInsertRandomSparseKeySequenceTest, doKnownKeySequenceTest, doRandomIndexOfTest, doRandomKeyInsertTest, doRandomLookupTest, doRemoveStructureStressTest, doSplitTest, doSplitWithDecreasingKeySequence, doSplitWithIncreasingKeySequence, doSplitWithRandomDenseKeySequence, getBTree, getBTree, getKeysAndValues, getRandomKeys, getRandomKeyValues, i2k, nextLong, useRawRecords

Methods inherited from class junit.framework.TestCase2

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEqualsWithinUlps, assertSameArray, assertSameArray, assertSameBigDecimal, assertSameBigDecimal, assertSameBigInteger, assertSameBigInteger, assertSameIterator, assertSameIterator, assertSameIteratorAnyOrder, assertSameIteratorAnyOrder, assertSameValue, assertSameValue, assertZeroUlps, assertZeroUlps, fail, getInnerCause, getNormalInt, getProjectBuildPath, getProperties, getRandomObject, getRandomObject, getRandomOrder, getRandomString, getTestInputStream, getTestResource, getTestResource, getUlps, getUlps, isDEBUG, isDEBUG, isINFO, isINFO, isInnerCause, logProperties

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TestSplitJoinThreeLevels

public TestSplitJoinThreeLevels()

TestSplitJoinThreeLevels

public TestSplitJoinThreeLevels(String name)

Parameters:

name -

Method Detail

test_removeOrder3a

public void test_removeOrder3a()

Test ability to split and join a tree of order m == 3 driven by the insertion and then the removal of a known sequence of keys. This test checks the state of the tree after each operation against the expected postconditions for that operation. In particular, testing at m == 3 helps to check for fenceposts in the split/join logic. Note: a branching factor of three (3) is equivalent to a 2-3 tree, where the minimum #of children (for a node) or values (for a leaf) is two (2) and the maximum #of children (for a node) or values (for a leaf) is three (3). This makes it very easy to provoke splits and joins. There is another version of this test that builds the same tree but uses a different sequence of keys during removal. This provokes some code paths in Node.merge(AbstractNode, boolean) and Node.redistributeKeys(AbstractNode, boolean) that are not exercised by this test.

See Also:

test_removeOrder3a()

test_removeOrder3b

public void test_removeOrder3b()

Variant of test_removeOrder3a() that excercises some different code paths while removing keys by choosing a different order in which to remove some keys. Both tests build the same initial tree. However, this tests begins by removing a key (7) from the right edge of the tree while the other test beings by removing a key (1) from the left edge of the tree.

test_removeOrder3c

public void test_removeOrder3c()

Variant of test_removeOrder3a() that is focused on testing the redistribution of keys among the left and right siblings of a node when that node underflows during a deletion operation.