## bct - binary cell tree module

### Module Description

The bct module implements an unbalanced binary tree with the key and data cell based. The implementation is non-recursive.

### Module Words

#### Binary tree structure

bct% ( -- n )
  Get the required space for a bct variable

#### Tree creation, initialisation and destruction

bct-init ( bct -- )
  Initialise the tree
bct-(free) ( bct -- )
  Free the nodes from the heap
bct-create ( "<spaces>name" -- ; -- bct )
  Create a named binary tree in the dictionary
bct-new ( -- bct )
  Create a new binary tree on the heap
bct-free ( bct -- )
  Free the tree node from the heap

#### Member words

bct-length@ ( bct -- u )
  Get the number of elements in the tree
bct-empty? ( bct -- flag )
  Check for an empty tree
bct-compare@ ( bct -- xt )
  Get the compare execution token for comparing keys
bct-compare! ( xt bct -- )
  Set the compare execution token for comparing keys

#### Tree words

bct-clear ( bct -- )
  Delete all nodes in the tree
bct-insert ( x1 x2 bct -- )
  Insert data x1 with key x2 in the tree
bct-delete ( x1 bct -- false | x2 true )
  Delete key x1 from the tree, return the cell data x2
bct-get ( x1 bct -- false | x2 true )
  Get the data x2 related to key x1 from the tree
bct-has? ( x1 bct -- flag )
  Check if the key x1 is present in the tree
bct-execute ( i*x xt bct -- j*x )
  Execute xt for every key and data in the tree
bct-execute? ( i*x xt bct -- j*x flag )
  Execute xt for every key and data in the tree until xt returns true

#### Inspection

bct-dump ( bct -- )
  Dump the tree node structure

### Examples

    include ffl/bct.fs
    include ffl/bci.fs
    include ffl/str.fs
    include ffl/enm.fs

    \ Example1: store mountain height in a binary tree with numerical keys

    \ The mountain enumeration

    begin-enumeration
      enum: MountEverest
      enum: MontBlanc
      enum: MountElbrus
      enum: Vaalserberg
    end-enumeration

    \ Create the binary tree on the heap and store it in the heights variable

    bct-new value heights

    \ Add the mountain heights in the tree; the key is the mountain enum value

    8300 MountEverest heights bct-insert
    4819 MontBlanc    heights bct-insert
    5642 MountElbrus  heights bct-insert

    \ Find a mountain height in the tree

    MontBlanc heights bct-get [IF]
      .( Mount:mont blanc height:) . cr
    [ELSE]
      .( Mount:mont blanc not in tree.) cr
    [THEN]

    Vaalserberg heights bct-get [IF]
      .( Mount:vaalserber height:) . cr
    [ELSE]
      .( Mount:vaalserberg not in tree.) cr
    [THEN]

    \ Free the heights tree from the heap

    heights bct-free

    \ Example2: store mountain height in a binary tree with string keys

    \ Create the binary tree in the dictionary

    bct-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 bct-compare!

    \ Add the mountain heights to the binary tree; the key is the mountain name in a (unique) dynamic string

    8300 str-new dup s" mount everest" rot str-set  mountains bct-insert
    4819 str-new dup s" mont blanc"    rot str-set  mountains bct-insert
    5642 str-new dup s" mount elbrus"  rot str-set  mountains bct-insert

    \ Find a mountain height in the binary tree

    str-new value mount-name

    s" mont blanc" mount-name str-set

    mount-name mountains bct-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 bct-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 bct-execute       \ Execute the word mount-emit for all entries in the tree

    \ Example binary tree iterator

    \ Create the tree iterator in the dictionary

    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 bct-clear

generated 03-Jun-2010 by ofcfrth-0.10.0