PureBasic Forums - English

Code: Select all

                    | PB's built-in map | AA tree
                    | (= hash table)    |
--------------------+-------------------+------------------
ordered enumeration | not               | time
of all items        | provided          | O(n)
--------------------+-------------------+------------------
                    | worst-case time   | worst-case time
lookup,             | O(n)              | O(log n)
insertion           +-------------------+------------------
or removal          | average-case time | average-case time
of an item          | under reasonable  |
                    | conditions        |
                    | O(1)              | O(log n)

Code: Select all

; AA-Tree (self-balancing binary tree) 1.10m
; PB 5.11 (& PB 5.70 beta 1)
; Luis, April 2013 (& Little John, July 2018)
;
; http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
; http://en.wikipedia.org/wiki/AA_tree
;
; This implementation supports:
; insert, search, delete, automatic enumeration in ascending and descending order for the whole tree or a single subtree, manual navigation of the tree.

; You can use it with just the key (a string), or you can associate optional external data to each stored key through a user value.
; See the examples for more info.

; 1.00 (april 2013)
; first version

; 1.01 (april 2013)
; minor modifications to examples and added one assert

; 1.10 (may 2013)
; modified the enumeration API and added manual navigation
; changed EnumStart(), EnumNext() and added EnumStartFromCurrent() 
; added : GetNodeValue(), GetNodeKey(), IsCurrentNode()
; added : IsLeft(), IsRight(), GoRoot(), GoLeft(), GoRight()
; examples updated and added a new example (TEST6)

