[bobby19]

Hey,

I am building a BSP tree using a recursive function, however, I seem to be stuck in getting out of the function. I'll paste my code and explain along the way:

module tree
  type treenode
	 type (treenode), pointer :: left, right
	 integer :: n
	 real :: data
  endtype

  type (treenode), pointer :: root
  real :: tree_xmin, tree_xmax
! Counters
  integer :: nodes, work

contains
  function create_node( ) result (node)
	type (treenode), pointer :: node
	integer :: ierr
	allocate( node, stat=ierr )
	if (ierr .ne. 0) then
	   print *, "Allocate Failed"
	   stop
	endif
	nullify( node%right )
	nullify( node%left )
	node%n = 0
  end function create_node

This code was given to us. Just the definition for the treenone and a create_node function

  integer function partition_data( xdata, xmiddle )
	implicit none

   real,INTENT(INOUT), dimension(:) :: xdata !Data Array
   real,INTENT(IN) :: xmiddle

   integer ::  l = 1, i
   integer ::  r = 16
   real :: temp

	do

	   if (xdata(l) < xmiddle) then !Data Value less than middle
		  if (l == r) then
			 partition_data = l
			return
		  end if

	   l = l + 1 !Increment Counter

	else

	   do
		  if (xdata(r) >= xmiddle) then
			 if (l == r) then
				partition_data = (l - 1)
				return
			 end if

			 r = r -1

		  else

			 temp = xdata(l)
			 xdata(l) = xdata(r)
			 xdata(r) = temp
			 exit

		  end if
	   end do


	end if


 end do

end function partition_data

This code I wrote. Essentially, it takes in a set array (given) and partitions the array so that any values lower than the x middle value are put to the left and value greater are put to the right. Then the function returns the array index of the element to the left of the xmiddle value. I have tested this function by itself, and it works fine and gives the expected results.

recursive function make_node( xdata, xmin, xmax ) result (node)
	implicit none
	type (treenode), pointer :: node
 real, intent(inout) :: xdata(:)
	real, intent(inout) :: xmin, xmax
	real :: xmiddle
	integer :: p, i, arraySize

	REAL, ALLOCATABLE, DIMENSION(:) :: newArray1, newArray2

	node => create_node()

	xmiddle = ((xmin + xmax) / 2)



   arraySize = size(xdata)
   print *, "The arraysize is ", arraysize

	if (arraySize  == 1 ) then
	   node%data = xdata(1)
	   node%n = 1


	else

	   p = partition_data(xdata, xmiddle)
	  print *, "THe partition value is", p
	  print *, "THe xmiddle value is ", xmiddle

	 ALLOCATE(newArray1(p)) !Allocate memory for the LEFT array


	   do i = 1,p !Copy data from xdata to newarray1
		 newArray1(i) = xdata(i)
	   enddo

	   print *, newArray1(1:p)

	   node%left => make_node(newArray1, xmin, xmiddle)


!	   ALLOCATE(newArray2((p+1):arraySize)) !Allocate memory for the RIGHT array

!	   do i = (p+1),arraySize !COpy data from xdata to newarray2
!		  newArray2(i) = xdata(i)
!	   enddo


!	   node%right => make_node(newArray2, xmiddle, xmax)



	end if
!
  end function make_node

This part I also wrote myself. (There are some print statements and commented out code for debugging purposes) This recursive function is used to make the nodes. The problem I am having is that this function never seems to hit the case where arraysize is equal to one. The parition value always stays constant and the new array that is suppose to be sent in, does not get changed. Tracing it out on paper, the function seems like it should work.

  subroutine build_tree( xdata, xmin, xmax )
	implicit none
	real, intent(inout)  :: xdata(:)
	real, intent(in)  :: xmin, xmax

	if (size(xdata) == 0) then
	   print *, "No data provided"
	   return
	endif

	tree_xmin = xmin
	tree_xmax = xmax
	root => make_node( xdata, tree_xmin, tree_xmax )
  end subroutine build_tree
end module tree

This was the build_tree subroutine given to us.

program treetest
  use tree
  implicit none
  integer, parameter :: ndata = 16
  real, target :: xdata(ndata)
  integer ::  partition_value, i
  real :: xpartition = 0.7
!  call random_number( xdata )
  xdata = (/ 0.00392, 0.0251, 0.453, 0.667, 0.963, 0.838, 0.335, 0.975, &
	   0.796, 0.833, 0.345, 0.871, 0.0899, 0.888, 0.701, 0.735 /)

  nodes = 0
 ! call build_tree( xdata, 0.0, 1.0 )
  print *,"Tree Built: nodes ",nodes

  print *, xdata(1:16)

  partition_value = partition_data(xdata, xpartition)

  print *, "The partition value is ", partition_value
  print *, "The partitioned array is "
  do i=1,16
	 print *, xdata(i)
  end do

end program treetest

This is the main driver program.


I apologize for the length of this post, however, any help at all would be appreciated. This is the only forum I can find offering Fortran help.

Thanks!

This post has been edited by bobby19: 25 November 2007 - 02:27 PM