of_addnode

pfcapsrv.pbl   >   pfc_n_cst_tree   >   of_addnode

Name	Datatype
li_compare	integer
li_rc	integer
lnv_pivot1	n_cst_treenode
lnv_pivot2	n_cst_treenode
lnv_temp	n_cst_treenode

protected function integer of_addnode (n_cst_treenode anv_newnode, ref n_cst_treenode anv_currentnode, ref boolean ab_height);//////////////////////////////////////////////////////////////////////////////
//
//	Function:  of_addnode
//
//	Access:  protected
//
//	Arguments : 
//	anv_newnode n_cst_treenode : node to be added
//	anv_currentnode n_cst_treenode : current node of the tree
//	ab_height boolean : indicates whether the 'height; of the tree has changed or not
//
//	Returns:  integer
//	1 : node was added
//	0 : node with this key already exists in the tree, so node was not added
//	-1 : node was not added due to some error
//
//	Description:  
//	Recursive function finds the properlocation for the new node and 
//	then inserts it into the tree. It also 'balances' the tree if the resulting
//	height of the branch is more that one level different than neighboring 
//	branches
//
//////////////////////////////////////////////////////////////////////////////
//
//	Revision History
//
//	Version
//	6.0   Initial version
//
//////////////////////////////////////////////////////////////////////////////
//
//	Copyright © 1996-1997 Sybase, Inc. and its subsidiaries.  All rights reserved.
//	Any distribution of the PowerBuilder Foundation Classes (PFC)
//	source code by other than Sybase, Inc. and its subsidiaries is prohibited.
//
//////////////////////////////////////////////////////////////////////////////
n_cst_treenode lnv_pivot1
n_cst_treenode lnv_pivot2
n_cst_treenode lnv_temp
integer li_compare
integer li_rc

if not isvalid(anv_currentnode) then 
	// node not in tree so insert it
	ab_height = true
	anv_newnode.of_setnext(lnv_pivot1) // force left and right pointers to nil
	anv_newnode.of_setprev(lnv_pivot1) // force left and right pointers to nil
	anv_newnode.of_setbalance(0)
	anv_currentnode = anv_newnode // return the node
else
	li_compare = inv_compare.of_compare(anv_newnode,anv_currentnode)
	choose case li_compare
		case  inv_compare.LESSTHAN  
			// anv_newnode < anv_currentnode
			anv_currentnode.of_getprev(lnv_temp)
			li_rc = of_addnode(anv_newnode,lnv_temp,ab_height)
			if li_rc <= 0 then return li_rc
			anv_currentnode.of_setprev(lnv_temp)
			if ab_height then 
				// left branch has grown higher
				choose case anv_currentnode.of_getbalance()
					case 1
						anv_currentnode.of_setbalance(0)
						ab_height = false
					case 0
						anv_currentnode.of_setbalance(-1)
					case -1  
						// rebalance
						anv_currentnode.of_getprev(lnv_pivot1)
						if lnv_pivot1.of_getbalance() = -1 then // single LL rotation						
							lnv_pivot1.of_getnext(lnv_temp)
							anv_currentnode.of_setprev(lnv_temp)
							lnv_pivot1.of_setnext(anv_currentnode)
							anv_currentnode.of_setbalance(0)
							anv_currentnode = lnv_pivot1
						else 
							// double LR rotation
							lnv_pivot1.of_getnext(lnv_pivot2)
							lnv_pivot2.of_getprev(lnv_temp)
							lnv_pivot1.of_setnext(lnv_temp)
							lnv_pivot2.of_setprev(lnv_pivot1)
							
							lnv_pivot2.of_getnext(lnv_temp)
							anv_currentnode.of_setprev(lnv_temp)
							lnv_pivot2.of_setnext(anv_currentnode)
							if lnv_pivot2.of_getbalance() = -1 then
								anv_currentnode.of_setbalance(1)
							else
								anv_currentnode.of_setbalance(0)
							end if
							if lnv_pivot2.of_getbalance() = 1 then

								lnv_pivot1.of_setbalance(-1)
							else
								lnv_pivot1.of_setbalance(0)
							end if
							anv_currentnode = lnv_pivot2
						end if
						anv_currentnode.of_setbalance(0)
						ab_height = false
				end choose
			end if		
		case inv_compare.GREATERTHAN 
			// anv_newnode > anv_currentnode
			anv_currentnode.of_getnext(lnv_temp)
			li_rc = of_addnode(anv_newnode,lnv_temp,ab_height)
			if li_rc <= 0 then return li_rc
			anv_currentnode.of_setnext(lnv_temp)
			if ab_height then // Right branch has grown higher
				choose case anv_currentnode.of_getbalance()
					case -1
						anv_currentnode.of_setbalance(0)
						ab_height = false
					case 0
						anv_currentnode.of_setbalance(+1)
					case 1  
						// rebalance
						anv_currentnode.of_getnext(lnv_pivot1)
						if lnv_pivot1.of_getbalance() = 1 then // single RR rotation
							lnv_pivot1.of_getprev(lnv_temp)
							anv_currentnode.of_setnext(lnv_temp)
							lnv_pivot1.of_setprev(anv_currentnode)
							anv_currentnode.of_setbalance(0)
							anv_currentnode = lnv_pivot1
						else 
							// double RL rotation
							lnv_pivot1.of_getprev(lnv_pivot2)
							lnv_pivot2.of_getnext(lnv_temp)
							lnv_pivot1.of_setprev(lnv_temp)
							lnv_pivot2.of_setnext(lnv_pivot1)
							
							lnv_pivot2.of_getprev(lnv_temp)
							anv_currentnode.of_setnext(lnv_temp)
							lnv_pivot2.of_setprev(anv_currentnode)
							if lnv_pivot2.of_getbalance() = 1 then
								anv_currentnode.of_setbalance(-1)
							else
								anv_currentnode.of_setbalance(0)
							end if
							if lnv_pivot2.of_getbalance() = -1 then
								lnv_pivot1.of_setbalance(1)
							else
								lnv_pivot1.of_setbalance(0)
							end if
							anv_currentnode = lnv_pivot2
						end if
						anv_currentnode.of_setbalance(0)
						ab_height = false
				end choose				
			end if			
		case inv_compare.EQUAL
			// return an error (do not allow nodes with the same key)
			ab_height = false
			return 0
	end choose
end if

return 1


end function

Name	Owner
pfc_n_cst_tree.of_addnode	pfc_n_cst_tree
pfc_n_cst_tree.of_add	pfc_n_cst_tree

Name	Owner
systemfunctions.isvalid	systemfunctions
pfc_n_cst_nodecomparebase.of_compare	pfc_n_cst_nodecomparebase
pfc_n_cst_tree.of_addnode	pfc_n_cst_tree
pfc_n_cst_treenode.of_getbalance	pfc_n_cst_treenode
pfc_n_cst_treenode.of_setbalance	pfc_n_cst_treenode
pfc_n_cst_nodebase.of_setprev	pfc_n_cst_nodebase
pfc_n_cst_nodebase.of_setnext	pfc_n_cst_nodebase
pfc_n_cst_nodebase.of_getnext	pfc_n_cst_nodebase
pfc_n_cst_nodebase.of_getprev	pfc_n_cst_nodebase