Heap.Update (gb.data)
Sub Update ( Old As Variant, New As Variant )
Trova tutte le occorrenze di
Old e le sostituiscile con
New. Cerca nell'intero heap quindi è di per sé un'operazione O(n).
Inoltre, l'heap deve essere ricostruito non appena viene effettuata più di una sostituzione che è di nuovo un'operazione O(n). Se viene effettuata esattamente una sostituzione, possiamo cavarcela con una singola operazione O(log n).
Se
New è Null, la voce verrà eliminata, anche O(log n) per correggere la struttura dell'heap.
Algoritmo di confronto per l'Update
La ricerca di oggetti viene eseguita da
identity e
non utilizzando il metodo _compare(). "Identity" significa che se si devono confrontare due oggetti ed entrambi hanno un metodo speciale _identity() che restituisce una variante, i valori di ritorno di questi metodi vengono confrontati. Se uno degli oggetti non implementa il metodo _identity(), si torna al confronto in base agli indirizzi degli oggetti in memoria. Lo speciale metodo _compare() non è
mai utilizzato nell'algoritmo Update.
Questa strategia consente di salvare nell'heap tipi di dati primitivi (booleani, interi, stringhe, ecc.) senza problemi. Ma può anche gestire oggetti
distinti nelle classi di equivalenza: il metodo _compare() definisce la tua relazione di equivalenza (in quale modo gli oggetti sono approssimativamente ordinati nell'heap) e il confronto delle identità consente di discernere oggetti diversi, anche della stessa classe (per aggiornarli singolarmente).
Il metodo _identity() lascia a te il significato di "identità". Se è necessario aggiornare intere classi di equivalenza alla volta, è possibile definire _identity() in modo che corrisponda anche al metodo _compare().
È un mezzo puramente facoltativo per raggruppare gli oggetti in modo diverso.
Ecco un frammento pseudo-Gambas dell'algoritmo di confronto utilizzato da 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
' Vogliamo un metodo Public Function _identity() As Variant
Return Object.Class(vValue)["_identity"].Type = "v"
End
' CompareVariants è una funzione che confronta due varianti
' in base ai tipi di dati dei loro contenuti effettivi.
' Il nucleo dell'interprete sa come farlo.
Esempio
Immagina di implementare l'algoritmo di Dijkstra (o qualsiasi prioritaria ricerca iniziale come Prim o A*). È possibile utilizzare un heap per tenere traccia della priorità dei tuoi nodi.
Definendo:
Public Sub _compare(hOther As Node) As Integer
Return Sgn(Me.Priority - hOther.Priority)
End
si ottengono dall'heap prima gli elementi con la priorità più bassa (che è ciò di cui abbiamo bisogno).
Quando è necessario aggiornare la priorità di un nodo e correggere la sua posizione nell'heap, non è possibile utilizzare il metodo _compare() per trovare il nodo perché molti nodi potrebbero avere la stessa priorità e sarebbero quindi indistinguibili.
Qui, non è necessario un metodo _identity(). Per aggiornare la priorità di hNode su 17 e correggerne la posizione nell'heap, fai:
hNode.Priority = 17
hHeap.Update(hNode, hNode)