Разделение массивов - моя реализация верна? - PullRequest
Новая
       8

Разделение массивов - моя реализация верна?

1 голос
/ 10 октября 2010

Я пишу код для гибридной структуры данных для школы и отлаживаю код. По сути, эта структура представляет собой комбинацию двойного связанного списка и массива, где каждый узел списка содержит массив заданного размера. Поскольку это упорядоченная структура, необходимо предусмотреть возможность идентифицировать и разбивать полные массивы на два равных узла.

Это мой код для разбиения узла на две части и последующего копирования второй половины значений массива родительского узла в дочерний узел. 

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;

}

Метод toArray () возвращает нулевые значения из списка, поэтому я думаю, что с этим методом split что-то происходит.

У меня есть следующие вопросы:

Корректна ли связь нового узла с остальной частью списка? Является ли обнуление значений внутри цикла ответственным за нулевую распечатку?

Ответы [ 2 ]

2 голосов
/ 10 октября 2010

Чтобы полностью ответить на этот вопрос, вы должны написать несколько юнит-тестов.Например: 

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.
  }
}

Это бросает в меня NullPointerException с, потому что node.next может быть null, в этом случае вы не можете получить доступ к node.next.next.Это, вероятно, означает, что ваш код не работает.По крайней мере, это не работает, поскольку Я ожидаю этого.

Обновление: Ваш код неверен.Я написал модульный тест следующим образом: 

@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);
}

И затем я изменил код, чтобы этот тест прошел успешно.Мне пришлось заменить несколько строк на: 

// 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;
0 голосов
/ 10 октября 2010

Лучше было бы задать вопрос: «Как я могу изолировать (отследить) местоположение ошибки в исходном коде путем отладки?»

Сначала вы захотите найти способ воспроизвести проблему,Похоже, у вас уже есть это.В нетривиальной кодовой базе вы захотите выполнить бинарный поиск проблемы.Имея две точки A и B при выполнении программы, где программа находится в допустимом состоянии в A, но не в B, выберите точку C между A и B и проверьте, все ли правильно в C. Если это так, ошибка находится междуC и B, еще между A и C. Повторяйте, пока он не сузится до очень маленькой части кода, где это обычно довольно очевидно.

Это оставляет вопрос о том, как проверить, было ли выполнение правильнымдо сих пор.Есть разные способы сделать это, но, вероятно, наиболее поучительно выполнить программу в отладчике, использовать точку останова для приостановки выполнения и проверить, что переменные содержат ожидаемые значения.

...