Программа, бросающая исключение после проверки исключения

Question

Мне что-то не хватает очень просто потому, что это дует мне на ум!

Я пытаюсь реализовать кучу, используя CompleteBinaryTree (который реализован с использованием массива). Этот CompleteBinaryTree представляет собой массив из Position<T>, где каждый элемент Position содержит элемент. Я пишу метод add(T t) для кучи, где t вставляется в следующую свободную позицию CompleteBinaryTree, а затем процесс перебора выполняется до тех пор, пока не будет заказано CompleteBinaryTree. Вот метод:

private CompleteBinaryTree<T> tree = new CompleteBinaryTree<T>(); 
    private Position<T> entry = null; 

    public void add(T t) { 
     entry = tree.add(t); 

     if (entry.equals(tree.root())) { 
      return; 
     } 

     //continue to swap inserted element with its parent 
     //while it is smaller than its parent 
     while (entry.element().compareTo(tree.parent(entry).element()) < 0) { 
      Position<T> parent = tree.parent(entry); 
      Position<T> temp = entry; 
      entry = parent; 
      parent = temp; 
     } 
    } 

Первый элемент добавляется штраф в Heap, но когда я пытаюсь добавить второй элемент, InvalidPositionException выбрасывается на while() линии. Это где Exeption выбрасывают внутри класса CompleteBinaryTree:

public Position<T> parent(Position<T> p) { 
     if (p == root()) throw new InvalidPositionException(); 

     return array[((ArrayPosition) p).index/2]; 
    } 

А вот две другие методы, используемые в CompleteBinaryTree:

public Position<T> root() { 
     if (isEmpty()) throw new InvalidPositionException(); 
     return array[1]; 
    } 

    public Position<T> add(T t) { 
     if (last == array.length) { 
      // extend array 
      ArrayPosition[] temp = (ArrayPosition[]) new Object[array.length*2]; 
      for (int i=1; i < array.length; i++) { 
       temp[i] = array[i]; 
      } 
      array = temp; 
     } 

     array[last] = new ArrayPosition(last, t); 
     return array[last++]; 
    } 

Как я получаю исключение брошено из-за p == root() года, когда Сначала я проверяю, является ли p корнем?

EDIT

Вот CompleteBinaryTree toString(), который возвращается Кучи toString():

public String toString() { 
    StringBuffer buf = new StringBuffer(); 

    for (int i = 1; i < last; i++) { 
     buf.append(" ").append(array[i]); 
    } 

    return buf.toString();  
} 

Answer 1

Как я получаю исключение брошено, потому что р == корень(), когда Сначала я проверяю, является ли p корнем?

Но вы делать не чек каждый tree.parent() аргумент, чтобы увидеть, является ли это корень. Вы проверяете только аргумент, переданный первому вызову этого метода. Каждый раз, когда выполняется цикл цикла while, он устанавливает entry в новое значение, а когда цикл цикла передает это новое, непроверенное значение, значение tree.parent(). Действительно, каждое новое значение entry ближе к корню, чем предыдущее, потому что все дело в том, чтобы перемещать дерево от дочернего к родительскому, то есть к корню. Весьма вероятно, что иногда эта процедура будет достигать корня, и, более вероятно, чем меньше элементов уже находится в дереве.

Одним из способов решения этой проблемы было бы переместить корень проверки в while условие:

while (!entry.equals(tree.root()) 
     && entry.element().compareTo(tree.parent(entry).element()) < 0) { 
    // ... 
} 

В этом случае, конечно, вам не нужен текущий контроль разовый, что вы выполняете за пределами петля.