/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 2002-2005
*      Sleepycat Software.  All rights reserved.
*
* $Id: TreeTest.java,v 1.79 2004/12/22 14:11:46 linda Exp $
*/

package com.sleepycat.je.tree;

import java.io.IOException;

import com.sleepycat.je.BtreeStats;
import com.sleepycat.je.DatabaseException;
import com.sleepycat.je.DatabaseStats;
import com.sleepycat.je.DbInternal;
import com.sleepycat.je.VerifyConfig;
import com.sleepycat.je.dbi.NullCursor;
import com.sleepycat.je.txn.BasicLocker;
import com.sleepycat.je.txn.Locker;
import com.sleepycat.je.util.TestUtils;

public class TreeTest extends TreeTestBase {

    public TreeTest() {
	super();
    }

    /**
     * Rudimentary insert/retrieve test.
     */
    public void testSimpleTreeCreation()
	throws DatabaseException {
        initEnv(false);
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
        insertAndRetrieve(cursor, new Key("aaaaa".getBytes()),
                          new LN((byte[]) null));
        insertAndRetrieve(cursor, new Key("aaaab".getBytes()),
                          new LN((byte[]) null));
        insertAndRetrieve(cursor, new Key("aaaa".getBytes()),
                          new LN((byte[]) null));
        insertAndRetrieve(cursor, new Key("aaa".getBytes()),
                          new LN((byte[]) null));
        txn.operationEnd();
    }

    /**
     * Slightly less rudimentary test inserting a handfull of keys and LN's.
     */
    public void testMultipleInsertRetrieve0()
	throws DatabaseException {

        /* 
	 * Set the seed to reproduce a specific problem found while debugging:
         * IN.split was splitting with the identifier key being on the right
         * side.
	 */
        initEnv(false);
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
        for (int i = 0; i < 21; i++) {
            Key key = new Key(new byte[N_KEY_BYTES]);
            TestUtils.generateRandomAlphaBytes(key.getKey());
            insertAndRetrieve(cursor, key, new LN((byte[]) null));
        }
        txn.operationEnd();
    }

    /**
     * Insert a bunch of keys and test that they retrieve back ok.  While we
     * insert, maintain the highest and lowest keys inserted.  Verify that
     * getFirstNode and getLastNode return those two entries.  Lather, rinse,
     * repeat.
     */
    public void testMultipleInsertRetrieve1()
	throws DatabaseException, IOException {

        initEnv(false);
	doMultipleInsertRetrieve1();
    }

    /**
     * Helper routine for above.
     */
    private void doMultipleInsertRetrieve1()
	throws DatabaseException {

        Key[] keys = new Key[N_KEYS];
        LN[] lns = new LN[N_KEYS];
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
        for (int i = 0; i < N_KEYS; i++) {
            Key key = new Key(new byte[N_KEY_BYTES]);
            keys[i] = key;
            lns[i] = new LN((byte[]) null);
            TestUtils.generateRandomAlphaBytes(key.getKey());
            insertAndRetrieve(cursor, key, lns[i]);
        }

        for (int i = 0; i < N_KEYS; i++) {
            assertTrue(retrieveLN(keys[i]) == lns[i]);
        }

        TestUtils.checkLatchCount();
        IN leftMostNode = tree.getFirstNode();

        assertTrue(leftMostNode instanceof BIN);
        BIN lmn = (BIN) leftMostNode;
        lmn.releaseLatch();
        TestUtils.checkLatchCount();
        assertTrue(lmn.getKey(0).compareTo(minKey) == 0);

        TestUtils.checkLatchCount();
        IN rightMostNode = tree.getLastNode();

        assertTrue(rightMostNode instanceof BIN);
        BIN rmn = (BIN) rightMostNode;
        rmn.releaseLatch();
        TestUtils.checkLatchCount();
        assertTrue(rmn.getKey(rmn.getNEntries() - 1).compareTo(maxKey) == 0);
        TreeStats ts = tree.getTreeStats();
        assertTrue(ts.nRootSplits > 1);

        txn.operationEnd();
    }

    /**
     * Create a tree.  After creation, walk the bins forwards using getNextBin
     * counting the keys and validating that the keys are being returned in
     * ascending order.  Ensure that the correct number of keys were returned.
     */
    public void testCountAndValidateKeys() 
	throws DatabaseException, IOException {

        initEnv(false);
	doCountAndValidateKeys();
    }

    /**
     * Helper routine for above test.
     */
    private void doCountAndValidateKeys()
	throws DatabaseException {
        Key[] keys = new Key[N_KEYS];
        LN[] lns = new LN[N_KEYS];
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);

