;;$File idl_tree.pro
;;
;; DESCRIPTION:
;;
;;	This set of routines is used to build a simple tree data structure 
;;	using IDL handles.
;;
;;	Note: When you compile this file, compile it twice. This is due
;;	to the use of a recursive function.
;;
;;	IDL> .run idl_tree idl_tree
;;
;; MODIFICATION HISTORY:
;;	March 1994,  -KDB	Initial coding
;;
;;===========================================================================
;;$ Procedure Tree_New

PRO Tree_New, Tree, cmp_func

;; PURPOSE:
;;	Initializes an IDL tree structure
;;
;; PARAMETERS:
;;	tree		- The new tree data structure
;;		
;;	cmp_proc	- The comparison procedure for the tree data
;;			  Since the data depends on the user, the
;;		 	  user must supply a procedure that has the 
;;		          following format:
;;
;;			    cmp_func,d1,d2, result
;;
;;			    result = -1  if d1 < d2
;;				      0  if d1 = d2
;;				      1  if d1 > d2
;;

;; If cmp_func is undefined (i.e., a null string) return:

   if( StrLen(StrCompress(cmp_func,/REMOVE_ALL) ) le 0) then BEGIN
    
	Message, "Data Compairson procedure undefined, aborting", /CONTINUE

	Return
   ENDif

;; Make sure the tree data structure is defined:

   TreeType = {treetype, left:-1l, right:-1l, data:-1l}

  
;; Make a header for the tree, using anonymous structures:

   tree = { cnt:0l, cmp:cmp_func}

;; That's all:

   Return
END


;;==========================================================================

FUNCTION Tree_NewNode, Data


;; PARAMETERS:
;;	Data	- The data value that will be placed in a node
;;
;; Create a new tree node, insert the data and return the handle ID:

   Tmp = Replicate( {treetype}, 1)
   Tmp.Data = HANDLE_CREATE(VALUE=Data)

   Return, HANDLE_CREATE( VALUE = Tmp)

END
;;==========================================================================

PRO Tree_Insert, Tree, Data, NodeId

;; PURPOSE:
;;	This procedure is used to add a new node to the tree specified by
;;  	the structure Tree. The procedure will recurses on itself until
;;	the correct insert location is found on the tree, then it
;;      inserts the node and returns.
;;
;; PARAMETERS:
;;	Tree	- A tree struct
;;
;;	Data	- The data to be put in the tree
;;
;;	NodeId  - The Handle of the current node
;;

;; See if Data is defined, Else return an error:

   if(N_Elements(Data) eq 0)then BEGIN
 	message, "Data value undefined",/continue
	return
   ENDif

;; Now see if the current handle is valid. If not, add a new node to this
;; location:

   IF (NOT HANDLE_INFO(Nodeid, /VALID_ID)) then BEGIN 
   
   ;; Add a new node to the tree and return:

      NodeId = Tree_NewNode(Data)
      Tree.cnt = Tree.cnt + 1		       
      Return
   ENDif
 
;; This is not the insertion point, get the node and the nodes data passed
;; in by the handle NodeId:
  
   HANDLE_VALUE, Nodeid, Node, /NO_COPY		 	;get node struct
   HANDLE_VALUE, Node.data, Ndata, /NO_COPY		;get node data

;; Use the comparison function for the data to see what do to:

   Call_Procedure, Tree.cmp, Data, Ndata, result

   if( result(0) le 0)then BEGIN
        tmp = Node.left			; Don't pass by value
	Tree_Insert, Tree, Data, tmp
        Node.left = tmp
   ENDif else BEGIN
        tmp = Node.right  		; Pass by ref, not value
	Tree_Insert, Tree, Data, tmp
        Node.right = tmp 
   ENDelse

;; Place the data back into the node handle:

   HANDLE_VALUE, Node.data, Ndata, /SET, /NO_COPY

;; Place the node back into the handle:

   HANDLE_VALUE, NodeId, Node, /SET, /NO_COPY

   RETURN
   
END

;;============================================================================

FUNCTION Tree_Search, Tree, Data, NodeId & END

FUNCTION Tree_Search, Tree, Data, NodeId

;; PURPOSE:
;;	Searches the tree for a match and returns -1 if there is no
;;	match and a handle if there is a match. This function is recursive.
;;
;; PARAMETERS:
;;	Tree	- The Tree to search
;;
;;	Data	- The data to search for
;;
;;	NodeId  - Handle of the current node

   if(N_Elements(Data) eq 0) then BEGIN
      Message, "Data value undefined", /CONTINUE
      Return, -1
   ENDif

   if(not Handle_Info(NodeId, /VALID_ID) ) then $
      Return, -1
 
;; Get the handle value and see if we have a match:

   HANDLE_VALUE, NodeId, Node
   HANDLE_VALUE, Node.data, NData

   Call_Procedure, Tree.cmp, Data, Ndata, cmp_res

   if(cmp_res lt 0)then 				$
       return, Tree_Search( Tree, Data, Node.left )  	$
   else if(cmp_res gt 0)then 				$
       return, Tree_Search(Tree, Data, Node.right)	$
   else	$
       return, Node.data

END

;;============================================================================

PRO Tree_DeleteNode, Tree, Data, NodeId

