Splitting Arrays- is my implementation correct?

Question

I'm writing code for a hybrid data structure for school, and am debugging the code. Basically, this structure is a combination of a Double Linked List and an Array, where each list node contains an array of set size. Since this is an ordered structure, a provision has to be made to identify and split full arrays into equally into two nodes.

This is my code for splitting a node into two and then copying the latter half of the parent node's array values to the child node.

public Chunk<E> split(Chunk<E> node) {
  Chunk<E> newChunk= new Chunk<E>();
  newChunk.index= node.index++;

  //connect to previous node
  node.next= newChunk.next;
  newChunk.prev= node.prev;

  //connect to next node
  newChunk.next= node.next.next;
  node.next.prev= newChunk.prev;

  //adds the latter half of the array contents to the new node
  //and erases the same contents from the old node
  for (int i=chunkSize/2; i<node.numUsed; i++) {
   newChunk.items[i-chunkSize/2]= node.items[i];
   node.items[i]=null;
  }

  //update capacity counter for both chunks
  node.numUsed=chunkSize/2;
  newChunk.numUsed= chunkSize/2;

  return newChunk;

}

The toArray() method is returning null values from the list, so I think something is going on with this split method.

Questions I have are:

Are the linking of the new node to the rest of the list correct?

Is the the nulling of values inside the loop responsible for the null printout?

Answer 1

A better question would be: "How can I isolate (track down) the location of a bug in the source code by debugging?"

First you'll want to have a way to reproduce the problem. It appears you already have that. In a non-trivial code base, you will then want to do a binary search for the problem. Having two points A and B in program execution, where the program is in valid state in A, but not in B, choose a point C between A and B and check whether everything is correct at C. If it is, the bug is between C and B, else between A and C. Recurse until you have it narrowed down into a very small part of the code, where it is usually quite obvious.

This leaves the question of how verify whether execution was correct so far. There are various ways to do that, but it is probably most instructive to execute the program in a debugger, use a break point to suspend execution, and check that the variables contain the expected values.

Answer 2

To answer this question thoroughly you should write some unit tests. For example:

package so3898131;

import static org.junit.Assert.*;

import org.junit.Test;

public class ChunkTest {

  /** Ensure that the simplest possible case works as expected. */
  @Test
  public void testEmptySplit() {
    Chunk<Object> old = new Chunk<Object>();
    Chunk<Object> split = old.split(old);
    assertEquals(0, split.chunkSize);
    assertEquals(0, split.items.length);
    assertEquals(0, split.index);
    assertEquals(1, old.index);
  }

  @Test
  public void testSplitWithOneItem() {
    // TODO: make sure that after splitting one of the chunks contains
    // one element, the other none.
  }

  @Test
  public void testSplitWithTwoItems() {
    // TODO: make sure that after splitting a chunk with two elements
    // each of the new chunks contains exactly one of the elements.
    // Use assertSame(..., ...) to check it.
  }
}

This throws NullPointerExceptions at me because node.next may be null, in which case you cannot access node.next.next. This probably means that your code does not work. At least it does not work as I expect it.

Update: Your code is not correct. I wrote a unit test like this:

@Test
public void testSplitLinkage() {
  Chunk<Object> old = new Chunk<Object>();
  assertNull(old.prev);
  assertNull(old.next);

  Chunk<Object> split = old.split(old);

  assertNull(old.prev);
  assertSame(split, old.next);
  assertSame(old, split.prev);
  assertNull(split.next);
}

And then I modified the code so that this test runs successfully. I had to replace some lines with:

// connect to previous and next node
Chunk<E> one = node, two = newChunk, three = node.next;
one.next = two;
two.prev = one;
two.next = three;
if (three != null)
  three.prev = two;