Hi,
I just realized that there seemingly is no code snippet implementing trees in Dark Basic - at least I did not find a thread on that topic.
Consequently I wrote a small library doing just that: allowing you to build and manipulate trees with arbitrary branching factor (i.e. it is not limited to binary trees).
The following functions are available:
Quote: "
tree_init() - has to be called once, before using any other tree-function
rootnode = tree_new(key) - creates a new tree
node = tree_addNode(parent, key) - adds a node to the given parent-node
tree_DeleteLeafNode(node) - removes a childless node from a tree
tree_DeleteSubtree(root) - deletes a complete subtree defined by the given root
tree_CutSubtree(root) - Removes a subtree from the tree it's currently in and makes a separate tree out of it
tree_SetParent(node, newParent) - takes a subtree and puts it somewhere else
n = tree_getChildcount(node)
node = tree_GetFirstChild(node) - returns the first child of an inner node (0 if node is a leaf)
node = tree_GetNextChild(node) - returns 0 if there are no more childs in the list
bool = tree_isPredecessor(node1, node2) - returns 1 if node1 is predecessor of node2 (i.e. node1 is element of the transitive closure of node2 induced by its parent-attribute)
string = tree_toString(root) - can be used for debugging purposes, it takes a (sub)tree and converts it to a string of the form "key_of_node [ keys_of_children ] keys_of_siblings"
"
Note that I've not fully tested all those functions yet, but in case something is wrong with them I'll probably notice that since I'm going to rely on this library quite heavily in a project I'm currently working on.
So if I encounter a bug I'll make sure to fix it and update the code below, so you can be (almost) sure that it works well.
Now about the application: You obviously cannot just make trees for the sole purpose of having trees of numbers - they are actually pretty handy in certain situations.
For instance, the reason why I made this library in the first place is, as indicated above, my current project. Part of this project is an interface including windows, frames and so on. Those can be structured in a tree-like way: One frame lies within another frame, which is child of a window.
The tree-library provides the required functionality: I simply create a container()-array which includes all those windows, frames etc. as well as their attributes. Furthermore each container is associated to a node, and the array-ID of the container is used as the node's key. This way I can structure the whole arrangement of containers.
The tree is then used when, for instance, drawing the scene. I initially created a tree using "containerTree = tree_new(0)", all following containers are children of either this containerTree or of other containers. So drawing can be done recursively, with an approach similar to "drawMyself first, then draw my Children" which can be realized with tree_GetFirstChild and tree_GetNextChild.
On top of that I use the library for another purpose at the same time - a command history. Using an "undo"-feature traces back inside this history-tree, another action then opens up a new branch. Using a tree instead of a list here allows me to show the user the complete history of his/her actions, allowing him/her to go back to
any previous state of the document. As consequence it is impossible to lose changes by undoing them, which can easily happen with, say, usual text editing software.
OK then, enough about that.
Here's the code:
remstart
Code by MrKohlenstoff
V 0.1, 20th February 2012
Use or alter it however you want - if you name me
in the credits section of your project, I'll certainly
feel honoured. :)
remend
#constant tree_NODESTEP = 1024
rem Call this function _once_ at the beginning of your program
function tree_init()
rem Node Array
global tree_Capacity as integer = tree_NODESTEP
global tree_Nodes as integer = 0
dim tree_Node(tree_Capacity) as tree_Type
rem Free List
global tree_FreeCapacity as integer = tree_NODESTEP
global tree_FreeNodes as integer = 0
dim tree_Free(tree_FreeCapacity) as integer
endfunction
type tree_Type
key as integer
firstChild as integer
currentChild as integer
childCount as integer
sibling as integer
parent as integer
endtype
function tree_toString(root)
s$ = str$(tree_node(root).key) + " [ " + tree__toString(tree_node(root).firstChild) + "]"
endfunction s$
rem Create a new separate Tree using this function
rem you can use more than one tree at once without them interfering each other
function tree_new(key)
root = tree_addNode(0,key)
endfunction root
rem Add a node to any tree by appending it to a given parent node
function tree_addNode(parent,key)
ID = tree__newNode()
tree_node(ID).key = key
tree_node(ID).firstChild = 0
tree_node(ID).childCount = 0
tree_node(ID).parent = parent
tree_node(ID).sibling = 0
tree__addChildToParent(parent, ID)
endfunction ID
rem Use this function to remove a leaf node from a tree
rem Note: Make sure to check whether it's actually a root node - otherwise the tree will get inconsistent!
function tree_DeleteLeafNode(node)
tree__removeFromParentsChildlist(node)
endfunction
rem Remove a whole subtree, defined by the given root node, from any tree
function tree_DeleteSubtree(root)
rem First: Remove all children recursively
tree__DeleteSubtree( tree_node(root).firstChild )
rem Second: Remove this node
tree_DeleteLeafNode(root)
endfunction
rem Use this function to separate a subtree (defined by its root node) from
rem the tree its in - afterwards the given node will be root of a new tree
function tree_CutSubtree(node)
tree_SetParent(node, 0)
endfunction
rem Use this function to append a node as well as its implied subtree to
rem another node (from the original or any other tree)
function tree_SetParent(node, parent)
if tree_isPredecessor(node, parent) = 0
tree__removeFromParentsChildlist(node)
tree__AddChildToParent(parent, node)
endif
endfunction
rem Returns the amount of children owned by the given node
function tree_getChildCount(node)
r = tree_Node(node).childCount
endfunction r
rem Returns the node ID of the first child of this node
rem Call this function once when iterating through the children of a node, use tree_getNextChild(node) afterwards
function tree_getFirstChild(node)
r = tree_Node(node).firstChild
tree_Node(node).currentChild = r
endfunction r
rem Returns the node ID of the next child of the given node
rem if there are no more children, this function will return '0'
function tree_getNextChild(node)
r = tree_Node( tree_Node(node).currentChild ).sibling
tree_Node(node).currentChild = r
endfunction r
rem Returns '1' if the given node1 is a successor of node2
function tree_isPredecessor(node1,node2)
if tree_Node(node2).parent = 0
rem Case 1: Node 2 is root -> False
r = 0
else
if tree_Node(node2).parent = node1
rem Case 2: Node 1 is father of Node 2 -> True
r = 1
else
rem Case 3: Maybe indirect relationship -> Recursion
r = tree_isPredecessor(node1, tree_Node(node2).parent)
endif
endif
endfunction r
remstart
*** NOTE: ALL FUNCTIONS BELOW ARE MEANT TO BE INTERNAL ***
*** DON'T USE THEM UNLESS YOU'RE TOTALLY SURE WHAT YOU'RE DOING ***
remend
function tree__newNode()
if tree_FreeNodes = 0
inc tree_Nodes
if tree_Nodes > tree_Capacity
inc tree_Capacity, tree_NODESTEP
array insert at bottom tree_node(), tree_NODESTEP
endif
ID = tree_Nodes
else
ID = tree_Free(tree_FreeNodes)
dec tree_FreeNodes
endif
endfunction ID
function tree__delNode(ID)
inc tree_FreeNodes
if tree_FreeNodes > tree_FreeCapacity
inc tree_FreeCapacity, tree_NODESTEP
array insert at bottom tree_Free(), tree_NODESTEP
endif
tree_Free(tree_FreeNodes) = ID
endfunction
function tree__addChildToParent(parent, node)
inc tree_node(parent).childCount
tree_node(node).parent = parent
tree_node(node).sibling = tree_node(parent).firstChild
tree_node(parent).firstChild = node
endfunction
function tree__DeleteSubtree( node )
if node <> 0
rem Siblings
tree__DeleteSubtree( tree_Node(node).sibling )
rem Children
tree__DeleteSubtree( tree_Node(node).firstChild )
rem Self
tree_DeleteLeafNode(node)
endif
endfunction
function tree__removeFromParentsChildlist(node)
parent = tree_Node(node).parent
rem Apply child count
dec tree_node(parent).childCount
rem Remove Child from list
if tree_node(parent).firstChild = node
rem Node is parent's first Child
tree_node(parent).firstChild = tree_node(node).sibling
else
rem Node is somewhere deeper inside parent's child list
cur = tree_node(parent).firstChild
while tree_node(cur).sibling <> node : cur = tree_node(cur).sibling : endwhile
tree_node(cur).sibling = tree_node(node).sibling
endif
rem Make sure Node has no reference to old siblings anymore
tree_node(node).sibling = 0
endfunction
function tree__toString(node)
if node = 0
s$ = ""
else
s$ = str$(tree_node(node).key)
if tree_node(node).childCount > 0
s$ = s$ + " [ " + tree__toString( tree_node(node).firstChild ) + "] "
endif
s$ = s$ + " " + tree__toString( tree_node(node).sibling )
endif
endfunction s$
I hope it helps.
Thanks for your interest.
Questions, comments, suggestions and criticism are welcome.
Have a nice day,
MrK