; 1.10m (July 2018) -- by Little John
; - wrapped in a module, and changed names of public procedures and constants
; - Instead of Luis' "Assert.pb" this version just uses PB's built in Assert() macro
;   (file "PureUnit.res" must be located in the "Residents\" subfolder).


DeclareModule AAT
   #EnumAscending = 0
   #EnumDescending = 1
   
   Structure T_AAT_NODE
      *left.T_AAT_NODE
      *right.T_AAT_NODE
      key$
      value.i
      level.i
   EndStructure
   
   Structure T_AAT
      *root.T_AAT_NODE
      *EnumCurrentNode.T_AAT_NODE
      *CurrentNode.T_AAT_NODE
      *fpFreeItem
      EnumDirection.i
      EnumInProgress.i
      TotalNodes.i
      LastPathLength.i   
      Modified.i 
   EndStructure
   
   ; create new tree with optional callback to free user-allocated elements
   Declare.i New (*fpFreeItem = 0)
   
   ; destroy the tree
   Declare Destroy (*tree.T_AAT)
   
   ; clear the tree
   Declare.i Clear (*tree.T_AAT)
   
   ; return the num of nodes
   Declare.i CountNodes (*tree.T_AAT)
   
   ; the len of the last path followed to access an item
   Declare.i GetLastPathLength (*tree.T_AAT)
   
   ; start enumeration (tree become temporart read-only)
   Declare.i EnumStart (*tree.T_AAT, direction = #EnumAscending)
   
   ; start enumeration from the current node (tree become temporart read-only)
   Declare.i EnumStartFromCurrent (*tree.T_AAT, direction = #EnumAscending)
   
   ; stop enumeration
   Declare.i EnumEnd (*tree.T_AAT)
   
   ; get the key of the next node and optionally the user data value if any
   Declare.i EnumNext (*tree.T_AAT) 
   
   ; insert a new key in the tree and optionally associate the user data value if any
   Declare.i Insert (*tree.T_AAT, key$, value = 0)
   
   ; search for a key in the tree and optionally return the associated user data value if any
   Declare.i Search (*tree.T_AAT, key$, *value.Integer = 0)
   
   ; delete a key from the tree and optionally return the associated user data value if any
   Declare.i Delete (*tree.T_AAT, key$, *value.Integer = 0)
   
   ; check if there is a current node or not
   Declare.i IsCurrentNode (*tree.T_AAT)
   
   ; get the key of the current node
   Declare.s GetNodeKey (*tree.T_AAT)
   
   ; get the value (if any) associated with the current node
   Declare.i GetNodeValue (*tree.T_AAT)
   
   ; check if there is a node to the left of the current node
   Declare.i IsLeft (*tree.T_AAT)
   
   ; check if there is a node to the right of the current node
   Declare.i IsRight (*tree.T_AAT)
   
   ; set the current node to the root
   Declare.i GoRoot (*tree.T_AAT)
   
   ; set the current node to the node at the left of the current node
   Declare.i GoLeft (*tree.T_AAT)
   
   ; set the current node to the node at the right of the current node
   Declare.i GoRight (*tree.T_AAT)
EndDeclareModule


Module AAT
   EnableExplicit
   
   ;********************************************************************
   ;- PRIVATE
   ;********************************************************************
   
   Procedure.i _AAT_Min (iVal1, iVal2)
      If iVal1 < iVal2
         ProcedureReturn iVal1
      EndIf 
      ProcedureReturn iVal2 
   EndProcedure
   
   Procedure.i _AAT_Split (*node.T_AAT_NODE)
      Protected *Right.T_AAT_NODE
      
      If *node = #Null
         ProcedureReturn #Null
      EndIf
      
      If *node\right = #Null Or *node\right\right = #Null
         ProcedureReturn *node
      EndIf
      
      If *node\level = *node\right\right\level
         *Right = *node\right
         *node\right = *Right\left
         *Right\left = *node
         *Right\level + 1
         ProcedureReturn *Right
      EndIf
      
      ProcedureReturn *node
   EndProcedure
   
   Procedure.i _AAT_Skew (*node.T_AAT_NODE)
      Protected *Left.T_AAT_NODE
      
      If *node = #Null
         ProcedureReturn #Null
      EndIf
      
      If *node\left = #Null
         ProcedureReturn *node
      EndIf
      
      If *node\left\level = *node\level
         *Left = *node\left
         *node\left = *Left\right
         *Left\right = *node
         ProcedureReturn *Left
      Else
         ProcedureReturn *node
      EndIf
   EndProcedure
   
   Procedure.i _AAT_DecreaseLevel (*node.T_AAT_NODE)
      Protected target, ll = 0, lr = 0
      
      ASSERT(*node <> #Null)
      
      If *node\left
         ll = *node\left\level
      EndIf
      
      If *node\right
         lr = *node\right\level
      EndIf
      
      target = _AAT_Min(ll, lr) + 1
      
      If target < *node\level
         *node\level = target
         If *node\right
            If target < *node\right\level
               *node\right\level = target
            EndIf
         EndIf
      EndIf
      ProcedureReturn *node
   EndProcedure
   
   Procedure.i _AAT_Predecessor (*node.T_AAT_NODE)
      If *node\right
         ProcedureReturn _AAT_Predecessor(*node\right)
      EndIf
      ProcedureReturn *node
   EndProcedure
   
   Procedure.i _AAT_Successor (*node.T_AAT_NODE)
      If *node\left
         ProcedureReturn _AAT_Successor(*node\left)
      EndIf
      ProcedureReturn *node
   EndProcedure
   
   Procedure _AAT_Free (*tree.T_AAT, *node.T_AAT_NODE)
      If *node
         _AAT_Free (*tree, *node\left)
         _AAT_Free (*tree, *node\right)
         
         If *tree\fpFreeItem         
            CallFunctionFast(*tree\fpFreeItem, *node\value)
         EndIf
         
         *tree\TotalNodes - 1   
         ClearStructure(*node, T_AAT_NODE)
         FreeMemory(*node)   
      EndIf
   EndProcedure
   
   Procedure.i _AAT_Delete (*tree.T_AAT, *node.T_AAT_NODE, *key, *value.Integer = 0)
      Protected *Left.T_AAT_NODE
      
      *tree\LastPathLength + 1
      
      If *node = #Null
         ProcedureReturn *node
      EndIf
      
      If PeekS(*key) > *node\key$
         *node\right = _AAT_Delete(*tree, *node\right, *key, *value)
         
      ElseIf PeekS(*key) < *node\key$
         *node\left = _AAT_Delete(*tree, *node\left, *key, *value)   
         
      Else
         
         *tree\Modified = #True
         
         If *node\left = #Null And *node\right = #Null ; leaf
            If *value
               *value\i = *node\value
            EndIf
            ProcedureReturn #Null
         EndIf
         
         If *node\left = #Null
            *Left = _AAT_Successor(*node\right)
            *node\right = _AAT_Delete(*tree, *node\right, @*Left\key$, *value)
         Else
            *Left = _AAT_Predecessor(*node\left)
            *node\left = _AAT_Delete(*tree, *node\left, @*Left\key$, *value)
         EndIf       
         
         If *value
            *value\i = *node\value
         EndIf   
         
         *node\key$ = *Left\key$   
         *node\value = *Left\value
      EndIf
      
      *node = _AAT_DecreaseLevel(*node)
      
      *node = _AAT_Skew(*node)
      
      *node\right = _AAT_Skew(*node\right)
      
      If *node\right
         *node\right\right = _AAT_Skew(*node\right\right)
      EndIf
      
      *node = _AAT_Split(*node)
      
      *node\right = _AAT_Split(*node\right)   
      
      ProcedureReturn *node
   EndProcedure
   
   Procedure.i _AAT_Insert (*tree.T_AAT, *node.T_AAT_NODE, *key, value) 
      *tree\LastPathLength + 1
      
      If *node = #Null
         *node = AllocateMemory(SizeOf(T_AAT_NODE))   
         ASSERT(*node, "Out of memory.")
         
         *node\key$ = PeekS(*key)
         *node\value = value
         *node\level = 1
         *tree\CurrentNode = *node
         *tree\Modified = #True           
         ProcedureReturn *node
         
      ElseIf PeekS(*key) < *node\key$
         *node\left = _AAT_Insert (*tree, *node\left, *key, value)   
      ElseIf PeekS(*key) > *node\key$
         *node\right = _AAT_Insert (*tree, *node\right, *key, value)     
      EndIf       
      
      *node = _AAT_Skew(*node)
      
      *node = _AAT_Split(*node)
      
      ProcedureReturn *node
   EndProcedure
   
   Procedure.i _AAT_Search (*tree.T_AAT, *node.T_AAT_NODE, *key)   
      *tree\LastPathLength + 1
      
      If *node
         If PeekS(*key) < *node\key$   
            ProcedureReturn _AAT_Search (*tree, *node\left, *key)       
         ElseIf PeekS(*key) > *node\key$   
            ProcedureReturn _AAT_Search (*tree, *node\right, *key)       
         Else   
            ProcedureReturn *node       
         EndIf
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i _AAT_EnumNextAscending (*tree.T_AAT)
      Protected *pre.T_AAT_NODE
      
      While *tree\EnumCurrentNode
         If *tree\EnumCurrentNode\left = 0
            
            *tree\CurrentNode = *tree\EnumCurrentNode
            
            *tree\EnumCurrentNode = *tree\EnumCurrentNode\right
            
            ProcedureReturn 1
         Else
            *pre = *tree\EnumCurrentNode\left
            
            While *pre\right And *pre\right <> *tree\EnumCurrentNode
               *pre = *pre\right
            Wend
            
            If *pre\right = 0
               *pre\right = *tree\EnumCurrentNode
               *tree\EnumCurrentNode = *tree\EnumCurrentNode\left
            Else
               *pre\right = #Null
               
               *tree\CurrentNode = *tree\EnumCurrentNode
               
               *tree\EnumCurrentNode = *tree\EnumCurrentNode\right
               
               ProcedureReturn 1
            EndIf               
         EndIf
      Wend
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i _AAT_EnumNextDescending (*tree.T_AAT)
      Protected *pre.T_AAT_NODE
      
      While *tree\EnumCurrentNode
         If *tree\EnumCurrentNode\right = 0
            
            *tree\CurrentNode = *tree\EnumCurrentNode
            
            *tree\EnumCurrentNode = *tree\EnumCurrentNode\left
            
            ProcedureReturn 1
         Else
            *pre = *tree\EnumCurrentNode\right
            
            While *pre\left And *pre\left <> *tree\EnumCurrentNode
               *pre = *pre\left
            Wend
            
            If *pre\left = 0
               *pre\left = *tree\EnumCurrentNode
               *tree\EnumCurrentNode = *tree\EnumCurrentNode\right
            Else
               *pre\left = #Null
               
               *tree\CurrentNode = *tree\EnumCurrentNode
               
               *tree\EnumCurrentNode = *tree\EnumCurrentNode\left
               
               ProcedureReturn 1
            EndIf               
         EndIf
      Wend
      
      ProcedureReturn 0
   EndProcedure
   
   
   
   ;********************************************************************
   ;- PUBLIC
   ;********************************************************************
   
   Procedure.i New (*fpFreeItem = 0)
      ; *fpFreeItem is to call an optional callback if you used external data and you want to remove that data too automatically.
      ; Please note sometimes this is not what you want, because the same data can be associated to different datastructures for example,
      ; or because the data must continue to live on even if a tree has been cleared/destroyed.
      ; But some other times when the data and the tree are really one and the same you can find the callback useful.
      
      Protected *tree.T_AAT
      
      *tree = AllocateMemory(SizeOf(T_AAT))
      
      ASSERT(*tree, "Out of memory.")
      
      ClearStructure(*tree, T_AAT)
      
      *tree\fpFreeItem = *fpFreeItem
      
      ProcedureReturn *tree
   EndProcedure
   
   Procedure Destroy (*tree.T_AAT)
      ; Release the tree
      
      ASSERT(*tree)
      
      If *tree\root
         _AAT_Free(*tree, *tree\root)
         ClearStructure(*tree, T_AAT)
         FreeMemory(*tree)
      EndIf
   EndProcedure
   
   Procedure.i Clear (*tree.T_AAT)
      ; Clear the tree
      
      ASSERT(*tree)
      
      If *tree\root
         _AAT_Free(*tree, *tree\root)
         ClearStructure(*tree, T_AAT)
      EndIf
   EndProcedure
   
   Procedure.i CountNodes (*tree.T_AAT)
      ; Return the number of nodes in the tree
      
      ASSERT(*tree)
      
      ProcedureReturn *tree\TotalNodes
   EndProcedure
   
   Procedure.i GetLastPathLength (*tree.T_AAT)
      ; Return the length of the last path walked for the last search/insert/delete operation.
      
      ASSERT(*tree)
      
      ProcedureReturn *tree\LastPathLength
   EndProcedure
   
   Procedure.i EnumEnd (*tree.T_AAT)
      ; End the current enumeration sequence and unlock the tree to allow modifications.
      ; The current node is undefined after calling this.
      
      ASSERT(*tree)
      ASSERT(*tree\EnumInProgress = 1, "Enumeration is not in progress.")
      
      *tree\CurrentNode = 0
      *tree\EnumCurrentNode = 0
      *tree\EnumInProgress = 0
   EndProcedure
   
   Procedure.i EnumStart (*tree.T_AAT, direction = #EnumAscending)
      ; Prepare the tree to be enumerated with AAT_EnumNext() in ascending or descending order.
      ; Return 1 if ready to enumerate, 0 in case of error (tree empty)
      ; The current node is undefined after calling this.
      
      ASSERT(*tree)
      ASSERT(*tree\EnumInProgress = 0, "Enumeration is already in progress.")
      ASSERT(direction = #EnumAscending Or direction = #EnumDescending)
      
      *tree\EnumCurrentNode = *tree\root
      *tree\CurrentNode = 0
      *tree\EnumInProgress = 1
      *tree\EnumDirection = direction
      
      If *tree\TotalNodes 
         ProcedureReturn 1
      EndIf
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i EnumStartFromCurrent (*tree.T_AAT, direction = #EnumAscending)
      ; Like EnumStart, but from the current node instead of the root.
      ; The current node is undefined after calling this.
      
      ASSERT(*tree)
      ASSERT(*tree\EnumInProgress = 0, "Enumeration is already in progress.")
      ASSERT(direction = #EnumAscending Or direction = #EnumDescending)
      
      *tree\EnumCurrentNode = *tree\CurrentNode
      *tree\CurrentNode = 0
      *tree\EnumInProgress = 1
      *tree\EnumDirection = direction
      
      If *tree\TotalNodes 
         ProcedureReturn 1
      EndIf
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i EnumNext (*tree.T_AAT)
      ; Enumerate the next node from the tree, setting the current node to it.
      ; Return 0 if there are not more items to enumerate.
      ; NOTE: You cannot alter the tree structure while an enumeration is in progress (no insert / no delete).
      
      ASSERT(*tree)
      ASSERT(*tree\EnumInProgress = 1)
      
      If *tree\EnumDirection = #EnumAscending
         ProcedureReturn _AAT_EnumNextAscending (*tree)
      Else
         ProcedureReturn _AAT_EnumNextDescending (*tree)
      EndIf
   EndProcedure
   
   Procedure.i Insert (*tree.T_AAT, key$, value = 0)   
      ; Insert a new item in the tree using key$, with an optional value.
      ; At least you need to specify the key, value is optional and it's usually a pointer.
      ; Return 1 if the item is inserted, else 0 (an item with that key was already present or the tree is being enumerated).
      ; The current node is set to the one just inserted.
      
      Protected *node.T_AAT_NODE
      
      ASSERT(*tree)
      ASSERT(Len(key$))
      ASSERT(*tree\EnumInProgress = 0, "Tree is locked for enumeration.")
      
      If *tree\EnumInProgress = 0
         *tree\LastPathLength = 0
         
         *node = _AAT_Insert(*tree, *tree\root, @key$, value)
         
         ASSERT(*node)
         
         *tree\root = *node
         
         If *tree\Modified
            *tree\Modified = #False
            *tree\TotalNodes + 1       
            ProcedureReturn 1
         EndIf
      EndIf
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i Search (*tree.T_AAT, key$, *value.Integer = 0)   
      ; Search for an item in the tree using key$.
      ; If *value is not null, copy the associated value there.
      ; Return 1 if the item is found, else 0.
      ; The current node is set to the one found.
      
      Protected *node.T_AAT_NODE
      
      ASSERT(*tree)
      ASSERT(Len(key$))
      
      *tree\LastPathLength = 0
      
      *node = _AAT_Search(*tree, *tree\root, @key$) 
      
      If *node
         If *value 
            *value\i = *node\value
         EndIf
         *tree\CurrentNode = *node
         ProcedureReturn 1
      EndIf   
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i Delete (*tree.T_AAT, key$, *value.Integer = 0)   
      ; Delete the item indexed by key$ from the tree.
      ; If *value is not null, copy the associated value there.
      ; Return 1 if the item has been deleted, else 0 (item not found or the tree is being enumerated).
      ; The current node is undefined after calling this.
      
      Protected *node.T_AAT_NODE
      Protected local_value
      
      ASSERT(*tree)
      ASSERT(Len(key$))
      ASSERT(*tree\EnumInProgress = 0, "Tree is locked for enumeration.")
      
      If *tree\EnumInProgress = 0
         *tree\LastPathLength = 0
         
         *node = _AAT_Delete (*tree, *tree\root, @key$, @local_value)
         
         ASSERT((*node > 0) Or (*node = 0 And *tree\TotalNodes = 1))
         
         *tree\root = *node
         
         If *tree\Modified
            If *tree\fpFreeItem         
               CallFunctionFast(*tree\fpFreeItem, local_value)
            EndIf           
            
            If *value
               *value\i = local_value
            EndIf
            
            *tree\Modified = #False
            *tree\TotalNodes - 1       
            ProcedureReturn 1
         EndIf
      EndIf
      
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i IsCurrentNode (*tree.T_AAT)
      ; Return 1 if there is a current node, else 0 (current node is undefined: do a search or an insertion)
      ; If AAT_Search() is successful changes the current node to the one just found.
      ; If AAT_Insert() is successful changes the current node to the one just inserted.
      ; If AAT_Delete() is successful changes the current node to undefined.
      
      ASSERT(*tree)
      
      If *tree\CurrentNode
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.s GetNodeKey (*tree.T_AAT)
      ; Get the key of the current node
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode
         ProcedureReturn *tree\CurrentNode\key$
      EndIf
      ProcedureReturn ""
   EndProcedure
   
   Procedure.i GetNodeValue (*tree.T_AAT)
      ; Get the value (if any) associated with the current node.
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode
         ProcedureReturn *tree\CurrentNode\value
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i IsLeft (*tree.T_AAT)
      ; Check if there is a node to the left of the current node
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode\left
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i IsRight (*tree.T_AAT)
      ; Check if there is a node to the right of the current node
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode\right
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i GoRoot (*tree.T_AAT)
      ; Set the current node to the root node.
      ; Return 1 if successful, else 0 (this means the tree is empty).
      
      ASSERT(*tree)
      ASSERT(*tree\root)
      
      If *tree\root
         *tree\CurrentNode = *tree\root
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i GoLeft (*tree.T_AAT)
      ; Set the current node to the node at the left of the current node.
      ; Return 1 if successful, else 0 (in this case the current node dosnt't change).
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode\left
         *tree\CurrentNode = *tree\CurrentNode\left
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
   
   Procedure.i GoRight (*tree.T_AAT)
      ; Set the current node to the node at the right of the current node.
      ; Return 1 if successful, else 0 (in this case the current node dosnt't change).
      
      ASSERT(*tree)
      ASSERT(*tree\CurrentNode)
      
      If *tree\CurrentNode\right
         *tree\CurrentNode = *tree\CurrentNode\right
         ProcedureReturn 1
      EndIf
      ProcedureReturn 0
   EndProcedure
EndModule

Code: Select all

; Changes in version 1.10m:
; - Prepended structure names with "AAT::"

; This is a simple tree viewer I used while debugging.
; Should be only used with a small amount of nodes (less then 100) since the screen space required to
; show a larger tree with the text from the keys displayed would be too much.
; But to verify if the code is working is more than enough.

#aat_draw_offset_y = 50

Procedure DrawNode (*node.AAT::T_AAT_NODE, w, *x.Integer, *y.Integer, level) 
   ; draw a single node
   
   Protected kw, kh, lw, offx, key$, lvl$
   
   If *node
      key$ = *node\key$
      lvl$ = "(" + Str(*node\level) + ")"
      
      kw = TextWidth(key$)
      kh = TextHeight(key$) + 1
      
      lw = TextWidth(lvl$)
      
      offx = w  / 1 << (level+1)
      
      DrawText(*x\i - kw/2, *y\i, key$, #Blue, #White)
      
      Circle(*x\i, *y\i + kh, 2, #Black)
      
      DrawText(*x\i - lw/2, *y\i + kh + 3, lvl$, #Red, #White)
      
      If *node\right
         Line(*x\i, *y\i + kh, offx, #aat_draw_offset_y - kh - 5, #Black)
      EndIf
      
      If *node\left
         Line(*x\i, *y\i + kh, - offx, #aat_draw_offset_y - kh - 5, #Black)
      EndIf   
   EndIf
EndProcedure


Procedure DrawTree (*node.AAT::T_AAT_NODE, w, *x.Integer, *y.Integer, level)
   ; navigate the tree
   
   Protected offx
   
   If *node       
      level + 1   
      offx = w  / 1 << level     
      *y\i + #aat_draw_offset_y   
      
      *x\i - offx
      DrawTree (*node\left, w, *x, *y, level)
      *x\i + offx
      
      level - 1       
      DrawNode (*node, w, *x, *y, level)
      level + 1
      
      *x\i + offx
      DrawTree (*node\right, w, *x, *y, level)     
      *x\i - offx
      
      *y\i - #aat_draw_offset_y       
   EndIf
EndProcedure


Procedure TreeView (*tree.AAT::T_AAT, w = 1280, h = 768, title$ = "")
   Protected iEvent, flgExit, x, y
   Protected iImageTree
   Protected nWin, nBtnClose, nImageTree, nFont
   
   flgExit = #False
   
   iImageTree = CreateImage(#PB_Any, w, h)
   
   If iImageTree 
      nFont = LoadFont(#PB_Any, "Arial", 7)
      
      x = w/2 : y = 10 - #aat_draw_offset_y
      
      StartDrawing(ImageOutput(iImageTree))
      DrawingFont(FontID(nFont))
      Box(0,0,w,h,#White)
      DrawTree (*tree\root, w, @x, @y, 1)
      StopDrawing()
      
      If Len(title$) = 0
         title$ = "Tree Viewer"
      EndIf
      
      nWin = OpenWindow(#PB_Any, 10, 10, w, h + 70, title$, #PB_Window_SystemMenu) 
      
      If nWin
         nBtnClose = ButtonGadget(#PB_Any, w/2 - 50, h + 35, 100, 30, "Close")               
         
         nImageTree = ImageGadget(#PB_Any, 0, 0, w, h, ImageID(iImageTree))
         
         Repeat
            iEvent = WaitWindowEvent()
            
            Select iEvent
               Case #PB_Event_Gadget
                  Select EventGadget()
                     Case nBtnClose
                        flgExit = #True
                  EndSelect
            EndSelect       
         Until iEvent = #PB_Event_CloseWindow Or flgExit     
         
         FreeImage(iImageTree)
         FreeFont(nFont)
         CloseWindow(nWin)   
      EndIf
   EndIf 
EndProcedure