        for (int i = 0; i < N_KEYS; i++) {
            Key key = new Key(new byte[N_KEY_BYTES]);
            keys[i] = key;
            lns[i] = new LN((byte[]) null);
            TestUtils.generateRandomAlphaBytes(key.getKey());
            insertAndRetrieve(cursor, key, lns[i]);
        }
        assertTrue(countAndValidateKeys(tree) == N_KEYS);
        txn.operationEnd();
    }

    /**
     * Create a tree.  After creation, walk the bins backwards using getPrevBin
     * counting the keys and validating that the keys are being returned in
     * descending order.  Ensure that the correct number of keys were returned.
     */
    public void testCountAndValidateKeysBackwards()
	throws DatabaseException, IOException {

        initEnv(false);
	doCountAndValidateKeysBackwards();
    }

    /**
     * Helper routine for above test.
     */
    public void doCountAndValidateKeysBackwards()
	throws DatabaseException {

        Key[] keys = new Key[N_KEYS];
        LN[] lns = new LN[N_KEYS];
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
        for (int i = 0; i < N_KEYS; i++) {
            Key key = new Key(new byte[N_KEY_BYTES]);
            keys[i] = key;
            lns[i] = new LN((byte[]) null);
            TestUtils.generateRandomAlphaBytes(key.getKey());
            insertAndRetrieve(cursor, key, lns[i]);
        }
        assertTrue(countAndValidateKeysBackwards(tree) == N_KEYS);
        txn.operationEnd();
    }

    public void testAscendingInsertBalance()
	throws DatabaseException {

        initEnv(false);
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);

        /* Fill up a db with data */
        for (int i = 0; i < N_KEYS; i++) {
            byte[] keyBytes = new byte[4];
            TestUtils.putUnsignedInt(keyBytes, TestUtils.alphaKey(i));
            insertAndRetrieve(cursor, new Key(keyBytes),
                              new LN((byte[]) null));
        }
        
        TestUtils.checkLatchCount();

        /* Count the number of levels on the left. */
        IN leftMostNode = tree.getFirstNode();
        assertTrue(leftMostNode instanceof BIN);
        int leftSideLevels = 0;
        do {
            SearchResult result =
		tree.getParentINForChildIN(leftMostNode, true);
            leftMostNode = result.parent;
            leftSideLevels++;
        } while (leftMostNode != null);
        TestUtils.checkLatchCount();

        /* Count the number of levels on the right. */
        IN rightMostNode = tree.getLastNode();
        assertTrue(rightMostNode instanceof BIN);
        int rightSideLevels = 0;
        do {
            SearchResult result =
		tree.getParentINForChildIN(rightMostNode, true);
            rightMostNode = result.parent;
            rightSideLevels++;
        } while (rightMostNode != null);
        TestUtils.checkLatchCount();
        if (leftSideLevels > 10 ||
            rightSideLevels > 10) {
            fail("Levels too high (" +
                 leftSideLevels +
                 "/" +
                 rightSideLevels +
                 ") on descending insert");
        }
        txn.operationEnd();
    }

    public void testDescendingInsertBalance()
	throws DatabaseException {
        initEnv(false);
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);

        for (int i = N_KEYS; i >= 0; --i) {
            byte[] keyBytes = new byte[4];
            TestUtils.putUnsignedInt(keyBytes, TestUtils.alphaKey(i));
            insertAndRetrieve(cursor, new Key(keyBytes),
                              new LN((byte[]) null));
        }
        
        TestUtils.checkLatchCount();
        IN leftMostNode = tree.getFirstNode();

        assertTrue(leftMostNode instanceof BIN);
        int leftSideLevels = 0;
        do {
            SearchResult result =
		tree.getParentINForChildIN(leftMostNode, true);
            leftMostNode = result.parent;
            leftSideLevels++;
        } while (leftMostNode != null);
        TestUtils.checkLatchCount();

        IN rightMostNode = tree.getLastNode();

        assertTrue(rightMostNode instanceof BIN);
        int rightSideLevels = 0;
        do {
            SearchResult result =
		tree.getParentINForChildIN(rightMostNode, true);
            rightMostNode = result.parent;
            rightSideLevels++;
        } while (rightMostNode != null);
        TestUtils.checkLatchCount();
        if (leftSideLevels > 10 ||
            rightSideLevels > 10) {
            fail("Levels too high (" +
                 leftSideLevels +
                 "/" +
                 rightSideLevels +
                 ") on descending insert");
        }
        txn.operationEnd();
    }

    /**
     * Insert a bunch of keys.  Call validate and validate the results.
     */
    public void testValidate()
	throws DatabaseException {

        initEnv(false);
	Key[] keys = new Key[N_KEYS];
	LN[] lns = new LN[N_KEYS];
        Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
        NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
        
	for (int i = 0; i < N_KEYS; i++) {
	    Key key = new Key(new byte[N_KEY_BYTES]);
	    keys[i] = key;
	    lns[i] = new LN((byte[]) new byte[1]);
	    TestUtils.generateRandomAlphaBytes(key.getKey());
	    insertAndRetrieve(cursor, key, lns[i]);
	}

	DatabaseStats stats = db.verify(new VerifyConfig());
	BtreeStats btStats = (BtreeStats) stats;

	assertTrue(btStats.getInternalNodeCount() <
		   btStats.getBottomInternalNodeCount());
	assertTrue(btStats.getBottomInternalNodeCount() <
		   btStats.getLeafNodeCount() +
		   btStats.getDeletedLeafNodeCount());
	assertTrue(btStats.getLeafNodeCount() +
		   btStats.getDeletedLeafNodeCount() ==
		   N_KEYS);
        txn.operationEnd();
    }
}
