Module DescriptionThe act module implements an AVL binary tree with the key and data cell based. The act module is a specialisation of the bct module. As a result the bci iterator can be used as iterator on the act tree. The implementation is non-recursive. Module Wordsact% ( -- n ) Get the required space for an act variable
Tree creation, initialisation and destructionact-init ( act -- ) Initialise the act tree
act-(free) ( act -- ) Free the nodes from the heap
act-create ( "<spaces>name" -- ; -- act ) Create a named tree in the dictionary
act-new ( -- act ) Create a new tree on the heap
act-free ( act -- ) Free the tree from the heap
Member wordsact-length@ ( act -- u ) Get the number of elements in the tree
act-empty? ( act -- flag ) Check for an empty tree
act-compare@ ( act -- xt ) Get the compare execution token for comparing keys
act-compare! ( xt act -- ) Set the compare execution token for comparing keys
Tree wordsact-clear ( act -- ) Delete all nodes in the tree
act-insert ( x1 x2 act -- ) Insert data x1 with key x2 in the tree
act-delete ( x1 act -- false | x2 true ) Delete key x1 from the tree, return the data x2 if found
act-get ( x1 act -- false | x2 true ) Get the data x2 related to key x1 from the tree
act-has? ( x1 act -- flag ) Check if the key x1 is present in the tree
act-execute ( i*x xt act -- i*x ) Execute xt for every key and data in the tree
act-execute? ( i*x xt bct -- j*x flag ) Execute xt for every key and data in the tree until xt returns true
Inspectionact-dump ( act -- ) Dump the tree variable
Examplesinclude ffl/act.fs
include ffl/bci.fs
include ffl/str.fs
include ffl/enm.fs
\ Example1: store mountain height in a AVL tree with numerical keys
\ The mountain enumeration
begin-enumeration
enum: MountEverest
enum: MontBlanc
enum: MountElbrus
enum: Vaalserberg
end-enumeration
\ Create the AVL tree on the heap and store it in the heights variable
act-new value heights
\ Add the mountain heights in the tree; the key is the mountain enum value
8300 MountEverest heights act-insert
4819 MontBlanc heights act-insert
5642 MountElbrus heights act-insert
\ Find a mountain height in the tree
MontBlanc heights act-get [IF]
.( Mount:mont blanc height:) . cr
[ELSE]
.( Mount:mont blanc not in tree.) cr
[THEN]
Vaalserberg heights act-get [IF]
.( Mount:vaalserber height:) . cr
[ELSE]
.( Mount:vaalserberg not in tree.) cr
[THEN]
\ Free the heights tree from the heap
heights act-free
\ Example2: store mountain height in a AVL tree with string keys
\ Create the AVL tree in the dictionary
act-create mountains
\ Setup the compare word for comparing the mountain names
: mount-compare ( str str - n = Compare the two mountain names )
str^ccompare
;
' mount-compare mountains act-compare!
\ Add the mountain heights to the AVL tree; the key is the mountain name in a (unique) dynamic string
8300 str-new dup s" mount everest" rot str-set mountains act-insert
4819 str-new dup s" mont blanc" rot str-set mountains act-insert
5642 str-new dup s" mount elbrus" rot str-set mountains act-insert
\ Find a mountain height in the AVL tree
str-new value mount-name
s" mont blanc" mount-name str-set
mount-name mountains act-get [IF]
.( Mount:) mount-name str-get type
.( height:) . cr
[ELSE]
.( Mount:) mount-name str-get type .( not in tree.) cr
[THEN]
s" vaalserberg" mount-name str-set
mount-name mountains act-get [IF]
.( Mount:) mount-name str-get type
.( height:) . cr
[ELSE]
.( Mount:) mount-name str-get type .( not in tree.) cr
[THEN]
\ Word for printing the mountain heights
: mount-emit ( x x -- = Print mountain )
str-get type ." --> " . cr
;
\ Print all mountain heights
' mount-emit mountains act-execute \ Execute the word mount-emit for all entries in the tree
\ Example binary tree iterator
\ Create the tree iterator in the dictionary (use bci also for AVL trees)
mountains bci-create mount-iter \ Create an iterator named mount-iter on the mountains tree
\ Using the iterator
mount-iter bci-first [IF]
.( First mount:) mount-iter bci-key drop str-get type
.( height:) . cr
[ELSE]
.( No first mountain.) cr
[THEN]
mount-iter bci-last [IF]
.( Last mount:) mount-iter bci-key drop str-get type
.( height:) . cr
[ELSE]
.( No last mountain.) cr
[THEN]
\ Cleanup the tree
mountains act-clear
Generated by ofcfrth-0.10.0
|
