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.
This post has been edited by bobby19: 25 November 2007 - 02:27 PM