;; PURPOSE:
;;	Deletes the first node if finds that contains Data. This routine
;;	recurses.
;;
;; PARAMETERS:
;;	Tree	- The tree you are Deleting from
;;
;;	Data	- The data that is to be deleted
;;
;;	NodeId	- The Handle of the current node.

   if(N_Elements(Data) eq 0)then BEGIN
      Message, "Data value undefined", /CONTINUE
      Return
   ENDif

   if(not HANDLE_INFO(NodeId, /VALID_ID) )then BEGIN
       
       Message, "Data not found", /CONTINUE
       Return
   ENDif

;; Get the handle value and see if we have a match:

   HANDLE_VALUE, NodeId, Node
   HANDLE_VALUE, Node.data, NData

   Call_Procedure, Tree.cmp, Data, Ndata, cmp_res

   if(cmp_res lt 0)then BEGIN
       tmp = Node.left			;Need to pass by reference
       Tree_DeleteNode, Tree, Data, tmp
       Node.left =tmp
       Handle_Value, NodeId, Node, /SET, /NO_COPY

   ENDif else if(cmp_res gt 0)then BEGIN
       tmp = Node.right
       Tree_DeleteNode, Tree, Data, tmp
       Node.right = tmp
       Handle_Value, NodeId, Node, /SET, /NO_COPY

   ENDif else BEGIN

     l_valid = HANDLE_INFO(Node.left , /VALID_ID)
     r_valid = HANDLE_INFO(Node.right, /VALID_ID)

     if(not l_valid and not r_valid )then BEGIN

     ;; No children, just delete this node:

        HANDLE_FREE, Node.data
        HANDLE_FREE, NodeId
        NodeId= -1l
		
     ENDif else if(l_valid and r_valid)then  BEGIN
 
     ;; Both children are *valid* so we need to find the next smallest
     ;; child. This is the child that is the farthest left branch of the
     ;; current right child:

        Parent  = NodeId
        ParVal  = Node
        Current = Node.right
        Handle_Value, Current, CurVal      

     ;; Go down the left side of the right branch until there are no more
     ;; valid handles:

        While( Handle_Info(CurVal.left, /VALID))do BEGIN
           Parent  = Current
           Parval  = CurVal
	   Current = ParVal.left
	   Handle_Value, Current, CurVal
        ENDwhile

     ;; Replace the current node's data with data from the node
     ;; we are *splicing* in:

        Handle_Free, Node.data    ;; Free the handle
        Node.data = CurVal.data

        if(Parent eq NodeId)then   	$
           Node.right = CurVal.right 	$
        else BEGIN
           ParVal.left = CurVal.right
           Handle_Value, Parent, ParVal, /SET
        ENDelse

        HANDLE_FREE, Current		 ;Dont need current anymore
        HANDLE_VALUE, NodeId, Node, /SET ;Set the new node values in handle
      
     ENDif else BEGIN

     ;; Only have one child. Delete the node data and the node handle
     ;; and return the valid child.

        HANDLE_FREE, Node.data
        HANDLE_FREE, NodeId     ;; Have the node struct so we can kill Handle

        if(l_valid)then 	$
	   NodeId= Node.left	$
        else			$
	   NodeId= Node.right	
    
     ENDelse

   ENDelse

   Return
   
END

;;=====================================================================

PRO Tree_Traverse, Proc, Nodeid , INORDER=INORDER, 	$
		   PREORDER=PREORDER, POSTORDER=POSTORDER

;; PURPOSE:
;;	This function recursivly traverses the tree in the selected order
;;  	applying the given procedure to each node.
;;
;; PARAMETERS:
;;	Proc	- Name of the procedure to apply to each node
;;
;;	Nodeid	- The Handle of the current node
;;
;; KEYWORDS:
;;	INORDER    - Do an inorder traversal
;;
;;	PREORDER   - Do a preorder traversal
;;
;;	POSTORDER  - Do a postorder traversal

   if(not HANDLE_INFO(NodeId, /VALID_ID))then $	
	Return

   HANDLE_VALUE, NodeId, Node
   HANDLE_VALUE, Node.data, Data

   if(Keyword_Set(PREORDER))then BEGIN
      Call_Procedure, Proc, Data
      Tree_Traverse, Proc, Node.left , /PREORDER 
      Tree_Traverse, Proc, Node.right, /PREORDER 

   ENDif else if( Keyword_Set(POSTORDER))then BEGIN
      Tree_Traverse, Proc, Node.left,  /POSTORDER
      Tree_Traverse, Proc, Node.right, /POSTORDER
      Call_Procedure, Proc, Data

   ENDif else BEGIN
      Tree_Traverse, Proc, Node.left , /INORDER
      Call_Procedure, Proc, Data
      Tree_Traverse, Proc, Node.right, /INORDER

   ENDelse

   Return
END

;;============================================================================

PRO Tree_Delete, NodeId

;; PURPOSE:
;; 	This procedure is used to delete all of the nodes in the tree.
;;	This is just a postorder traversal of the tree. This is done
;;	Recursivly.
;;
;; PARAMETER:
;;	NodeId - The current node.


   if(not HANDLE_INFO(NodeId, /VALID_ID))then $	
	Return

   HANDLE_VALUE, NodeId, Node, /NO_COPY
   HANDLE_VALUE, Node.data, Data, /NO_COPY
     
   Tree_Delete, Node.left
   Tree_Delete, Node.right

   HANDLE_FREE, Node.data
   HANDLE_FREE, NodeId

   Return

END