Heap.Update (gb.data)

Sub Update ( Old As Variant, New As Variant )

Find all occurences of Old and replace them by New. It searches the entire heap and is thus an O(n) operation per se.

Additionally the heap has to be rebuilt as soon as there is more than one replacement made which is O(n) again. If exactly one replacement is made, we can get away with a single O(log n) operation.

If New is Null, then the entry will be deleted, also O(log n) to fix the heap structure.

Comparison algorithm for Update

The search for objects is done by identity and not by using the _compare() method. "By identity" means that if two objects are to be compared and both have a special _identity() method returning a Variant, the return values of these methods are compared. If one of the objects does not implement the _identity() method, we fall back to comparison by object addresses in memory. The special _compare() method is never used in the Update algorithm.

This strategy lets you save primitive data types (Boolean, Integer, String, etc.) in the heap seamlessly. But you can also manage distinct objects in equivalence classes: The _compare() method defines your equivalence relation (how objects are roughly ordered in the heap) and the identity comparison enables to discern different objects, even of the same class (in order to update them individually).

The _identity() method leaves it up to you what "identity" really means. If you need to update whole equivalence classes at a time, you can define _identity() to match your _compare() method, too.

It is a purely optional means of grouping objects differently.

Here is a pseudo-Gambas snippet of the comparison algorithm used by 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
  ' We want a method Public Function _identity() As Variant
  Return Object.Class(vValue)["_identity"].Type = "v"
End

' CompareVariants is a function which compares two Variants based on
' their actual contents' data types. The interpreter core knows how
' to do that.

Example

Imagine you are implementing Dijkstra's algorithm (or any priority first search like Prim or A*). You could use a Heap to keep track of the priority of your nodes. By defining:

Public Sub _compare(hOther As Node) As Integer
Return Sgn(Me.Priority - hOther.Priority)
End

you get the lowest-priority elements out of the heap first (which is what we need).

When we need to update a node's priority and correct its position in the heap, we cannot possibly use the _compare() method to find the node because many nodes may have the same priority and would thus be indistinguishable.

Here, you don't need an _identity() method. To update hNode's priority to 17 and correct its position in the heap, you do:

hNode.Priority = 17
hHeap.Update(hNode, hNode)