Heap.Update (gb.data)
Sub Update ( Old As Variant, New As Variant )
Encontra todas as ocorrências
Old e substitui por
New. Esta é uma operação O(n).
Além disso, a pilha tem que ser reconstruída, se, foi realizada
mais de uma substituição.
Se
New é nulo, então a entrada será excluída.
A busca dos objetos é feita por identidade e
não usando o
método _compare(). "Por identidade" significa que, se dois objetos são
comparados e ambos têm um método especial _identity() retornando uma Variant,
os valores de retorno desses métodos é que são comparados.
Se um dos objectos não implementa o método _identity(), o
padrão é a comparação por endereços de objetos na memória. Esta estratégia permite que
você salve tipos de dados primitivos (Integer, Boolean, String), etc. no
heap. Mas você também pode gerenciar objetos distintos em classes de equivalência: O método _compare()
define a sua relação de equivalência (como os objetos são mais ou menos ordenado no heap)
e a comparação identidade permite discernir objetos diferentes, mesmo da mesma classe (a fim de atualizá-los individualmente).
Se somos um amontoado de objetos cujos métodos _compare() comparam algum tipo de
prioridade, e
Old é o mesmo objeto que
New, este pode ser utilizado para
propagar uma mudança de prioridade feita para o objeto que vai corrigir a
posição no heap.
O método _identity() deixa isso para você o que a "identidade" realmente significa.
Se você precisa atualizar classes de equivalência inteiras de cada vez, você também pode definir
_identity() para combinar com seu método _compare ().
É um meio puramente opcional de agrupar objetos de forma diferente.
Aqui está um trecho pseudo-Gambas do algoritmo de comparação usado por Update:
Private Function Compare(Old As Variant, New As Variant) As Integer
If TypeOf(Old) <> gb.Object Or If TypeOf(New) <> gb.Object Then
Return CompareVariants(Old, New)
Else If HasIdentityFn(Old) And If HasIdentityFn(New) Then
Return CompareVariants(Old._identity(), New._identity())
Endif
Return Sgn(Object.Address(Old) - Object.Address(New))
End
Private Function HasIdentityFn(vValue As Variant) As Boolean
If Not TypeOf(vValue) = gb.Object Then Return False
' Queremos um método Public Function _identity() As Variant
Return Object.Class(vValue)["_identity"].Type = "v"
End
' CompareVariants é uma função que compara duas variantes com base nos
' tipos de dados de seus conteúdos. O núcleo interpretador sabe fazer isso.
Exemplo
Imagine que você está implementando o algoritmo de
Dijkstra (ou qualquer pesquisa de primeira prioridade
Like Prim ou A*). Você poderia usar um Heap para acompanhar a prioridade de seus nós.
Ao definir:
Public Sub _compare(hOther As Node) As Integer
Return Sgn(Me.Priority - hOther.Priority)
End
Primeiro você obtém os elementos de menor prioridade fora do heap (que é o que precisamos).
Quando necessário atualizar a prioridade de um nó e corrigir a sua posição na pilha, nós
não podemos utilizar o método _compare() para encontrar o nó porque muitos nós podem ter
a mesma prioridade e seria, portanto, indistinguíveis.
Aqui, você não precisa de um método _identity(). Para atualizar a prioridade da hNode a 17 e
corrigir a sua posição na pilha, você faz:
hNode.Priority = 17
hHeap.Update(hNode, hNode)