Gambas Documentation
Application Repository
Code Snippets
Compilation & Installation
Components
gb
gb.args
gb.cairo
gb.chart
gb.clipper
gb.complex
gb.compress
gb.crypt
gb.data
.List.Backwards
.List.Item
AvlTree
Circular
Deque
Heap
_new
Count
First
Insert
IsEmpty
Remove
Update
List
PrioQueue
Queue
Stack
Trie
TriePrefix
gb.db
gb.db.form
gb.db.mysql
gb.db.odbc
gb.db.postgresql
gb.db.sqlite2
gb.db.sqlite3
gb.dbus
gb.dbus.trayicon
gb.debug
gb.desktop
gb.desktop.gnome.keyring
gb.desktop.x11
gb.eval
gb.eval.highlight
gb.form
gb.form.dialog
gb.form.editor
gb.form.htmlview
gb.form.mdi
gb.form.print
gb.form.stock
gb.form.terminal
gb.gmp
gb.gsl
gb.gtk
gb.gtk.opengl
gb.gtk3
gb.gtk3.opengl
gb.gtk3.webview
gb.gui
gb.gui.opengl
gb.gui.qt
gb.gui.qt.ext
gb.gui.qt.opengl
gb.gui.qt.webkit
gb.gui.trayicon
gb.gui.webview
gb.hash
gb.highlight
gb.image
gb.image.effect
gb.image.imlib
gb.image.io
gb.inotify
gb.jit
gb.libxml
gb.logging
gb.map
gb.markdown
gb.media
gb.media.form
gb.memcached
gb.mime
gb.mysql
gb.ncurses
gb.net
gb.net.curl
gb.net.pop3
gb.net.smtp
gb.openal
gb.opengl
gb.opengl.glsl
gb.opengl.glu
gb.opengl.sge
gb.openssl
gb.option
gb.pcre
gb.pdf
gb.poppler
gb.qt4
gb.qt4.ext
gb.qt4.opengl
gb.qt4.webkit
gb.qt4.webview
gb.qt5
gb.qt5.ext
gb.qt5.opengl
gb.qt5.webkit
gb.qt5.webview
gb.qt6
gb.qt6.ext
gb.qt6.opengl
gb.qt6.webview
gb.report
gb.report2
gb.scanner
gb.sdl
gb.sdl.sound
gb.sdl2
gb.sdl2.audio
gb.settings
gb.signal
gb.term
gb.test
gb.util
gb.util.web
gb.v4l
gb.vb
gb.web
gb.web.feed
gb.web.form
gb.web.gui
gb.xml
gb.xml.html
gb.xml.rpc
gb.xml.xslt
Controls pictures
Deprecated components
Developer Documentation
Development Environment Documentation
Documents
Error Messages
Gambas Playground
How To's
Language Index
Language Overviews
Last Changes
Lexicon
README
Search the wiki
To Do
Topics
Tutorials
Wiki License
Wiki Manual

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)