# 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**)**