home *** CD-ROM | disk | FTP | other *** search
/ SGI Hot Mix 17 / Hot Mix 17.iso / HM17_SGI / research / examples / doc / idl_tree.pro < prev    next >
Encoding:
Text File  |  1997-07-08  |  8.4 KB  |  332 lines
  1. ;;$File idl_tree.pro
  2. ;;
  3. ;; DESCRIPTION:
  4. ;;
  5. ;;    This set of routines is used to build a simple tree data structure
  6. ;;    using IDL pointers.
  7. ;;
  8. ;;
  9. ;; MODIFICATION HISTORY:
  10. ;;    March 1994,  -KDB    Initial coding
  11. ;;    August 1996,  -KDB    Updated to use pointers
  12. ;;
  13. ;;===========================================================================
  14. ;;$ Procedure Tree_New
  15.  
  16. PRO Tree_New, Tree, cmp_func
  17.  
  18. ;; PURPOSE:
  19. ;;    Initializes an IDL tree structure
  20. ;;
  21. ;; PARAMETERS:
  22. ;;    tree        - The new tree data structure
  23. ;;
  24. ;;    cmp_proc    - The comparison procedure for the tree data
  25. ;;              Since the data depends on the user, the
  26. ;;               user must supply a procedure that has the
  27. ;;                  following format:
  28. ;;
  29. ;;                cmp_func,d1,d2, result
  30. ;;
  31. ;;                result = -1  if d1 < d2
  32. ;;                      0  if d1 = d2
  33. ;;                      1  if d1 > d2
  34. ;;
  35.  
  36. ;; If cmp_func is undefined (i.e., a null string) return:
  37.  
  38.    if(strtrim(cmp_func, 2) eq '')then begin
  39.     Message, "Data Compairson procedure undefined, aborting", /CONTINUE
  40.  
  41.     Return
  42.    ENDif
  43.  
  44. ;; Make sure the tree data structure is defined:
  45.  
  46.    TreeType = {treetype, left:ptr_new(), right:ptr_new(), data:ptr_new()}
  47.  
  48. ;; Make a header for the tree, using anonymous structures:
  49.  
  50.    tree = { cnt:0l, cmp:cmp_func, pHead:ptr_new()}
  51.  
  52. end
  53. ;;=========================================================================
  54.  
  55. FUNCTION Tree_NewNode, Data
  56.  
  57.  
  58. ;; PARAMETERS:
  59. ;;    Data    - The data value that will be placed in a node
  60. ;;
  61. ;; Create a new tree node, insert the data and return the pointer:
  62.  
  63.    Tmp = {treetype}
  64.    tmp.data = ptr_new(data)
  65.    return, ptr_new(tmp)
  66. END
  67. ;---------------------------------------------------------------------------
  68. pro  Tree_insert, Tree, Data
  69.  
  70. ;; See if Data is defined, Else return an error:
  71.  
  72.    if(N_Elements(Data) eq 0)then BEGIN
  73.      message, "Data value undefined",/continue
  74.     return
  75.    ENDif
  76.  
  77. ;  Do we have any nodes yet?
  78.  
  79.    if(Tree.pHead eq ptr_new())then $
  80.        tree.pHead = Tree_NewNode(Data) $
  81.    else $
  82.        _Tree_Insert, Tree, Data, Tree.pHead
  83. end
  84. ;;==========================================================================
  85.  
  86. PRO _Tree_Insert, Tree, Data, pNode
  87.  
  88. ;; PURPOSE:
  89. ;;    This procedure is used to add a new node to the tree specified by
  90. ;;      the structure Tree. The procedure will recurses on itself until
  91. ;;    the correct insert location is found on the tree, then it
  92. ;;      inserts the node and returns.
  93. ;;
  94. ;; PARAMETERS:
  95. ;;    Tree    - A tree struct
  96. ;;
  97. ;;    Data    - The data to be put in the tree
  98. ;;
  99. ;;    pNode   - Pointer to the current node. If this is null, insert
  100. ;;          node here.
  101. ;;
  102. ;; Use the comparison function for the data to see what do to:
  103.  
  104.    Call_Procedure, Tree.cmp, Data, *(*pNode).data, result
  105.  
  106.    if( result(0) le 0)then BEGIN
  107.     if(ptr_valid((*pNode).left))then $ ; continue traverse
  108.         _Tree_Insert, Tree, Data, (*pNode).left $
  109.     else begin
  110.         (*pNode).left = Tree_NewNode(Data)
  111.         tree.cnt = tree.cnt+1;
  112.         endelse
  113.    ENDif else BEGIN
  114.     if(ptr_valid((*pNode).right)) then $
  115.         _Tree_Insert, Tree, Data, (*pNode).right $
  116.     else begin
  117.         (*pNode).right = Tree_NewNode(Data)
  118.         tree.cnt = tree.cnt+1;
  119.         endelse
  120.    ENDelse
  121.  
  122. END
  123.  
  124. ;;============================================================================
  125. FUNCTION _Tree_Search, Tree, Data, pNode
  126.  
  127. ;; PURPOSE:
  128. ;;    Searches the tree for a match and returns a null ptr if there is no
  129. ;;    match and a pointer if there is a match. This function is recursive.
  130. ;;
  131. ;; PARAMETERS:
  132. ;;    Tree    - The Tree to search
  133. ;;
  134. ;;    Data    - The data to search for
  135. ;;
  136. ;;    pNode   - Pointer to node 
  137.  
  138.    forward_function _tree_search
  139.  
  140.    if(N_Elements(Data) eq 0) then BEGIN
  141.       Message, "Data value undefined", /CONTINUE
  142.       Return, ptr_new()
  143.    ENDif
  144.    
  145.    if(not PTR_VALID(pNode)) then $
  146.       Return, ptr_new()
  147.  
  148. ;  See if we have a match
  149.  
  150.    Call_Procedure, Tree.cmp, Data, *(*pNode).data, cmp_res
  151.    
  152.    if(cmp_res lt 0)then                 $
  153.        return, _Tree_Search(Tree, Data, (*pNode).left)   $
  154.    else if(cmp_res gt 0)then                 $
  155.        return, _Tree_Search(Tree, Data, (*pNode).right)    $
  156.    else    $
  157.        return, (*pNode).data
  158.  
  159. END
  160. ;---------------------------------------------------------------------------
  161. function Tree_Search, Tree, Data
  162.  
  163.    return, _Tree_Search(Tree, Data, Tree.pHead)
  164. end
  165. ;---------------------------------------------------------------------------
  166. pro Tree_DeleteNode, Tree, Data
  167.  
  168.     _Tree_DeleteNode, Tree, Data, Tree.pHead
  169. end
  170. ;;============================================================================
  171.  
  172. PRO _Tree_DeleteNode, Tree, Data, pNode
  173.  
  174. ;; PURPOSE:
  175. ;;    Deletes the first node if finds that contains Data. This routine
  176. ;;    recurses.
  177. ;;
  178. ;; PARAMETERS:
  179. ;;    Tree    - The tree you are Deleting from (structure)
  180. ;;
  181. ;;    Data    - The data that is to be deleted (structure)
  182. ;;
  183. ;;    pNode   - pointer to node
  184.  
  185.    if(N_Elements(Data) eq 0)then BEGIN
  186.       Message, "Data value undefined", /CONTINUE
  187.       Return
  188.    ENDif
  189.  
  190.    if (not PTR_VALID(pNode) ) then BEGIN
  191.        Message, "Data not found", /CONTINUE
  192.        Return
  193.    ENDif
  194.  
  195. ;; Do we match
  196.  
  197.    Call_Procedure, Tree.cmp, Data, *(*pNode).data, cmp_res
  198.  
  199.    if(cmp_res lt 0)then $
  200.       _Tree_DeleteNode, Tree, Data, (*pNode).left $
  201.    else if(cmp_res gt 0)then $
  202.       _Tree_DeleteNode, Tree, Data, (*pNode).right $
  203.    else BEGIN    ; we have a match
  204.  
  205.       l_valid = PTR_VALID((*pNode).left)
  206.       r_valid = PTR_VALID((*pNode).right)
  207.  
  208.       if(not l_valid and not r_valid )then begin
  209.  
  210.       ; No children, delete the node
  211.     ptr_free, (*pNode).data
  212.     ptr_free, pNode
  213.  
  214.       endif else if(l_valid and r_valid)then begin
  215.  
  216.      ;; Both children are *valid* so we need to find the next smallest
  217.      ;; child. This is the child that is the farthest left branch of the
  218.      ;; current right child:
  219.  
  220.     pParent  = pNode
  221.     pCurrent = (*pNode).right
  222.  
  223.      ;; Go down the left side of the right branch until there are no more
  224.      ;; valid pointers:
  225.  
  226.         While( PTR_VALID((*pCurrent).left))do BEGIN
  227.            pParent  = pCurrent
  228.        pCurrent = (*pParent).left
  229.         ENDwhile
  230.  
  231.      ;; Replace the current node's data with data from the node
  232.      ;; we are *splicing* in:
  233.  
  234.     ptr_free, (*pNode).data
  235.     (*pNode).data = (*pCurrent).data
  236.  
  237.         if(pParent eq pNode)then $
  238.            (*pNode).right = (*pCurrent).right     $
  239.         else $
  240.        (*pParent).left = (*pCurrent).right
  241.  
  242.     ptr_free, pCurrent
  243.      endif else BEGIN
  244.  
  245.      ;; Only have one child. Clean up node and move up the child to
  246.      ;; pNode
  247.  
  248.         if(l_valid)then         $
  249.        pKill = (*pNode).left    $
  250.         else                $
  251.        pKill= (*pNode).right
  252.         ptr_free, (*pNode).data
  253.     *pNode = *pKill
  254.       ptr_free, pKill    
  255.      ENDelse
  256.    ENDelse
  257. END
  258. ;---------------------------------------------------------------------------
  259. pro Tree_Traverse, Tree, Proc, INORDER=INORDER,     $
  260.            PREORDER=PREORDER, POSTORDER=POSTORDER
  261.  
  262.    _Tree_Traverse, Proc, Tree.pHead, INORDER=INORDER,     $
  263.            PREORDER=PREORDER, POSTORDER=POSTORDER
  264. end
  265. ;;=====================================================================
  266.  
  267. PRO _Tree_Traverse, Proc, pNode , INORDER=INORDER,     $
  268.            PREORDER=PREORDER, POSTORDER=POSTORDER
  269.  
  270. ;; PURPOSE:
  271. ;;    This function recursivly traverses the tree in the selected order
  272. ;;      applying the given procedure to each node.
  273. ;;
  274. ;; PARAMETERS:
  275. ;;    Proc    - Name of the procedure to apply to each node
  276. ;;
  277. ;;    pNode    - pointer to current node
  278. ;;
  279. ;; KEYWORDS:
  280. ;;    INORDER    - Do an inorder traversal
  281. ;;
  282. ;;    PREORDER   - Do a preorder traversal
  283. ;;
  284. ;;    POSTORDER  - Do a postorder traversal
  285.  
  286.    if(not PTR_VALID(pNode))then $
  287.     Return
  288.  
  289.    if(Keyword_Set(PREORDER))then begin
  290.       Call_Procedure, Proc, *(*pNode).data
  291.       _Tree_Traverse, Proc, (*pNode).left , /PREORDER
  292.       _Tree_Traverse, Proc, (*pNode).right, /PREORDER
  293.    endif else if( Keyword_Set(POSTORDER))then begin
  294.       _Tree_Traverse, Proc, (*pNode).left,  /POSTORDER
  295.       _Tree_Traverse, Proc, (*pNode).right, /POSTORDER
  296.       Call_Procedure, Proc, *(*pNode).data
  297.    endif else begin
  298.       _Tree_Traverse, Proc, (*pNode).left , /INORDER
  299.       Call_Procedure, Proc, *(*pNode).data
  300.       _Tree_Traverse, Proc, (*pNode).right, /INORDER
  301.    endelse
  302. end
  303. ;---------------------------------------------------------------------------
  304. pro Tree_Delete, Tree
  305.  
  306.     _Tree_Delete, Tree.pHead
  307. end
  308. ;;============================================================================
  309. PRO _Tree_Delete, pNode
  310.  
  311. ;; PURPOSE:
  312. ;;     This procedure is used to delete all of the nodes in the tree.
  313. ;;    This is just a postorder traversal of the tree. This is done
  314. ;;    Recursivly.
  315. ;;
  316. ;; PARAMETER:
  317. ;;    pNode - The current node.
  318.  
  319.  
  320.    if(not PTR_VALID(pNode))then $
  321.     Return
  322.  
  323.  
  324.    _Tree_Delete, (*pNode).left
  325.    _Tree_Delete, (*pNode).right
  326.  
  327.    ptr_free, (*pNode).data
  328.    ptr_free, pNode
  329. end
  330.  
  331.  
  332.