Когда вызывать SplHeap :: isCorrupted?

Question

Абстрактный класс SplHeap предоставляет метод isCorrupted :

Сообщает, находится ли куча в поврежденном состоянии

public SplHeap::isCorrupted ( void ) : bool

Интересно, как этот метод может быть полезен, не говоря уже о том, как куча может быть повреждена. Можно ожидать, что реализация внутренней кучи равна solid и никогда не будет повреждена.

Сначала я подумал, что, возможно, может быть прямой доступ к базовому массиву, который позволил бы что-то вроде этого (сродни тому, что было бы возможно с реализацией Python heapq):

$heap = new SplMinHeap();
$heap->insert(9);
$heap->insert(5);

echo $heap->top(); // 5

$heap[0] = 10; // make the heap inconsistent? -- not possible

Внутренняя структура данных кучи оказывается частной . var_dump из приведенной выше кучи выглядит следующим образом:

object(SplMinHeap)#1 (3) {
    ["flags":"SplHeap":private]=>int(0)
    ["isCorrupted":"SplHeap":private]=>bool(false)
    ["heap":"SplHeap":private]=>array(2) {
        [0]=>int(5)
        [1]=>int(9)
    }
}

В качестве другой возможности я подумал, что, возможно, ограничения памяти могут привести к повреждению кучи, но в этом случае представляется более полезным разрешить любому из модифицирующие методы (insert, extract, ...) вызывают исключение и оставляют кучу в ее первоначальном состоянии.

Итак, мой вопрос: зачем нам когда-либо вызывать $heap->isCorrupted() и в каком сценарии он может когда-либо возвращать true?

Answer 1

Куча может быть повреждена при возникновении исключения в пользовательской функции compare. Документация по SplHeap :: compare имеет следующее:

Предупреждение Создание исключений в SplHeap::compare() может повредить кучу и поставить ее в заблокированное состояние , Вы можете разблокировать его, позвонив по номеру SplHeap::recoverFromCorruption(). Однако некоторые элементы могут быть размещены неправильно и, следовательно, могут нарушить свойство кучи.

Например, этот скрипт создаст поврежденную кучу:

final class MySplHeap extends SplHeap {
    protected function compare($a, $b) {
        echo "compare $a with $b\n"; // Useful to see what is happening...
        if ($a === $b) return 0;
        if ($a > $b) return 1;
        throw new Exception("my error");
    }
}

$heap = new MySplHeap();

try {
    $heap->insert(3);
    $heap->insert(2);
    $heap->insert(1); 
    $heap->insert(4); // compare method raises error here
} catch(Exception $e) {}

var_dump($heap->isCorrupted()); // bool(true)

echo $heap->extract(); // RuntimeException: Heap is corrupted, heap properties are no longer ensured.

Из-за ошибка, значение 4 не может быть помещено в нужное место в куче.

Очевидное решение состоит в том, чтобы исключить исключения в функции сравнения.