statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/provisional/datastore/core/historytree/AbstractHistoryTreeTestBase.java - tracecompass/org.eclipse.tracecompass - Git at Google

 /*******************************************************************************
  * Copyright (c) 2017 École Polytechnique de Montréal
  *
  * All rights reserved. This program and the accompanying materials are
  * made available under the terms of the Eclipse Public License 2.0 which
  * accompanies this distribution, and is available at
  * https://www.eclipse.org/legal/epl-2.0/
  *
  * SPDX-License-Identifier: EPL-2.0
  *******************************************************************************/

 package org.eclipse.tracecompass.internal.provisional.datastore.core.historytree;

 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;

 import java.io.File;
 import java.io.IOException;
 import java.nio.channels.ClosedChannelException;
 import java.nio.file.Files;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Objects;

 import org.eclipse.jdt.annotation.Nullable;
 import org.eclipse.tracecompass.datastore.core.interval.IHTInterval;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;

 /**
  * This is the base class for all history tree implementation tests. Specific
  * tree's tests can extend this class to have some basic tests.
  *
  * It tests the {@link AbstractHistoryTree} class. This test class will fill
  * nodes only with sequential objects, so that each extending test for trees
  * will have to add the tests and filling methods that correspond to their own
  * use cases.
  *
  * @author Geneviève Bastien
  * @param <E>
  *            The type of objects that will be saved in the tree
  * @param <N>
  *            The base type of the nodes of this tree
  */
 public abstract class AbstractHistoryTreeTestBase<E extends IHTInterval, N extends HTNode<E>> {

     private @Nullable File fTempFile;

     /**
      * Create the temporary file for this history tree
      */
     @Before
     public void setupTest() {
         try {
             fTempFile = File.createTempFile("tmpStateSystem", null);
         } catch (IOException e) {
             fail(e.getMessage());
         }
     }

     /**
      * Delete the temporary history tree file after the test
      * @throws IOException failed to delete file
      */
     @After
     public void cleanup() throws IOException {
         if (fTempFile != null) {
             Files.delete(fTempFile.toPath());
         }
     }

     /**
      * Setup a history tree.
      *
      * @param maxChildren
      *            The max number of children per node in the tree (tree config
      *            option)
      * @param treeStart
      *            The start of the tree
      * @return The new history tree
      */
     protected AbstractHistoryTree<E, N> setupSmallTree(int maxChildren, long treeStart) {
         AbstractHistoryTree<E, N> ht = null;
         try {
             File newFile = fTempFile;
             assertNotNull(newFile);

             ht = createHistoryTree(newFile,
                     HtTestUtils.BLOCKSIZE,
                     maxChildren, /* Number of children */
                     1, /* Provider version */
                     1); /* Start time */

         } catch (IOException e) {
             fail(e.getMessage());
         }

         assertNotNull(ht);
         return Objects.requireNonNull(ht);
     }

     /**
      * Create the history tree to test
      *
      * @param stateHistoryFile
      *            The name of the history file
      * @param blockSize
      *            The size of each "block" on disk in bytes. One node will
      *            always fit in one block. It should be at least 4096.
      * @param maxChildren
      *            The maximum number of children allowed per core (non-leaf)
      *            node.
      * @param providerVersion
      *            The version of the state provider. If a file already exists,
      *            and their versions match, the history file will not be rebuilt
      *            uselessly.
      * @param treeStart
      *            The start time of the history
      * @return The history tree stub
      * @throws IOException
      *             Any exception thrown by the history tree
      */
     protected abstract AbstractHistoryTree<E, N> createHistoryTree(File stateHistoryFile,
             int blockSize,
             int maxChildren,
             int providerVersion,
             long treeStart) throws IOException;

     /**
      * "Reader" constructor : instantiate a history tree from an existing tree
      * file on disk
      *
      * @param existingStateFile
      *            Path/filename of the history-file we are to open
      * @param expProviderVersion
      *            The expected version of the state provider
      * @return The history tree stub
      * @throws IOException
      *             If an error happens reading the file
      */
     protected abstract AbstractHistoryTree<E, N> createHistoryTree(
             File existingStateFile,
             int expProviderVersion) throws IOException;

     /**
      * Create an interval that fits in the tree with the given start/end time
      *
      * @param start
      *            The start time
      * @param end
      *            The end time
      * @return The object
      */
     protected abstract E createInterval(long start, long end);

     /**
      * Create a reader history tree
      *
      * @return The history tree stub
      * @throws IOException
      *             If an error happened reading the file
      */
     protected final AbstractHistoryTree<E, N> createHistoryTreeReader() throws IOException {
         File tempFile = fTempFile;
         assertNotNull(tempFile);
         return createHistoryTree(tempFile, 1);
     }

     /**
      * Setup a history tree with config MAX_CHILDREN = 3 and start time of 1
      *
      * @return A new history tree
      */
     protected AbstractHistoryTree<E, N> setupSmallTree() {
         return setupSmallTree(3, 1);
     }

     /**
      * Add sequential elements to the history up to a certain size. Any element
      * that would go above the fixed limit should not be added
      *
      * @param ht
      *            The tree to which to add values
      * @param fillSize
      *            The limit on the size of the elements to add
      * @param start
      *            The start time of the values
      * @return The latest end time
      */
     protected abstract long fillValues(AbstractHistoryTree<E, N> ht, int fillSize, long start);

     /**
      * Insert objects in the tree to fill the current leaf node to capacity,
      * without exceeding it.
      *
      * This guarantees that the following insertion will create new nodes.
      *
      * @param ht
      *            The history tree in which to insert
      * @return Start time of the current leaf node. Future insertions should be
      *         greater than or equal to this to make sure the intervals go in
      *         the leaf node.
      */
     private long fillNextLeafNode(AbstractHistoryTree<E, N> ht, long leafNodeStart) {
         int prevCount = ht.getNodeCount();
         int prevDepth = ht.getDepth();

         /* Fill the following leaf node */
         N node = ht.getLatestLeaf();
         long ret = fillValues(ht, node.getNodeFreeSpace(), leafNodeStart);

         /* Make sure we haven't changed the depth or node count */
         assertEquals(prevCount, ht.getNodeCount());
         assertEquals(prevDepth, ht.getDepth());

         return ret;
     }

     /**
      * Test that nodes are filled
      *
      * It fills nodes with sequential elements, so that leafs should be filled.
      */
     @Test
     public void testSequentialFill() {
         AbstractHistoryTree<E, N> ht = setupSmallTree();

         // Make sure it is empty
         N node = ht.getLatestLeaf();
         assertEquals(0, node.getNodeUsagePercent());

         /* Fill ~10% of the node with elements */
         int initialFreeSpace = node.getNodeFreeSpace();
         int limit = node.getNodeFreeSpace() / 10;
         long start = fillValues(ht, limit, 1);
         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - limit);
         assertTrue(node.getNodeFreeSpace() < initialFreeSpace);

         /* Add elements up to ~20% */
         start = fillValues(ht, limit, start);
         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 2 * limit);
         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - limit);

         /* Add elements up to ~30% */
         start = fillValues(ht, limit, start);
         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 3 * limit);
         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 2 * limit);

         /* Add elements up to ~40% */
         fillValues(ht, limit, start);
         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 4 * limit);
         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 3 * limit);

         // Assert the integrity of the tree
         ht.closeTree(ht.getTreeEnd());
         HtTestUtils.assertTreeIntegrity(ht);

     }

     /**
      * Test the addition of new nodes to the tree and make sure the tree is
      * built with the right structure
      */
     @Test
     public void testDepth() {
         AbstractHistoryTree<E, N> ht = setupSmallTree();

         /* Fill a first node */
         N node = ht.getLatestLeaf();
         long start = 1;
         long time = fillValues(ht, node.getNodeFreeSpace(), start);

         /*
          * Add intervals that should add a sibling to the node and a new root
          * node
          */
         assertEquals(1, ht.getNodeCount());
         assertEquals(1, ht.getDepth());
         ht.insert(createInterval(time, time + 1));
         time += 1;
         assertEquals(3, ht.getNodeCount());
         assertEquals(2, ht.getDepth());

         /* Fill the latest leaf node (2nd child) */
         node = ht.getLatestLeaf();
         time = fillValues(ht, node.getNodeFreeSpace(), time);

         /*
          * Add an interval that should add another sibling to the previous nodes
          */
         ht.insert(createInterval(time, time + 1));
         time += 1;
         assertEquals(4, ht.getNodeCount());
         assertEquals(2, ht.getDepth());

         /* Fill the latest leaf node (3rd and last child) */
         node = ht.getLatestLeaf();
         time = fillValues(ht, node.getNodeFreeSpace(), time);

         /* The new node created here should generate a new branch */
         ht.insert(createInterval(time, time + 1));
         time += 1;
         assertEquals(7, ht.getNodeCount());
         assertEquals(3, ht.getDepth());

         /*
          * Completely fill the second level, such that there will be a 4th level
          * added
          */
         while (ht.getDepth() < 4) {
             time = fillNextLeafNode(ht, time);
             ht.insert(createInterval(time, time + 1));
         }
         assertEquals(4, ht.getDepth());

         // Assert the integrity of the tree
         ht.closeTree(ht.getTreeEnd());
         HtTestUtils.assertTreeIntegrity(ht);
     }

     /**
      * Make sure the node sequence numbers and parent pointers are set correctly
      * when new nodes are created.
      *
      * <p>
      * We are building a tree whose node sequence numbers will look like this at
      * the end:
      * </p>
      *
      * <pre>
      *     3
      *    / \
      *   1   4
      *  / \   \
      * 0   2   5
      * </pre>
      *
      * <p>
      * However while building, the parent pointers may be different.
      * </p>
      *
      * @throws ClosedChannelException
      *             If the file channel is closed
      */
     @Test
     public void testNodeSequenceNumbers() throws ClosedChannelException {

         long time = 1;

         AbstractHistoryTree<E, N> ht = setupSmallTree(2, time);
         time = fillNextLeafNode(ht, time);

         /* There is only one node in the tree at this point, with no parent */
         List<N> branch = ht.getLatestBranch();
         assertEquals(1, branch.size());
         assertEquals(0, branch.get(0).getSequenceNumber());
         assertEquals(-1, branch.get(0).getParentSequenceNumber());

         /* Create a new branch */
         ht.insert(createInterval(time, time + 1));
         time = fillNextLeafNode(ht, time + 1);
         assertEquals(3, ht.getNodeCount());
         assertEquals(2, ht.getDepth());

         /* Make sure the first node's parent was updated */
         N node = ht.getNode(0);
         assertEquals(0, node.getSequenceNumber());
         assertEquals(1, node.getParentSequenceNumber());

         /* Make sure the new branch is all right */
         branch = ht.getLatestBranch();
         assertEquals(2, branch.size());
         assertEquals(1, branch.get(0).getSequenceNumber());
         assertEquals(-1, branch.get(0).getParentSequenceNumber());
         assertEquals(2, branch.get(1).getSequenceNumber());
         assertEquals(1, branch.get(1).getParentSequenceNumber());

         /* Create a third branch */
         ht.insert(createInterval(time, time + 1));
         fillNextLeafNode(ht, time + 1);
         assertEquals(6, ht.getNodeCount());
         assertEquals(3, ht.getDepth());

         /* Make sure all previous nodes are still correct */
         node = ht.getNode(0);
         assertEquals(0, node.getSequenceNumber());
         assertEquals(1, node.getParentSequenceNumber());
         node = ht.getNode(1);
         assertEquals(1, node.getSequenceNumber());
         assertEquals(3, node.getParentSequenceNumber());
         node = ht.getNode(2);
         assertEquals(2, node.getSequenceNumber());
         assertEquals(1, node.getParentSequenceNumber());

         /* Verify the contents of the new latest branch */
         branch = ht.getLatestBranch();
         assertEquals(3, branch.size());
         assertEquals(3, branch.get(0).getSequenceNumber());
         assertEquals(-1, branch.get(0).getParentSequenceNumber());
         assertEquals(4, branch.get(1).getSequenceNumber());
         assertEquals(3, branch.get(1).getParentSequenceNumber());
         assertEquals(5, branch.get(2).getSequenceNumber());
         assertEquals(4, branch.get(2).getParentSequenceNumber());

         // Assert the integrity of the tree
         ht.closeTree(ht.getTreeEnd());
         HtTestUtils.assertTreeIntegrity(ht);
     }

     /**
      * Test reading a tree and make sure it is identical to the original one
      *
      * <p>
      * We are building a tree whose node sequence numbers will look like this at
      * the end:
      * </p>
      *
      * <pre>
      *       4
      *     /   \
      *    1     5
      *  / | \    \
      * 0  2  3    6
      * </pre>
      *
      * @throws IOException
      *             Exceptions with the HT file
      *
      */
     @Test
     public void testReadTree() throws IOException {

         long time = 1;

         // Build the tree for the test
         AbstractHistoryTree<E, N> ht = setupSmallTree();
         time = fillNextLeafNode(ht, time);

         /* Create a new branch */
         ht.insert(createInterval(time, time + 1));
         time = fillNextLeafNode(ht, time + 1);

         /* Fill the third child */
         ht.insert(createInterval(time, time + 1));
         time = fillNextLeafNode(ht, time + 1);

         /* Make sure the tree has the expected structure at this point */
         assertEquals(4, ht.getNodeCount());
         assertEquals(2, ht.getDepth());

         /* Add the third branch */
         ht.insert(createInterval(time, time + 1));
         time = fillNextLeafNode(ht, time + 1);

         /* Make sure the tree has the expected structure */
         assertEquals(7, ht.getNodeCount());
         assertEquals(3, ht.getDepth());

         // Close the tree and save the nodes for later
         ht.closeTree(time + 1);

         List<N> expectedNodes = new ArrayList<>(ht.getNodeCount());
         for (int i = 0; i < ht.getNodeCount(); i++) {
             expectedNodes.add(ht.getNode(i));
         }
         ht.closeFile();

         // Create a reader history tree
         ht = createHistoryTreeReader();

         // Make sure the number of nodes and depth is as expected
         assertEquals(7, ht.getNodeCount());
         assertEquals(3, ht.getDepth());

         for (int i = 0; i < ht.getNodeCount(); i++) {
             assertEquals(expectedNodes.get(i), ht.readNode(i));
         }

         // Assert the integrity of the read tree
         HtTestUtils.assertTreeIntegrity(ht);
     }

     /**
      * Test the tree end time
      */
     @Test
     public void testTreeEnd() {
         long time = 1;

         // Check the end time at the start
         AbstractHistoryTree<E, N> ht = setupSmallTree();
         assertEquals(time, ht.getTreeEnd());

         // Fill a node and check the end
         time = fillNextLeafNode(ht, time);
         assertEquals(time, ht.getTreeEnd());

         // Add an object that should not change the end time
         E object = createInterval(time - 10, time - 5);
         ht.insert(object);
         assertEquals(time, ht.getTreeEnd());

         // Assert the tree integrity
         ht.closeTree(ht.getTreeEnd());
         HtTestUtils.assertTreeIntegrity(ht);
     }

 }
	/*******************************************************************************
	* Copyright (c) 2017 École Polytechnique de Montréal
	*
	* All rights reserved. This program and the accompanying materials are
	* made available under the terms of the Eclipse Public License 2.0 which
	* accompanies this distribution, and is available at
	* https://www.eclipse.org/legal/epl-2.0/
	*
	* SPDX-License-Identifier: EPL-2.0
	*******************************************************************************/

	package org.eclipse.tracecompass.internal.provisional.datastore.core.historytree;

	import static org.junit.Assert.assertEquals;
	import static org.junit.Assert.assertNotNull;
	import static org.junit.Assert.assertTrue;
	import static org.junit.Assert.fail;

	import java.io.File;
	import java.io.IOException;
	import java.nio.channels.ClosedChannelException;
	import java.nio.file.Files;
	import java.util.ArrayList;
	import java.util.List;
	import java.util.Objects;

	import org.eclipse.jdt.annotation.Nullable;
	import org.eclipse.tracecompass.datastore.core.interval.IHTInterval;
	import org.junit.After;
	import org.junit.Before;
	import org.junit.Test;

	/**
	* This is the base class for all history tree implementation tests. Specific
	* tree's tests can extend this class to have some basic tests.
	*
	* It tests the {@link AbstractHistoryTree} class. This test class will fill
	* nodes only with sequential objects, so that each extending test for trees
	* will have to add the tests and filling methods that correspond to their own
	* use cases.
	*
	* @author Geneviève Bastien
	* @param <E>
	* The type of objects that will be saved in the tree
	* @param <N>
	* The base type of the nodes of this tree
	*/
	public abstract class AbstractHistoryTreeTestBase<E extends IHTInterval, N extends HTNode<E>> {

	private @Nullable File fTempFile;

	/**
	* Create the temporary file for this history tree
	*/
	@Before
	public void setupTest() {
	try {
	fTempFile = File.createTempFile("tmpStateSystem", null);
	} catch (IOException e) {
	fail(e.getMessage());
	}
	}

	/**
	* Delete the temporary history tree file after the test
	* @throws IOException failed to delete file
	*/
	@After
	public void cleanup() throws IOException {
	if (fTempFile != null) {
	Files.delete(fTempFile.toPath());
	}
	}

	/**
	* Setup a history tree.
	*
	* @param maxChildren
	* The max number of children per node in the tree (tree config
	* option)
	* @param treeStart
	* The start of the tree
	* @return The new history tree
	*/
	protected AbstractHistoryTree<E, N> setupSmallTree(int maxChildren, long treeStart) {
	AbstractHistoryTree<E, N> ht = null;
	try {
	File newFile = fTempFile;
	assertNotNull(newFile);

	ht = createHistoryTree(newFile,
	HtTestUtils.BLOCKSIZE,
	maxChildren, /* Number of children */
	1, /* Provider version */
	1); /* Start time */

	} catch (IOException e) {
	fail(e.getMessage());
	}

	assertNotNull(ht);
	return Objects.requireNonNull(ht);
	}

	/**
	* Create the history tree to test
	*
	* @param stateHistoryFile
	* The name of the history file
	* @param blockSize
	* The size of each "block" on disk in bytes. One node will
	* always fit in one block. It should be at least 4096.
	* @param maxChildren
	* The maximum number of children allowed per core (non-leaf)
	* node.
	* @param providerVersion
	* The version of the state provider. If a file already exists,
	* and their versions match, the history file will not be rebuilt
	* uselessly.
	* @param treeStart
	* The start time of the history
	* @return The history tree stub
	* @throws IOException
	* Any exception thrown by the history tree
	*/
	protected abstract AbstractHistoryTree<E, N> createHistoryTree(File stateHistoryFile,
	int blockSize,
	int maxChildren,
	int providerVersion,
	long treeStart) throws IOException;

	/**
	* "Reader" constructor : instantiate a history tree from an existing tree
	* file on disk
	*
	* @param existingStateFile
	* Path/filename of the history-file we are to open
	* @param expProviderVersion
	* The expected version of the state provider
	* @return The history tree stub
	* @throws IOException
	* If an error happens reading the file
	*/
	protected abstract AbstractHistoryTree<E, N> createHistoryTree(
	File existingStateFile,
	int expProviderVersion) throws IOException;

	/**
	* Create an interval that fits in the tree with the given start/end time
	*
	* @param start
	* The start time
	* @param end
	* The end time
	* @return The object
	*/
	protected abstract E createInterval(long start, long end);

	/**
	* Create a reader history tree
	*
	* @return The history tree stub
	* @throws IOException
	* If an error happened reading the file
	*/
	protected final AbstractHistoryTree<E, N> createHistoryTreeReader() throws IOException {
	File tempFile = fTempFile;
	assertNotNull(tempFile);
	return createHistoryTree(tempFile, 1);
	}

	/**
	* Setup a history tree with config MAX_CHILDREN = 3 and start time of 1
	*
	* @return A new history tree
	*/
	protected AbstractHistoryTree<E, N> setupSmallTree() {
	return setupSmallTree(3, 1);
	}

	/**
	* Add sequential elements to the history up to a certain size. Any element
	* that would go above the fixed limit should not be added
	*
	* @param ht
	* The tree to which to add values
	* @param fillSize
	* The limit on the size of the elements to add
	* @param start
	* The start time of the values
	* @return The latest end time
	*/
	protected abstract long fillValues(AbstractHistoryTree<E, N> ht, int fillSize, long start);

	/**
	* Insert objects in the tree to fill the current leaf node to capacity,
	* without exceeding it.
	*
	* This guarantees that the following insertion will create new nodes.
	*
	* @param ht
	* The history tree in which to insert
	* @return Start time of the current leaf node. Future insertions should be
	* greater than or equal to this to make sure the intervals go in
	* the leaf node.
	*/
	private long fillNextLeafNode(AbstractHistoryTree<E, N> ht, long leafNodeStart) {
	int prevCount = ht.getNodeCount();
	int prevDepth = ht.getDepth();

	/* Fill the following leaf node */
	N node = ht.getLatestLeaf();
	long ret = fillValues(ht, node.getNodeFreeSpace(), leafNodeStart);

	/* Make sure we haven't changed the depth or node count */
	assertEquals(prevCount, ht.getNodeCount());
	assertEquals(prevDepth, ht.getDepth());

	return ret;
	}

	/**
	* Test that nodes are filled
	*
	* It fills nodes with sequential elements, so that leafs should be filled.
	*/
	@Test
	public void testSequentialFill() {
	AbstractHistoryTree<E, N> ht = setupSmallTree();

	// Make sure it is empty
	N node = ht.getLatestLeaf();
	assertEquals(0, node.getNodeUsagePercent());

	/* Fill ~10% of the node with elements */
	int initialFreeSpace = node.getNodeFreeSpace();
	int limit = node.getNodeFreeSpace() / 10;
	long start = fillValues(ht, limit, 1);
	assertTrue(node.getNodeFreeSpace() > initialFreeSpace - limit);
	assertTrue(node.getNodeFreeSpace() < initialFreeSpace);

	/* Add elements up to ~20% */
	start = fillValues(ht, limit, start);
	assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 2 * limit);
	assertTrue(node.getNodeFreeSpace() < initialFreeSpace - limit);

	/* Add elements up to ~30% */
	start = fillValues(ht, limit, start);
	assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 3 * limit);
	assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 2 * limit);

	/* Add elements up to ~40% */
	fillValues(ht, limit, start);
	assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 4 * limit);
	assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 3 * limit);

	// Assert the integrity of the tree
	ht.closeTree(ht.getTreeEnd());
	HtTestUtils.assertTreeIntegrity(ht);

	}

	/**
	* Test the addition of new nodes to the tree and make sure the tree is
	* built with the right structure
	*/
	@Test
	public void testDepth() {
	AbstractHistoryTree<E, N> ht = setupSmallTree();

	/* Fill a first node */
	N node = ht.getLatestLeaf();
	long start = 1;
	long time = fillValues(ht, node.getNodeFreeSpace(), start);

	/*
	* Add intervals that should add a sibling to the node and a new root
	* node
	*/
	assertEquals(1, ht.getNodeCount());
	assertEquals(1, ht.getDepth());
	ht.insert(createInterval(time, time + 1));
	time += 1;
	assertEquals(3, ht.getNodeCount());
	assertEquals(2, ht.getDepth());

	/* Fill the latest leaf node (2nd child) */
	node = ht.getLatestLeaf();
	time = fillValues(ht, node.getNodeFreeSpace(), time);

	/*
	* Add an interval that should add another sibling to the previous nodes
	*/
	ht.insert(createInterval(time, time + 1));
	time += 1;
	assertEquals(4, ht.getNodeCount());
	assertEquals(2, ht.getDepth());

	/* Fill the latest leaf node (3rd and last child) */
	node = ht.getLatestLeaf();
	time = fillValues(ht, node.getNodeFreeSpace(), time);

	/* The new node created here should generate a new branch */
	ht.insert(createInterval(time, time + 1));
	time += 1;
	assertEquals(7, ht.getNodeCount());
	assertEquals(3, ht.getDepth());

	/*
	* Completely fill the second level, such that there will be a 4th level
	* added
	*/
	while (ht.getDepth() < 4) {
	time = fillNextLeafNode(ht, time);
	ht.insert(createInterval(time, time + 1));
	}
	assertEquals(4, ht.getDepth());

	// Assert the integrity of the tree
	ht.closeTree(ht.getTreeEnd());
	HtTestUtils.assertTreeIntegrity(ht);
	}

	/**
	* Make sure the node sequence numbers and parent pointers are set correctly
	* when new nodes are created.
	*
	* <p>
	* We are building a tree whose node sequence numbers will look like this at
	* the end:
	* </p>
	*
	* <pre>
	* 3
	* / \
	* 1 4
	* / \ \
	* 0 2 5
	* </pre>
	*
	* <p>
	* However while building, the parent pointers may be different.
	* </p>
	*
	* @throws ClosedChannelException
	* If the file channel is closed
	*/
	@Test
	public void testNodeSequenceNumbers() throws ClosedChannelException {

	long time = 1;

	AbstractHistoryTree<E, N> ht = setupSmallTree(2, time);
	time = fillNextLeafNode(ht, time);

	/* There is only one node in the tree at this point, with no parent */
	List<N> branch = ht.getLatestBranch();
	assertEquals(1, branch.size());
	assertEquals(0, branch.get(0).getSequenceNumber());
	assertEquals(-1, branch.get(0).getParentSequenceNumber());

	/* Create a new branch */
	ht.insert(createInterval(time, time + 1));
	time = fillNextLeafNode(ht, time + 1);
	assertEquals(3, ht.getNodeCount());
	assertEquals(2, ht.getDepth());

	/* Make sure the first node's parent was updated */
	N node = ht.getNode(0);
	assertEquals(0, node.getSequenceNumber());
	assertEquals(1, node.getParentSequenceNumber());

	/* Make sure the new branch is all right */
	branch = ht.getLatestBranch();
	assertEquals(2, branch.size());
	assertEquals(1, branch.get(0).getSequenceNumber());
	assertEquals(-1, branch.get(0).getParentSequenceNumber());
	assertEquals(2, branch.get(1).getSequenceNumber());
	assertEquals(1, branch.get(1).getParentSequenceNumber());

	/* Create a third branch */
	ht.insert(createInterval(time, time + 1));
	fillNextLeafNode(ht, time + 1);
	assertEquals(6, ht.getNodeCount());
	assertEquals(3, ht.getDepth());

	/* Make sure all previous nodes are still correct */
	node = ht.getNode(0);
	assertEquals(0, node.getSequenceNumber());
	assertEquals(1, node.getParentSequenceNumber());
	node = ht.getNode(1);
	assertEquals(1, node.getSequenceNumber());
	assertEquals(3, node.getParentSequenceNumber());
	node = ht.getNode(2);
	assertEquals(2, node.getSequenceNumber());
	assertEquals(1, node.getParentSequenceNumber());

	/* Verify the contents of the new latest branch */
	branch = ht.getLatestBranch();
	assertEquals(3, branch.size());
	assertEquals(3, branch.get(0).getSequenceNumber());
	assertEquals(-1, branch.get(0).getParentSequenceNumber());
	assertEquals(4, branch.get(1).getSequenceNumber());
	assertEquals(3, branch.get(1).getParentSequenceNumber());
	assertEquals(5, branch.get(2).getSequenceNumber());
	assertEquals(4, branch.get(2).getParentSequenceNumber());

	// Assert the integrity of the tree
	ht.closeTree(ht.getTreeEnd());
	HtTestUtils.assertTreeIntegrity(ht);
	}

	/**
	* Test reading a tree and make sure it is identical to the original one
	*
	* <p>
	* We are building a tree whose node sequence numbers will look like this at
	* the end:
	* </p>
	*
	* <pre>
	* 4
	* / \
	* 1 5
	* / \| \ \
	* 0 2 3 6
	* </pre>
	*
	* @throws IOException
	* Exceptions with the HT file
	*
	*/
	@Test
	public void testReadTree() throws IOException {

	long time = 1;

	// Build the tree for the test
	AbstractHistoryTree<E, N> ht = setupSmallTree();
	time = fillNextLeafNode(ht, time);

	/* Create a new branch */
	ht.insert(createInterval(time, time + 1));
	time = fillNextLeafNode(ht, time + 1);

	/* Fill the third child */
	ht.insert(createInterval(time, time + 1));
	time = fillNextLeafNode(ht, time + 1);

	/* Make sure the tree has the expected structure at this point */
	assertEquals(4, ht.getNodeCount());
	assertEquals(2, ht.getDepth());

	/* Add the third branch */
	ht.insert(createInterval(time, time + 1));
	time = fillNextLeafNode(ht, time + 1);

	/* Make sure the tree has the expected structure */
	assertEquals(7, ht.getNodeCount());
	assertEquals(3, ht.getDepth());

	// Close the tree and save the nodes for later
	ht.closeTree(time + 1);

	List<N> expectedNodes = new ArrayList<>(ht.getNodeCount());
	for (int i = 0; i < ht.getNodeCount(); i++) {
	expectedNodes.add(ht.getNode(i));
	}
	ht.closeFile();

	// Create a reader history tree
	ht = createHistoryTreeReader();

	// Make sure the number of nodes and depth is as expected
	assertEquals(7, ht.getNodeCount());
	assertEquals(3, ht.getDepth());

	for (int i = 0; i < ht.getNodeCount(); i++) {
	assertEquals(expectedNodes.get(i), ht.readNode(i));
	}

	// Assert the integrity of the read tree
	HtTestUtils.assertTreeIntegrity(ht);
	}

	/**
	* Test the tree end time
	*/
	@Test
	public void testTreeEnd() {
	long time = 1;

	// Check the end time at the start
	AbstractHistoryTree<E, N> ht = setupSmallTree();
	assertEquals(time, ht.getTreeEnd());

	// Fill a node and check the end
	time = fillNextLeafNode(ht, time);
	assertEquals(time, ht.getTreeEnd());

	// Add an object that should not change the end time
	E object = createInterval(time - 10, time - 5);
	ht.insert(object);
	assertEquals(time, ht.getTreeEnd());

	// Assert the tree integrity
	ht.closeTree(ht.getTreeEnd());
	HtTestUtils.assertTreeIntegrity(ht);
	}

	}